I'm about to program a copy of Mario in Java. I'm thinking on 2 representations/data structures for the levels but I'm not sure which one should I choose:
- A 2D integer array.
- A quadtree to divide the level in pieces.
What are its advantages and disadvantages?
Answer
The point of a quadtree is to efficiently cull large chunks of the data so that you only spend time on the data in the immediate vicinity. However a 2D array already gives you location-specific random access, so for a 2D game that may make a quadtree redundant. In a 3D game you can't use an array to locate everything and that's where quadtrees (or better yet octrees) are handy.
Now, I'm talking here about the underlying data representation for the level. Depending on how your graphic architecture is setup (eg. doing 2D graphics with planes in a 3D engine) you may want to use quadtrees in the scene graph in order to efficiently cull graphical content.
And then don't forget various enemies and other interactive objects in your level. Perhaps you use a 2D array to manage the tiles of the level, but use quadtrees to organize all the interactive elements (eg. for a physics engine).
Think of it this way: pick a point at random in your level, and then think about how much work it'll take to figure out everything within a 1000 pixel radius of that point. If you can do that quickly because everything is organized by location in a 2D array, then you don't need a quadtree. If however you would have to loop through everything and check each object's distance individually, then you could make the search much more efficient by using a quadtree.
No comments:
Post a Comment