Optimizing a QuadTree for enormous maps

Performance Tuning
#41

Relminator, OK, is there example code or pseudocode out there for using a K-D Tree to store regions? It seems like a pretty large divergence from the way K-D Trees are presented around the web. Handling dynamic entities that are moving in and out of tree nodes frequently and overlapping multiple nodes is a problem that I don’t immediately see the solution to.

Riven, if my question annoys you, you can go somewhere else. Trees are used for collision detection in professional games, this is not a purely academic question, and optimization of such trees is a problem that has been well studied, I just can’t find the publications that discuss that optimization. Asking how best to optimize a spatial tree is a perfectly on-topic question for this forum. You don’t know the answer and rather than just not comment, you insist that I shouldn’t want to know the answer myself.

#42

The quadtree and octree example I posted above has a basic source on how to store data at the nodes. That’s also the way how to store data on a kd tree.

Riven’s posts are actually good ideas. Your entities are dynamic(moving) every frame. While quadtrees are fast at querying where an entity is, building it in realtime will take a veeeery long time.

His suggestion of using grids for moving entities us the best posted so far.

Btw, building a kd-tree in realtime is also very slow.

#43

just giving you some more ideas:

  • use a quadtree with a fixed depth, which enables you to get insertion time of O(1)
  • take a look at loose quadtrees(you will probably only find something for loose octree), which gives you a much better balanced tree

also abstract this implementation details away, so you can program in a way dependent from using either just a list a grid or quadtree. So you can just swap out different things to compare them

I have a 90% finished loos quadtree lying around if you want to take a look.

#44

You are new here and Riven runs this place. He probably knows, what you wants to know, but he surely is more experienced than you - so maybe you should be listening and thinking about what he says.

But maybe you are not interested in finishing a game and more into “technology-wanking” - that’s OK, but you should be aware of that…

#45

Despite people defending me (or the points I make), I think I prefer the role of ‘one of em’ rather than ‘the cute fluffy overlord’. The fact that I run this forum doesn’t really mean that I’m right, or need to be taken more seriously than ‘the new guy’ :slight_smile:

Having said that, I’ve written many quadtree and octtree implementations, that worked well, scaled way beyond my needs, but nothing was as performant and easy to write as grids.

IMHO spatial data structures like trees only really make sense in 3D games these days, as that additional dimension is a complete game changer, distribution wise.

#46

I just came up with this approach for ‘keeping all entities in the leafs’, regardless of cell boundaries, provided that the entity bounding box is at most half the size of a grid cell:

Imagine this uniform grid, with empty cells:

Now imagine this uniform grid, with a few entities:

You’ll see that their bounding boxes sometimes overlap the boundaries of the grid cells.

How can we solve this?

We can move the grid, half a cell-size along an axis, to account for the overlap:

Now every possible entity, can fit in a cell of one of these four grids with the offsets:

  1. offset: (0,0)
  2. offset: (d/2,0)
  3. offset: (d/2,d/2)
  4. offset: (0, d/2)

These are the four grids rendered (roughly) on top of eachother:

http://indiespot.net/files/published/entity-grid-four.png

Inserting an entity in the datastructure, is trivial:

  1. put entity in cell in the black grid, if it fully fits in a cell
  2. if not, put entity in cell in the red grid, if it fully fits in a cell
  3. if not, put entity in cell in the green grid, if it fully fits in a cell
  4. if not, put entity in cell in the blue grid - it will fit!

For posterity, I call this mindblowing trivial approach:
the axis aligned offseted grid set (AAOGS for short) :persecutioncomplex:

(it even works in 3D)

#47

To stay on topic: you can use this approach with (quad) trees too, although it’s a tad harder to generate the (four) sets of sub-nodes for each node, as they may define the same area as the offset sub-nodes sets of a neighbouring node. Knock yourself out, I’d say.

Just know that entities high in the hierarchy of the tree will drag down the performance of the whole datastructure. You should make very sure that every entity is as deep as possible in the tree. (with a grid, this is trivial, for obvious reasons)

#48

Btw are there any nice open source examples for something like this ?
Because when writing grids I’m always worried I may not do it as fast as possible.

