Development Blog 1 - Procedural Content Generation and Maze Generation
Project Outline
The project intends to demonstrate an implementation of Procedural Content Generation (PCG) algorithms in the context of gaming.
The project will showcase research of existing implementations of different PCG algorithms, the considerations behind the choice of PCG algorithms used in the project and finally the details behind the projects core PCG algorithms in producing a game loop.
Maze Generation Algorithm Research
The first PCG algorithm decided upon for research was a maze generation-based algorithm. Maze generation has a long history of implementation in video games, allowing for the creation of structured environments with changing geographic layouts and content. This provides increased replayability vs a non-procedural maze as players are presented with seemingly new environments for exploration.
However, this raises the question regarding the “fun” factor that Procedural Generation can provide a player – bad procedural content can come across just as repetitive as a static level. This topic is worth exploring a further time. (See Week Four).
There exist many types of Maze generation algorithms, with each having various strengths and weaknesses. In the paper presented by Vijaya et al. (2024) they look at three maze generation algorithms and compare them. These algorithms are Depth-First Search, Prim’s Algorithm, and Recursive Division.1
For this projects research, Depth-First Search (DFS) was selected as an algorithm to implement in a practical demonstration considering the conclusions drawn by Vijaya et al. (2024) that DFS achieves the best results for player engagement, variability of the maze structure and the practical implementation computational. 2
The work by Kozlova, Brown, and Reading (2015) notes in their conclusion of comparison of DFS, Prim’s Algorithm, and Recursive Division, that they advise to using DFS as it produces winding pathways and longer path length then comparable Maze Generation algorithms. 3
A DFS algorithm provides suitability for traversing a grid of points generating a connected and branching path along all nodes within the grid. Furthermore, its easy-to-understand functionality contributed well to quick implementation for demonstration.
Tutorialspoint provides a clear explanation and walkthrough of the DFS algorithm, with the following three rules dictating the function of the algorithm. 4
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.
Figure 1: Visual representation of Depth-First Search traversal.
Source: Tutorialspoint, n.d. 5
This project's implementation can be found on GitHub.6
Below you can find a video demonstrating the DFS running in the Unity Editor.
Figure 2: Video demonstration of Depth-First Search traversal. Source: DodginJam, 2024. Lecture One Weekly Assignment. Available at: https://www.youtube.com/watch?v=YourVideoID [Accessed: 7 December 2024].7
The principles demonstrated in Figure 1 can be seen demonstrated in the video demonstration. The tiles represent the vertices of a grid, which in this instance was set to a 20 x 20 size. The two numbers layered on each tile represent the coordinates. The path drawn by the DFS algorithm can be seen by the lines forming over the tiles.
The colours of the tile represent the state of the tile / vertices in relation to the algorithm. If a tile has not be visited, it is coloured white. A visited tile is initially coloured green, whilst a tile that has been back-tracked over appears red. These features visualise the paths taken by the algorithm.
Conclusion
The randomised structure of the maze, if combined with further randomization, such as a replacement of the tiles with explorable (perhaps internal differing) rooms demonstrates the strength of Maze Generational algorithms for creating re-playability game spaces. The suitable for DFS has been demonstrated for its computational performance and sufficiently variability catering towards player engagement.
As a result, this method has consideration for usage in this project moving forward.
References
J. Vijaya, A. Gopu, K. V. S. G. Vinayak, T. J. Singh and K. Malhotra, "Analysis of Maze Generation Algorithms," 2024 5th International Conference on Innovative Trends in Information Technology (ICITIIT), Kottayam, India, 2024, pp. 1-6, doi: 10.1109/ICITIIT61487.2024.10580178.
J. Vijaya, A. Gopu, K. V. S. G. Vinayak, T. J. Singh and K. Malhotra, "Analysis of Maze Generation Algorithms," 2024 5th International Conference on Innovative Trends in Information Technology (ICITIIT), Kottayam, India, 2024, pp. 1-6, doi: 10.1109/ICITIIT61487.2024.10580178.
A. Kozlova, J. A. Brown and E. Reading, "Examination of representational expression in maze generation algorithms," 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan, 2015, pp. 532-533, doi: 10.1109/CIG.2015.7317902.
TutorialsPoint, n.d. Depth First Traversal (DFS) - Data Structures & Algorithms. [online] [Accessed 5 December 2024]. Available at: https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
Tutorialspoint, n.d. Depth First Traversal (DFS) - Data Structures & Algorithms. [online] [Accessed 5 December 2024]. Available at: https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm
DodginJam (2024) Lecture One Weekly Assignment. [online] [Accessed: 7 December 2024]. Available at: https://github.com/DodginJam/Lecture-One-Weekly-Assignment
DodginJam, 2024. Depth First Search Implementation. [Accessed: 7 December 2024]. Available at: https://youtube.com/shorts/XqZhZ3aoZfY?si=vxHpIB7mXfOe1iAm