Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
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 8342 times)
0 Members and 1 Guest are viewing this topic.
Offline Roquen
« Reply #30 - Posted 2013-05-03 12:54:24 »

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

Innocent Bystander





« Reply #31 - 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.
-Santtu

Offline ClickerMonkey

JGO Coder


Medals: 20


Game Engineer


« Reply #32 - 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:

Quote
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.

Quote
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.

Quote
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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline gouessej
« Reply #33 - Posted 2013-08-07 17:58:16 »

Cells and portals are better than grids for dynamic levels.

Offline Roquen
« Reply #34 - 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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (38 views)
2014-09-24 16:13:29

Pippogeek (29 views)
2014-09-24 16:12:22

Pippogeek (18 views)
2014-09-24 16:12:06

Grunnt (42 views)
2014-09-23 14:38:19

radar3301 (24 views)
2014-09-21 23:33:17

BurntPizza (61 views)
2014-09-21 02:42:18

BurntPizza (31 views)
2014-09-21 01:30:30

moogie (36 views)
2014-09-21 00:26:15

UprightPath (49 views)
2014-09-20 20:14:06

BurntPizza (53 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org 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‑gaming.org
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!