Planetary Dungeon

This is a continuation of last week’s project to cover a sphere in a square grid. The main idea is to build an infinitely scrollable but finite dungeon by placing it on the surface of a planet. But how do I put a square grid on a sphere? I treat it as a cube, with six square faces. Each of those faces can be covered in square tiles. Then I morph the cube into a sphere. That’s what I had learned as of last week. This week I’m generating a dungeon.

First a “Google Maps” style demo. Scroll the map:

Things to note:

• you can keep going north/east/south/west and you’ll wrap around to where you started
• there are some areas where there are no rooms (explained below)
• “up” on the screen isn’t always north; you can face different directions as you walk around the planet

I’ve never made a dungeon generator before, but I knew everything would be complicated by working on this cube/sphere surface, so I decided to keep the dungeon generation part simple. This page describes what I tried, what worked, and what didn’t.

 1  Map storage#

I started this project by copying the code from last week, and then removing the parts I wouldn’t need (animations mostly). I had originally used 0-5 to mark the cube faces, but then last week I realized it’d be easier to use a row/column arrangement to make the calculations simpler. But the row/column arrangement seemed like it’d be harder to work with, so I switched back. I wrote some code to convert back and forth, and then used 0-5 for all the code except the neighbors function.

With 0-5 for the face id, I have a way to have a global tile id for every tile on the cube.

Encoding:

• id = (face ⨉ size² + x ⨉ size + y)

Decoding:

• face = floor(id / size²)
• x = floor(id / size) % size
• y = id % size

Code:

const Tile = {
    id(face, x, y) { return face * (N * N) + x * N + y; }
    face(id) { return Math.floor(id / N / N); },
    x(id) { return Math.floor(id / N) % N; },
    y(id) { return id % N; },
};

I liked that the code was compact but … I found that bounds checking here was useful for catching bugs. And N is just too vague. So here’s what I ended up with:

const Tile = {
    id(face, x, y) {
        if (0 <= face && face < 6
            && 0 <= x && x < TILES_PER_SIDE
            && 0 <= y && y < TILES_PER_SIDE) {
            return face * (TILES_PER_SIDE * TILES_PER_SIDE) + x * TILES_PER_SIDE + y;
        }
        throw `id(${face}, ${x}, ${y})`;
    },
    face(id) { return Math.floor(id / TILES_PER_SIDE / TILES_PER_SIDE); },
    x(id) { return Math.floor(id / TILES_PER_SIDE) % TILES_PER_SIDE; },
    y(id) { return id % TILES_PER_SIDE; },
};

I can store the map data by using these indices with an array of 6 ⨉ size² elements.

 2  Rooms#

The next thing I did was try some dungeon map generation algorithms on a single face, where I was only working with x,y. This let me quickly try things out before I added the complexity of working on a cube.

I’m not sure this was the right approach. Sometimes I do what’s easy instead of doing what is best. I told myself that since I had never done dungeon generation before, I should do the easy version first and then adapt it. The danger is that I might end up algorithms that are easy to do with x,y but hard to run on a cube. I tried to keep this in mind, and worked on algorithms that only looked at neighboring tiles, but I still ended up with something that didn’t quite work.

 2.1 First attempt: parallel breadth first search#

I randomly scattered “seeds” randomly throughout the world, then ran Breadth First Search to let the seeds grow into rooms, with a limit on how large the rooms could grow. (I previously wrote about this technique here^[1] — see the last demo.)

Lots of the room boundaries were diagonals:

I should’ve expected this but it didn’t occur to me until I tried it. Although I like the organic feel of the room boundaries, it doesn’t look as good once I add walls. I also didn’t have a way to handle narrow diagonal rooms.

I also tried bfs with 4 neighbors instead of 8. It was a bit better here:

but in dense areas it produced a mess:

I think this would be useful but it wasn’t what I was going for. Since the focus of this experiment was the cube world, I wanted to keep the dungeon simple.

 2.2 Second attempt: serial breadth first search#

I switched to allocating tiles one room at a time. This worked much better. When bfs was about to stop because it hit a boundary or another room, I placed a wall. Sometimes seeds would be randomly placed in an existing room, and I would ignore them.

I was pretty happy with these rooms. I get a lot more variety this way than if I require all the rooms to be rectangular. But I had only implemented this per cube face; the rooms couldn’t cross the boundaries. You can see the rooms don’t cross this horizontal line

That’s a problem I need to tackle at some point, but I decided to work on doors next.

 3  Doors#