#49

Cas won’t let me write optimized code anymore :emo: :point:

Only worry about noticeably slow code, not inefficient code in general.

#50

Thought I’d chip in… quadtrees are rather a lot slower than grid cells. They might be more useful when you’ve got entities which vary in size from “huge” to “tiny” but if they’re all within a certain size range, grids are the way to go.

Cas :slight_smile:

#51

@riven
that what you describe is excatly what these loose quad/oct -trees are all about^^

update:

here my little experimental loose quadtree implementation.
beware^^:
-it’s in scala
-the project is just a mix of multiple experiments, you only need to look at the one file
-knearest search isn’t implemented only collision check(circle or AABB)

#52

your point being?

#53

Hey, sorry, I had to run off yesterday. That time of day where they pay me was calling.

Riven, sorry if I have come off as being a bit petulant. But I feel like I’ve been basically told to shut up, when I have a question that is reasonable. Yes, as people have suggested, my interests are more in the theory behind game development than in an actual, practical game. I’ve got a summer between semesters, no relationship with any artist, and little likelihood of finishing a game that can be released in any meaningful sense. But I am still interested in this world of coding, and I am curious about how space is managed in a theoretical game where the maps are large and the entities are arranged in a possibly degenerate way. Yeah, that’s more theoretical than practical.

And maybe that makes my interests off-topic for this board. Fair enough. But my question remains, quadtrees are used in real games by real industry developers, they are used in modified and optimized ways, and discussion about how they are optimized is not lost in some bizarre realm of fictitious coding. If anyone has access to articles or documentation about this particular usage of this particular data structure (which I KNOW has to be out there somewhere) I’d appreciate it, but if not I feel no deep regret letting this thread die a natural death.

I’d be interested to see any journal articles, textbook examples, or other published discussion of how the standard textbook quadtree is optimized for performance in scenarios that actually arise in real games. I’m sure there are industry writers who have covered this, but industry doesn’t often let its knowledge out to the public. There’s probably a good academic discussion as well, but academia is barely any better about being publicly accessible. So I was wondering if anyone around here had had personal experience with the ways this particular data structure is optimized for real-world use.

Anyway, I don’t want to come off as a jerk. I’ve got some other avenues I can follow for information about how academics and professionals have optimized a particular data structure, and I’ll let this thread drop. I code toy games compulsively and I’ve got a little platformer / adventure project going in addition to my more theoretical Massive 2d game, so I’ll probably have something less abstract to contribute to the forum in the future.

Thanks to everyone. Sorry if I’ve stepped on toes.

#54

69WbIEEs288

Heheh :slight_smile:

Back to theory:

in this theoretical system with infinite size you have a requirement to test for collisions between a theoretically infinite number of entities in some bounded time. A little thinking here would tell us that you cannot practically have infinite anything in a game, so you have to nail down both infinity requirements to something more realistic and put some actual numbers on it. Then we’re on to the questions of how much time?, how many entities, and how large is the space in which they live?, with the optional question of what is the size range that these entities occupy, relative to the universe? So let’s have these figures thrashed out in concrete first.

Cas :slight_smile:

#55

Region quad-tree’s are greedy…there is no re-balancing. As I mentioned earlier, uniform grids and region quad-trees are related…so it’s common that a technique useful for a UG to be equal useful to a RQT. Now it’s highly likely that by a wide margin the most important spatial query to optimize is collision detection. So how to store an entity in a single cell in a UG and perform collisions? The easiest IMHO is to consider the upper-left extent (in a AABB manner) and store the entity there. Then perform a grid-based sweep and prune:

Quoting myself from this thread:

This applies to RQT in the same manner, you just walk all of the leaves (actually the spatial ordering on the walk doesn’t really matter…to just more clear in the UG case as presented). Of course “the devil’s in the details” and this can be coded up in various ways and there are variations on the same theme.

This scheme does not work for other spatial queries however. And some auxiliary data needs to be stored to handle them. How? Depends on a number of factors…and of course this is just a single possible direction.

#56

