Where can I find fast spatial querying?

General Discussions
#1

Hi,

I’m developing a game where super fast spatial querying is a must, and I’m guessing many other games before have had this requirement (definitely not the first time this subject has been brought up on these forums).

So, how come there are no de facto standard go-to implementations of super fast structures like quad-trees? Ones that just work, and don’t require me to write a ton of code and going through a week of debugging and trying to speed up the implementation.

These structures seem like such a standard thing… Maybe I just don’t know where to look?

#2

Googling "java " and maybe even “site:github.com” seems to do well…
Another term sometimes used is “spatial index”

What specifically do you need?

#3

That only yielded shady results (might be buggy), or huge libraries that’re made for other purposes than being fast and practical (I’m thinking of http://sis.apache.org/).

I need to query nearest neighbor, bounds intersection and fast updating when elements are moved. These would be what is needed for any tower-defence game.

JSI seems great, but it is difficult to move entities around. It requires deletion and reinsertion, and deletion requires the element’s index in the tree. This seems like a hassle - especially since elements might come and go in a matter of frames.

In an old thread someone suggested bit-shifting element’s positions, in order to add them to a grid of lists, making queries a bit faster. This grid would be cleared every frame, making it easy to move, add and delete elements. However, I believe it had some other problematic flaw, making it less ideal. I’ll tyr to dig it up later.

What do you guys use for this problem?

#4

For a tower defence game you’ll only need a regular cell grid. Well, that’s what I’ve used, and it’s plenty fast enough.

Cas :slight_smile:

#5

+1 for a uniform grid

#6

Grids are good. They’re extremely easy to query (loop over grid tiles that intersect the query area) and they’re fast to maintain (check if all objects still are inside their grid tile. If not, remove from current tile and add to the correct tile).

#7

If you go with a grid for spatial partitioning (which sounds like a good fit for a TD game), consider to register each entity in all cells they occupy. I used to only put the anchor point in the cell, which required checking neighboring cells for collisions too.

My approach is usually to have a 1d array of Bitsets representing the grid and entities; though it requires that your entities/colliders can be represented by a zero-based numbering scheme.

http://gameprogrammingpatterns.com/spatial-partition.html

#8

Hi

Mads, you’ve just reminded me that I have to work on portal culling and I’ve found this open source (permissive license, BSD) library in C++ which I can partially port:
http://www.visualizationlibrary.org/documentation/pag_guide_portals.html

Coming here is almost always a pleasure, thanks to all.