I usually would do “top down” map generation where I first decide what rooms are connected to each other, then place them on the grid. But for this project I wanted to go “bottom up”. I first generated the rooms, then scanned the grid to find places that could potentially have a door. A door could go on any wall tile that has (a) two wall neighbors and (b) two neighbors from different rooms.

These walls are all candidates for doors. I put each of these walls into a set, keyed by the pair of rooms.

for (let faceId = 0; faceId < 6; faceId++) {
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < N; y++) {
            let N = tileAt(faceId, x, y-1),
                E = tileAt(faceId, x+1, y),
                S = tileAt(faceId, x, y+1),
                W = tileAt(faceId, x-1, y);
            if (N === -1 && S === -1
             && E >= 0 && W >= 0 && E !== W) {
                rememberWall(faceId, W, E, x, y);
            } else if (E === -1 && W === -1
                    && N >= 0 && S >= 0 && N !== S) {
                rememberWall(faceId, N, S, x, y);
            }
        }
    }
}

Oh, wait, that’s not great. Do you see what’s wrong with the code? I’m using -1 to represent walls. It’d be cleaner like this:

            if (N === OWNER_WALL && S === OWNER_WALL
             && E >= 0 && W >= 0 && E !== W) {
                rememberWall(faceId, W, E, x, y);
            } else if (E === OWNER_WALL && W === OWNER_WALL
                    && N >= 0 && S >= 0 && N !== S) {
                rememberWall(faceId, N, S, x, y);
            }

Ok, that’s better. I use magic numbers a lot, and I need to get better about using named constants. I’m using -2 for doors, -3 for prohibited corners, and I expect to keep adding special values over time.

Ok, now I have a hash table from (room, room) → Set[wall, wall, …]. For each pair of rooms, I picked one wall randomly out of the set and turned it into a door. This guaranteed exactly 1 door for each pair of rooms that share a wall. A minor variant would be to sometimes generate 0 doors instead of 1, but maybe I’ll try that later. And another bonus feature would be to turn each of these pairs of rooms into an edge in the room graph. Then I can analyze the graph for connectivity etc.

The main reason I went with this approach is that I wanted to generate doors independently from rooms. I can put in many different room generators but have them all use the same door system. Later I’ll show how I added a different room type, and the door generator didn’t have to change.

 4  Coordinate transforms#

I had been working on the map generation on a single face of the cube at a time. This was fun, but I had to remind myself that the goal of this project is not to make cool dungeon maps, but to explore how they would work on a cube/sphere. That means I need to extend the room and door algorithms to work across the seams.

At first I thought I’ll write a neighbor() function that takes a tile location and returns the 4 tiles adjacent to it. Since my room generation is using breadth first search, I don’t care about direction.

but … I do care about direction. The room size is a limit that depends on the direction. So I need to keep direction in mind.

Next idea: what if I store the direction of room growth relative to the seed point? I couldn’t get this to work right, again, because directions changed. The whole idea of having an integer “tile id” loses the direction, so when I store things in the map or the bfs queue, I lose track of which way is which.

Next idea: what if I construct rooms in local coordinates that let me pretend that I’m always on one face? If a face is 100x100, the valid coordinates are (0,0) to (99,99), but while constructing the rooms I’m going to allow going outside that area. The orientation of the room would stay consistent while constructing it, and I could apply the size limits. But when writing the room to the map, I’ll convert these local coordinates to global cube coordinates. This worked well! Let me describe it in more detail.

I keep x,ywithin each face, but if the coordinates go out of bounds, then I need to switch faces. I’ll assume each face is 100x100 tiles.

• x < 0: move to the west face
• x ≥ 100: move to the east face
• y < 0: move to the north face
• y ≥ 100: move to the south face

Then I can set x = x mod 100 and y = y mod 100 using a version of mod that handles negative numbers properly. That puts me back into the valid range, 0 ≤ x < 100, 0 ≤ y < 100.

Here’s the tricky bit. In addition to moving to another face, I also need to handle that face’s orientation. Let’s suppose I’m moving from 30,80 to 140,10. I have to move to the east face. If the east face has the same orientation:

I move to the east face, and then set x to 140 mod 100, which is 40. I set y to 10 mod 100, which is 10. So I end up at 40,10.

But what if the destination face has a different orientation? Here I’m still moving 30,80 to 140,10 but the east face is rotated:

In this case instead of 40,10 I end up at 10,59. Since the face is rotated right I need to rotate the coordinates left by changing from x,y to y,99-x.

Here I need to change 40,10 to 59,89. Change x,y to 99-x,99-y.

Here I need to change 40,10 to 89,40. Change x,y to 99-y,x.

So that’s how I handle the cube face orientation.

