Sign in to follow this  
spacecamp

How do I keep track of nearby objects?

Recommended Posts

Hello.

I was wondering if there's an elegant way to keep clients updated about their surroundings.

Right now I'm using a simple node system where I initially send objects in current/surrounding node and update them respectively if node boundaries are passed. But it looks extremely messy and perhaps inefficient. Opened for any suggestions.

Share this post


Link to post
Share on other sites

Generally games rely on a spatial tree of some kind.

 

For terms you can research: spatial hash, BSP trees, quadtrees, loose quadtrees, octrees, loose octrees.  Each is progressively bigger in implementation but generally more powerful.  

 

 

* A spatial hash is typically a manual subdivision based on what you provide. You manually specify how many divisions are used.

* BSP trees are generally better for linear data or where you need arbitrary slices. These can be manual or automatic.

* Quadtrees and their variants usually operate along axis-aligned boxes in 2D, automatically subdividing as needed based on rules you provide. This works well in many games when you can use ground coordinates.

* Octrees and their variants are like Quadtrees, except in 3D. Usually overkill for games unless you're working on games with true six degrees of freedom.

Share this post


Link to post
Share on other sites
Right now I'm using a simple node system where I initially send objects in current/surrounding node and update them respectively if node boundaries are passed. But it looks extremely messy and perhaps inefficient. Opened for any suggestions.

Would this happen to be a normal uniform grid? I wrote a blog article years ago that covered the grid and spatial hashing methods. Might compare the data structures I use against yours.

 

A big picture idea of interest management is that you don't have to run it in real-time. As Frob mentioned loose variations will often be used that exploit this. If designed correctly you can update entities in cells, quadtrees, etc like once per second then query and build the list of nearby entities every 2 seconds or stagger updates across many ticks. This can get kind of complex, but in the end you can end up with a system that supports thousands of entities and scales. (Overkill usually).

Edited by Sirisian

Share this post


Link to post
Share on other sites

 

Right now I'm using a simple node system where I initially send objects in current/surrounding node and update them respectively if node boundaries are passed. But it looks extremely messy and perhaps inefficient. Opened for any suggestions.

Would this happen to be a normal uniform grid? I wrote a blog article years ago that covered the grid and spatial hashing methods. Might compare the data structures I use against yours.

 

A big picture idea of interest management is that you don't have to run it in real-time. As Frob mentioned loose variations will often be used that exploit this. If designed correctly you can update entities in cells, quadtrees, etc like once per second then query and build the list of nearby entities every 2 seconds or stagger updates across many ticks. This can get kind of complex, but in the end you can end up with a system that supports thousands of entities and scales. (Overkill usually).

 

It's similar but not as well designed. Just a simple cell struct and a huge 1D array(the grid).

 

My biggest issue with the grid approach is when objects are moving through the grid I'm having a hard time figuring out which cells should be updated.

Maybe if I represent objects as 2D boxes(visible range being the dimensions), use a quadtree and send update packets only to collided 'boxes' it would work out? 

Share this post


Link to post
Share on other sites

I'm having a hard time figuring out which cells should be updated.


There are two ways to view this.
One is: An object should be in each cell that it can be visible from.
Another is: An object is in "its own" cell, and visibility queries cover many cells.

Implementation is easier for the second option.

Quad trees are great theoretically because of the ability to adjust dynamically to object load.
I find that hash grids work great in practice. They are like a fixed grid, but don't pay storage for empty cells.

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