## Saturday, November 3, 2012

### Creating Caves

I'm procedurally generating caves for this game, and I want them to look interesting.  A few examples:

Here's how I create them:

1. I start out generating a grid of X by Y booleans (tiles).
2. I start with a "cursor" at the top middle.  I move either left to right, or right to left a random number of tiles, removing all of them.
3. Move down one row.
4. Repeat steps 2 & 3 until I reach the bottom.  At this point, I have a simple cave with a path through it from top to bottom.  Of course that's pretty boring.
5. Next up I just start deleting tiles.  I choose a tile at random, check if it is bordering empty space, and if so, delete it.
6. At this point I have a path from top to bottom, with little rooms branching off.  At this point though, there are some tiles which are diagonal to other tiles

without any non-diagonal tiles joining the diagonal tiles.  Think something like (# being a tile, - being a blank space)

###-
####
----#

The one on the bottom right is diagonal from other tiles and joined to them directly.  This looks weird, and would mess up later steps in my process, so I do a sweep

for all tiles which meet this diagonal condition, and likewise, set them to false.

7. Now I iterate my tiles and generate line segments which form nice outlines of everything.  This is important if I need to draw anything other than boxes.  Simple

algorithm:
-For each tile (if it is true and not erased):
-If the tile above it is false, generate a line segment for the top edge of that tile
-If the tile below it is false, generate a line segment for the bottom edge of that tile
-If the tile left of it is false, generate a line segment for the left edge of that tile
-if the tile right of it is false, generate a line segment for the right edge of that tile

This ends up generating line segments which encapsulate the outline of the various cave walls.

9. Store the individual points of the segments in a map so that you can figure out which segments connect with each-other.  I actually do this as part of step 7, but

it doesn't really matter.

10. Pick a point (from the segments) at random.  Trace the connecting segments one at a time, until you end up back at the original point.  You now have a distinct

polygon.  Be sure to remove points from the list as you go.

11. Repeat step 10 until all points have been removed.  Now you have a group of distinct polygons made up from your segments.

12. For every segment within every polygon, split it into N chunks.  I'm taking each segment and splitting it into 3 chunks.  So every tile wall ends up being 3

shorter segments combining to form that wall.

13. Now just perturb every point a random amount.  You want to keep it less than "TILE_WALL_LENGTH / SUBSEGMENTS_PER_WALL", otherwise walls may intersect each-other

and it won't look good.