Chris Zetter

Generating random maps

After learning about the BSicons that Wikipedia uses to build route maps for transport systems, I wanted to see if I could use BSicons in randomly generated maps.

A diagram of the circular line 4 that shows the route of the metro alongside station names and connecting rail services
A route map of Line 4 of the Shanghai Metro that has been built with BSicons.

Automatic matching

I wanted to include as many different BSicons as possible in my generated maps. I made a copy of all the BSicons from Wikipedia and created a script to analyse them. By examining the pixels in the icon the script would categorize each edge. I used this later to decide if two icons could ‘fit’ together. The strategy for map generation was to:

  1. Place a random icon in the centre of the grid
  2. For each empty tile in a spiral from the centre, find a tile where the edges of the tile matched with the edges of all adjacent placed tiles

This was a good start and made some interesting maps. However, the way I was determining if icons could fit together wasn’t very reliable. It meant that many icons were never be placed because they had no matches. While icons with curves wouldn’t visually match to the icons they were placed next to.

A partially filled grid of icons showing a road and some rail lines
An early random map I generated. The [?] icons show where my code was unable to find a icon that fitted in the gap.
A filled grid of icons showing train lines going under and over each other in a diagonal lattice.
This is my favourite image my code produced. It uses only a few tiles to create a complex maze-like pattern that reminded me of 10 PRINT.

Less is more

By reducing the number of BSicons I was working with, it became feasible for me to manually categorise what tiles could fit together. I changed to using the wavefunction collapse algorithm to place the tiles. The wavefunction collapse algorithm prioritizes placing tiles in the spaces with the greatest restriction on them. This reduces situations where the algorithm can’t place anything and gets stuck.

Icons placed in a grid showing two overlapping train lines
An early map I generated with this method. The algorithm has no understanding of what the icons themselves mean so it can produce maps that are unlikely to exist such as a train line with no stations.
Icons placed in a grid showing two overlapping train lines with tunnels and roads.
I slowly introduced more kinds of icons into my generated maps.
Icons placed in a grid showing rail lines and roads that go past the edge of the image
I changed the generator to make tiled maps that could be repeated. With this extra restriction, the generation doesn't always work. If no more tiles can be placed before the grid is filled it starts again.

I really like the interconnected and overlapping routes the generator can make. You can use it to generate your own maps.

Read more by me, follow me on twitter or subscribe.