Side Quest: Valkea Vuori

Back in May, I went to Amsterdam for the Unite Europe conference, and whilst in the city, visited the Stedlijk design museum. It’s a weird collection of modern art and design, but well worth a visit if you’re into that sort of stuff. It’s also partly housed in a gigantic bathtub!

Anyway, whilst there, I found a piece of art called Valkea Vuori by a lady called Rut Bryk (below). It had a really strong aesthetic that was vaguely reminiscent of old school isometric strategy games like Transport Tycoon.

As a side project, I’m now attempting to procedurally generate a tiled world/map in video game form, which I then have a number of ideas about using for creating a strategy game. By happy coincidence, I’ve started working on this around the same time as procjam – the annual game jam around procedural generation. Whilst not technically part of procjam, since I started this a week or two early, I still feel it’s worth sharing with the rest of the community interested in procedural generation in video games.

To that end, I’ve so far produced two different algorithms for attempting to recreate the grid / world of varying square tile sizes. The first looks aesthetically the most pleasing and closest to the art work:

This is generated using a reverse quad tree. Quad trees are a useful data structure used for efficiently storing and quickly retrieving an array of points over a geographical area. However, in my case, rather than starting with a series of points and then trying to create a quad tree to store them, I’ve instead started with a single quad, split it, then randomly selected a new quad (including the just-split quads) to split again.

I also set a minimum width/height below which a quad can’t be split any further. The algorithm then just keeps going until it has performed a set number of splits (which can be adjusted as a parameter, along with the overall dimensions of the grid/map/world).

However, this often leads to a few big quad plus large areas of tiny quad, since the further the algorithm is along its path, the more small quad there are in the list of possible quads (so small quads tend to be more likely to be split, creating even more small quads).

Also, it failed to give the interesting forms in the Valkea Vuori artwork where some larger squares were offset from each other and didn’t always line up.

So I decided to try the reverse approach. Starting with a big grid of minimum-sized squares and merging them together where possible: Pick a random square, pick a random direction (top-left, bottom-left, bottom-right, top-right). Then see if all the neighbours of the square in that direction were the right size and position to be merged.

This proved a big headache, as there are a lot of cases where merging is not possible. It also meant that the aesthetically pleasing balanced-mix of large and small squares was missing – Most of the time it’d be a lot of small and medium sized squares and very few larger ones.

I am though, inclined to stick with this latter algorithm and refine it. The algorithm eventually stops when it fails to find a suitable candidate for merging x times in a row (usually 50). I could simply brute-force search for any candidates it may have missed when picking randomly. More likely though, I plan to play about with adding extra parameters, such as a budget for the number and size of larger squares, to be created first, before randomly merging from the remaining tiny squares in-between the larger ones.

I also need to do the heights, though it should be relatively easy to create passable “hills” using Perlin noise and a few extra variables.

As for the game I plan to make with it, my thinking is at the moment, it’ll be a turn-based 4x-esque strategy game where you grow a little empire by claiming tiles around your home city. Much like how certain iterations of Civilisation series let you claim territory.

Then give players the option to split or merge tiles. Larger tiles may be more productive, but have a greater maintenance cost. Larger tiles also make army / unit movement quicker, since a unit’s maximum speed is measured in squares they can move per turn. That could be a good or a bad thing, depending on how you want to defend your territory or how easy you want to make it to get your troops to the front-line at the edge of your empire!