Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Computer Games Design

Adventures in Procedural Content Generation - Adam Speers

Dungeon Generator: Part 7

Unity - Implementation

The dungeon generator utility, is controlled within a Unity scene by first creating an empty game object and adding the MazeGeneratorExtended script.

This script requires the completion of several key variables:

• Width – desired maze width in cells

• Height – desired maze length in cells

• Tile width – base floor dimension of the prefab tiles in unity units

• No rooms – the number of rooms to try and create

• No loops – the number of loop paths to try and create

• No sections – desired number of gated sections 2 – 4

It is required to add a companion script NodeGridExtended, this script holds references to the scriptable objects, which are used to lookup the correct tile type, rotation and associated Prefab.

• TileMatchExtended - Lookup for matching the tile type

• TileTypeMatchSimple - Lookup for matching tile type to Prefab

Please see (Figure 7.1, 7.2, 7.3) for examples of these scripts inspection windows completed with information from the prototype.

Figure 7.1: Inspector window

Figure 7.2: Tile Type Match

Figure 7.3: Tile Type Prefab


Process Overview

The dungeon generator utilises 5 key scripts in its implementation which can be found in the code repository (available here):

• MazeGeneratorExtended.cs

• Node.cs

• NodeGridExtended.cs

• TileMatchExtended.cs

• TileTypeMatchSimple.cs

Together these scripts perform a number of process steps in order to generate a dungeon. (Figure 7.4)

Figure 7.4: Process Overview


Process 1: Generate Maze

The first stage in the process (Figure 7.5) is creating the base structure for the dungeon, this is formed of a maze generated using a recursive backtrack algorithm. Further algortihm information can be found in Dungeon Generator: Part 2.

Summary:

1. From the chosen starting point.

2. Randomly choose a neighbour and carve a passage through to that cell, but only if the neighbour has not been visited yet. This becomes the new current cell.

3. If all neighbour cells have been visited, back up to the last cell that has unvisited neighbours and repeat.

4. The algorithm ends when the process has backed up all the way up to the starting point.

Code:

This process calls the following methods: contained within MazeGeneratorExtended.cs

• GenerateMaze() - Lines 60-76

• CreateMaze() - Lines 78-110

• GetValidNeighbours(CurrentTile) - Lines 115-141

• HasThreeWallsIntact(Vector2 Vector2ToCheck) - Lines 467-487

• IsInside(neighborToCheck) - Lines 489-492

Figure 7.5: Generate Maze


Process 2: Make Rooms

Summary:

The designer may have requested that rooms be created. Rooms are created by identifying candidates in the maze data grid. To qualify a cell must be surrounded on three sides (checking the four cardinal directions) by paths. Qualifying cells are added to a candidates pool. A check is made to ensure the requested number of rooms does not exceed the number of candidates, if the number requested is greater, it is capped at the number possible. The requested number of candidates (or maximum possible) are then randomly selected from the pool and changed into paths; these cells now form larger open areas.

Code:

This process calls the following methods contained within MazeGeneratorExtended.cs

• SaveEndCaps() - Lines 494-512

• HasThreePaths(Vector2 Vector2ToCheck) - Lines 532-552

• MakeRooms() - Lines 514-530

Figure 7.6: Make Rooms


Process 3: Node Grid

Summary:

This process uses the scripts Node.cs and NodeGridExtended.cs to expand on the maze grid previously created. It begins by building a Nodegrid, an array of Nodes holding rich information about each cell in the dungeon, initially it records:

• public bool walkable;

• public Vector3 position;

• public int gridX;

• public int gridY;

Code:

This process calls the following methods:

• GetDepthMap() - Lines 234-238 (MazeGeneratorExtended.cs)

• CreateNodeGrid() - Lines 35-49 (NodeGridExtended.cs)

• Node() - Lines 26-32 (Node.cs)

Further information about information maps can be found in this blog post (Dungeon Generator: Part 3).

 

 

