Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Dungeon Generator: Part 2

Maze Algorithms

The first step in creating the dungeon generator is to choose an algorithm which will produce a perfect maze. A maze is considered perfect when every cell can reach every other cell by exactly one path (Buck, 2015, p. 5; Tulleken, 2016). For clarity, the system will generate a maze rather than a labyrinth (Figure 2.1). A labyrinth is a unicursal maze, In which a perfect maze is formed by a single passage with no junctions, as such there is no scope for exploration beyond the designated path (H.urna, 2019).

Three algorithms that produce perfect maze's will be assessed against a set of desired attributes (see below), one will then be selected for the dungeon generators development, this algorithm will then be enhanced into a partial-braid maze.

Figure 2.1: Comparison of a labyrinth and a maze. The labyrinth has only one path from a to b, the maze offers choices along the way.

From a mathematical point of view, an ideal algorithm would produce each possible maze with equal probability, which is called an unbiased algorithm (Tulleken, 2016). The opposite of a perfect maze is a braid maze. These differ from perfect mazes by having fewer dead ends and having passages that connect to form loops. Moving between cells in a braid maze can sometimes be accomplished by using multiple paths, allowing paths to intersect themselves can open up exciting new ways for the game to be played (Buck, 2015, pp. 5, 129). And if the maze offers generative or emergent paths, it can also lead to a different player experience each time the dungeon is generated (Smed & Hakonen, 2017, p. 90).

A maze also provides the experience of problem solving and is very well suited for use in games involving exploration. They have traditionally been used within an education setting to help develop these skills (H.urna, 2019):

• Planning and brainstorming strategies.

• Spatial representation and developing orientation.

• Scanning complex environments and memorizing paths.

• Relaxing.

Desired Maze Attributes

Mazes may be classified using seven different attributes: Dimension, Hyper-dimension, Topology, Tessellation, Routing, Texture, and Focus (Pullen, 2015). Using this maze classification system (available here), the following subset of attributes, have been selected, that will produce results desirable for the dungeon generator when evaluated against the level design rules.

Dimension: 2D - most mazes are this dimension, in which it's always possible to display the floor plan on a sheet of paper and navigate it without overlapping any other passages in the maze (Pullen, 2015).

Normal Topology - a standard maze in Euclidean space (Pullen, 2015).

Orthogonal Tessellation - a standard rectangular grid where cells have passages intersecting at right angles (Pullen, 2015).

Partial braid routing - a mixed Maze (Perfect, Braid) with both loops and dead ends in it. The term braid can be used quantitatively, in which a "heavily braid Maze" means one with many loops or detached walls, and a "slightly braid Maze" means one with just a few (Pullen, 2015).

River texture - the algorithm will look for and clear out nearby cells to the current one being created, i.e. it will flow (hence river) into uncreated portions of the Maze. A perfect Maze with less river will tend to have many short dead ends, while a Maze with more river will have fewer, but longer dead ends (Pullen, 2015).

Passage carver focus - algorithms that focus on passages start with a solid block and carve passages. Examples of a real-world passage carver could be a maze composed of mine tunnels, or within a network of pipes (Pullen, 2015).

Rooms - mazes that produce U bends, a path formed around a wall or corridor make good candidates for opening up larger spaces. The wall can be removed joining the surrounding paths into an open space.

Choosing a maze algorithm:

There were numerous maze generator algorithms available to learn from (Buck, 2015; H.urna, 2019; Tulleken, 2016). Three prototypes have been created using the following algorithms (Binary tree, Sidewinder, Recursive backtracker) and the results assessed against the list of desired attributes.

Binary Tree Algorithm

For each cell in the grid, a random binary operator decides whether to carve a passage north or west.

Steps: For each existing cell in the grid:

1. Get, if they exist, north or west neighbours.

2. Randomly pick one and connect with it.

Figure 2.2: Binary Tree maze showing diagonal bias from upper left to lower right. Braid candidates are red dots. Room candidates are blue dots.

Assesment: Binary tree mazes differ from standard perfect mazes since about half the cell types can never exist in them. For example, there will never be a crossroads, and all dead ends have passages pointing either down or right, and never up nor left.

The resulting maze always displays a diagonal bias from upper left to lower right, where the maze is much easier to navigate from the lower right to the upper left. In these mazes you will always be able to travel up or left, but never both. Then, leading to the top left corner, you can always deterministically travel diagonally up and left without encountering any barriers to reaching the exit. Finally, two of the four sides of the maze will be spanned by a single corridor due to its directional construction. The directional bias inherent in the binary tree algorithm makes this candidate undesirable for the dungeon generator, as solutions can be easily predicted.

This type of maze does display characteristics that would make braiding simple. Any dead-end cell within the maze (not on an edge) can be used to identify a candidate for forming a loop:

• Walls to the east, west and south - extended to the south to form a loop.

• Walls to the north, east and west - extended to the east to form a loop.

This type of maze also displays characteristics for making rooms.

• A wall with paths to the north, west, and east - remove to form a room.

• A wall with paths to the north, south, and west - remove to form a room.


Sidewinder Algorithm

The Sidewinder Maze Generator is slightly more complicated than the Binary Tree algorithm. The Sidewinder algorithm only needs to consider the current row, and therefore can be used to generate infinitely large mazes (like the Binary Tree).

While binary tree mazes have two of four sides formed by long passages, a Sidewinder maze has just one long passage.

Steps: For each row in the grid:

