This is a little demo to help me explore some super cool pathfinding algorithms. Part and parcel of this process of learning is good visualization techniques, and so I have implemented the demo in Unity3D to make the abstract algorithms concrete.
Open this project in Unity and simply press Play.
This project was made using Unity version 2018.4.10. It probably wouldn't hurt to try opening it in a newer or older version though - YMMV.
Click on the World GameObject in order to access some options in the Inspector that will vary the behavior of the algorithms.
I am currently focusing on tile/grid-based maps for experimenting with pathfinding. The cell size is the length of a side of a square-shaped grid cell in Unity units. Based on this value, the World is transformed into a grid structure from which a Graph data structure can be built to perform pathfinding on.
It determines the size of the grid. For example, a World that is 10 by 10 units and a cell size of 0.5 will result in the construction of a 20 by 20 grid containing 400 cells.
The range of possible values is [0.05, 1]. Any more or less and you either get terrible pathing or terrible performance.
Choose the heuristic function to be used by the A* algorithm.
The demo supports dynamic obstacle detection at tilemap generation time. You can add/remove/move objects with Collider components on the Ground object, then press Play to see them being considered as impassable tiles during the pathfinding algorithm!
Pathfinding is performed on a Ground GameObject that must have some sort of a Collider component. For simplicity, it is assumed to be an object that is spread out along the X-Z plane such that the Y-axis is insignificant. Slopes, inclines and general rugged terrain is currently not supported. I chose to use a Plane but a stretched out Cube should get the job done too.
The Ground surface is split across the X-Z plane into a 2D grid, aka tilemap. Tiles that overlap with an object with a Collider are marked as obstructing tiles and will be rendered as impassable during pathfinding.
Left-click anywhere on the Ground to choose the starting location. Right-click anywhere else on the Ground to choose the ending location. As soon as this is done, the pathfinding algorithm will compute a path from the starting location to the ending location and this path is then rendered on the Ground. Start and end locations can be changed freely to explore different paths.
Press and hold the middle-mouse button and drag around to pan the camera.
Tim Roughgarden's Algorithms Illuminated textbook. Prior to working through this book I was intimidated by Graph algorithms, particularly Djikstra's single-source shortest path algorithm. That is no longer the case!
Amit Patel's splendid pathfinding algorithm illustrations and sample code have been extremely insightful. The interactive explanations helped me grasp the intuition of Djikstra's and A* algorithms. This is a gem of a resource!
There are many more aspects of pathfinding that I will be exploring.
- Move a 3D object along a computed path.
- Add a new heuristic function: Precomputed shortest path distance to the end goal.
- Smoothly move a 3D object along a computed path, even when the path looks jagged and ugly.
- Increase real-time dynamism. Make every change result in "refreshing" the tile graph OR simply re-running the algorithm. For ex: move obstacles, change cell size.
- Add UI components in-game to tweak parameters
- Allow camera rotation + zoom.