# Lightweight Spatial Managment

This topic is 3560 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im trying to solve a problem here, and im not sure what to do atm. On our server, we currently have a QuadTree for spatial management. But, we are implimenting a feature in which people can get 'badges' for visiting certain locations in the game, and we want to do it in a way that it dosnt create a bottleneck by checking the coords of the player each time he moves. What i kinda had in mind, is making a static cell map (that didnt split into 4 each time an object entered it), and have it so when the player moved, it would take his position, and divide it by X amount to find the cell he is currently in, and when he enters a new cell, it would do an Update() function or OnEnter() in which it would give him the badge. The only potential bottleneck i can see is having to find his cell.

##### Share on other sites

The cell map could work as a lazy evaluation (the cells might not have to be so small but do have to be a regular rectangular array to make for an efficient position test (powers of 2 are also good to eliminate divides (use shifts instead...)

The 'lazy; part is that only a boolean flag is required (and thus you could bit pack your cell array to save space) which indicates that a list (sparse array methodology) of all the Badge Spots needs to be searched (the actual badge spots can thus be some more complicated/precise position test -- probably a linear serach).

You only would need to do the more costly comparison if the cell flag indicates there is a badge position within its cell. Most of the map Im guessing isnt badge chek areas so when the basic simple check is done its just a lookup in the static array. Once you are in a cell and earn your badge you keep track of the current cell you are in and only allow the costly check again if the current cell changes.

The check is taking the coordinates and dividing by the regular fixed cell size to get an ordinal for the XY position in the cell array.

If you have seperate zone maps, then you would have seperate cell maps and badge area lists for each one.

1. 1
2. 2
3. 3
Rutin
24
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631766
• Total Posts
3002232
×