Sign in to follow this  
GanonPhantom

Lightweight Spatial Managment

Recommended Posts

GanonPhantom    100
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 this post


Link to post
Share on other sites
wodinoneeye    1689


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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this