How Townscaper Works: A Story Four Games in the Making

'AI and Games' is a crowdfunded YouTube series that explores research and applications of artificial intelligence in video games. You can support this work by visiting my Patreon page.

Townscaper is a small game, with big ambitions. A city builder in which players can simply add or remove a block from the game world. With this limited toolset, you can craft everything from idyllic seaside towns to a horizon spanning metropolis. A procedural generation engine running under the hood caters to the unique topographies players establish and refines the world with each new action taken. But how is it capable of expanding, and rebuilding the world with such consistency? While also introducing fun and novel ideas for players to discover on their own.

For this case study we’re going to explain the different level generation systems that power Townscaper and the AI principles they derive from. Plus I sat down with the game’s creator Oskar Stalberg to gain a stronger understanding of how it all works and his aspirations in designing the game. In order to truly understand Townscaper, we’ll be taking a journey through Stalberg’s career and his previous work. Because the secrets to the game’s success are hiding in plain sight, in everything else that he has built to date.

Townscaper Explained

First released on PC and Mac in June of 2020, Townscaper is, by Stalberg’s own admission, more of a toy than a game. It does not have any explicitly defined objectives and instead, you are left to craft towns based on your own design principles. Players have a very limited number of interactions: you can decide where a block is added or removed, and you can customise the colour of the blocks you place. That’s it. Everything else that you see, is achieved courtesy of the game’s procedural generation system. This creates what we would typically consider to be a mixed-initiative AI system: meaning that the player gives input to where the game needs to expand the structure, and the system assesses the current shape, identifies what prebuilt chunks of architecture are valid for that space and then injects them into the game world. Despite this lack of direct control, the system is highly flexible and can handle a myriad of different scenarios that players can come up with, resulting in a variety of fun, interesting and aesthetically varied settlements.

And it’s this simplicity in gameplay combined with the game’s bright, abstract yet detailed aesthetic, that has led to Townscaper transcending boundaries: developing a huge following across social media that has captured the imaginations of many who don’t typically play videogames. Plus if you’re a game developer on Twitter, you’re bound to have seen one of Stalberg’s development tweets on your timeline. Either for Townscaper, his previous game Bad North or his more recent projects.

The secret to Townscaper’s success is one that many aspiring (and current) game developers should reflect upon. The game is effectively the fourth entry in a series of works that capitalises on Stalberg’s interest and growing expertise in procedural generation and technical art, with each project building upon the previous one. And to successfully explain the tricks employed in Townscaper, we need to go back and visit each of them in turn.

So with this in mind, we start our journey in what is arguably an unexpected and unlikely place. The game that inspired Townscaper and everything that preceded it: Tom Clancy’s The Division.

Brick Block

Stalberg graduated in 2012 from The Game Assembly, a school specialising in game development based in Malmo: arguably the biggest hub of game development studios in Sweden. Not long after, he landed a job at Ubisoft’s Massive Entertainment, creators of Tom Clancy’s The Division, working as a Technical Artist. The Division takes place in downtown Manhattan, an area comprised largely of tall skyscrapers and ominous-looking buildings. While Stalberg wasn’t involved in this part of the production – his work was actually on the very cool looking holographic map – he watched his colleague’s work on the city building team with great interest.

This led to a small but significant question that would drive the creation of Townscaper: how to build urban structures that respect the local topography. The answer was a small prototype called Brick Block: in which players can place blocks within a fixed 5x5x7 grid that allow for small, yet fun looking urban environments to be constructed. As you can see, Brick Block glues together pieces of apartment buildings together in ways that make sense.

To make this work, Stahlberg built a tool that is markedly similar to what is commonly known as Marching Cubes: an algorithm built for the purposes of generating a polygonal mesh within a specified three-dimensional volume. By discretising a grid space into a series of points, you can create a polygonal mesh using select points within that 3D space. Technical complexities aside, what this means is that by selecting several points in space you can draw a 3D shape. In Brick Block the game only allows you to build a new unit provided the cell selected connects to polygons already constructed in neighbouring cells. This prevents rogue blocks from floating in space, but can still allow for structures that would make a civil engineer break out in a sweat. However, the key thing, is that gives players a lot of freedom to make interesting and fun structures.

