Pathfinding study
I started this project because I wanted to see how well I could implement the A* pathfinder and use it in a game like scenario.
In this project, I ventured into the world of A* pathfinding, a crucial aspect of turn-based gaming. Throughout its development, I explored various phases, ranging from basic navigation through open terrains and randomized obstacles to overcoming complex labyrinths in both 2D and 3D environments. The objective was to create a flexible pathfinding solution suitable for improving gameplay in turn-based games.
I began the project by implementing a straightforward A* pathfinder within a 2D environment. The initial phase aimed at introducing obstacles for the pathfinder to navigate around, adding complexity to its decision-making. Subsequently, a substantial portion of the project involved optimizing the pathfinding algorithm to enhance its efficiency.
100x100 cells, 0% obtacle coverage, path found in 166ms
255x255 cells, 30% obtacle coverage, path found in 4.6s
The initial runtime of over four seconds for pathfinding was significantly reduced to create a more responsive solution. Furthermore, I incorporated a "no-corner cutting" feature to ensure that the pathfinding remained reliable. I then put this improved pathfinder to the test on a 255x255 map inspired by Baldur's Gate II.
As the project evolved, my focus shifted to the exploration of path limiting, introducing an "energy" score that decreased with each cell traversed. This mechanism was evaluated on a labyrinth map, demonstrating that the pathfinding process conformed to the initial energy constraints. To further enhance realism, I introduced variable cell costs to simulate rough terrain.
255x255 cells, Baldur's Gate II map, added no cornercutting
Labiryth with max-movement and tile movement cost
Variable cost nodes(left) & Uniform cost nodes (right)
Satisfied with the 2D pathfinder's performance, I expanded its capabilities into the realm of 3D pathfinding. The challenges here included navigating inclines, slopes, and addressing issues related to paths passing through objects. Despite these initial hurdles, I swiftly resolved these concerns.
3D test environment showing all walkable cells
3D test environment different elevation and slopes
3D test environment path blocking with different elevations
3D test environment path down slopes and ledge drop off
The next step involved extending the pathfinding to consider dropping off edges to discover the shortest path while reintroducing wall structures that obstructed movement in specific directions.
3D test environment with walls blocking the path
3D test environment elevated room with slope and walls
Once this functionality was fully integrated, I created a test map inspired by the layouts of XCOM: UFO Defense. However, adapting these maps, originally designed for an old isometric game, to a 3D environment presented some scaling challenges. These were successfully addressed, resulting in a more fluid mapping experience.
Original XCOM map from XCOM: UFO Defense
Recreation of XCOM map in Unity (Isometric view)
Recreation of XCOM map in Unity (perspective view)
Nevertheless, as the project advanced, performance issues became evident, particularly when mapping longer paths. To rectify this, I transitioned to Unity's burst job system, significantly enhancing the pathfinder's performance. The result is a functional and efficient pathfinding solution ready for practical application.
Show case:*Note: Project source temporarily not available.