Random Cave Generator

Random Cave Generator

Foreword

Following the success of my Dungeon Generation article I decided to write one on generating random caves. In this Random Cave Generator Tutorial, we’ll be using cellular automata to generate nice looking caves in JavaScript.

If you have any questions, feel free to contact me on twitter.

Random CaveGenerator (DEMO)

Algorithm

First, let’s discuss the random number generator. We’ll be using a generator that is able to generate reproducible results.

Math.seed = 6;
Math.seededRandom = function (max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

We are adding a property and method to the built-in Math object. The seededRandom function will return a random number based on the seed we have provided. This means that we can always get the same result for the given seed which will ultimately lead to the same cave being generated.

If you would like caves to always be random, you can just make the seed value itself random.

function get2DArray(size) {
    var map = [];
    for (var i = 0; i < size; i++) {
        map.push([]);
        for (var j = 0; j < size; j++) {
            map[i].push(0);
        }
    }
    
    return map;
}

This is another helper function we'll be using. It simply returns an empty 2 dimensional array that we can use.

var size = 64;
var map = get2DArray(size);
for (var i = 0; i < size; i++) {
    for (var j = 0; j < size; j++) {
        map[i][j] = ~~Math.seededRandom(2, 0);
    }
}

Here we create a new array and populate it with random data. I've used 2 as a max since the random generator will use the max value as an exclusive upper limit (it will always generate a value lower and not equal to it).

var smoothness = 3;
for (var i = 0; i < smoothness; i++) {
    var new_map = get2DArray(size);
    for (var x = 0; x < size; x++) {
        for (var y = 0; y < size; y++) {
            var x_range = {low: Math.max(0, x - 1), high: Math.min(size - 1, x + 1)};  
            var y_range = {low: Math.max(0, y - 1), high: Math.min(size - 1, y + 1)};  
            var wall_count = 0;
            for (var a = x_range.low; a <= x_range.high; a++) {
                for (var b = y_range.low; b <= y_range.high; b++) {
                    if ((a == x) && (b == y))
                        continue;
                    
                    wall_count += 1 - map[a][b];
                }
            }
            if (((map[x][y] == 0) && (wall_count >= 4)) ||
                ((map[x][y] == 1) && (wall_count >= 5)) ||
                ((x == 0) || (y == 0) || (x == size - 1) || (y == size - 1)))
                    new_map[x][y] = 0;
            else
                new_map[x][y] = 1;
        }
    }
    map = new_map;
}

This is where the magic happens. First we define a variable in which to store the smoothness of the cave. You can play around with this number until you get a result you like.

We iterate through the map a number of times (defined by the smoothness). For each iteration we create a new map to store the result of the iteration in.

For each cell, we check all of its neighbors (taking care not to look at cells falling outside the range of our map) and make a note of how many cells have walls in (map[x][y] == 0). We achieve this by keeping track of a count variable and increment it by '1 - map[a][b]'. This means that if a cell has a 0 in, we will increase the count by 1.

When we have calculated how many neighbors have walls, we perform a bit of logic: If the cell is a wall and has at least 4 neighbors that are walls, the cell will stay a wall. If the cell isn't a wall but has at least 5 neighbors that are walls, the cell will become a wall. Also, if the cell lies on the edge of the map, it becomes a wall (don't let those players escape!) Lastly, if none of those three cases are true, the cell becomes (or stays) a floor.

After the iteration, we set the current map to the new map and start over.

Conclusion

That's all there is to it. And you thought it would be complicated! As always, if you have questions, drop me a tweet. Also, if there are any generators you would like to see in the future, let me know, I'd be happy to oblige!

2 thoughts on “Random Cave Generator

  1. Pingback: Dev Time » Gold Hunter: Part 1

  2. Pingback: Making a cave-like structure

Comments are closed.