Dungeon Generator: Part 3
Pathfinding, Depth Maps and Information maps
The dungeon generator requires inputs for the desired length and width of the initial maze to be generated. For this blog article and explanation, dimensions of 9 x 9 are used.
After the initial stage of the dungeon generator has run (Recursive backtracker), the algorithm has generated a grid array of co-ordinates (Figure 3.1) and associated walkable values (Figure 3.2):
The generated sample maze (Figure 3.2) used x, y co-ordinates [1,1] as the starting point. Then there is the question, where to logically place the exit?.
The following options were considered:
1. Approximate middle of the maze
2. Cell furthest away on the diagonal from start
3. Cell that is the furthest walk distance from the start
4. A random walkable location
It was initially decided, for ease of prototyping, to use option 2. Implementation of a pathfinding algorithm, to display on the maze, the shortest path to the exit from the start was investigated. This information would also allow for placement of obstacles and challenges in the player’s path.
Pathfinding research identified several candidate algorithms:
• Breadth First Search (BFS) – Beginning at the root (start cell), explore all its children in the next level(neighbours) before moving to each of the root children, and then, it explores the children of the root children, and so on. The algorithm uses a queue to perform the BFS (Elgabry, 2016; Patel, 2016; TheHappieCat, 2017).
• Depth-first search (DFS)- Another way to traverse a grid, starting at the root (start cell) and exploring one of its children’s sub tree, explores as far as possible along each branch before, moving to the next child’s sub tree, and so on. It uses stack, or recursion to perform the DFS (Elgabry, 2016; Patel, 2016; TheHappieCat, 2017).
• Dijkstra's algorithm - Keeps track of the total cost (walk distance) from the root (start cell) to every cell that is visited and uses it to determine the best order to traverse the grid. Works with weighted grids and returns the shortest path but might involve a lot of searching. This variant uses a single cell as the root and finds shortest paths from the root to all other cells in the grid (Buck, 2015, p. 42) (Elgabry, 2016) (Patel, 2016) (TheHappieCat, 2017).
• A* algorithm - Similar to Dijkstra but implements a heuristic to estimate how close each node is to the goal, in order to make the best decision. Because of this heuristic, A* finds the shortest path in a weighted grid in a much timelier manner (Elgabry, 2016; Lague, 2014; Patel, 2016).
Research was initially undertaken on the Dijkstra algorithm as described in Jamis Bucks – Mazes for programmers (Buck, 2015, pp. 36-37) and viewing Youtube videos regarding how others had implemented these algorithms within Unity (Lague, 2014; TheHappieCat, 2017).
This was a video by TheHippieCat describing BFS and DFS, which demonstrated that a DFS algorithm was not always guaranteed to return the shortest path. This highlighted that it could be beneficial to explore every node and know all paths, not only the shortest path. The second video in the series described Dijkstra’s algorithm and provided an excellent solution to finding the shortest path. For the purposes of the dungeon generator, which produces an unweighted maze, the BFS approach would always provide the shortest path with the simplest implementation.
This is a popular video series, by Sebastian Lague, explaining an A* implementation within Unity. The games industry widely regards A* implementation as the optimal pathfinding solution (Popovici, 2017). A* is an improvement on Dijkstra’s algorithm as it adds a distance to target heuristic, which is used to bias the future walk path. In this way, it is always trying to optimise for shortest distance.
It was decided to follow the steps for Sebastian Lague’s A* algorithm as research showed this to be the fastest method (Lague, 2014; Patel, 2016; Popovici, 2017). His approach, creating a node for each element in the grid as a separate class and containing additional information about that node, e.g. distance from start; x,y position, parent node and walkability. Was considered to be very useful.
At this point it became clear that storing and making available, extra information about each cell in the maze would provide more utility than simply finding the shortest path. It was decided to combine the exploration technique from TheHippieCat BFS method (TheHappieCat, 2017) with Sebastian Lague’s node creation (Lague, 2014). TheHippieCat method would ensure all cells were visited in the desired order. The node creation method would ensure that all pertinent information was recorded for further use. The synthesis of these two techniques would provide a detailed and useful information map of the maze. Furthermore, should the procedural technique generate a particularly interesting maze, saving the node grid created for this maze would allow it to be exactly reproduced. This would prove useful for a designer; they could generate hundreds of mazes and white list those of interest for inclusion in a game. This technique of white listing was used by the creators of Spore for their procedural planet generator (Compton, 2017).
The Node class within the dungeon generator holds the rich information map for each tile (Cell in the grid) it contains the following information:
• public bool walkable;
• public Vector3 position;
• public int gridX;
• public int gridY;
• public int distance;
• public float tileRotation;
• public bool criticalPath;
• public GameObject tilePrefab;
• public Node parent;
To visualise this new information in the prototype, floating text elements were added above each cell and colour coded to give addition visual feedback to the designer.
Red - Max Distance Cell
Blue - Dead ends
Yellow - T Junctions
Green - Crossroads
Each of the researched pathfinding techniques are designed to provide a solution for finding the shortest path from point A to B. Through investigation it was determined that the requirement for locating the exit, was best fulfilled by building an information map of the entire maze.
Using this information map, placement of the exit for the maze on the longest path seemed like the best fit in order to encourage exploration of the maze (Figure 3.3). The furthest cell could now be identified by returning ‘maxdistance’ from the node class collection. In addition, the path back to the start could be returned (Figure 3.4). To help visualise this new information, the cells’ walk distance text was colour coded to give feedback to the designer within Unity. This depth map would also provide the information required to implement a three-act structure and fulfil the specified design goals as discussed in Dungeon Generator: Part 1.
Buck, J. (2015). Mazes for programmers : code your own twisty little passages. Dallas: The Pragmatic Bookshelf.
Compton, K. (2017). Practical Procedural Generation for Everyone. San Francisco, GDC 2017.
Elgabry, O. (2016). Path Finding Algorithms. Available at: https://medium.com/omarelgabrys-blog/path-finding-algorithms-f65a8902eb40 (Accessed: 20 October 2019).
Lague, S. (2014). A* Pathfinding (E01: algorithm explanation). Available at: https://www.youtube.com/watch?v=-L-WgKMFuhE (Accessed: 01 October 2019).
Patel, A. (2016). Introduction to the A* Algorithm. Available at: https://www.redblobgames.com/pathfinding/tower-defense/ (Accessed: 01 October 2019).
Popovici, A. (2017). Pathfinding in games. Available at: https://www.slideshare.net/popoviciadrian1/pathfinding-in-games (Accessed: 01 October 2019).
TheHappieCat (2017). How to Do Pathfinding: The Basics (Graphs, BFS, and DFS in Unity). Available at: https://www.youtube.com/watch?v=WvR9voi0y2I (Accessed: 01 October 2019).