Figure 7.7: Node Grid and Nodes


Process 4: Pick Tile

Summary:

This process uses NodeGridExtended.cs and the scriptable Object references held for TileMatchExtended.cs and TileTypeMatchSimple.cs. A detailed description of this process can be found in the previous blog post (Dungeon Generator: Part 6).

1. For each node in nodegrid.

2. Create a local variable for each direction neighbour.

3. For each neighbour offset, read tile in nodegrid and assign local variable based on value of walkable, if requested offset location is outside grid walkable is false.

4. Read the scriptable object for tile matching using local variables direction neighbour walkable value. Store rotation and tiletype

5. Read the scriptable object for tile type and store the Prefab.

Code:

This process calls the following methods:

• PickTile() Line 111-251 (NodeGridExtended.cs)

Figure 7.8: Pick Tile


Process 5: Calculate Depth Map

Summary:

This process calculates a depthmap for the entire nodegrid. Further information about depth maps and pathfinding can be found in this blog post (Dungeon Generator: Part 3).

1. From the starting position set depth to 0. Set to current node.

2. Find each walkable neighbour.

3. For each unexplored neighbour (Add to closedset). set distance to current distance + 1, Store a reference to the neighbours parent.

4. Add explored neighbour to queue for exploring its neighbours.

5. Continue until all walkable nodes have been explored.

Code:

This process calls the following methods:

• NodeGridCalcDepth(Vector3 startPos) Line 71-109 (NodeGridExtended.cs)

 

Figure 7.9: Calculate Depth Map


Process 6: Max Distance

Summary:

This process follows on from the depth map calculation and parses the node grid to identify the maximum distance from the start position. This max distance value can be used to identify a logic exit for the dungeon as discussed in (Dungeon Generator: Part 3).

1. Set maximum distance to 0.

2. For each node in node grid.

3. Test to see if the node is walkable

4. If walkable, is the node distance > current max distance. If greater set the maximum distance = node distance.

5. Continue until all walkable nodes have been explored.

Code:

This process calls the following methods:

• maxDist() Line 71-109 (MazeGeneratorExtended.cs)

Figure 7.10: Max Distance


Process 7: Set Start Node

Summary:

This simple process parses the node grid and identifies the start node, it stores this as a seperate reference for later use in Process 9: Parent Path.

Code:

This process calls the following method:

• selectStart() Line 158-168 (MazeGeneratorExtended.cs)

Figure 7.11: Set start node reference


Process 8: Select Finish

Summary:

This is process parses the node grid and identifies any node whose distance from the start = maximum distance calculated in Process 6. These nodes are stored into 2 lists. Those that have the tile type "tile_end" into list finishPathsEnd and everything else into finishPaths. If there are candidates in list finishPathsEnd select a node at random and set it to be the finish. Otherwise select select a node at random from finishPaths and set it to be the finish. 

Code:

This process calls the following method:

• selectFinish() Line 170-207 (MazeGeneratorExtended.cs)

 

Figure 7.12: Select Finish


Process 9: Parent Path

Summary: 

This process performs a walk through the node grid starting with the finsh node identified in Process 8. The walk will continue to move through the grid by selecting each nodes parent in turn, until it has reached the start node. Each node it passes through is flagged as forming part of the critical path. This critical path can then be used to implement bottlenecks and challenges as discussed in (Dungeon Generator: Part 1).

Code:

This process calls the following method:

• ParentPath(Node startNode, Node endNode) Line 680-696 (MazeGeneratorExtended.cs)

Figure 7.13: Parent Path


Process 10: Setup Obstacles

Summary:

This process uses the critical path created previously in Process 9. And uses this information to create bottlenecks. These are required to implement the desired three-act structure as discussed in (Dungeon Generator: Part 1).

1. Read the number of sections required - default is 3 max 4

2. If the number required is > 1.

