I’ve been plugging away at procedural level generation in Gunmetal Arcadia this week, slowly getting more interesting results on the screen. Last week, I started by copying and pasting whole screens’ worth of tiles around, following a hardcoded layout in which individual rooms that met the conditions could be selected and swapped in. I then reduced the scale of the prefabs to a quarter of the screen and assembled them into larger scrolling regions.

This week, I’ve been working on generating a layout for the internal structure of each scrolling region and for the structure of the level as a whole. I’ve decoupled these tasks such that I can tinker with each independent of the other. Today I’ll be looking at the internals of each room, and I’ll cover level structure in Wednesday’s video.

When thinking about how to construct a room from quarter-scale prefabs, I started with a few assumptions. I wanted to find a solution that would facilitate prefabs larger than a quarter of a room (to allow for distinct, recognizable set pieces and landmarks) and could handle these without needing to know in advance whether they would exist or what size they might be. The solution I’ve developed accounts for this and should also give me some room to grow and adapt it as my needs shift throughout this project.

Cards representing prefabs and a board representing the level layout we want to construct

I like to think of this solution as laying cards on a board. Given a number of types of cards (prefabs) of various sizes (and theoretically different shapes), each marked with open or closed paths to adjacent cells, we want to pick cards at random that adhere to some pre-determined path that runs throughout the board (scrolling region). For the purposes of this algorithm, I assume I have an infinite number of each type of card, but it was be easy to limit these as well, e.g., to prevent large setpieces from being seen more than once per level.

A board of a predetermined size with no layout information

The first step in this process is to determine the path through the board. This must exist before we can start picking cards that align with it. I create this path by choosing a cell on the board at random and then proceeding to perform a random walk to unvisited adjacent cells, carving a path as I go. If no adjacent cell is available, I step back until one is and branch in that direction. I repeat this process until the entire board is connected. This creates a connected graph with no loops, which could also be represented as a tree, with any cell on the board arbitrarily chosen as the root.

The board after doing a random walk to create non-looping paths

At the scale I’m working at, these paths tend to be fairly non-descript, but this could conceivably scale up to larger boards and more intricate paths. In the future, I’ll likely also look into introducing loops, tagging paths as one-way (especially for vertical drops), and anything else that could facilitate more interesting gameplay.

Once the path exists, the next step is to pick cards that fit it. (To reiterate, “cards” is a synonym for “prefabs” in this context.) I don’t want to give preference to any particular cards, large or small; I want each card to have an equal chance of being selected.

For each cell on the board, I create a list of every card that could possibly fit that cell, given its paths to adjacent cells. For cards that are larger than a single cell, each part of the card must match the board cell it would overlay, else the card as a whole is rejected. At this point, I can verify that at least one solution exists, by virtue of the fact that every cell has at least one corresponding card.

A potential match for a card

Once I’ve compiled the lists of applicable cards for each cell, I begin playing cards on the board at random. I select a random cell on the board, choose a random card from its list of options, and place it. (If that card is larger than one cell, I remove any cells that it overlaps from further solving.) I continue this process until cards have been placed over every cell on the board. The room is then fully constructed.

A potential match for a larger card spanning multiple cells

Each prefab may also have entities placed within it, and these are concatenated and assigned correct positions within the room as part of the card-laying process. At this point, the fully assembled room can be treated exactly as if it had been built by hand in my editor.

Thanks to the support of my generous Patreon contributors, I’ve begun a regular development livestream. You can find the archives of last week’s stream below.

Since that stream, I’ve wrapped up the work on CRT presets, and the feature is mostly ready to ship. Some of the code could still use some cleaning up, but I’m pretty happy with the implementation otherwise.

I’ve been debating voluntarily increasing the frequency of these streams (and updating the Patreon incentive tiers accordingly) simply because one stream a month is too infrequent to really make a part of my normal schedule. It’s going to feel like an oddity every time; I’m not really going to be able to get comfortable with the format at that pace. (The flip side of that is that I’ll risk running out of good, discrete, streamable tasks too quickly, but that’s something I’ll have to deal with in any case.)

As a reminder, I will be making the rounds at a number of events this summer and beyond:

Let’s Play Gaming Expo
June 18-19, 2016
Plano Centre
Plano, TX

RTX 2016
July 1-3, 2016
Austin Convention Center
Austin, TX

Retropalooza IV
October 1-2, 2016
Arlington Convention Center
Arlington, TX

I’ve applied for space with the Indie Megabooth at PAX Prime/West, but those slots are limited and in high demand, and it’s too early to say whether I’ll be there. I’ll also be looking at demoing one or both of the Gunmetals Arcadia at PAX South 2017 early next year, so stay tuned on that one.