What is a good way to store tilemap data?

Question

I'm developing a 2D platformer with some uni friends. We've based it upon the XNA Platformer Starter Kit which uses .txt files to store the tile map. While this is simple it does not give us enough control and flexibility with level design. Some examples: for multiple layers of content multiple files are required, each object is fixed onto the grid, doesn't allow for rotation of objects, limited number of characters etc. So I'm doing some research into how to store the level data and map file.

This concerns only the file system storage of the tile maps, not the data structure to be used by the game while it is running. The tile map is loaded into a 2D array, so this question is about which source to fill the array from.

Reasoning for DB: From my perspective I see less redundancy of data using a database to store the tile data. Tiles in the same x,y position with the same characteristics can be reused from level to level. It seems like it would simple enough to write a method to retrieve all the tiles that are used in a particular level from the database.

Reasoning for JSON/XML: Visually editable files, changes can be tracked via SVN a lot easier. But there is repeated content.

Do either have any drawbacks (load times, access times, memory etc) compared to the other? And what is commonly used in the industry?

Currently the file looks like this:

....................
....................
....................
....................
....................
....................
....................
.........GGG........
.........###........
....................
....GGG.......GGG...
....###.......###...
....................
.1................X.
####################

1 - Player start point, X - Level Exit, . - Empty space, # - Platform, G - Gem

Answer 1

So reading through your updated question, it seems you're most concerned about "redundant data" on disk, with some secondary concerns about load times and what the industry uses.

First off, why are you worried about redundant data? Even for a bloated format like XML, it would be pretty trivial to implement compression and get the size of your levels down. You're more likely to take up space with textures or sounds than your level data.

Second, a binary format is more than likely going to load faster than a text-based one that you have to parse. Doubly so if you can just drop it in memory and have your data structures just there. However, there are some downsides to that. For one, binary files are next to impossible to debug (especially for content creation people). You can't diff or version them. But they will be smaller, and load faster.

What some engines do (and what I consider an ideal situation) is implement two loading paths. For development, you use a text-based format of some kind. It really doesn't matter which specific format you use, as long as you use a library that's solid. For release, you switch to loading a binary (smaller, faster loading, possibly stripped of debug entities) version. Your tools to edit the levels spit out both. It's a lot more work than just one file format, but you can kind of get the best of both worlds.

All that being said, I think you're jumping the gun a bit.

Step one to these problems is always describe the problem you're running in to thoroughly. If you know what data you need, then you know what data you need to store. From there it's a testable optimization question.

If you have a use case to test against, then you can test a few different methods of storing/loading data to measure for whatever you consider to be important (loading time, memory usage, disk size, etc.). Without knowing any of that, it's hard to be more specific.

Answer 2

• XML: Easy to edit by hand but once you start loading a lot of data, it slows down.
• SQLite: This may be better if you want to retrieve lots of data at once or even just small chunks. However, unless you're using this elsewhere in your game, I think it's overkill for your maps (and probably overcomplicated).

My recommendation is to use a custom binary file format. With my game, I just have a SaveMap method which goes through and saves each field using a BinaryWriter. This also allows you to choose to compress it if you want and gives you more control over file size. i.e. Save a short instead of an int if you know it's not going to be larger than 32767. In a large loop, saving something as a short instead of an int can mean a lot smaller file size.

Also, if you go this route, I recommend your first variable in the file be a version number.

Consider for example, a map class (very simplified):

class Map {
    private const short MapVersion = 1;
    public string Name { get; set; }

    public void SaveMap(string filename) {
        //set up binary writer
        bw.Write(MapVersion);
        bw.Write(Name);
        //close/dispose binary writer
    }
    public void LoadMap(string filename) {
        //set up binary reader
        short mapVersion = br.ReadInt16();
        Name = br.ReadString();
        //close/dispose binary reader
    }
}

Now, let's say you wanted to add a new property to your map, say a List of Platform objects. I picked this because it's a little bit more involved.

First of all, you increment the MapVersion and add the List:

private const short MapVersion = 2;
public string Name { get; set; }
public List<Platform> Platforms { get; set; }

Then, update the save method:

public void SaveMap(string filename) {
    //set up binary writer
    bw.Write(MapVersion);
    bw.Write(Name);
    //Save the count for loading later
    bw.Write(Platforms.Count);
    foreach(Platform plat in Platforms) {
        //For simplicities sake, I assume Platform has it's own
        // method to write itself to a file.
        plat.Write(bw);
    }
    //close/dispose binary writer
}

Then, and this is where you really see the benefit, update the load method:

public void LoadMap(string filename) {
    //set up binary reader
    short mapVersion = br.ReadInt16();
    Name = br.ReadString();
    //Create our platforms list
    Platforms = new List<Platform>();
    if (mapVersion >= 2) {
        //Version is OK, let's load the Platforms
        int mapCount = br.ReadInt32();
        for (int i = 0; i < mapCount; i++) {
            //Again, I'm going to assume platform has a static Read
            //  method that returns a Platform object
            Platforms.Add(Platform.Read(br));
        }
    } else {
        //If it's an older version, give it a default value
        Platforms.Add(new Platform());
    }
    //close/dispose binary reader
}

