Mazes: Not just for Maze-related scenarios

[Cruiser1]

Parts of the programming in the Hunger Games Roguelike use Mazes for things that aren't Maze related, which might be of interest. The Hunger Games Simulation is a part of the Maze program Daedalus, and so has access to many Maze creation and solving abilities, which can be used to help create landscape features. Consider the random arena map above, which is a flat wooded grassland with rivers, lakes, mountains placed upon it:

Rivers: We want to have random river-like lines crossing the arena. To do this, we create a Maze (a "perfect" Maze with no loops) the same size as the arena, then solve it leaving a single squiggly line. Each additional entrance on the edge of the bitmap results in an additional line or fork in the river. (The river in the map above is from a Maze with four entrances/exits, one on each edge of the bitmap.) The solved path is expanded slightly so that fanfold passages will merge into each other, resulting in a slightly wider section there, so the river realistically has different widths in different areas. The Maze is generated with the Growing Tree algorithm, which has the right amount of curviness (curvier than Prim's Algorithm, but not as curvy as Recursive Backtracking).

Lakes: To have lakes, mountains (and meadows which are open spaces in the trees) we want to create irregular boundary shapes. To do this, we start creating a Maze in a separate bitmap using Prim's Algorithm, which semi-roughly "flows" outward from a start point. Stop creating the Maze after a certain number of cells, then expand the paths slightly so the passages cover adjacent walls, and the shape of the visited cells forms a nice random blob, which can then be randomly placed over the arena. For example, lakes will occasionally have small islands in them.

[Rickton]

This is pretty cool. I'd been generating rivers using a pretty simple drunk-walking method, I'll have to try making some using a maze algorithm.

[Cruiser1]

The newest version of the Hunger Games Roguelike uses Mazes in a few new areas. They can be seen in the aerial view map of the arena in the first post, which has been updated. Maze solutions not only generate random lines for rivers, but also boundaries between terrain types. In the picture, green is grass/forest, and yellow is desert. Also, Maze generation not only generates irregular blob shapes for lakes, mountain footprints, and meadows, but also terrain exceptions (e.g. a few areas of desert in the forest, and a few areas of forest in the desert).

Finally, Maze generation can be used for actual Mazes! The screenshot above shows an obvious Maze with walls for the players, with Mazes also used behind the scenes for the river, mountains, etc. For actual Mazes in an arena game I've found a "braid" style of Maze without dead ends (with many passage loops instead) works best, because it prevents human and computer players from camping out in dead ends, meaning you always have to watch your back.

[Bear]

For rivers, I think it's worthwhile to generate a topographic map first.  Then you can make your river using a random-walk algorithm except that you never go from a square of lower altitude to a square of higher altitude.  This prevents the occurrence of several kinds of "well that's obviously wrong" scenarios.

Awesome work on the HG roguelike, btw.  It's a rare opportunity to engage audiences with something like an "arena combat" scenario that is familiar enough to them to not require explanation.

[CaptainKraft]

For rivers, I think it's worthwhile to generate a topographic map first.  Then you can make your river using a random-walk algorithm except that you never go from a square of lower altitude to a square of higher altitude.  This prevents the occurrence of several kinds of "well that's obviously wrong" scenarios.

Awesome work on the HG roguelike, btw.  It's a rare opportunity to engage audiences with something like an "arena combat" scenario that is familiar enough to them to not require explanation.

That's a really good point. The maze river looks cool, but do you need to fix any issues with it based on terrain?

[Cruiser1]

For rivers, I think it's worthwhile to generate a topographic map first.

I actually do generate an initial topographic map first. My rivers (and lakes) are generated at the lowest elevation possible. That means rivers don't flow in any direction, since all parts are at equal elevation. I overlay the rivers on top of the terrain, having the river and its zero elevation cut through the hills. Rivers/lakes have an "invisible aura" which gradually pulls down nearby hills to the water level, to prevent "roadcut" type vertical drops into water. A similar concept is used to have make the starting flat area by the Cornucopia, which gradually rises into the surrounding hills. The universal water level means you can dig down anywhere, and will hit water when you reach that level. See the above picture for an example of a lake with a river intersecting it, and how they affect nearby terrain.

An alternative approach would be to "paint" the river on the surface of existing terrain, which indeed should mean always flowing downhill. However, random terrain would likely quickly result in a river ending in the first concave bowl area it reaches, or else that bowl area becoming a potentially large lake (until it fills up and overflowing water can keep flowing downhill somewhere).

Awesome work on the HG roguelike, btw.  It's a rare opportunity to engage audiences with something like an "arena combat" scenario that is familiar enough to them to not require explanation.

Indeed, this Roguelike is a single player vs. many combat game, which is close enough to the Hunger Games scenario that you can just say "Hunger Games", and most players know exactly the program is like.