Z-Ordering for Isometric Tile Maps

For a 2D, top-down view, the natural ordering of a tile map is a linear array, organized as a 2D matrix. The coordinates of any given tile can be calculated by `y * width + x` (row-major) or `x * height + y` (column-major). Conversely, you can calculate the x and y from the index of a given tile. [1] This is not the only way to represent such a map — for example, if you have an extremely large map it may be worthwhile to ‘swizzle’ the array, storing blocks of tiles sequentially rather than entire rows. [2]

The advantage of the top-down view is that order of rendering is less important. Tiles do not overlap, so the order they are rendered to the screen does not affect the final image. Therefore, rearranging the tile array has no visible effect on rendering. The matrix view of the map is easy to reason about, so this is convenient.

An isometric view, on the other hand, is a different matter.

Isometric tiles, by definition, do not fit tightly into a rectangular pixel region. They are skewed, and rely on overlap to render a seamless map. For this to work properly, they must be rendered back-to-front. [3] The matrix layout only works, in this case, when the origin is at the top of the grid (i.e., the view is facing (0, 0)). The obvious fix is to change the axis you iterate along with the camera rotation. This is trickier to write, and on large maps (large enough not to fit in cache) will cache miss regularly when you go “against the grain” of the array. [4]

The easiest solution is to sort the tile array. Since this destroys our implicit coordinate system, tiles must know their spatial position rather than inferring it from the array.

Let’s call the rotation facing toward the origin “North”. (0, 0) is the first tile rendered (as it is behind all other tiles.) Next, the two tiles directly in front, (0, 1) and (1, 0) are rendered. Then the three in front of those. The order within any given diagonal is irrelevant, only front-to-back matters.

We end up with the following ordering:

0  1  2  3  4
1  2  3  4  5
2  3  4  5  6
3  4  5  6  7
4  5  6  7  8

You’ll note that the diagonal rows are the sum of each tile’s x and y coordinates. In fact, that’s how we sort them:

std::sort(&tiles[0], &tiles[width * height], 
    [](const Tile& a, const Tile& b) {
        return a.x + a.y < b.x + b.y;
});

Okay, so that works for one rotation, how about the others. If we rotate to face “West” (facing (0, height)), we simply flip the sign on the y coordinate: [5]

 0  1  2  3  4
-1  0  1  2  3
-2 -1  0  1  2
-3 -2 -3  0  1
-4 -3 -2 -1  0

The ordering for “East” flips the sign of the x coordinate:

 0 -1 -2 -3 -4
 1  0 -1 -2 -3
 2  1  0 -1 -2
 3  2  3  0 -1
 4  3  2  1  0

Finally, and perhaps most obviously, facing “South” flips both coordinates:

 0 -1 -2 -3 -4
-1 -2 -3 -4 -5
-2 -3 -4 -5 -6
-3 -4 -5 -6 -7
-4 -5 -6 -7 -8
void SortTiles(Tile * tiles, int width, int height, Direction dir) {
    Vector2 orient;

    // The Direction enum is here to make the orientation more explicit.
    // A better solution is to have the orient vector passed in by the 
    // caller (or a member variable in the class wrapping the tile map).
    switch (dir) {
    case NORTH:
        orient.x = 1;
        orient.y = 1;
        break;
    case EAST:
        orient.x = -1;
        orient.y = 1;
        break;
    case WEST:
        orient.x = 1;
        orient.y = -1;
        break;
    case SOUTH:
        orient.x = -1;
        orient.y = -1;
        break;
    }

    std::sort(&tiles[0], &tiles[width * height], 
        [=](const Tile& a, const Tile& b) {
            const int a_dist = a.x * orient.x + a.y * orient.y;
            const int b_dist = b.x * orient.x + b.y * orient.y;
            return a_dist < b_dist;
    });
}

Since this ordering depends only on the camera direction, you need only sort the tile data when the camera rotates. This is relatively rare — almost certainly not every frame — and as such the sort is *probably* a net win for performance. (As always, profiling is the only way to know for sure.)

There is one fairly significant problem with this approach that I’ve glossed over so far. By sorting the array in a non-deterministic fashion, we can no longer easily find the neighbors of a tile. [6] Even for a static, unchanging map, you may want to directly adjust a tile (e.g, showing the walkable distance of a character). The simple solution is to keep a separate array of pointers to the tiles, stored in matrix order. After each sort, iterate over the sorted array and update the pointer array:

void UpdateTilePointers(Tile * tiles, Tile ** tilePointers,
    int width, int height) {
        for (int i = 0; i < width * height; ++i) {
            Tile * t = &tiles[i];
            tilePointers[t.y * width + t.x] = t;
        }
    }
}

The problem with this approach is it introduces another level of indirection in accessing tiles by their coordinates. However, in practice most operations on a tile map are simply applied to the entire map. The most expensive of these is rendering, and it has strict ordering requirements. On the other hand, operations that require finding specific tiles (like showing walk distance or weapon range for a character) are relatively uncommon, and will usually only affect a small portion of tiles.

[1]
For row-major:
x = i % width
y = floor(i / width)
For column-major:
y = i % height
x = floor(i / height)

[2]
Swizzling offers better cache coherency when rendering only part of the map — otherwise wide gaps to either side of the columns / rows you access are loaded but ignored. (For this reason, it’s the format GPUs prefer for texture data.) However, in almost all cases the matrix approach is a better choice for a tile map due to its simplicity.

[3]
I’m ignoring another option here: use the GPU’s depth buffer. Even if you go this route, generating the z-coordinate for each tile is the same.

[4]
For perspective, the Intel Sandy Bridge architecture (as well as every subsequent architecture) has an L1 cache of 32KB (32,768 bytes). If each tile is represented by a 32-bit integer, a 100×100 tile map is 40,000 bytes. The L2 cache is 256KB, capable of holding up to a 256×256 map. If tiles contain any more data, this only gets worse. In and of itself this is not terrible, but swapping out cache only to reload the same data on the next row / column is not an efficient use of memory bandwidth.

[5]
Remember that these are *relative* orderings. The higher the value, the closer the tile is to the camera and the later it is rendered.

[6]
This can be fixed. Since we care about the order, rather than the index, we can modify one component of the coordinate to create a deterministic order:

0    1    2    3    4
1.1  2.1  3.1  4.1  5.1
2.2  3.2  4.2  5.2  6.2
3.3  4.3  5.3  6.3  7.3
...

Calculating the coordinate from the index in this case is left as an exercise for the reader.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s