Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (553)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
   Home   Help   Search   Login   Register   
  Show Posts
Pages: [1]
1  Game Development / Performance Tuning / Re: Optimizing a QuadTree for enormous maps on: 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

Pages: [1]
 

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

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (24 views)
2014-08-22 19:31:30

atombrot (34 views)
2014-08-19 09:29:53

Tekkerue (30 views)
2014-08-16 06:45:27

Tekkerue (28 views)
2014-08-16 06:22:17

Tekkerue (18 views)
2014-08-16 06:20:21

Tekkerue (27 views)
2014-08-16 06:12:11

Rayexar (65 views)
2014-08-11 02:49:23

BurntPizza (41 views)
2014-08-09 21:09:32

BurntPizza (33 views)
2014-08-08 02:01:56

Norakomi (42 views)
2014-08-06 19:49:38
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!