The origins of Townscaper are clearly evident here, but it was shelved for the time being. While Stalberg struggled with how to take this idea and turn it into a fully-fledged game, the big technical issue was that Brick Block structures quickly become repetitive. Hence in the demo you can play online, a conscious decision was made to keep the grid very small. Hence there was a new question to tackle: how could you approach the same idea on a larger grid while enabling more diversity in the generated output?

Bad North & Wave Function Collapse

Stalberg left Massive Entertainment in 2016, not long before the release of Tom Clancy’s The Division and after a stint at the Malmo studio of Monument Valley developer UsTwo Games, transitioned into indie development. Working alongside colleagues Richard Meredith and Martin Kvale, this led to the creation of the micro RTS combat game Bad North, published by Raw Fury and released in 2018.

In Bad North players are presented with the challenge of defending small islands with village structures that can be attacked by Viking invaders. To enable the roguelike elements of the game, the game procedurally generates each island prior to its appearing on the game world map. But unlike Brick Block, which needs only create something aesthetically pleasing, Bad North had the added challenge of satisfying a myriad of gameplay functions. Each island needs to provide sufficient real estate for the movement of armies, large coastlines that will enable all of the invading forces in that level to beach successfully. And critically, the ability for player and enemy AI characters to be able to move from one area of the island to another successfully.

This time around, the resulting solution needed to provide a lot of variety, while ensuring logical consistency. And it’s with this in mind, Stalberg drew inspiration from Wave Function Collapse – an algorithm that can be used to decide what objects can be placed next to each other based on the rules provided to it. Wave Function Collapse is what in AI terms we call a constraint solver. Constraints Solvers are a class of AI algorithms designed to solve problems in which variables can be assigned a myriad of possible values, but there are rules on what values can be assigned, and those rules can have a huge chain reaction on the final solution. A simple, yet very effective example of these constraint satisfaction problems, is a game of Sudoku. In Sudoku, each cell can only have one value between 1 and 9, and the rules of the game add constraints that tell us that no number can appear twice in the same row, the same column and in the defined 9×9 subsquares. The goal of an AI Sudoku player is then to ensure that every new digit added to the grid satisfies those constraints, but also doesn’t prevent other cells from having any valid numbers left to assign themselves.

So what’s this got to do with Bad North? The algorithm Wave Function Collapse, developed by Maxim Gumin in 2016, is designed to create large 2D graphics using the same principle. The idea is that upon reading a smaller image, it learns what are the valid rules for generating new images of its own, of any size. The original image highlights adjacency constraints, meaning that for any pixel in the graphic, we can quickly determine what valid pixels can be placed next to it. Stalberg was inspired by this idea and sought to build a 3D version of this. It’s worth noting that the implementation in Bad North is bespoke, and it isn’t the first time Wave Function Collapse has been adapted for 3D. In fact, Wave Function Collapse is markedly similar to an existing algorithm called Model Synthesis, developed by Paul Merrell in 2007, which can achieve the same thing for both 2D and 3D shapes.

In order for this to work in Bad North, adjacency rules need to be established by assessing each of the individual chunks of 3D terrain known as tiles. There are over 300 tiles in Bad North – be it rock faces, stairwells, beaches, cliff edges and more – which are first built in the 3D modelling tool Maya. When imported into the Unity game engine, the edges are scanned to establish where other tiles could conceivably connect to them. So for example, a corner tile for the coastline could be connected to extend the coastline, back away from the coast into the island itself, or the coast doesn’t extend at all and simply becomes water. By completing this process, it enables for the Wave Function Collapse to know what tiles are available in any particular cell of the game world grid, based on whether adjacent cells were also populated on the X, Y and Z-axis. But of course, in order for it to work, there are some additional rules such that the maps make sense and they help satisfy the gameplay.

Upon generating, the game always assumes water at the bottom and sky at the top, after which, it fills out the grid by seeding all the possible tiles that could fit in each cell. Think of this as the possibility space: all potential islands that the system could generate. This already imposes some constraints given the pre-determined size of the island, given beaches, cliff edges or other terminal edges imposing on the limits of the terrain. Some hardcoded constraints are also added to make sure the islands look more realistic, rather than something that is clearly procedural. This often means two tiles that are the same, or some tiles that reflect or mirror one another can’t be placed next to each other. Plus there may be level-specific constraints based on specific tilesets which can also influence the possibility space. What can speed this up is there are some tiles that are designed to cover two cells in the grid, which can help reduce the grid-like outputs given they are manually crafted and help reinforce a key aesthetic. But ultimately, the larger the map, the longer this all takes to execute.

