Random terrain generation with caves

Question

I am currently working on a small game that will generate a world with caves and entrances to the caves, something like Terraria if you will. Today I reached some trouble on the world/cave generation code. I want to use Perlin Noise but I am not so sure how to implement it into my code. Could someone point me in the right direction for a reference or even code samples?

Answer 1

Here's something to get you started; for organic structures such as caves I've found that random walk works fine, and it's great because it's dead simple.

This sample code does the following:

• Create a basic 2d terrain (any method will do)
• Choose a cave entrance
• Starting from that cave entrance, do a 2D random walk and "carve" out the interior of the cave, making sure that we don't break through the surface

http://ideone.com/CJhzhm

using System;
using System.Collections.Generic;

public class Test
{
    static Random rand = new Random();
    static int width = 79;
    static int height = 24;
    static char[] cells = new char[width * height];
    // Cells are ordered left-to-right, top-to-bottom

    public static void Main()
    {
        GenerateRandomTerrain();

        // pick a point on the surface as the cave entrance
        int caveX = 35;
        int caveY = 0;
        while (cells[caveY * width + caveX] == ' ')
        {
            caveY++;
        }
        // drill down until we are deep underground
        while (cells[caveY * width + caveX - 1] == ' ' ||
            cells[caveY * width + caveX + 1] == ' ')
        {
            cells[caveY * width + caveX] = '.';
            caveY++;
        }

        // starting from the entrance, walk randomly within the terrain,
        // "carving out" the cave
        // make sure we do not create new entrances; the carving must not go
        // adjacent to an "open air" cell
        for (int i = 0; i < 1000; i++)
        {
            // "carve out" the current cell
            cells[caveY * width + caveX] = '.';

            // Get random direction:
            // 0: up
            // 1: right
            // 2: down
            // 3: left
            int dir = rand.Next(4);
            switch (dir)
            {
                case 0: // up
                    if (IsValidCaveCell(caveX, caveY + 1))
                    {
                        caveY++;
                    }
                    break;
                case 1: // right
                    if (IsValidCaveCell(caveX + 1, caveY))
                    {
                        caveX++;
                    }
                    break;
                case 2: // down
                    if (IsValidCaveCell(caveX, caveY - 1))
                    {
                        caveY--;
                    }
                    break;
                case 3: // left
                    if (IsValidCaveCell(caveX - 1, caveY))
                    {
                        caveX--;
                    }
                    break;
            }
        }

        // Show our results
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                System.Console.Write(cells[y * width + x]);
            }
            System.Console.WriteLine();
        }
    }

    static void GenerateRandomTerrain()
    {
        for (int x = 0; x < width; x++)
        {
            int elevation = rand.Next(height * 4 / 5, height);
            for (int y = 0; y < height; y++)
            {
                if (y < height - elevation)
                {
                    // Open air
                    cells[y * width + x] = ' ';
                }
                else
                {
                    // Ground
                    cells[y * width + x] = 'X';
                }
            }
        }
    }

    static bool IsValidCaveCell(int x, int y)
    {
        // a cave cell is valid if:
        // - it doesn't exceed the world boundaries
        // - it isn't adjacent to an "open air" cell
        if (x < 0 || x >= width || y < 0 || y >= height)
        {
            // out of world bounds
            return false;
        }
        for (int dx = -1; dx <= 1; dx++)
        {
            if (x + dx < 0 || x + dx >= width)
            {
                continue;
            }
            for (int dy = -1; dy <= 1; dy++)
            {
                if (y + dy < 0 || y + dy >= height)
                {
                    continue;
                }
                if (cells[(y + dy) * width + (x + dx)] == ' ')
                {
                    // adjacent to "open air" cell
                    return false;
                }
            }
        }
        return true;
    }
}

Sample output:

          X   XX  XXX     X                    X       X   XX   X  XX X  X     
        X XX  XX XXXX     X             X      X  X  X X X XX   X  XXXXX X X X 
   X XXXXXXXX XXXXXXX  XXXXX X X    X   XX XX  X  X  X X X XX  XXXXXXXXXXX X X 
XX X XXXXXXXXXXXXXXXXXXXXXXXXX X XX.XXXXXXXXXX X  X XX X X XX XXXXXXXXXXXX X XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XX........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.......X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX.X.XXXXXXXXXXXXX..X.........X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXX.....XXXXXXXXXXX...........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX......XXXXXXXXXXXXX....X.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX.X......XX...X....XXX.X.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
.XXXXXXX.........X........XXX...XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
......X..X.XX..X.X.............XXX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
...........XXXXX...................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
..........XXXXXX........X.....X....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

You can play around with the number of iterations (it's set to 1000) to see what results you prefer.

Note that for platformers (you mentioned terraria) you would want to make sure players can't get stuck, that is there are no platforms for the player to jump out of. Platformers also prefer caves that are flatter than they are deep; you can modify the random walk to bias horizontal movements more than vertical for instance.