3. Calculate desired obstacle position (obstacleInterval = endNode.distance / noSections). int obstacle1 = obstacleInterval; int obstacle2 = obstacleInterval * 2; int obstacle3 = obstacleInterval * 3;

3. Create a new list straights and add nodes from the Mazepath with tile type "tile_straight".

4. Setup obstacle 1: Foreach node in list straights, if the nodes distance = obstacle1. Set node variables: hasDivider = true; hasObstacle = true; section = 1; obstacle1set = true; section1Node = straights.node;

5. If the nodes distance <> obstacle1 set obstacle1 = obstacle1 - 1 and repeat step 4.

6. Repeat steps 4 & 5 as required for the remaining sections.

Code:

This process calls the following method:

• SetupObstacles() Line 240-323 (MazeGeneratorExtended.cs)

Figure 7.14: Setup Obstacles


Process 11: Set Section Identifiers

Summary:

This process uses a similar method to the parent path, it's purpose is set the section number identity for each node. The method always begins with the endnode of the maze and walks back towards the start. The walk will continue until it has found all the members of a section. Sections end at the next bottleneck encountered or the startnode.

The identification of each sector, allows for the implemention of solutions to obstacles. This forms another part of the desired three-act structure as discussed in (Dungeon Generator: Part 1).

Code:

This process calls the following methods:

• CreateSections() Lines 325-348 (MazeGeneratorExtended.cs)

• NodeGridSetSection(Vector3 startPos, int section) Lines 622-657 (MazeGeneratorExtended.cs)

Figure 7.15: Set section identifiers


Process 12: Create loop paths

Summary:

This process creates addition loop paths (braids) within the dungeon. These are desired in order to encourage additional exploration and aid the illusion of player choice. The assignment of section identities in the process 11, allows constraint when creating loop paths. The code will only form new corridors between members of the same section, this preserves the bottlenecks previously created. Futher information about identifying braid candidates can be found in (Dungeon Generator: Part 2). 

Code:

This process calls the following methods:

• SaveNodeLoopCandidates() Lines 553-591 (MazeGeneratorExtended.cs)

• MakeNodeLoops() Lines 592-610 (MazeGeneratorExtended.cs)

 

 

Figure 7.16: Make loop paths


Process 13: Make dividers

Summary:

This process parses through the newly created loop paths and if a newly created loop has tile type "tile_straight" sets a variable in the node information map for for having a divider. These divider indicators can subsequently be used to spawn in addition geometry, providing additional variation to the dungeon, such as a wall, archway or destructible object.

Code:

This process calls the following method:

• MakeLoopsDividers() Lines 612-621 (MazeGeneratorExtended.cs)

Figure 7.17: Make loop dividers


Process 14: Make Solutions (Keys)

Summary:

This process identifies a cell within a section as a candidate for spawning a solution to an obstacle. The player will be required to find / interact with this object before they can proceed past the bottleneck. In the prototype dungeon scene (MazeTesting) this is demonstrated using a system of locked doors and keys.

1. For each section prior to last section

2. Identify 2 lists of candidate nodes, keysNonCritTemp and keysCritTemp. The difference being cells that are also on the critical path.

3. If keysNonCritTemp count > 0 select a node at random and set hasKeyItem = true.

4. Else If keysCritTemp count > 0 select a node at random and set hasKeyItem = true.

Code:

This process calls the following method:

• MakeKeyHolders() Lines 700-750 (MazeGeneratorExtended.cs)

Figure 7.18: Make Keys


Process 15: Spawn Dungeon

Summary:

This process is the culmination of all the previous steps. The system parses through the node grid and for each tile spawns the appropriate Prefab(s). If the debug switches are selected within the editor (Figure 7.1) the system will also spawn addition information into the scene:

Debug Information

• Distance text

• Section text

• Tile type indicator (Coloured)

• Breadcrumb (Critical path)

Prefabs

• Tile

• Divider

• Wall + Door

• Key

Figure 7.19: Spawn Maze