Walls in Tile Maps with Tile Strings

Example of a tile map.

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.

Configurations of a tile with its neighbors.

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”).

Calculating the Tile String.

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.

Rending of room using the tile string algorithm.

My result using the tile string algorithm with 14 elements

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.

Veganer Flammkuchen

Veganer Flammkuchen.

Veganer Flammkuchen.

Zutatenliste

Rezept für ca. zwei Flammkuchen

Teig

  • 175 g 550 Mehl
  • 100 ml lauwarmes Wasser
  • Prise Salz
  • 5 g Hefe

Belag

  • Vegane Crème fraîche (z.B. Creme VEGA)
  • Rauchsalz
  • Knoblauchpulver
  • Pfeffer
  • 1 rote Zwiebel
  • 6 Champignons

Zubereitung

  • Teigzutaten zu einem glatten Teig kneten
  • Teig im Kühlschrank mindestens 24 Stunden gehen lassen. Alle 24 Stunden Teig durch kurzes kneten entlüften.
  • 30-60 Minuten vor dem backen zwei Teigbälle a 100-150 g formen und warm gehen lassen und Backofen auf 300°C vorheizen
  • Teig sanft zu möglichste dünnen Fladen formen
  • Fladen mit Crème fraîche bestreichen und mit nach belieben würzen
  • Zwiebeln in dünne Ringe schneiden und Champignons würfeln und Fladen belegen
  • ca 5 Minuten bei 300°C backen

Django Migrate MySQL to Postgres

I’ve recently migrated my tools project from an old the server to a new one. In the process I’ve decided to change the used database from MySQL to PostgreSQL. To do so I’ve used this amazing guide from calazan.com.

As the guide was written for django 1.6 some minor changes were necessary when working with newer versions (I’ve used django 3.1.4).

Setup for migration

Steps 1 + 2 work as described in the guide above. A new database is created and added to the settings.py.

DATABASES = {
    'default': {
        'ENGINE': 'django.db.backends.mysql',
        'NAME': 'dbname',
        'USER': 'dbuser',
        'PASSWORD': 'dbpass',
        'HOST': 'mysql.example.com',
        'PORT': '',
    },
    'postgresql': {
        'ENGINE': 'django.db.backends.postgresql_psycopg2',
        'NAME': 'dbname',
        'USER': 'dbuser',
        'PASSWORD': 'dbpass',
        'HOST': 'postgresql.example.com',
        'PORT': '',
    }
}

Apply migrations to new database

python manage.py migrate --database=postgresql

syncdb is no longer available in newer django versions and was replaced by migrate. The flag --no-initial-data is no longer available and I didn’t find a substitution.

Clean Up the new database

Some migrations will create initial data in your database. This will probably create conflicts, as we are migrating existing data into this database. I did this step by hand, but the command python manage.py sqlflush --database=postgresql will give you the SQL query to do it automatically.

Copy data to new database

In order to copy the data we use dumpdata and loaddata.

When dumping the data it is important to use the flag --natural-foreign, otherwise the import process cannot import data with foreign keys.

python manage.py dumpdata --all --natural-foreign > dump.json

The dumped data can be loaded into the new database. This process can take a long time. Ensure that your machine executing this command is as close as possible to the database, ideally running on the same machine. First, I started this command on my local machine. After 30 minutes I decided that it took too long and uploaded the dump to the server running the database, which finished the command in about a minute. My dump file was only 16 MB big.

python manage.py loaddata dump.json --database=postgresql

Adjust config

Now all data is available in the new database. Just adjust the settings to use the postgresql as the default database.