Let me semi-address your question of references. The trick is that I’m not aware of much “new” that pertains to the problem. The speed issue of UG and RQT is solely an implementation detail related to being cache obvious. Back when I had anything to do with academia (and dinosaurs walked the earth) the references were by Hanan Samet. You’re probably better off just spending some time on citeseer, arxiv and/or mendeley. You kids today have no idea how lucky you are to have free access to tons of research papers. A quick search yielded this http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.148.4652 which appears (from a 2 minute skim of 160 page paper) to be a reasonable to get an overview of some various methods.

#57

(Remember to be generous with that “appreciate” button, everyone!)

Cas :slight_smile:

#58

I just ran across this: http://www.dtecta.com/files/GDC13_vandenBergen_Gino_Physics_Tut.pdf

#59

Hello, I just stumbled upon this page when searching info about quadtrees, and I notice there’s lot of talk about algorithms on this website. So I created an account just to give my two cents.

I have been able to use modified quadtrees for an efficient implementation of nearest neighbor algorithm on c++. The choice of language doesn’t really matter, but the balancing conditions do.

It’s quadtree with variable width/height buckets. I insert the first five items to a bucket in no particular order. When a bucket is filled (it has five items), I take the most centre point of the five and make it a pivot. The other four points are then re-inserted into some or all of the quadrants defined by said pivot: upper right quadrant, upper left, lower left, lower right.

Each node in the tree is balanced at most 1 time. As I keep the pivot in the branch (not in the leaves), even a pathological input will lead to a working tree, because at each branch the number of items in the biggest bucket is reduced by at least 1 item, the pivot. In practice the branching factor becomes a bit more than 2.0 on average.

When a node is searched, start from the root, check if the item in current branch is the item you seek. If not, if it’s a branch with 4 quadrants, check which quadrant the item should be in and search that subtree (recursively). If it’s a branch with 1…4 items in no particular order, search all of them.

I’ve chosen the center item with simple heuristic: remove from the 5 items in order a) the rightmost b) the leftmost c) the top item d) the bottom item. The item that’s now left is pretty much in the center, with good probability to divide the current and future items in a balanced manner.

Hope it helps.
-Santtu

#60

Ohh I’m so sad I missed the meat of this topic!

I love me some spatial partitioning.

To address a few things:

You don’t need to make a Quadtree each frame, it’s stupid simple to adjust them. I used to LOVE grids, until I spent some time implementing a QuadTree… I actually like it more now. It’s simpler (yes I said it) and it’s a little faster.

Like I said previously, I’ve experienced them being faster. I’m fairly confident my Grid & Quad spatial structures are pretty optimized. I’ll post them below. In theory you’re right, it definitely depends on the processor and the implementation as well.

I think QuadTrees are easier, mostly because the case where an object lies on a border you just push it up until it’s completely contained within a node. The only efficient way I’ve found to combat entities on the borders for a Grid is to maintain lookback distances (based on the entities contained in a cell, account for all overlapping entities efficiently by optimally looking at surrounding cells while minimizing false positives).

I have a couple implementations I’ve been working on for a Steering Behavior/Spatial Database library (Steerio) I’ve been working on:

  1. Brute Force
  2. Dual Tree (something I call the hamburger/hotdog tree)
  3. Grid
  4. Quad
  5. Sweep and Prune

And of course the interface they all implement so you get an idea on how I have it working:


public interface SpatialDatabase
{
	public void add( SpatialEntity entity );
	public void clear();
	public int refresh();
	public int handleCollisions( CollisionCallback callback );
	public int intersects( Vector offset, float radius, int max, long collidesWith, SearchCallback callback );
	public int contains( Vector offset, float radius, int max, long collidesWith, SearchCallback callback );
	public int knn( Vector point, int k, long collidesWith, SpatialEntity[] nearest, float[] distance );
}

AND if you checkout my project because you want to watch them do their thing (and tinker with the variables live) here’s my example:

SpatialDatabaseExample

AND finally some stats on how it performs:

Steerio README

Hopefully my code helps you, let me know if you have anymore questions.

ALSO! I challenge someone to improve the performance of my Grid implementation to beat out my Quad and Dual tree implementations.