Walls in Tile Maps with Tile Strings

I'm working on a small game with a procedural map. As the whole game is set in a labyrinth-like building I've decided to use tile maps. The map generation algorithm produces a 2D matrix with 0s and 1s. A 1 indicates that the tile is walkable while a 0 represents an impassable field.

In a simple 2D setting this could be represented by using a floor sprite for each 1 and a wall sprite for each 0. However, this isn't very appealing. Instead the visual representation of a tile should be depended on its neighborhood.

Each tile can have one of 256 (2^8) configurations. These configurations can be reduced to 41 by considering rotations as one configuration. As multiple configurations need the same wall layout we will only need 15 tiles to render the tile map.

My first approach to implement the rendering was to use shit ton of if statements. The approach tested for all configurations to find the needed piece and rotation. A few shortcuts prevented that I had to test for all 256 configurations but it was still too much. After implementing this approach for 4 tile pieces I gave up.

My next idea was to represent the knowledge of which piece and rotation is required for each configuration in a lookup map. This approach is similar to marching cubes where you need a lookup map to know how to construct the faces of a cube. After writing down 30 entries of the lookup map I came up with the following idea (which I will call "Tile Strings").

Instead of checking for all 256 configurations, we only look at a 2x2 section of the neighborhood.

We start with the 2x2 patch in the upper left corner and determine the character it represents. This character represents whether the left side of the tile needs a wall, a corner or needs to be empty.

The 2x2 patch is than rotated around the center to determine the characters for the other sides. After the full rotation we have a 4 character string representing the configuration of the center tile, for example "WCCE". This is our tile string.

Example code for a single 2x2 check (written in GDScript):

if cell(p + Vector3(-1, 0, 0)):
    if cell(p + Vector3(0, 0, -1)) and not cell(p + Vector3(-1, 0, -1)):
        tile_str += "C"
    else:
        tile_str += "E"
else:
    tile_str += "W"

With the calculated tile string we can start to search for a suitable sprite or model in a library (our library should consist of 15 assets named by their tile string). We still have to manipulate the tile string and determine the rotation, as we most likely only want to create 15 assets.

As the tile string represents a unique configuration we only have to rotate it (at most 3 times) to find a fitting configuration in our library. We start by checking if the tile string already fits an element in our library. If this is the case we can just use it! If no element fits we rotate by 90 degrees, by moving the last character of the string to the front, "WCCE" is transformed to "EWCC". The number of rotations are counted. We do this at most 3 times. If you didn't find a fitting element after 3 rotations your library is not yet complete. Once the rotated element fits, it can be inserted into our scene with the determined rotation.

Example code for finding an element in the library (written in GDScript):

var rotation = 0
for i in range(4):
    if tile_str in library:
        add_part(position, rotation, tile_str)
        break
    rotation += 90
    cfg_str = cfg_str[3] + cfg_str[0] + cfg_str[1] + cfg_str[2]

Your library does not have to be limited to 15 elements. Maybe corridors running north-south should have a different design than east-west corridors. Just add a new element with the corresponding tile string to your library.

This approach only requires a few lines of code. There is probably a lot of potential for improvement but it works perfectly for my use case. The process of developing this once again showed me that it is worthwhile to take a step back and think about your problem. The first two approaches showed me properties of the problem and implementing them (partially) deepened my knowledge, which ultimately led to the "Tile String" algorithm.