Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
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-05-01 16:22:42
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.
2  Game Development / Performance Tuning / Re: Optimizing a QuadTree for enormous maps on: 2013-04-30 16:08:38
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.
3  Game Development / Performance Tuning / Re: Optimizing a QuadTree for enormous maps on: 2013-04-30 15:54:03
OK, Roquen, toward the one optimization that has been actually stated in this thread, pushing all rectangles to leaf nodes, how does this work in relation to the tree implementation linked above?

What if an entity overlaps multiple leaf nodes?  If the leafs are particularly small, a single entity could overlap even more than 4 nodes.  How does the algorithm move entities between different nodes?  What happens when nodes become empty?  Is there any way to rebalance the tree?
4  Game Development / Performance Tuning / Re: Optimizing a QuadTree for enormous maps on: 2013-04-30 15:38:29
OK, I'm looking at K-D Trees and this looks interesting, but I can't find any reference that talks about how to use a K-D Tree to store rectangular regions rather than points.  Can that be done?
5  Game Development / Performance Tuning / Re: Optimizing a QuadTree for enormous maps on: 2013-04-30 15:11:25
I will have:

A very large game world
Many entities
Dynamic entities moving between regions
Large discrepancies in how densely populated the world is, there will be regions thousands of viewports wide with no entities at all, and there will be regions a few viewports large with many hundreds of entities.  I can't assume an ideal or normalized distribution.

The objection to a quadtree that people offer in every thread that it comes up in is that it's too hard to code and a grid works just fine 95% of the time.  I am starting with an engine that is designed from the ground up to work with tens or even hundreds of thousands of entities distributed unevenly across a map that is hundreds of thousands of viewports large, or infinite if I can figure out how to do that.

I really don't think a grid is appropriate, and the argument for a grid tends to run "it's easier to code."  I don't mind working with a somewhat complicated data structure.  I'm a Computer Science student, I did well in data structures, and spending some time optimizing a quadtree is not something I'm afraid of.  A little bit of logical puzzling appeals to me.

So I'll reiterate my question:  How best to optimize a quadtree for large numbers of dynamic rectangular entities arranged in an uneven distribution across a vast space, beyond the simple textbook implementation presented around the web?
6  Game Development / Performance Tuning / Optimizing a QuadTree for enormous maps on: 2013-04-30 14:26:51
Hello everyone, I've been lurking on this board for a bit and now I'd like to post a discussion topic, I hope I'm not making any faux-pas.  I don't think I'm stepping on any toes.

There have been discussions elsewhere about Quadtrees vs. Grids for optimized collision detection and the opinions of people who seem to know what they are talking about is:

1) Grids save coder effort vs. Quadtrees
2) Quadtrees are only useful for enormous maps with tons and tons of entities.
3) The basic Quadtree implementation that you see on Wikipedia, forums, and elsewhere is unoptimized and modern quadtrees in real games are tuned to reduce the search size when looking for potential collisions.

I've got a few ideas for games that involve massive generated worlds, 2d spaces that will have coordinates into the millions, hundreds of millions, even potentially "infinite" if I can work out a good algorithm for an infinite map.  Imagine something like a 2d EVE or Skyrim, so I'm working on an engine that will let me experiment and I'm definitely going to need collision detection across an enormous area.  I think I need a quadtree.

So my question is what resources exist for optimizing giant quadtrees (specifically a region quadtree that looks for collisions between rectangular entities and map squares.  I've heard it helps to keep everything in leaf nodes, but I don't see how that's possible.  There seems to be an opinion that if there are really large numbers of entities moving around, rebalancing is needed, and in general handling entities moving from quadtree node to quadtree node dynamically isn't discussed in the public presentation of trees that you see.

Second question, lets say my map consists of a regular arrangement of equally sized squares, perhaps broken down into a grid of regions that are dynamically generated as the player explores.  What's the best way to check for collisions between entities in the quadtree and grid squares.  Should the map grid just be in the tree instead of in a separate grid?  That seems like it could get out of hand for a huge map, but maybe I'm not thinking about the equal space and search requirements for a big enough grid and I should just keep all collision / proximity testing in the same data structure.  Eventually it seems like there would be a need to load only parts of the map and corresponding areas of the quadtree at any one time.

As a reference point I'm looking at this quadtree implementation as an example of a "typical" unoptimized tree:
http://code.google.com/p/slick2d-tests/source/browse/SlickTutorials/trunk/src/de/myreality/dev/slick/collisions/Quadtree.java?r=3

Though there are others out there that are mostly similar.  It does no rebalancing and can require a very deep search comparing many entities of many different levels.  Also if the bounds on the outermost tree node are very large (say 2 ^ some significant power) and there are many entities clustered in a small local area, the tree will have to be divided into many many sublayers for a small number of entities and many nodes will be used to hold large empty areas.

Ideally, there's a discussion in a journal, magazine, or textbook about this topic.  I have access to a university library.

Thanks!
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.

rwatson462 (36 views)
2014-12-15 09:26:44

Mr.CodeIt (29 views)
2014-12-14 19:50:38

BurntPizza (61 views)
2014-12-09 22:41:13

BurntPizza (98 views)
2014-12-08 04:46:31

JscottyBieshaar (58 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (76 views)
2014-11-29 21:32:03

toopeicgaming1999 (136 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (37 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!