Storing maps for tile-based 2D game engine

Question

We have a (potentially large) side-scrolling 2D world with lots of repeated tiles (e.g. terrain, walls, water, etc.) For example, there are large "hills" which can be very high, but are rendered using the same small piece of "rock" texture.

I would like to optimize the storage and rendering of this world (it's better to draw one large quad and apply the same repeated texture to it than draw a lot of small adjacent quads separately).

What is a good way to do that? Currently I see a two potential solutions:

Allow the map designer to specify "chunks" (large rectangles of repeated tiles) manually
Allow the map designer to design the map on a tile-by-tile basis and then compute the chunks automatically (what is a good algorithm to do this?)

If you have worked on a similar game, would love to hear your particular solution.

Sorry about close vote, I take it back since the answers in that question weren't really conclusive. But you might want to take a look into it nevertheless: http://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas — tskuzzy, Jul 05 '12 at 17:56

score 0 · Answer 1 · answered Jul 05 '12 at 18:43

Since you won't draw rectangles anyway (but triangles), I suggest to choose the second option. Furthermore, never trust the user of your program.

The first task is to divide the map into polygons of the same texture. Because your terrain is based on a grid, this can be achieved very easily by a kind of flood fill in combination with a marker algorithm, which runs e.g. like this:

- n := 0 // will be the polygon numbers
- Iterate over each grid cell
    - If cell is marked, continue with next cell
    - mark cell with n
    - check adjacent cells for the same texture and mark them accordingly * 
    - n := n + 1

* This step can be performed in various ways: FloodFill. Furthermore, you should store an edge cell for each chunk. I.e. a cell that has at least one adjacent cell with a different texture. Let's call this the seed cell.

Then you have your grid marked with the polygon numbers and n is equal to the polygon count.

The next step is to extract the polygons. This is, where the seed cell will be of help. For each chunk, start at the seed cell and run along the edges of the chunk collecting all corner points. These corner points will make your polygon.

After that you have a set of polygons. The final step is to triangulate the polygon for rendering. This can be achieved e.g. with the Ear Cutting / Clipping Algorithm or others.

Ani · Answer 2 · 2012-07-05T19:36:22.253

If pixel shaders are available to you, another approach would be to provide a "tile-atlas" texture(s) that contains all possible tiles smushed together into a lightmap-style texture and also provide a much smaller "tilemap" texture (screenWidth / tileWidth X screenHeight / tileHeight) which contains a single component pointing to the "tile type" at that position in the tilemap.

You can then draw a single fullscreen, screen-aligned quad and the pixel shader would sample the "tile-atlas" using the current tile-type and put those pixel(s) on the screen. The current varying texture coordinates, along with knowledge of the width/height of the quad can be used to get the current pixel position inside the shader.

The "tilemap" texture can then be updated as required to change the current level.

Storing maps for tile-based 2D game engine

2 Answers2