Generation

I spent a good chunk of last year writing about compass, the map-generation library with all the fluvial generators and cellular caverns. The whole time I was building it as a standalone library, the real motive was to eventually drop it into a game. This month I finally did, and DET-33 now generates every one of its floors through compass. Pulling the library in Wiring it up was almost anticlimactic, which is the point of having spent the time on the composition layer. DET-33 pulls compass in as a git dependency and the level code just imports the scanning digger and the template data: ...

The individual generators in compass (the arroyos and rivers, the caverns and meanders) are the fun part to show off, but they aren’t what makes the library usable. The part I’m actually proud of is the composition layer that sits on top, and it owes a lot to the runtime pipeline patterns I wrote about a while ago. Shapes times features Every room is described as a shape combined with a feature. There are 24 shapes: squares and circles, but also blobs, crystalline caverns, crescents, capsules, and a handful of hallway types. There are 18 features: pillars, islands, stepping stones, pools, moats, chasms, rubble, and four kinds of river. Any shape can pair with any feature, which is 432 distinct room configurations before you’ve placed a single one. A feature is just two functions: an initialize step that works out the geometry (the meandering river feature, for example, generates a sine-wave centerline and expands around it), and a content step that decides the terrain type for each tile inside the shape. Keeping those two responsibilities separate is what lets the same river feature drop into a square room or an L-shaped hallway without caring which it landed in. ...

Back in 2015 I tackled automata generated caverns for a 7DRL, and in 2018 I wrote up the meander algorithm for rivers. Both made it into compass and both got a little sharper along the way, so I wanted to revisit them with the actual implementations in hand. Caverns The cavern generator is Conway’s Game of Life pointed at a terrain problem. It’s almost embarrassing how little code it takes. Clone the map and randomly seed roughly 55% of it as floor. Run a single Game of Life pass over the Moore neighborhood (the 8 surrounding cells). An empty cell is born as floor with 5 or more floor neighbors, and an existing floor cell survives with 4 or more. clipOrphaned keeps only the largest connected blob so you don’t get a dozen disconnected pockets. Build walls around everything walkable and force the map border to wall so the cave is sealed. One pass is enough. The birth and survival thresholds are doing the smoothing that I used to iterate several times to get, and the result is the lumpy organic cave you’d expect. ...

A few years back I wrote a handful of posts about faking water on top-down maps: generating 2d rivers, cliffs, and an exhumed river channel. Those one-off experiments eventually grew into a proper map library I’ve been maintaining called compass. Revisiting them now is fun because real-world geology already solved the “make it look natural” problem ages ago. I just borrow the names and loosely approximate the process. Here are three of the fluvial generators and how they actually work. ...

At numerous times I’ve created demos trying to figure out how to merge a traditional roguelike into a FPS without sacrificing it’s roots. Here’s an article I made in 2017. Unlike many others I don’t feel like just random maps makes a roguelike, I’ve even gone so far as saying no FPS is a roguelike. In this experiment I’ve tried to merge those ascii characters into the map itself and dropped the textures. The code can be executed and ran or viewed in its entirety on Github here. ...

The meander algorithm is a combination of using mazes to allow a meandering with bresenhams line. Below you can see the actual algorithm in simplicity. Obviously you could use noise maps to created heighted terrain based on the river to make it look pretty. Choose a starting map edge and ending map edge, acquire the terminal points based on those edges. Usually this would be a random point on those edges. Maybe you’d want to weight it so it’s predominately in the center, or you could restrict it to a certain part. Create Bresenhams line between the terminal points. This is called the pathing vector. Break up the pathing vector into chunks of 9x9 where the pathing vector crosses the center. There may be left-over of the pathing vector. For each chunk, perform a recursive maze generation algorithm on the chunk. Repeat this step until there is a path from the start of the pathing vector within the chunk to the end of the pathing vector in the chunk. A* pathing algorithm can be used for the pathing. Merely use Bresenhams line to wrap up the extraneous pathing vector not covered by chunks, alternatively break up the remaining path into the largest odd number and chunk and process it similarly to the previous part of the algorithm to make it more consistent. Left overs in this optional way would still be filled in with bresenhams line. Recursive Maze Generation: ...

I recently did some work in generating rivers in a 2d game. Revisiting this work to create an exhumed river channel, I decided it might be fun to revisit how to generate it to make the channel look more realistic. Instead of using a drunken walker, this is a more expensive but interesting map generator: Start by generating 2d simplex noise where less <0.6 is floor rest is walls Generate terminal lines at each map exit (north, south, east, west). Shuffle those lines and randomly choose a start and end location for the river based on two of those lines. Later you can add another line with terminal point to allow a split river channel ...

Source code available on github here.\n\nA recurring problem in 2d games is how to represent depth. In isometric games this is easily solved but in discretely top-down games it’s harder to solve. After doing a lot of research I fell onto a simple idea: do the best you can insinuating the depth and leave the rest to the imagination. Here’s the algorithm I used to create 2d top-down cliffs: Create a small map of perlin noise and a wide map of perlin noise. Add the two together and give the large map a weight of 3 with the small a weight of 1 and render the result with different breakpoints. This is ref map A. Less than 0.01 on A is deep water ...

Rivers are really hard to generate for 2d top-down games for multiple reasons: Rivers primarily form based on heightmaps which are hard to display in top-down Displaying fluidity when working with sectors or grid-based rendering can be complicated, bresenham’s line algorithm only goes so far to make things look smooth naturally occurring mechanisms of nature have numerous factors in play that caused them to exist. Simulating all of these factors isn’t reasonable. I was able to make relatively decent 2d rivers using a few techniques. ...

I had originally written an article on how to implement PHS. Having found the maps generated slightly redundant I decided to take another look. Here are the steps taken to successfully generate a more realistic town. It’s essentially a drunken walker like Diffusion Limited Aggregation mixed with a hallway constraint that mimics the large part of PHS. Start somewhere in the middle, add this and all possible directions up to a certain dynamic length (I used a standard deviation of 1.4 with a mean of 5, ) as nodes: [{x,y,direction},...]. We will be looping until all nodes and edges (we’ll describe that shortly,) are gone. When we have node then check to see if the path between it’s ‘x,y’ and ‘x2,y2’ (given the length and direction) is clear. If it is, then add the entire path minus the start and end as edges, and add the end as a new node. Shuffle nodes after adding a new one. After building the path run through the path array randomly attempting to build a room in all directions. (this won’t be entirely possible and will leave negative space to fill with edges.) If there are no nodes, repeat step 3 except with edges (this helps fill the map negative space.) After all nodes and edges are gone then cover all cells adjacent to floors with walls if it’s empty. I found it helpful to use this simple formula to generate hallway lengths with a mean and standard deviation constraint. Both the x and y would work fine, here we’re using the y only. ...