Sunday, August 7, 2011

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


  1. Hey! I found out about this project rather recently and I'm rather intrigued by what possibilities it could hold.

    Now, I know you're just working on basic engine stuff at the moment, but I must ask...

    "Systems that exist for thousands of years enter a kind of equilibrium; most anything you do can upset that equilibrium, and change the cave in ways you may not expect."

    You wrote this in a video description, and I'm curious about exactly how this is going to be factored into level generation. Did you already write a post on this subject earlier? If not, would you be willing to enlighten a curious fellow programmer?

  2. The idea is, dynamic systems eventually enter into a state of minimum energy. Basically, the idea is to simulate the world a bit before the player ever gets to see it, and let things "settle." I might end up not being able to fulfill the letter of that idea however; in fact, an entirely settled system is somewhat boring. Rivers are more fun than lakes. Boulder avalanches are more exciting than big piles of boulders resting at the bottom of the map.

  3. Not to be contrary to your intentions, but I'd like to point out that natural rivers manage to exist in real caves, even after thousands of years. Water is naturally provided by the surface, although I can't say I can pinpoint exactly where it all goes, so that the cave doesn't flood completely. Evaporation, perhaps? Regardless, in your simulation, liquid could naturally flow in from the surface periodically, or may seep in through rock near the surface, on and off, depending on time variables that may not otherwise be reflected in the environment. Rivers need not be unrealistic!

    Other precariously balanced systems can be found in real caves as well, I assume. I would encourage some research, followed by some experimentation to see if you can simulate the generation of such systems! Of course, I concede that fun levels must take precedence to realistic levels. But I would love to see some simulation of realistic natural cave formation.

    These are my ideas. I don't mean to push anything on you though, I'm looking forward to this game, whatever you do!

  4. Yes, I know about the water cycle and that things in real life are a bit more complex than that. But real life also has erosion and other things that, when they are possible to simulate at all, have limited gameplay potential. I am considering adding liquid evaporation, but I'm unsure how useful it'll be to play. It would mean that it'd have to be a much higher priority adding temperature to the game, which I think would increase its play usefulness.

  5. I love reading about procedural generation, it's something I'm really into. Keep these posts coming ! ^^

    Do you have any links about procedural generation ?