Once the first tile is placed in a cell, the possibility space begins to change. Typically the generation starts with houses, given all levels need houses for players to defend. Once a single house is added, the possibility space will begin to shrink. This is because the constraints of the wave function collapse algorithm are rolling out from those placed tiles. If a building has been placed high on the island, then that imposes a need for land to surround it, which in turn will impose further constraints on the need for connecting terrain that will eventually link down to the beach.

The real challenge that Bad North faces compared to Brick Block, and even Townscaper, is that the levels need to satisfy gameplay needs. The generator doesn’t know it’s creating a level for a strategy game, it’s just trying to make a nice wee island. Hence there are two key aspects to Bad North’s Wave Function Collapse implementation that don’t exist in the other games. First of all, there is a need for the enemy soldiers to be able to navigate from the beach to the houses in order to attack them. And indeed for your forces to be able to go mess them up. Typically, we require a navigation mesh for NPCs to know how to navigate from one point to another. They’re fairly common in game engines such as Unity and Unreal. But you can’t rely on a navigation mesh for an island that isn’t technically built yet. So how do you ensure there’s always a path from the beach to the houses?

Secondly, there is a need to run a validation check when islands are generated. This is to ensure that the level is going to satisfy all the requirements and actually be playable. While there are rules on tile placement that must be followed, which we would typically call a ‘hard constraint’, there are also ‘soft constraints’, that should be followed but have some flexibility. If an island isn’t going to be able to satisfy constraints, then the generator will restart. To do this, the generator saves the state of the island once the initial constraints and possibility space are established and can reset back to that point when necessary.

Once the generation is complete, the islands are merged into one mesh to minimise draw calls and graphical overheads, and its good to go. The process of bringing this together, from initial concept through to completion, took around 2 years to complete. But the results speak for themselves, with the system capable of building myriad challenging gameplay environments while solving the problem that Brick Block faced, in ensuring greater diversity and variety in the generated output.

Irregular Grids

Now there’s one last piece of the puzzle to consider: both Brick Block and Bad North operate on square grids, but Townscaper does not. In fact, the grids are irregular and look a lot less rigid than in previous games. This was a conscious decision on Stalberg’s part, in order to create more natural and realistic geometry that respects the weird and winding ways in which real cities are built.

The inspiration for this came from Oskar briefly working as a developer on Night Call: a noir adventure game developed by MonkeyMoon and BlackMuffin and first released on PC in 2019. In Night Call players assume the role of Houssine, a taxi driver in Paris who solves a murder mystery through interactions with passengers. The map of Night Call is derived from publically available data of the city, meaning you drive through the city in a realistic fashion. But all of the conversations in the cab, rely on a fully three-dimensional representation of the city being rendered in the game. To address this, Stalberg developed a tool to deform grids such that they better fit the shapes of city blocks and then generate simple building structures within them. While not perfect, it more than services the needs of the game, but it left an open question, of how to take this idea and apply it to a fully procedural environment.

So how do you go about generating aperiodic infinite deterministic irregular relaxed quadrilateral grids? I mean it was a fair question and not one that many had answers to. The direction taken was inspired by Amit Patel of Red Blob Games and his explanations of Hexagonal Grids (that’s another link in the description for you). Using this approach, Stalberg came up with the idea of taking a fixed hexagonal grid, breaking it up into quads, then breaking it up into quads again and then moving some of the points within the grid. And so with this final piece of the puzzle, we can finally address the title of the episode.

How Townscaper Works

The secret of how Townscaper works is that it’s the culmination of everything that preceded it:

But combining all of these ideas isn’t as straightforward as I make it sound, taking around 3 months to go from an early prototype to a working implementation. The real contribution that Townscaper brings is how the placement of building elements works. Given that the game now runs on this more triangle-based grid – allowing for a more European aesthetic to town construction – placing cubes and cuboids into that space is no longer straightforward. Hence the Marching Cubes algorithm allows for tiles to be placed in ways that best fit the shape of the grid cells given it focuses on how to place the corners of buildings. This in turn had an influence on how the tiles are built, with them no longer being complete chunks of building, but rather corner segments that can be more easily put together to create shapes that fit within the cells.

