All Alchementalogs
Table of Contents
- The First Shovelful
- Cellularing Some Automata
- The Space Between Spaces
- Forging Connections
- No Room Left Behind
- Again, This Time With Feeling
The First Shovelful
Alchementalist takes place in a world called Ember. There’s a lot of history to Ember, but one of the main periods of interest is during the reign of the Ember-mages. These guys were militant, exuberant miners (think Dwarves crossed with a magical Roman Empire and you’re getting there) and heavily addicted to a magical mineral called Ember-source. They used Ember-source for all sorts of rituals and spells and to maintain a steady supply they had to mine. And mine deep.
The Alchementalist lives much, much later in the history of the world, but there are still all sorts of relics and remnants from the period of the Ember-mages. In fact, it’s inside one of these remnants that the Alchementalist finds themself. You see the “dungeon” that the Alchementalist is exploring is, in fact, an ancient mining operation originally dug by the Ember-mages.
So the question today is: How do we procedurally generate a mine?
I’ve been toying with ideas in the back of my head for awhile now. The generation so far has just been a very basic cellular automata method, which is cool, but not quite what I’m aiming for. This blog will be a blow by blow account of me shaping the generation into a mine more fitting it’s history.
Cellularing Some Automata
Now, I don’t want to throw the baby out with the bathwater. Cellular automata (hereafter referred to as CA) will still hold a central role in the generation of the Alchementalist map. It creates awesome cave looking structures which are perfect for the voids around the deep bones of the world. So let’s start with some experimentation. My first goal is to generate a nice clumpy map that will signify ore deposits. After some playing around with the input for the CA, I got to this:
That seems alright, at least for now. Plenty of deposits spread around, but they aren’t too clumped up together.
For those who don’t quite understand what they’re looking at, you can imagine this as a birds-eye view of the entire map. A single “tile” in Alchementalist is normally 16×16 pixels, which is then scaled up 6x, so each tile when displayed on the screen is 96×96 pixels. Here I’ve outlined a single tile in pink:
In the generated cellular automata map, each tile is represented by a 4×4 pixel square (well, it’s really a 4×5 tile because the scaling is slightly off, but let’s pretend it’s 4×4). The red circle on the below picture is pointing out a single “tile” on the generated map:
So if you were directly playing on that map, that tile would actually be 96×96 and it would look roughly like this on-screen:
“Compressing” the data of the map in a much smaller representation like this is common during generation of a map (in reality, there isn’t really a visual representation of the data like this stored anywhere, it’s simply flags in an array or a grid or something. If you were to imagine the map while it’s in this state, each “pixel” would represent one tile on the map).
Interestingly, while I was playing around with the generation, I hit on a pretty wide variety of interesting patterns being generated. Here’s a slideshow of the one’s I thought were the most unique and strange:
What I really loved about these patterns is that no matter how many times I generated them, they maintained the same sort of overall structure (as they should) with only variations in the finer detail. It’s not super surprising in a technical sense, but it is some really cool stuff.
Anyway, lo and behold, during this experimentation I found this really interesting pattern:
Now that is doing something cool, I can definitely use that with a bit of tweaking. As I was doing this experimentation I was slowly formulating a new plan. Originally, I was going to use CA to generate the ore deposits and then a more traditional “room based” generator to create the sections that the Ember-mages had delved out trying to get to the ore. However, seeing the above structure being generated solely with CA gave me an idea.
You see, while the above map is definitely “grid-like”, it doesn’t have the same grid feeling as most room generators. It’s got some really odd qualities to the rooms, with some seeming in a much worse state of repair than others and others had weirdly shifting walls that seemed to be following strange lines. This really made it stand out to me in comparison to the more traditional methods and it gave a unique vibe to the old “rooms connected by corridors” look that usually comes from procedural generation.
In fact, it’s almost as if the rooms were being delved by following imaginary ore lines! What a co-in-key-dink!
The Space Between Spaces
Ok, let’s start digging into this properly. Before I do any overlapping with the ore, I wanted to get the room generation working properly and I needed to set up the regions (or rooms).
In most normal generators, you are “manually” creating regions (let’s say with Binary Space Partitioning, or placing “rooms” in random points and shuffling them until they no longer collide) and because of the nature of the generator saying “I am creating a region here” it’s quite simple to tag that area as a room in some way (perhaps using objects as the rooms and storing their ID’s, or manually marking the areas you want as rooms and adding their boundaries to a list). However, with CA, there’s not really a nice way to grab each “room” as you are basically working on one cell at a time and you don’t know if that cell is connected to other cells or not. So how do I go about distinguishing the rooms?
With a flood fill, of course! Quick (relatively) and easy! So I’ll write up a flood fill algorithm that finds an EMPTY cell (the cells in CA are usually marked as SOLID and EMPTY or WALL and FLOOR or something like that), gives it a value (this value being a simple number that represents the region that it belongs to), flood fills from that cell until it’s hit all the other cells marked as EMPTY that aren’t blocked off by a SOLID cell and, as it’s doing this, stores each cell in a data structure that keeps track of all the cells for that particular region. Once it’s done that, it moves on until it finds another cell marked as EMPTY and repeats the process.
Once all that’s done, I’ll quickly loop through all the regions and see how many cells each has. If it’s below a certain number (which means the room is too small), I’ll simply delete that region and turn all the cells that it’s tracking into SOLID cells so that they turn into wall sections. Make sense? No? Well here’s a gif showing the process so maybe it’ll make a little more sense.
First we generate the CA, then we flood fill the regions with an increasing number, then we delete the regions that are too small:
You can see that each “bubble” of empty space fills itself with the same number; these are the regions (or rooms). Once the actual region finding is done, you can see all the smaller chunks of empty cells disappear and the region numbers update themselves to reflect the fact that there are now fewer regions.
As a side note, this is running much slower than it would normally so that you can actually see what is going on, and I’ve got a little text box at the top that roughly describes what’s happening at each point in time.
Forging Connections
The next task is to connect each region. I could go complicated and implement Kruskal’s Minimum Spanning Tree or something like that, but I think, at least to begin with, I’ll first try a very simple algorithm that simply finds the nearest non-connected room to each room and then connects them with a line that follows the manhattan distance (using mod to alternate between x and y steps so the corridors follow straight lines less and are more zig-zaggy).
There we go. I’m just connecting two random points between two rooms that are close together using the manhattan distance thing I described above. However, I’m not super happy with it. There are corridors going through some of the thickest parts of the walls, which doesn’t make a lot of sense. I expected something like this, but no harm in trying.
So we’ll move onto a smarter approach. Let’s use A* to path between the regions. A* is a pathfinding algorithm that takes into account the “cost” of a cell and the distance from that cell to the target cell. I’ve actually written an in-depth guide to implementing A* before here: Procedural Generation in GMS #6: A* Is Born (Pathfinding’s Greatest Hits) (incidentally, I have another guide on implementing flood fills as well, if you’re curious about how that works: Procedural Generation in GMS #5: A Flood of Fills)
We’ll need a cost map for this, so I’ll implement one (invisibly) over the top of the current map. EMPTY cells will cost less than SOLID cells, so the A* will try to path through the EMPTY cells first and then find the thinnest section of the wall that makes sense to move through. On top of that, I can make the A* decrease the cost for each cell in whatever path it picks, which means that if another room is trying to make a path close to an existing path, the two paths will merge for as long as it makes sense, cutting down on corridors that run directly beside each other or corridors with only a single wall gap between them.
To make it visible, I’ll first add the corridors in a different colour and then drill them out of the floor map bit by bit.
Let’s check it out:
Ok, I think that works a lot better. Things are progressing nicely. However, there is a problem with the generation above. There’s two “sections” of that map that aren’t linked. If you look at the top right and the bottom left, there’s no corridor that exists to connect those two groups of rooms together. So we’ll have to come up with a way to guarantee connectivity.
No Room Left Behind
First thing I’ll do is make another flood fill that starts from the first room. This flood fill will count each region it encounters and then compare that number to how many regions there are total. If the numbers differ, we know we have a region (or group of regions) that aren’t connected. Once we know that a region isn’t connected, we simply build a new corridor connecting the two regions using A* exactly like we did before. We can perform this in a loop until we know that every region has at least one path to every other region.
I don’t have a fancy gif for this because I got lazy cutting the algorithms up and making them run over time, but we can see the results here:
You can see a new corridor being drilled out in the bottom right that connects the two previously unconnected groups of regions.
Perfect! I’m mostly done with this stage of the generation now. Let’s quickly code up an auto-tiler and see how it looks with actual tiles instead of white rectangles.
And there we are. The mining operation of the Ember-mages has been generated. We still have to combine it with the ore layer and there’s still a fair bit of gen work to do involving broken down sections, water filled areas, magma, etc, but this post is already getting pretty hefty, so I’ll save that for another time.
Again, This Time With Feeling
Before we go, let’s watch the whole thing from start to finish:
Now that’s satisfying. Till next time!
RefresherTowel Games 