next »

[Epitaque]

What is the advantage of using Quadtrees over a simple 2-dimensional array for games with grids? I thought the whole point of Quadtrees was to reduce the number of calculations needed for detecting a collision by dividing it into squares with objects that could possibly be colliding but if you can access squares on a grid by location then it seems unnecessary. On another forum somebody suggested a developer of a gridded 2d game use quadtrees, so I'm just curious as to why. Asked them but they don't seem to be answering.

In a gridded game where each block is the same width and height, you can easily access them by location without needing to loop through anything (e.g. to get a block at (3, 2) where the width and height of each block is 1 and you're storing your blocks in an C++ array called Blocks you could just type Blocks[3][2] to access that block). So you can just access the blocks around the player to detect collision. In a non-gridded game, I see how it could be useful because you can't easily access objects by location and each object could have different dimensions and shape.

[Boreal]

Spatial partitioning isn't only useful for collision detection.  It can be used to cut down storage costs, in what is called a "sparse" representation.

There's not much out there on sparse quadtrees, but sparse (voxel) octrees are quite popular in 3D rendering, especially with regard to global illumination.

Hopefully this image should illustrate the concept:

[BorisTheBrave]

\[if you can\] access squares on a grid by location then it seems unnecessary.

If you have an object slightly smaller than one square, then sure, you can access 4 cells and be done. But if you have objects much larger than a few cells, then you may have to access many cells. Quad trees can help there. Conversely if you have too many tiny objects in one cell, you also end up in trouble, but quad trees don't suffer so much from this.

So they are good for games where there isn't a very consistent size to objects. Frankly, such games are pretty rare, particuarly after applying obvious hacks, so they are hard to justify.

There are many other queries that are faster to answer with quadtrees than with cells, for example, ray casts, nearest point, support, or mass computations, so if you did a lot of that it might be worth while.

I have used quadtrees before, but in a library - I mostly wanted to avoid having to force the library users to choose any "tuning" factors, as required in a grid.

[Columbo]

I think in your scenario, the grid is clearly the better solution.

Even if your game doesn't have a grid, a grid can be a good solution - google spatial hashing. It basically maps your game's 2D or 3D space onto a virtual grid so you can do quick grid lookups for potential collisions. If the game's space is too large to fit into a practically sized grid, then the grid space can be wrapped.

Grid solutions become trickier where you have objects with large size variations as it becomes tricky to choose a good cell size.

It's not unusual in games to use a quad tree (or similar hierarchical structure) for the game's static environment collision polygons to deal with dynamic vs static collisions, and a spatial hash approach for the broadphase for dynamic vs dynamic collisions.