The Wave Function Collapses operates similar to before, but now it’s optimised for working in real-time. In Bad North, the algorithm would only generate islands prior to the player getting to interact with them. To pull this off, the decoration of a tile is separate from when it is generated. What this means is that the hard part of the process is done first: when a new piece is added, the Wave Function Collapse identifies the possible modules for that cell, and then afterwards it will decorate it. The placement of a new block forces the rest of the existing structure to re-evaluate, to make sure constraints are satisfied and also for new opportunities to emerge given a block has been added where once there wasn’t one, but also when a block is removed, new constraints have been placed on everything around it and they have to respect that change.

Once the possibility space is identified, it then works on drawing in the selected pieces. This is why you can sometimes see a block appear, and then the detail fills in a short while afterwards. In fact, as structures become larger and more complex, you will notice the delay between block placement and decoration increases. This is ultimately a performance overhead of the algorithm: given the larger a structure becomes, one change ripples through the entire connected area as the Wave Function Collapse has to reassert that all of the constraints are being respected, and an appropriate tile has been selected.

Speaking of decoration, there are a lot of additional quirks in Townscaper that operate on different levels. You’ll notice windows, chimneys, bushes and benches appear around a recently placed block. But also, you’ll see more bespoke urban architecture appear depending on how the level is built, resulting in everything from luscious gardens to stairwells, statues and even weird floating buildings.

These are all part of Townscaper’s Wave Function Collapse: the decorations on individual tiles are smaller-scale patterns designed to reflect the topology: looking at what space is available around the placed block and then placing props against the surfaces. This is very useful for the likes of windows, given that Stalberg uses a stencil buffer to cut them out of the mesh after it is placed, rather than having the windows in the tiles themselves, given there would be many edge cases that crop up leading to windows being cut in half or stuck on corners.

Meanwhile, the more interesting and unique level segments that can appear, are known as recipes. These are also hidden deep in the Wave Function Collapse and are assigned a much higher priority than other patterns. They are intended to be discovered by curious players and reward them with something fun and distinct. But, their priority in the algorithm ensures they’re predictable enough so that players can then reproduce them when they wish.

And while this is the bulk of the actual generation process, there are lots of smaller considerations made to help make each town look more alive, but also ensure it continues to be readable at a distance. There are really simple AI birds and butterflies, which simply anchor to a game object in proximity, and then occasionally fly around it, and react to local geometry. Plus optimisations to the rendering to minimise aliasing and ensure outlines of shapes and structures continue to look crisp yet detailed at any angle or distance.

Given the structure of the algorithm, it is feasible that Townscaper could be re-skinned, by creating different tiles that reflect different architectural moods or themes. However, to do so would not only mean making somewhere in the region of 500 tiles, but it would detract somewhat from the original artistic vision.

Having now been released on Steam, Switch, Xbox and mobile, Townscaper has achieved a massive following and what was once a side project Stalberg could indulge in for a time thanks to the success of Bad North, has proven to be even more successful. With a community of players who share their works online, and even create 3D printed versions of them thanks to a feature in the Steam version that lets you export your towns to 3D model files. And while Stalberg was convinced it would develop a following thanks to that initial enthusiasm on Twitter, it has certainly caught him by surprise.

Conclusion

At the time of writing, Oskar is working on another project, and if you’re following him on Twitter, you’ll no doubt have seen some recent progress. As discussed in a talk at the 2021 Sweden Game Conference, Stalberg went back to the grid idea once again. Seeking to balance between using both triangular and square tiles and tackling ideas that could not be achieved in Townscaper or Bad North, with cliffs and rivers being generated once again within a fixed pre-defined region. It’s all got a while to go, but if you’re following Stalberg on Twitter – you’ll catch all the updates as they happen.

Thanks for reading this article on Townscaper. It’s a game that has dominated a lot of gamedev Twitter feeds for the past couple of years, and with good reason. While it’s now available on pretty much any device worth having, you can also play a limited demo in your web browser. Plus if you’re interested in creating your own procedural algorithms, links to some supporting materials on Marching Cubes and Wave Function Collapse are included below, including a fantastic tutorial by Joseph Parker over on PROCJAM.

A special thank you to Townscaper creator Oskar Stalberg for taking the time to sit down with me and answering the many questions I had. Especially given that I asked some very specific questions about his career to date and the inner workings of the algorithms that have been constructed. I hope this has done his work justice!

Links & References