Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (778)
Games in Android Showcase (231)
games submitted by our members
Games in WIP (856)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Optimizing a QuadTree for enormous maps  (Read 34584 times)
0 Members and 1 Guest are viewing this topic.
Offline santtu

Innocent Bystander

« Reply #30 - Posted 2013-08-06 11:15:56 »

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.

Offline ClickerMonkey

JGO Coder

Medals: 26
Exp: 10 years

Game Engineer

« Reply #31 - Posted 2013-08-06 11:56:30 »

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

I love me some spatial partitioning.

To address a few things:

For dynamic entities, grids should be better. Quadtrees are fast to traverse but slow to make.

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.

Traversing (quad) trees is incredibly inefficient due to cache misses.

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.

it's easier to code

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:


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.

Offline gouessej
« Reply #32 - Posted 2013-08-07 17:58:16 »

Cells and portals are better than grids for dynamic levels.

Julien Gouesse | Personal blog | Website | Jogamp
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen

JGO Kernel

Medals: 518

« Reply #33 - Posted 2013-08-07 19:27:21 »

Cells & portal are awesome in appropriate situations..they are also orthogonal to other choices (i.e. how a cell is organized).
Pages: 1 [2]
  ignore  |  Print  

hadezbladez (350 views)
2018-11-16 13:46:03

hadezbladez (183 views)
2018-11-16 13:41:33

hadezbladez (349 views)
2018-11-16 13:35:35

hadezbladez (85 views)
2018-11-16 13:32:03

EgonOlsen (2179 views)
2018-06-10 19:43:48

EgonOlsen (2221 views)
2018-06-10 19:43:44

EgonOlsen (1379 views)
2018-06-10 19:43:20

DesertCoockie (2012 views)
2018-05-13 18:23:11

nelsongames (1671 views)
2018-04-24 18:15:36

nelsongames (2309 views)
2018-04-24 18:14:32
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!