Development Hello

When I started work on SilverQuest: Gaiden, it used a dungeon generator heavily based on a GameMaker example created by YellowAfterlife. It works well but it is poorly commented. It’s also cleverly coded making it even harder to follow unless you already know what it does. I’ll try to remedy that below.

In broad strokes, the steps of this dungeon generator are:

• Generate a Maze
• Prune Dead Ends
• Loop Dead Ends
• Add Rooms

Generate a Maze

How is the maze generated? The original example uses a variant of the Hunt-and-Kill algorithm with variable inertial bias.

In a nutshell, it works like this:

1. Choose a starting location.
2. Perform a random walk, carving passages to unvisited neighbors, until the current cell has no unvisited neighbors.
3. Enter “hunt” mode, where you scan the grid looking for an unvisited cell that is adjacent to a visited cell. If found, carve a passage between the two and let the formerly unvisited cell be the new starting location.
4. Repeat steps 2 and 3 until the hunt mode scans the entire grid and finds no unvisited cells.

So what is inertial bias? When selecting a random direction, it will favor the direction it is already moving in. This has the effect of creating corridors with long, straight sections.

In the generation of the maze, the algorithm uses an array to represent the individual cells of the maze. They are not quite the same as the pixels you see in the first image. Rather they are nodes in a graph where each node represents connectivity to neighboring nodes. This information is encoded with a binary scheme where each of four bits represents a cardinal direction, ie. Up (1), Down (2), Right (4), and Left (8). The sum of these bits is a number stored in the node. The actual example uses different bits and stores additional information in other bits but the image below should help demonstrate the concept.

Prune Dead Ends

The next step is the pruning of dead ends. Wherever there is a node which is a dead end (meaning it has only one bit of connectivity), remove it. When this happens also clear the relevant connectivity of the neighboring node. This stage is repeated until the maze has the desired sparseness.

Loop Dead Ends

Now the example attempts to connect any remaining dead ends with neighboring nodes. Wherever it finds a dead end end, it checks if there are any immediate neighbors which are open and traversable. If there are, it selects one at random to connect to. This fills the maze with loops, making it much more interesting, especially in a tactical roguelike setting.

Add Rooms

The final stage is the adding of rooms. Rooms are added one by one. First their dimensions are selected from a random range. Then begins the most computationally expensive part of the process. For every node in the maze, an area the size of the room is measured. Each node has a weight and the sum of all of them within the room area represents a score value. Each node which is part of a corridor (ie. has some connectivity with another node) has a weight of one. Each node flagged as part of a room has a weight of 100. Whichever position in the node graph has the lowest score is the position where the room is placed and the nodes encompassed by the room are flagged as room nodes. This ensures that the rooms gravitate towards empty parts of the maze where corridor and room densities are lowest.

The dungeon generation is now complete. At this point, the example uses the final array of nodes to spawn wall objects into the game and place the player in the first generated room. Now the player is permitted a chance to wander a lonely, vacant dungeon and that is the extent of the example.

SilverQuest: Gaiden follows this same dungeon generation procedure with one major difference. It switches the last two steps, placing the rooms before connecting the dead ends. This gives dead ends a better chance of connecting into loops because rooms and corridors are treated equally and thus there are more opportunities for connections.

Next time I will go into the ways this was extended and the problems encountered with this approach.