I would like to know the advantages and disadvantages of using octree or quadtree for spacial data structures? In a 3d gaming setting would you ever need more than 4 children nodes? Does it take longer to traverse through oct tree than quad tree? Is one of the two by all means faster than the other or is it a trade off sort of thing?
\$\begingroup\$
\$\endgroup\$
5
-
2\$\begingroup\$ Since octrees are just quadtrees with a third dimension, what you're really asking is whether you should use that third dimension, which can't be answered unless you provide more details about your game, such as what kind of game it is, what are the size and dimensions of typical levels etc. \$\endgroup\$– congusbongusCommented Mar 26, 2015 at 2:49
-
\$\begingroup\$ @congusbongus then give an answer that pertains rather than the particular game but to the size and dimensions of typical levels. Do larger levels run better with more children or less? How does size then pertain to the number of child nodes. \$\endgroup\$– Andrew WilsonCommented Mar 26, 2015 at 2:55
-
\$\begingroup\$ This question is pointless. Read and understand what quadtrees/octrees are and what are they used for, and you'll realize that without telling us WHAT you intend to use them for, it's impossible to say if one is better than the other. And of course quadtree is faster as it's less complicated because it uses one less dimension, which affects memory cost,memory access and traversal complexity. \$\endgroup\$– BabisCommented Mar 26, 2015 at 9:46
-
\$\begingroup\$ You ignored congusbongus's point. Which one you need is dependent on what you are doing, not on some abstract quality of betterness. If you want to know which one is appropriate, you have to describe your use case. Asking for a general answer to all conditions is unanswerably broad. \$\endgroup\$– Seth BattinCommented Mar 26, 2015 at 12:40
-
\$\begingroup\$ @SethBattin I didn't ignore his point as said in the initial question, "Is one of the two by all means faster than the other or is it a trade off sort of thing?" Implying that I don't know if there is an "abstract quality of betterness" and furthermore wanting someone to clear up if there is one? You say, "if you want to know which one is appropriate, you have to describe your use case." I clearly asked for the particular advantages of one over the other. Even hinting, "...or is it a trade off sort of thing." Which you now implied, saying that it matters what exactly you use them for. \$\endgroup\$– Andrew WilsonCommented Mar 27, 2015 at 3:08
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
1
I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] of every child[4] the calculation for the octtree could be as much as N^2(?) longer.
Since you don't specify how/why the tree is being used, it's hard to give a definitive answer.
The advantage is based on your objects' perspective/degrees-of-freedom.
Here are two examples:
Quad:
If your world is a quad-based terrain-style game, and your objects are all earth-bound, there's no reason to add a third dimension to your search. That is to say that your objects all traverse the terrain by moving from (X, Z) to (X1, Z1), interpolating their Y-values from an arbitrary second source (height map). The Y value also provides hints to the objects about what is in-between them (line-of-sight/collision ray-casting). In all cases, down is down. From your objects' perspective, other objects may be higher or lower, but always appear in one of 4 quadrants.
An anti-example of this would be ray-casting the mouse cursor with an octtree in SimCity. Do you care if you are hovering the top-half of the building vs. the bottom half? You wouldn't save any time by sorting the top half of every sky-scraper into a separate search dimension. For SimCity, we need to know if any part of a building is hovered, or not. In SimCity, each building occupies an (X, Z) and has a variable height.
Oct:
If many of your objects can move in 3D, an octtree may make more sense. In a space simulator, objects could be out-of-range, or out-of-scope, in more ways (above/below). Culling things behind you is still necessary, but now your object's are able to orient arbitrarily; "down" is no longer down, "forward" is now down, and "down" is now backward. From your objects' perspective, other objects may appear in any one of the 8 quadrants.
Using C&C, a quad-based, terrain-style game with flying units ("down" is always down, even for aircraft), as an example, where all flying units still occupy an (X, Z) but maintain a height of (heightmap + 20), neglecting combat animations. While ray-casting through the extra dimension, even on a quad-based game, the node directly above your test-object contains only flying units. Air-to-air craft don't have to test against units in the same node as the terrain; in other words, when an air-to-air jet is testing for objects in front of it, any node returned that contains the terrain, can be skipped. Likewise, a bomber aircraft that can only target ground-based objects, can skip all nodes that do not contain the terrain. Surface-to-air missile launchers wouldn't need to test terrain nodes either.
A similar anti-example would be jet aircraft in Battlefield-style games. You can move up and down, but you must do so by only flying "forward". A jet in Battlefield cannot fly or shoot in any direction other than forward, so if you used an octtree while flying, you would always skip 4 of the 8 quadrants. Another jet shooting you from behind requires the same (only) 4 quadrants that you are using. A helicopter or VTOL, however, can move straight "down" and, if equipped with turrets, shoot in semi-vehicle-independent directions. The turrets can only see and shoot "forward".
Round-up:
Hopefully this highlights the differences in needs/advantages. Don't get locked into one or the other, use them when applicable.
One more edit:
Back to the Battlefield example, if you maintain separate air-only and ground-only octrees that are identical in every other way, neither the overall object count nor the overall dimension count increase, so overhead does not increase (neglecting the increased memory footprint). So, for a vehicle that can shoot "bullets" (at land and air vehicles) and can also shoot lock-on style anti-air missiles at only air-craft, the difference, for targeting purposes, is a matter of which tree(s) to test, not how long it will take (the node coordinates/dimensions are identical). A bullet from a jet can skip ground-nodes until the bullet enters a node that contains the terrain. A ground-node returned from the air-tree, could link directly to the corresponding node in the ground-tree, allowing the bullet to be "handed off" to the ground tree. Separating the objects into different, nearly-identical trees ahead of time may help your performance if your game has to frequently distinguish between the two. Indexing between two 3D trees is a 4D tree. (X, Y, Z, WhichTree)
-
\$\begingroup\$ Thank you for the very detailed answer. It really cleared up exactly what applications I would want to use them for. Everyone else seemed to think the question needed an exact application to answer it. \$\endgroup\$ Commented Mar 27, 2015 at 3:19