Storing Large 2D Game Worlds

Question

I've been experimenting with different ideas of how to store a 2D game world. I'm interested in hearing techniques of storing large quantities of objects while managing the set that's visible ( lets say 100,000 tiles square ). Obviously the techniques can vary based on how the game renders that space.

Lets assume that we're describing a scrolling 2d game world rather than screen based as you could fairly easily do screen based rendering from such a setup while the converse is a bit more messy.

Looking for language agnostic solutions here so it's more helpful to others.

Edit: I think a good answer here would be a general review of the ideas to consider when thinking about this, as some of the responders have attempted, but also begin to explain how different solutions would apply to those scenarios. It's a somewhat complex question, so I would expect a good answer to reflect that.

Tragedian

Answer 1

Quadtrees are a fairly efficient solution for storing data about a large 2-dimensional world and the objects within it.

Selfmortification

From what I've read of Quadtrees they seem expensive to update. So if there are any actively moving objects, that could be problematic, no? – Tragedian

It depends, mainly on the sparseness of the world - if the ratio of objects to space in the world is fairly small, then the gains of using quadtrees will outweigh a slightly more complicated update process. If the ratio is large (and thus the world is rather dense with objects), then quadtrees will not be as ideal a solution, and another representation would be more ideal. – Selfmortification

Answer 2

You might get some ideas on how to implement this from some spatial data structures like range or kd trees.

However, the answer to this question would vary considerably depending exactly on how your game works.

Are we talking a 2D platformer with 10 enemies onscreen, 20 more offscreen but "active", and an unknown number more "inactive"? If so, you can probably store your whole level as an array of "screens" where you manipulate the ones closest to you.

Or do you mean a true 2D game with lots of up/down movement too? You might have to be a bit more careful here.

The platform is also of some importance. If you're implementing a simple platformer for desktop PCs, you probably wouldn't have to worry about performance as much as you would on an embedded device. This is no excuse to be naive about it, but you might not have to be terribly clever either.

This is a somewhat interesting question I think. Presumably someone smarter than I who has experience with implementing platformers has thought these things out already.

Nanon

Answer 3

Break the world into smaller areas, and deal with them. Any solution to this problem is going to boil down to this concept (such as quadtrees, mentioned in another answer). The differences will be in how they subdivide the world.

How much data is stored per tile? How fast can players move across the world? What's the behavior of NPCs, etc., that are offscreen? Do they just reset when the player comes back (like old Zelda games)? Do they simply resume where they were? Do they do some kind of catch-up script?

How much different rendering data is going to be needed for different areas?

How much of the world can be seen at one time?

All of these questions are going to immpact your solution, as well as the capabilities of your platform. Coming up with a general answer for these without having a reasonable idea of these parameters is going to be a bit difficult.

Beaverbrook

I can provide specifics for my particular goings-ons, but that doesn't seem as useful to others here. I'll try to further specify the parameters for a good answer here... – Tragedian

Answer 4

Assuming that your game will only update what is visible and some area around what is visible, just break the world in "screens" (a "screen" is a rectangular area on the tilemap that can fill the whole screen). Keep in memory the "screens" around the visible area (and some more if you want to update entities which are close to the character - but there is little reason to update an entity that far away) and have the rest on disk with a cache to avoid loading/unloading of commonly visited areas when you move around. Some setup like:

+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|VVV|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+

Where "V" part is the "screen" where the center (hero or whatever) is, the "N" parts are those who are nearby and have active (updating) entities, are checked for collisions, etc and "F" parts are far parts which might get updated infrequently and are prone to be "swapped" out (stored to disk). Of course you might want to use more "N" screens than two :-).

Note btw that since 2D games do not usually hold much data instead of saving the far away parts to disk you might want to just keep them in memory compressed.

Wonderwork

Thanks for sharing this. I'm already doing something much like this, and have found it to be efficient enough for my purposes at the moment. – Tragedian

Answer 5

You probably want to use a single int or byte array that links to block types. If you need more optimization from there, then you'll want to link to more complicated data structures like oct trees from your array. There is a good discussion on a Java game forum here: http://www.javagaming.org/index.php/topic,20505.30.html text

Anything with links becomes very expensive because the pointer takes up something like 8 bytes each, depending upon the language, so depending upon how populated your world is it can get expensive very quickly (8 pointers 8 bytes each is 64 bytes per item, and a byte array is 1 byte per item). So unless 1/64 of your world is empty, a byte array is going to be a much better option. You're also going to need to spend a lot of time iterating down the tree whenever you're doing a lookup for collision or whatever else - a byte array will be an instantaneous lookup.

Hopefully that's detailed enough for you. :-)

Zeitgeist

I appreciate the thoughts! It's not general enough to be the accepted answer, but thanks for sharing the idea. – Tragedian