1. For each cell randomly decide whether to carve a passage leading East

   a. If the passage is carved add the cell to the current run set

   b. If the passage is not carved, randomly pick one cell from the route set, carve a passage leading North and empty the current run set

Figure 2.3: Sidewinder Maze showing bias along the north passage. Braid candidates are red dots. Room candidates are blue dots.

Assesment: Mazes generated by this Sidewinder algorithm will never have any North-facing dead-ends, which means the player can never get stuck when moving from south to north. This is like the Binary Tree algorithm, which will never have any dead ends in the direction of its bias. A sidewinder maze tends to have an easy solution, where the east path is straightforward, but many long false paths are present, leading down from the north path. The solution is deterministic without error from bottom to top: it will never double back on itself or visit a row more than once, although it will wind (or wave) from side to side. The directional bias inherent in the sidewinder algorithm also makes this candidate undesirable for the dungeon generator, as solutions can always be found by exploring all branches of north passage.

This type of maze also displays characteristics that would make braiding simple. Any dead-end cell within the maze (not on an edge) can be used to identify a candidate for forming a loop:

• Walls to the east, west and south - extended to the south to form a loop.

• Walls to the north, east and west - extended to the east to form a loop.

• Walls to the north, west and south - extended to the west to form a loop.

This type of maze also displays characteristics for making rooms.

• A wall with paths to the north, west, and east - remove to form a room.

• A wall with paths to the north, south, and east - remove to form a room.

• A wall with paths to the north, south, and west - remove to form a room.


Recursive Backtracker

A recursive backtracker or Depth First Search (DFS) maze generator is a randomized version of the depth-first search traversal algorithm. Implemented with a stack, this approach is one of the simplest ways to generate a maze. It starts at any cell and explores as far as possible along each branch before backtracking. To generate a maze, the algorithm must randomize the traversal, meaning it picks a random but unvisited neighbour to continue. When it encounters a dead end (a cell with no unvisited neighbours), it will backtrack to the most recent cell in the stack.

Steps: Choose a starting cell and add it to the stack. While there is a cell to be handled in the stack:

1. Pop cell from the top of the stack.

2. Connect and visit all available unvisited neighbours from the bottom, left, right and top.

3. Randomly select the one to be on the top and push those neighbours on the stack.

Figure 2.4: Recursive back tracker maze showing no directional bias. Braid candidates are red dots. Room candidates are blue dots.

Assesment: Mazes generated using this algorithm have a low branching factor and so contain many long corridors. The algorithm explores as far as possible along each branch before backtracking. This algorithm produces the desired river characteristic when creating the maze. DFS mazes tend to have a main River, resulting in a large amount of short dead ends. All of this makes depth-first an excellent candidate algorithm for the dungeon generator. In mazes generated by this algorithm, it will typically be relatively easy to find the way back to the start (or critical path) since most paths lead to or from there, but it is hard to find the way out. This algorithm does not introduce any directional bias. 

This type of maze also displays characteristics that would make braiding simple. Any dead-end cell within the maze (not on an edge) can be used to identify a candidate for forming a loop:

• Walls to the east, west and south - extended to the south to form a loop.

• Walls to the north, east and west - extended to the east to form a loop.

• Walls to the north, west and south - extended to the west to form a loop.

• Walls to the south, west and eash - extended to the north to form a loop.

This type of maze also displays characteristics for making rooms.

• A wall with paths to the north, west, and east - remove to form a room.

• A wall with paths to the south, west, and east - remove to form a room.

• A wall with paths to the north, south, and east - remove to form a room.

• A wall with paths to the north, south, and west - remove to form a room.

Conclusion

The recursive backtracker algorithm was assessed to be the best fit for the dungeon generator. The bias’s inherent in both the binary tree and sidewinder algorithms produced mazes where the player could potentially anticipate the route to the exit. This could be mitigated, however, through the application of bottlenecks as discussed in Dungeon Generator: Part 1. Bottlenecks may be utilised to encourage additional exploration along branching paths. Whilst none of the three algorithms produce the desired partial braiding characteristic, without modification. It would be simple to extend these algorithms to create the desired looping paths. It is also desirable to be able to easily create larger spaces, all three algorithms created the surrounded wall end pattern necessary for easily creating rooms. However, the recursive backtracker algortihm was the only candidate, to produce the loop and room matching patterns in all four directions.

Overall the recursive backtracker produces the most satisfying maze, without directional bias, showing a strong river characteristic and providing the best opportunities for further modification.

References

Buck, J. (2015). Mazes for programmers : code your own twisty little passages. Dallas: The Pragmatic Bookshelf.

H.urna, H. (2019). Maze generations: Algorithms and Visualizations. Available at: https://medium.com/analytics-vidhya/maze-generations-algorithms-and-visualizations-9f5e88a3ae37 (Accessed: 01 December 2019).

Pullen, W. D. (2015). Maze Classification. Available at: http://www.astrolog.org/labyrnth/algrithm.htm (Accessed: 08 January 2020).

Richards, E., (2017). Mazes in C#. Available at: http://richardssoftware.net/Home/Post/73 (Accessed: 08 January 2020).

Smed, J. & Hakonen, H. (2017). Algorithms and Networking for Computer Games. New York: John Wiley & Sons.

Tulleken, H. (2016). Algorithms for making more interesting mazes. Available at: https://www.gamasutra.com/blogs/HermanTulleken/20161005/282629/Algorithms_for_making_more_interesting_mazes.php (Accessed: 03 December 2019).