I've been working on map generation in Adrift this week. I've been through a few different unsatisfying iterations of the map generation code and I'm finally feeling like I've encountered a rich algorithmic vein, so I wanted to write a little bit about what's been working.
The world of Adrift is a space ship, so unlike a lot of other roguelike environments, I want it to feel designed. There are a lot of examples of map generation algorithms for generating caves, or dungeons, where a little chaos is acceptable (or even desirable). But not so many examples of algorithms which try to generate something that feels ordered. Another challenge is that if we're generating a space ship, we want to fill all the available space—anything less would be wasteful!
I spent a long time trying to make use of the idea of symmetry, to try to generate maps that were symmetrical and thereby create a feeling of orderedness. I never found anything that felt like it hit the right balance between randomness and orderedness. But a few weeks ago, my collaborator Nato said something that made my brain click into a new place. He said that it's a generation ship—it's more like a city than a spaceship. And that got me thinking about city grids, like this block in Chicago.
If this were generated output, I think it hits a really good place on the ordered/chaotic spectrum! It has a lot of parallel lines, and blocks of similar sizes, but it's broken up so that it doesn't seem mathematical. It feels lived-in. That's what I want to capture!
I immediately thought of binary space partitioning as a way to produce this sort of layout. There's a pretty good description of BSP here (as video), or if you happen to have a copy of Procedural Generation in Game Design, there's a great chapter in there by Brian Bucklew on space partitioning of various kinds, including binary. I'd recommend either or both of those if you want to implement this yourself. At a high level, the process is this:
- Start with a rectangle.
- Cut it in two. You now have two rectangles.
- Recurse.
There's still a bit more tweaking that I want to do to get things working right. For starters, there are a lot of long thin rooms in that example that I think I can eliminate, either by merging them into adjacent rooms, or by setting a minimum size when splitting larger rectangles. Currently, the algorithm terminates when a room gets below a certain cut-off area threshold, which means most rooms are about the same size, but I'd like some rooms to be larger to accommodate some more variation in the space, and to make room for larger areas like arboreta, recycling plants, engine rooms and so on. But I think this algorithm has legs! It's flexible, it's simple, and it generates layouts that I like.
Here's how it looks in the game (with FOV turned off so you can see the layout):
Next time: how to fill rooms with room-type-appropriate furniture when they're not a fixed shape!