Refactoring the thoughts
So far, we've worked under the general assumption that we want the whole world "locked" and the areas to define where players can build (define-allow). But there's another scenario, maybe even more common: Let the players interact with most of the world, except for some areas that are reserved for specific players (define-deny). The second approach means that we won't be able to use the above optimization, because we really need to check even the protection areas for not-connected players.
But we can still optimize even this second variant. It's very probable that the protection areas will be spread out throughout the world, rather than all intersecting one space. So instead of loading per-player areas, let's load per-space areas. Space, in this sense, will be a defined rectangle of blocks. So for example if a player is at XZ [160, 260], we'll load all the areas that affect the space of [100, 200] - [250, 350]. If the player moves to [140, 260], we'll load all the areas that affect the space of [50, 200] - [200, 350] - so we'll always have a space of 150x150 blocks and the player will be more than 50 blocks away from the edge of this space. The expectation is that there won't be too many protected areas in the space.
Still, we will keep a per-player map of protection areas that each connected player can "reach", as defined by the Space above. Only the map will have to change when the player moves.
Here's a diagram to illustrate:
![[Image: areas_space.png]](http://mc-server.xoft.cz/img/areas_space.png)
The dashed rectangle represents the current space, 150 x 150 blocks around the player. Area1, Area2 and Area3 will be loaded, while Area4 won't.
Performance, revisited
With the new approach, what are the expected performance stats? Let's use the same scenario - a server with 80 connected players and 400 regulars, with average 6 areas each. Let's also suppose that the areas are at least 16x16 blocks in size and less than 50 % of them overlap.
With this data, we can calculate that there are at most 200 protected areas within each player's space (150 / 16 = 10 areas in each direction, 50 % overlap -> 2x more areas). So each interaction needs to be checked with 200 areas, i. e. 80 * 5 * 200 = 80.000 comparisons per second. For a worst-case scenario, this is a nice number. For a more real scenario, let's use a "town" with 20x20 building sites and 12 block wide streets; each building site being a single protection area. That means a maximum of 25 areas within each players space (150 / 32 = 5 areas in each direction), 80 * 5 * 25 = 10.000 comparisons per second. That is an acceptable number.
If we need to optimize even more, we can make the Space smaller, 150 blocks seems quite large anyway. Dividing the space dimensions in half means we'll be slicing the comparisons by a factor of 4. However, we must not shrink the Spaces too much, because we need to be able to account for player's reach (up to 5 blocks away from current position) and we don't want to be re-loading the spaces too often when the player moves.
So far, we've worked under the general assumption that we want the whole world "locked" and the areas to define where players can build (define-allow). But there's another scenario, maybe even more common: Let the players interact with most of the world, except for some areas that are reserved for specific players (define-deny). The second approach means that we won't be able to use the above optimization, because we really need to check even the protection areas for not-connected players.
But we can still optimize even this second variant. It's very probable that the protection areas will be spread out throughout the world, rather than all intersecting one space. So instead of loading per-player areas, let's load per-space areas. Space, in this sense, will be a defined rectangle of blocks. So for example if a player is at XZ [160, 260], we'll load all the areas that affect the space of [100, 200] - [250, 350]. If the player moves to [140, 260], we'll load all the areas that affect the space of [50, 200] - [200, 350] - so we'll always have a space of 150x150 blocks and the player will be more than 50 blocks away from the edge of this space. The expectation is that there won't be too many protected areas in the space.
Still, we will keep a per-player map of protection areas that each connected player can "reach", as defined by the Space above. Only the map will have to change when the player moves.
Here's a diagram to illustrate:
The dashed rectangle represents the current space, 150 x 150 blocks around the player. Area1, Area2 and Area3 will be loaded, while Area4 won't.
Performance, revisited
With the new approach, what are the expected performance stats? Let's use the same scenario - a server with 80 connected players and 400 regulars, with average 6 areas each. Let's also suppose that the areas are at least 16x16 blocks in size and less than 50 % of them overlap.
With this data, we can calculate that there are at most 200 protected areas within each player's space (150 / 16 = 10 areas in each direction, 50 % overlap -> 2x more areas). So each interaction needs to be checked with 200 areas, i. e. 80 * 5 * 200 = 80.000 comparisons per second. For a worst-case scenario, this is a nice number. For a more real scenario, let's use a "town" with 20x20 building sites and 12 block wide streets; each building site being a single protection area. That means a maximum of 25 areas within each players space (150 / 32 = 5 areas in each direction), 80 * 5 * 25 = 10.000 comparisons per second. That is an acceptable number.
If we need to optimize even more, we can make the Space smaller, 150 blocks seems quite large anyway. Dividing the space dimensions in half means we'll be slicing the comparisons by a factor of 4. However, we must not shrink the Spaces too much, because we need to be able to account for player's reach (up to 5 blocks away from current position) and we don't want to be re-loading the spaces too often when the player moves.