Development Log 11 - Furthering Procedural Content Research Post-Project
Idea Formulation
With the focus of the project to date revolving around Mesh generation in the pursuit of creating a terrain like surface, and having largely achieved that, any further Procedural Algorithms should help provide further contextualisation of the game world.
Two procedural-centric ideas are proposed for implementation into the project – Object Placement and Path Carving.
Object Placement
Adding objects onto the terrain would further visually advance the re-production of terrain – be it grass, trees or rocks it would create a more immersive world.
The placement of objects procedurally on the surface of the mesh requires a way of determining the maximum and minimum distance required for placing around a given point. In his video [Unity] Procedural Object Placement (E01: poisson disc sampling), Lague (2018) highlights practical implementation of this in Unity. 1
A requirement for object placement onto a terrain requires aligning relevant objects to the surface of the mesh. The video by NULL (2022) provides insight for finding the gradient of the slope of a mesh and ensuring that objects placed there have the same rotation as the ground. 2
Pathway Carving
The ability to create a pathway throughout the terrain requires an algorithm to create a path from a given start position to an end position, therefore it is of this projects determination that a pathfinding algorithm is ideally suited.
Kuprešak et al. (2024) explored this, having a Perlin-Noise based mesh environment where the authors compared different types of pathfinding algorithms in generating pathways. 3
These algorithms were; A* Algorithm (A*), Breadth-First Search Algorithm (BFS) and Dijkstra Algorithm.
Kuprešak et al. (2024) concluded that A* was the superior algorithm of the three, due to superior time computationally when compared to Dijkstra, and A* guiding its search more efficiently towards the end goal due to heuristics costs assigned to open vertices on its open list unlike Breath First Search. 4
An important feature of the A* algorithm is the cost it assigns to each point of the growing tested pathways – these can have greater cost due to the intrinsic cost of moving to a given point. This could be translated into this papers project terrain mesh, with an A* algorithms’ pathfinding through vertices of the mesh assigning cost values to vertices based upon terrain slope.
This natural cost to certain vertices based on the gradients to adjacent vertices, would help provide a bias into the pathway formed allowing it to move around step slopes in the mesh, mirroring real-life road / rail placement being built around landscape features.
Practical Testing of Pathway Carving – A* Algorithm Demonstration
A demonstration example of A* Pathfinding algorithm has been produced in the Unity Engine by this author. 5
The inputs within the inspector (Figure 1) allowed for a custom grid width and height of a grid of GameObject Tiles, which acted in place as the vertices. The percentage of blocked tiles represented areas that could not be pathed through to showcase the pathfinding element around blockages.
Figure 1: Screenshot of Unity Inspector settings for the A-Star search algorithm (DodginJam, 2024) 6
First, a starting and end tile would be randomly selected from different ends of the grid edges. The current selected tile is added to a Closed List to prevent backtracking. Neighbouring tiles of the currently selected tile are added to an Open List for (if they do not already appear on either list).
Tiles on the Open List are then evaluated a cost based upon two additive factors; cost to the end tile from the evaluated tile in real space length, plus the cost from the start to the evaluated tile as the number of tiles traversed.
All items on the Open List are then looped through and the lowest cost tile is selected for the next neighbour evaluation, repeating the whole process until either a no more tiles to exist or the end location is located.
In the example project below (Figure 2), the costs of choosing the next cell are overlayed onto the tiles. Green tiles are visited, having had their neighbours costed. The end tile is coloured blue. The black tiles are considered untraversable tiles and are not evaluated in the neighbour selection or costing evaluation.
Figure 2: Video demonstration of A Star Algorithm. Source: DodginJam, 2024. A-Star-search-algorithm. Available at: https://youtube.com/shorts/XSFPI34IKzY?si=bUOo8pQV8cIPl9AG [Accessed: 8 December 2024] 7
The demonstration above shows A* algorithms suitability to form procedurally generated pathways through environments with blockages and is a prime consideration for implementation in the final main project. The GameObject tiles will instead be replaced with the vertices of the meshes, and the slopes of connecting vertices will replace the untraversable tiles.
Appendix B - Further Implementation of Existing Algorithms in Project
Perlin Noise in Unity
Further research on terrain generators that use techniques other than the common usage of just Perlin Noise. 8
The video focused on terrain generation in the context of mountainous terrain. It introduced two new techniques – Fractal Perlin Noise, which builds upon the usage of Perlin noise through the usage of multiple layers of Perlin noise plus what the author terms as the “gradient trick”, which provides detail on flatter surfaces while weakening the details on sharper surfaces by looking at gradient between points, in order create more contrasting terrain for mountain generation.
The second technique is called DLA, standing for Diffusion Limited Aggregation. This generates lattices of pixels via random walks at differencing resolutions (for the sake of performance). These lattices are upscaled in resolution, blurring their details, and then have further passes of the algorithm added on. The benefits of these two techniques is the quality of the terrain generated are closer in appearance to real-life terrain.
References
Lague, S. (2018). [Unity] Procedural Object Placement (E01: poisson disc sampling) [Video]. YouTube. Available at: https://youtu.be/7WcmyxyFO7o?si=eoMtbvmrD9BpQFQ0 [Accessed 7 December 2024].
NULL (2022) Simple Approach to Surface Alignment | Unity [YouTube video]. Available at: https://www.youtube.com/watch?v=Gt4NQDKc3tk (Accessed: 7 December 2024)
M. Kuprešak, Č. Livada, T. Galba and A. Baumgartner, "Pathfinding in Procedurally Generated Mazes," 2024 International Conference on Smart Systems and Technologies (SST), Osijek, Croatia, 2024, pp. 145-151, doi: 10.1109/SST61991.2024.10755394.
M. Kuprešak, Č. Livada, T. Galba and A. Baumgartner, "Pathfinding in Procedurally Generated Mazes," 2024 International Conference on Smart Systems and Technologies (SST), Osijek, Croatia, 2024, pp. 145-151, doi: 10.1109/SST61991.2024.10755394.
DodginJam (2024) A-Star search algorithm. Available at: https://github.com/DodginJam/A-Star-search-algorithm (Accessed: 7 December 2024).
DodginJam (2024) A-Star search algorithm. Available at: https://github.com/DodginJam/A-Star-search-algorithm (Accessed: 7 December 2024).
DodginJam, 2024. A-Star-search-algorithm. Available at: https://youtube.com/shorts/XSFPI34IKzY?si=bUOo8pQV8cIPl9AG [Accessed: 8 December 2024]
Josh’s Channel (2024) Better Mountain Generators That Aren't Perlin Noise or Erosion [YouTube video]. Available at: https://www.youtube.com/watch?v=gsJHzBTPG0Y (Accessed: 7 December 2024)