Like a lot of folks, the desire to create my own video games is what originally got me into computer programming. While I don’t play many video games these days, video game development still holds a special place in my heart. I’m especially fascinated by procedural generation techniques used in video games and many forms of computer art, so you’ll often find me creeping around the /r/roguelikedev and /r/generative subreddits.

Inspired by a recent post on /r/roguelikedev, I decided to try my hand at implementing a very basic dungeon generator using a random walk algorithm.

After getting our canvas set up, we can implement our basic random walk algorithm by starting in the center of our grid and moving in random directions, filling in each square we encounter as we come to it:

let pixelSize = 32;
let w = Math.floor(width / pixelSize);
let h = Math.floor(height / pixelSize);

let state = [];
let x = Math.floor(w / 2);
let y = Math.floor(h / 2);
let filled = 0;
let path = [];
let maxFilled = 500;

while (filled < maxFilled) {
    path.push(y * w + x);
    if (!state[y * w + x]) {
        state[y * w + x] = true;
        filled++;
    }
    let [nx, ny] = getNextDirection(x, y);
    x += nx;
    y += ny;
}

Notice that we’re also keeping track of the sequence of steps, or the path we took to as we moved through our grid. Also notice that this isn’t particularly “good” code. That doesn’t matter as long as we’re having fun.

The getNextDirection function just returns a random direction, with a little added fanciness to keep our path from falling off our grid:

let getNextDirection = (cx, cy) => {
    let [x, y] = _.sample([[0, 1], [0, -1], [1, 0], [-1, 0]]);
    if (cx + x < 1 || cy + y < 1 || cx + x >= w - 1 || cy + y >= h - 1) {
        return getNextDirection(cx, cy);
    } else {
        return [x, y];
    }
};

Animating this algorithm is its own microcosm of interesting divergences…

Once we have our fully filled out grid, we can flip our perspective and render the walls around the steps we took through the grid, rather than rendering the steps themselves:

We can add a path through our dungeon by removing the cycles from our path and tracing its newly simplified form through our grid. We could even hint at up and down stairways with orange dots at the beginning and end of our path.

This is a ridiculously simple algorithm, but what comes out of it absolutely pulls me in. What else lives in these dungeons? What kinds of things could we expect to find, and how would we bring those things to life?

Refresh the page to get more dunegons!