Quadtrees?

[woperri]

Hi, I'd like to know some of the benefits of using quadtrees as a data structure to represent 2D maps. I'm not 100% sure how it works, because I've only read about them, but if it's anything like a binary tree (which it sort of seems to be like), it seems that you'd have to spend more time accessing a particular element by quadtree than you would using a 2D array, since you have to follow the branches down instead of having direct access. I've googled a bit about quadtrees, and many people seem to say that they're great for cutting down processing time, but I'm still in the dark about in what specific places - especially pertaining to roguelikes - that they would time down in and how/why. What are the pros and cons of using quadtrees vs a 2D array?

Or is it simply better to use both, if that were possible? If so, how would I do it - would I simply make the data references in a quadtree node point to the corresponding element (for example, a Tile) at indices x,y in the array? Would this potentially cause issues? Is this idea too inefficient to use?

[Tapio]

Well, in quadtree, every non-leaf node has 4 children and their arrangement is usually spatial, so quite different from binary tree. Quadtrees (and octrees, their 3d counterpart) are useful for level-of-detail stuff (mainly in 3d graphics and terrain rendering: for parts close to the camera you dive deep into the quadtree branches and far away parts of the scene can be left to higher levels) and data compression (e.g. if you have a large area of water, you could represent a big part of that as a big quadtree node and then subdivide i.e. create finer grained cells when there is an island).

You could also put something like enemies to a quadtree which would allow searching for them in a specific area very efficiently since a quad tree can potentially tell you very early that there is no one there (or alternatively "zoom-in" to the targets quickly). However, this really only becomes beneficial with a huge map and lot of stuff to search. In the context of fairly traditional roguelikes, I don't really see use for quadtrees - array is much easier to work with.

[woperri]

Hmm, ok, thanks. If there's no real purpose to it, it's probably better not to use it. Makes things more complicated. Thanks.

[guest509]

  I can't think of how you would significantly improve performance with a quadtree data structure over the less complex array in the roguelike context. But I can definitely see how you might get bogged down by such a complex structure and get discouraged.

  That said many people use roguelike creation and tinkering as a learning tool. If you want to learn quadtrees then by all means use 'em! And above all have fun doing it. Hobby gaming should be fun first I say.