• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
japro

Why is everyone so in love with quadtrees?

8 posts in this topic

The need for data structures that allow for some sort of neighbor search and/or region query are quite common in almost any kind of simulation including video games. Possible solutions include simple sorted lists, grids, hash maps, all sorts of trees etc.. I found myself in the situation that I had to implement such a structure many times now and almost always do a little search to see if there are particularly well suited structures for the specific problem I'm trying to solve. Especially in forums any question about this sort of thing will invariably result in someone mentioning a quad/octree in the first few answers (often the first). Accordingly I started out writing a quadtree many times and so far I ditched every one of those attempts and went for something that I felt was better suited. So either quadtrees are overhyped or I just don't know how to write one.

The "replacement" solutions I mostly use are either grids, hash maps or binary trees. Grids work nicely in situations where the domain is finite and in average cases give almost optimal complexity (build in O(n), search in O(1), usually about O(n) memory requirement) and iteration over them can be implemented to be very cache friendily. I use hash maps in pretty much the same situation with the difference that I don't need a finite domains for those. With binary trees I mean the ones where you subdivide the space either along the longest axis (which actually is almost equivalent to a quad/octree) or at the "median" element (kd-tree?).

Quadtrees in comparison just always seemed unwieldy to me. They are "finite domain", "fixed subdivision" structures and seem to mostly combine the disadvantages of the other structures. But given the wide usage I have to assume I'm missing something. I especially get frustrated with their implementation. Not that I don't get them to work or something, It's just that the other structures always look "cleaner" to me, especially the grids which look borderline trivial and are super easy to maintain/test. Also apart from the algorithmic complexity, the "raw speed" (as in measured speed) from say a coarse grid is often better for my use cases (running in a fraction of a single frame) because of the more linear memory access patterns.

So what is the deal with Quadtrees? How are they really efficiently implemented? In what cases are they better than the alternatives?
2

Share this post


Link to post
Share on other sites
[quote name='japro' timestamp='1315322187' post='4858193']
Also apart from the algorithmic complexity, the "raw speed" (as in measured speed) from say a coarse grid is often better for my use cases (running in a fraction of a single frame) because of the more linear memory access patterns.

So what is the deal with Quadtrees? How are they really efficiently implemented? In what cases are they better than the alternatives?
[/quote]

For special cases like terrain, where you already know that the entire tree will be filled, you can use a pointer free tree, consecutively stored in memory and being pretty fast with little overhead (none, actually, since nodes don't store anything but user data). Besides that I wouldn't use any tree unless the number of objects/data really begs for it.
0

Share this post


Link to post
Share on other sites
I think I've read somewhere an article about "relaxed quadtrees" or something. I'd currently like to investigate them in more detail. Standard QuadTrees never catched up with me. Hell, I'm not at home even with BSPs...
0

Share this post


Link to post
Share on other sites
[quote name='Trienco' timestamp='1315331714' post='4858259']
For special cases like terrain, where you already know that the entire tree will be filled, you can use a pointer free tree, consecutively stored in memory and being pretty fast with little overhead (none, actually, since nodes don't store anything but user data). Besides that I wouldn't use any tree unless the number of objects/data really begs for it.
[/quote]

Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?
0

Share this post


Link to post
Share on other sites
[quote name='japro' timestamp='1315342071' post='4858324']
Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?
[/quote]

I don't think that you're missing anything japro. At a basic level it's [i]exactly[/i] another way to index a grid. One point though of the tree over, say, a regular grid is would be memory usage. With a regular grid you need resources to maintain every grid element of the entire world. With the tree you're able to condense empty areas of the world into larger elements and potentially spend that memory to provide a more fine grained partition for areas where there actually are a lot of objects. I wouldn't be surprised if the people that keep saying 'use an octree' are just using that as a shortcut for 'use some form of data structure that provides reasonably spatial partitioning'. Grids can work out great for that, as can octrees or BSP trees.

One thing to remember about any data structure is that they're always situational. If I were building a board game like chess a grid seems like the most reasonable data structure but for something more free-form like a GTA game, maybe it's not.
1

Share this post


Link to post
Share on other sites
[quote name='japro' timestamp='1315342071' post='4858324']
Hmm, but then the "tree" is nothing but a storage order? I see the advantage that this order has better "spatial coherence", but it's primarily another way to index a grid, or am I missing something?
[/quote]

Pretty much that. If the tree doesn't have additional info (like bounding volumes for each node) there is no reason for it to explicitly exist at all and it just boils down to index your grid a certain way (at this point the tree is probably useless). It's just the one special case, where you can implement a tree without all the child/parent pointers that waste space and make collecting all leaves of a higher up node very painful. It is very useless for dynamic game objects unless your world is so full that (almost) every cell of the underlying grid is actually filled.

Besides that, if there really is any particular love for quadtrees it's probably because the concept is simpler than trees using arbitrary or alternating planes and with even 3D games mostly happening in 2 dimensions they are the most commonly applicable kind of tree.
1

Share this post


Link to post
Share on other sites
[url="http://wiki.gamedev.net/index.php/Spatial_Partitioning"]You'd like this article then.[/url] People sometimes question the last part in it, but usually end up accepting it. Quadtrees do have one advantage, but most people never need it and that is optimal frustum culling for 2D portal tests and such. The same algorithm can be implemented for grids, but it ends up being not as optimal.
2

Share this post


Link to post
Share on other sites
During the creation of my google maps clone (that is displaying vector & raster data using the mercator projection) a quadtree came in very handy and was several magnitudes faster for frustum culling than an ordinary hash map. Even with "huge" amount of items (about 100.000) it performed quite well and provided other means for culling as well. Drawing so many items would result in too much overdraw (for example if each is represented by a smal 16px² image) and thus less benefit for the user: I quickly came up with an algorithm that filtered out a big percentage of unseen items (basically only N items could be drawn PER bucket, where N is calculated from bucket_size / maximum_item_size).
But as always, choose the right tool for the job: If a quadtree didn't perform as well for you, then it may not be the right one (or your implementation was bad, or you used it wrong, but I can't judge that ;) ).
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0