Meander

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. ...

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: ...