As you can see, the LoadMaps method can not only load the latest version of the map, but also older versions! When it loads the older maps, you have control over the default values it uses.

Answer 3

Short Story

A neat alternative to this problem is to store your levels in a bitmap, one pixel per tile. Using RGBA this easily allows four different dimensions (layers, ids, rotation, tint, etc.) to be stored on a single image.

Long Story

This question reminded me of when Notch livestream'd his Ludum Dare entry a few months back, and I'd like to share in case you don't know what he did. I thought it was really interesting.

Basically, he used bitmaps to store his levels. Each pixel in the bitmap corresponded to one "tile" in the world (not really a tile in his case since it was a raycasted game but close enough). An example of one of his levels:

So if you use RGBA (8-bit per channel), you can use use each channel as a different layer, and up to 256 types of tiles for each of them. Would that be enough? Or for instance, one of the channels could hold the rotation for the tile like you mentioned. Besides, creating a level editor to work with this format should be pretty trivial too.

And the best of all, you don't even need any custom content processor since you could just load it into XNA like any other Texture2D and read the pixels back in a loop.

IIRC he used a pure red dot on the map to signal an enemy, and depending on the value of the alpha channel for that pixel it would determine the type of the enemy (e.g. an alpha value of 255 might be a bat while 254 would be a zombie or something else).

Another idea would be to subdivide your game objects into those that are fixed in a grid, and those that can move "finely" between tiles. Keep the fixed tiles in the bitmap, and the dynamic objects in a list.

There might even be a way to multiplex even more information into those 4 channels. If someone has any idea on this, let me know. :)

Answer 4

You could probably get away with almost anything. Unfortunately modern computers are so fast that this presumably relatively small amount of data wouldn't really make a noticeable time difference, even if it is stored in a bloated and badly constructed data format that craves a huge amount of processing to be read.

If you want to do the "right" thing you make a binary format like Drackir suggested, but if you make another choice for some silly reason it probably won't come back and bite you (at least not performance wise).

Answer 5

See this question: 'Binary XML' for game data? I would also opt for JSON or YAML or even XML, but that has quite much overhead. As for SQLite, I would never use that for storing levels. A relational database is handy if you expect to store a lot of data that is related (eg has relational links/foreign keys) and if you expect to ask a large amount of different queries, storing tilemaps doesn't seem to do these kinds of things and would add needless complexity.

Answer 6

The fundamental problem with this question is that it conflates two concepts that have nothing to do with one another:

1. File storage paradigm
2. In-memory representation of the data

You can store your files as plain text in some arbitrary format, JSON, Lua script, XML, an arbitrary binary format, etc. And none of that will require that your in-memory representation of that data take on any particular form.

It is the job of your level loading code to convert the file storage paradigm into your in-memory representation. For example, you say, "I see less redundancy of data using a database to store the tile data." If you want less redundancy, that's something your level loading code should look to. That's something your in-memory representation should be able to handle.

It is not something your file format needs to be concerned with. And here's why: those files have to come from somewhere.

Either you are going to be writing these by hand, or you are going to be using some kind of tool that creates and edits level data. If you're hand-writing them, then the most important thing you need is a format that is easy to read and modify. Data redundancy is not something your format even needs to consider, because you will be spending most of your time editing the files. Do you want to actually have to manually use whatever mechanisms you come up with to provide data redundancy? Wouldn't it be a better use of your time to just have your level loader handle it?

If you have a tool that creates them, then the actual format only matters (at best) for readability's sake. You can put anything in these files. If you want to omit redundant data in the file, just design a format that can do so, and make your tool use that ability correctly. Your tilemap format can include RLE (run-length encoding) compression, duplication compression, what ever compression techniques you want, because it's your tilemap format.

Problem solved.

Relational Databases (RDB) exist to solve the problem of performing complex searches over large datasets that contain many fields of data. The only kind of search you ever do in a tile map is "get tile at position X, Y". Any array can handle that. Using a relational database to store and maintain tilemap data would be extreme overkill, and not really worth anything.

Even if you build some compression into your in-memory representation, you'll still be able to beat RDBs easily in terms of performance and memory footprint. Yes, you will have to actually implement that compression. But if the in-memory data size is such a concern that you would consider an RDB, then you probably want to actually implement specific kinds of compression. You'll be faster than an RDB and lower in memory at the same time.

Answer 7

• XML: really simple to use, but overhead becomes annoying when structure gets deep.
• SQLite: more convenient for larger structures.

For really simple data, I'd probably just go the XML route, if you're already familiar with XML loading and parsing.