next »

[Ankmannen]

Hi!

I have a huge space game with a lot of objects spanning a very large area. What I'm interested in is for each object to keep track of objects near it self. Is a quad tree the way to go?

Thanks

// Johan

[nox]

If it's 3D, you probably want an octree. If it's 2D, a quadtree would be good, but I would only bother with either if a fixed grid wasn't sufficient for your needs.

[Pampattitude]

Could you please tell us more about your technical constraints? Engine, perspective, etc.?
There could be simpler solutions than a *tree depending on that.

[Ankmannen]

It's a 2D game, (http://spacelot.io2gamelabs.se for gameplay video, a bit old but you get the point or search on youtube for spacealot).

It's a MonoGame based game using Farseer for the physics. Perhaps I could get my info from farseer directly, I'm sure they perform some kind of broad phase assessment of close objects each frame.

What I need is a close range radar that each ship uses for its AI.

// Johan

[nox]

I would start with a 2D grid.

You start by defining world-space dimensions for the cells of the grid. The ideal choice of dimensions is game dependent, and relates to the size and distribution of objects in your world. Represent a GridCell as a vector of object references. Represent a Grid in such a way that you can index GridCell objects by their grid-space coordinates. You can determine the grid-space coordinates for any point with a very simple function. Something like this:

Code:

-- given a grid of infinite squares of cell_dim,
-- gets the grid coordinates for a point in the world
function get_grid_coords(pos, cell_dim)
   return floor(pos.x / cell_dim), floor(pos.y / cell_dim)
end

You'll use these coordinates to index into your Grid.

Every time something moves, use this function to determine the grid-space coordinates, and add a reference to this moved object to the GridCell that it currently resides in. Of course, also remove it from any GridCell that it no longer resides in.

THEN

To find nearby objects, you first find the grid-space coordinates of an object, and then you use them to index into the Grid to get the GridCell, which contains references to all of the objects in the same GridCell as the object in question.

[gimymblert]

Back in the days, when I was programming on casio oblivious of what real programming was, I had a little trick to manage collision between objects by tracking neighbor in a cardinal fashion. Basically there was two way I knew to handle collision, either you use aabb style square root of coordinate comparison (expensive to compute), or grid (expensive with memory). On casio every resource is precious so I need something cheap both to compute and to store.

The solution was to generate n*m objects relative to each other at initialization. Ie object where placed such as they where sorted in a way they always have a single neighbor in each 4 cardinal direction, each objects store a pointer to their neighbor. So when I move up, I check the North neighbor and check the distance to see if there is collision OR if character is further his neighbor (in which case we shuffle the objects and update to their new neighbor). When a n*m number of objects is not met, empty object are created to fill the void. Object on the edge of the relation have a pointer to that signal the limit of the map in that direction.

It was pretty powerful on casio as now I also had spatial relationship, now I could compute for free if an object is in between me or another, concept like behind, in front, etc emerge naturally from the structure as you can look at an object and query it's neighbor.

Maybe a similar structure can fit your need.

[Ankmannen]

Great tips! Thanks all! I'll provide som feedback with my results.