# A way to store potentially infinite 2D map data?

I have a 2D platformer that currently can handle chunks with 100 by 100 tiles, with the chunk coordinates are stored as longs, so this is the only limit of maps (maxlong*maxlong). All entity positions etc etc are chunk relevant and so there is no limit there.

The problem I'm having is how to store and access these chunks without having thousands of files. Any ideas for a preferably quick & low HD cost archive format that doesn't need to open everything at once?

• Some data structures that you could look into for more inspiration are sparse matrices and (multilevel) page tables. – Andrew Russell Jun 8 '11 at 14:00
• Low priority: Could you clarify if the "long" data type is 32- or 64-bit? – Randolf Richardson Jun 8 '11 at 16:38
• @Randolf given that this is C#, presumably he means the C# long which is 64-bit (so maxlong is Int64.MaxValue). – Andrew Russell Jun 9 '11 at 12:56
• Notch has some interesting things to say about the infinite maps in Minecraft in his blog here: notch.tumblr.com/post/3746989361/terrain-generation-part-1 – dlras2 Jul 14 '11 at 0:23

Create a custom map format for your game. It's easier than you might think. Just use the BinaryWriter class. First write the header in a few ints or uints. Information to include in the header:

• The magic string / magic number of you file format.
• The start/end/size of the chunks described in this file

and also (and here comes the performance critical part

• ints that describe the starting position inside the file. So you don't have to search for specific chunks.

With the above methode you can (and should) create an index of your files contents, containing some sort of description(a user specified name for the region/chunk, or just the coordinates) and as a second value the position in the file.

Then, when you want to load a specific chunk, you'll just have to search inside the index. When you got the position just set fileStream.Position = PositionOfChunkFromIndex and you can load it.

It's all about the design of the fileformat with the header describing the contents of the file most efficiently.

Just save the files with a custom extension you made up and there you go.

BONUS: Add BZip2 compression to specific regions of the file / the whole contents (not the header!!), so you can unpack specific chunks from the file, for a very small memory footprint.

• It's worth pointing out that, if you're going to be modifying this file on-the-fly, you will want either a fixed-sized or external header/index, such that you can add chunks to the file without having to rewrite the entire file (due to the offsets changing). – Andrew Russell Jun 8 '11 at 13:58
• At that point, aren't you just implementing a flatfile database? – Ape-inago Apr 13 '14 at 23:58

I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

You can specify a minimum magnitude for each node (a magnitude of 7 would be 128x128) and once any node has a specified percentage of its subnodes populated, it automatically flattens itself into a two-dimensional array. This means that a very densely populated portion (e.g., a completely explored continent) will have the performance of an array (very fast) but a sparsely populated portion (e.g., a shoreline someone wandered up and down but didn't explore inland) will have good performance and a low memory usage.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.

I've not yet used it to store data to a file, but it's an interesting problem and I may tackle that next.

• So this is basically a expandable tree, right? What am I missing? – kaoD Jun 15 '11 at 5:54
• The biggest improvement over an expandable tree is that it 'flattens' certain nodes of the tree which are heavily populated (default 70%) into 2D arrays, rather than keeping them structured like trees. This gives you the speed of an array lookup, without the (infinite) size of an infinite array. – dlras2 Jun 15 '11 at 11:40
• Both leaf and inner nodes, right? Interesting idea, might give good results, I'll give it a try if I ever need this. Btw, +1 for giving out the code and the quick answer! Oh, and unit testing done too, I (sadly) never do that in my personal projects :) – kaoD Jun 15 '11 at 17:29
• We don't do any unit testing at my work, so sadly it's my way of rebelling.. I did make up a demo app for it, which shows how it populates and flattens, so if I can clean that up in the next few days so it's presentable, I'll post it here as well. It makes a lot more sense when you see it. – dlras2 Jun 16 '11 at 6:12
• I lost sight of it, sorry! I'd still like to get it cleaned up, but I'm slowly reworking some of the code between class and homework, so that won't be for a while. For now, the old, un-pretty demo is here: j.mp/qIwKYt By un-pretty, I partially mean it requires a lot of explanation, so don't forget to read the README and feel free to ask questions here or via email. – dlras2 Sep 7 '11 at 23:57

You could use a database instead -- PostgreSQL has some special indexing capabilities optimized for this type of data which is located by X and Y coordinates. You can also specify that the data returned is within a certain radius rather than in a square or oblong shaped area.

PostgreSQL (free and open source)
http://www.postgresql.org/

There are other databases as well, and for the client-side you may find certain types to be better-suited to this since they can run stand-alone (initiated by your game client application) or can be included as part of a code library that you can "just use." The advantage is that you don't have to design an indexing scheme because most SQL database engines already do this quite well.

An advantage with the database approach is that you can make your chunks smaller (or get rid of chunks completely and just use tiles directly, but the use of at least small chunks/groups of many tiles may be more efficient depending on your design), and then use the SQL query to bring in a larger area than is viewable. By pre-loading to overlap nearby non-viewable areas, the tiles can be prepared before the player moves their character, resulting in a better (hopefully smoother) gaming experience.

I've noticed that some games keep a "cache" of the map data on the local hard drive after obtaining it the first time (this is undoubtedly to reduce network I/O), such as Ashen Empires:

Ashen Empires (free to play, beautiful 2D implementation)
http://www.ashenempires.com/

Keeping track of "last updated" timestamps with each chunk/tile will also be helpful since, for where locally stored data is available, the SQL query could include an additional "WHERE timestamp_column > \$local_timestamp" clause so that only updated chunks/tiles get downloaded (two benefits of saving bandwidth like this are lower connectivity costs, and less lag for your players, which will become more obvious when your game gets popular).

A screen shot from Ashen Empires (a few characters are at a local bank, and by the looks of those bones on the floor it looks like a few skeleton monsters must've wandered in and were likely slaughtered by the local town's guards):

Do not store and access them, store only the necessary random seeds as well as the player's changes to the map. Then generate required portions at run-time (run your generation algorithm, then apply the player's changes). With correct and consistent generation procedure, the resulting map will always be the same for the same starting seed.

Theoretically you can do literally infinite map that will save to a very small file this way.

• @Josh Petrie thanks for the significant and great language/stylistic corrections to my post. pity i can't upvote an edit :-D – sh code May 29 '17 at 8:11

Is there any way you can partition chunks (some kind of 'subcontinents / countries' in you world) ? So maybe you can have some kind of index files that let you quickly find which sub-file / part of bigger file you need to load to have a chunk in memory ...

• there is always a way you can partition chunks. ALWAYS. whether they're visible to the player/relevant to the rest of the system or not, there's always a way to partition world data to chunks, usually in multiple different ways. – sh code May 29 '17 at 8:08

You could take the idea from Minecraft. Originally they had a file per chunk. Now they use the MCRegion format, which groups chunks into 32x32 areas and stores one of those per file.