1. Move to the new face.
2. Mod x and y with 100 to put x,y back into the valid coordinate range.
3. Rotatex,y according to the orientation.

function wrapTileId(face, x, y) {
    if (0 <= x && x < N && 0 <= y && y < N) {
        return Tile.id(face, x, y); // easy case
    }
    
    if (x >= N) {
        direction = 1;
        x -= N;
    } else if (x < 0) {
        direction = 3;
        x += N;
    } else if (y >= N) {
        direction = 2;
        y -= N;
    } else if (y < 0) {
        direction = 0;
        y += N;
    }
    if (x < 0 || x >= N || y < 0 || y >= N) {
        throw `double wrap not allowed`;
    }
    
    let newFace = new FaceCoordinate(face, 0).neighbor(direction);
    face = newFace.faceId;
    switch (newFace.orientation) {
        case 0:                          break; /* north */
        case 1: [x, y] = [y, N-1-x];     break; /* east */
        case 2: [x, y] = [N-1-x, N-1-y]; break; /* south */
        case 3: [x, y] = [N-1-y, x];     break; /* west */
    }
    return Tile.id(face, x, y);
}

This only works when either x or y has to wrap. If both x and y wrap, then the cube distortions don’t allow us to move in this way (it becomes ambiguous). I solved that by:

1. keeping room sizes relatively small (I wanted to do this anyway)
2. not generating rooms near the problematic corners (I needed to do this anyway)

This worked well!

I also tweaked the room generator to place small rooms first and then large rooms later, and corridors at the end. I got some nice shapes, including small rooms cutting corners out of larger rooms.

Sometimes, especially in gamedev, it’s easier to avoid the hard cases than to solve them.

 5  Poles#

Which way is North? While exploring the map I found myself getting disoriented. The first thing I did was add a special room at the poles:

The round room looked kinda cool, and the door algorithm worked unchanged, so I decided to add more round rooms:

Even with the smaller rooms, the door algorithm seems to work. Great! But this is a distraction. The real problem I’m trying to solve here is that I was trying to stay oriented while wandering around the map.

 6  Compass#

Since the poles are useful only when you’re close enough to see them, I decided to add compass directions:

There are multiple ways of defining this and I haven’t found one I like a lot. For now I’m using the simplest approach:

1. Equatorial faces: north is constant
2. North pole face: north points towards the center
3. South pole face: north points away from the center

function northVectorAt(faceId, orientation, x, y, maxLength) {
    let v = [maxLength * Math.sin(Math.PI/2 * orientation),
             -maxLength * Math.cos(Math.PI/2 * orientation)];
    if (faceId >= 4) {
        let sign = faceId === 4 ? -1 : +1;
        v = [sign * (x - TILES_PER_SIDE/2), sign * (y - TILES_PER_SIDE/2)];
        v = v.map(w => w * Math.min(1, maxLength/Math.hypot(v[0], v[1])));
    }
    return v;
}

However there are discontinuities between the polar and equatorial faces. I also tried a different approach but it also had discontinuities. I decided what I had was good enough. The main goal is to demonstrate procedural generation on a cube/sphere, and the problem I’m solving right now is to add compass directions to avoid getting disoriented. I find myself often going down random tangents, and it’s useful to keep my goal written down on a sheet of paper so that ask myself: am I working towards my goal? is what I have good enough to meet my needs? These compass directions work well enough.

 7  Room graph#

Something I didn’t explore this time is the room graph. The door algorithm makes connections between adjacent rooms. By keeping track of which rooms are connected, we produce a room graph:

This could be used for:

• removing unreachable rooms
• merging adjacent corridors
• removing corridors to nowhere
• removing some doors to increase branching and dead ends
• large scale analysis and restructuring

 8  More#

The goal of this short “game jam” style project was to learn how to work with grid maps on a sphere. I think I’m happy with how that went. The secondary goal was to learn how to make dungeon maps. There are lots of different techniques, and I think what I did worked reasonably well for a first attempt, but there are so many things to add.

• add items to the world, using the room graph structure
  • monsters
  • treasures
  • keys & locks
• field of view
• mix indoor and outdoor maps

I have never implemented grid FOV and I don’t understand the algorithms well enough to adapt them to this coordinate system. Instead, I could make each room visible when you walk into it. That’s what the original Rogue did^[2].

I’m glad I was able to meet my primary goal. Last week I learned about cube/sphere geometry and this week I put it to use. The rest of these features would be nice but aren’t necessary, so I don’t want to spend a lot more time on them here. It’s time to move on to another project.

If you want to poke around in the messy code, it’s here: planetary-dungeon.js