Optimizing a QuadTree for enormous maps

Performance Tuning
#61

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

#62

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.

#63

Cells and portals are better than grids for dynamic levels.

#64

Cells and portals are better than grids for dynamic levels.

#65

Cells & portal are awesome in appropriate situations…they are also orthogonal to other choices (i.e. how a cell is organized).

#66

Cells & portal are awesome in appropriate situations…they are also orthogonal to other choices (i.e. how a cell is organized).