In Profundis Progress 8/7

It's still rolling along.  Here I'm going to detail some of the finer steps in the world creation algorithm I'm working on.

The steps (partly restated from last time):

1. Define random material properties.
2. Make an array of sectors (each representing a 12x12 area of world tiles).
3. Build a maze in that array, with each element holding which adjacent elements it's connected with in bitfields.
4. Perform processing on that maze (this is what this post is actually about -- see below).
5. Take maze, indexed into heightmap influence templates, and apply that to an array matching the size of the world.  (This is what I talked about last time.)
6. Turn heightmap into wall cells in game world array.  Along the way, apply any special codes in the templates that produce special features - <i>ignoring liquids</i>.  (This part is new.  I'll have more to say about it later.)
7. Perform "flow experiments" to find good liquid flow paths through the world and create "wormholes" (actually, grates) that moves liquids from lower to higher points.  I'm handling this process by putting in some simulated liquid into the world and running some turns to see what it does, then cleaning up the liquid afterwards.
8. Apply the liquids skipped back in step 5.
9. Later processing, tile smoothing, sediment laying, etc.

Mazes are intrinsically interesting structures to explore, but have some problems, especially related to their use in random world generation.  A proper maze has only one way to get to any location in the maze, meaning if there is a difficulty in getting through a section, it makes it correspondingly more difficult to get to any location beyond that section.  By putting in more ways to get to a place, the gameplay experience is made more robust.  At the same time it actually simplifies navigation, due to the existence of tricks like the "left/right hand rule," a.k.a. the wall follower trick.  (More on maze solving algorithms at <a href="http://en.wikipedia.org/wiki/Maze_solving_algorithm">the Wikipedia page</a>.)

My idea is to put loops in the maze that allow the player to find ways around trouble spots.  (It's possible that the other ways have troublespots as well, but we're not trying to hand them the victory here.  They will have to sweat sometimes.)  I used a system like this in Mayflight, but I didn't care much about where the loops went.  This often meant the loops were trivial, like connecting two already-connected rooms.

I had already come up with a way to solve this problem many years ago however in an old Commodore program.  The solution is to make an intermediate pass and record each spots' minimum distance, traveling through the maze, from a random starting point.  Then look through the maze and find the adjacent spots with the greatest difference in distances from that point, and connect them.  To make additional loops it's then best to refigure distances, taking the new path into account, from a new random point.  The result (if memory serves) is a more satisfying maze to explore, with longer paths and more work to do to find alternate access routes.