There Course: CS380
Instructor: Iker Silvano
Type: Solo project
This subject covered multiple topics about AI, one of them was pathfinding, which I found very interesting, specially the JPS+ algorithm. It completely outperforms A* when the map is open (see JPS+ video 00:57).
In the videos I am just showcasing the A* and JPS+ algorithms, but, apart from the actual algorithms behind them I also implemented some other features:
- Rubber banding and Smoothing post processing to improve the path the agent will follow.
- Variable weight for the cost of each node.
- Multiple heuristic computation functions: Euclidean, Octile, Chebyshev and Manhattan.
- Ability to divide the algorithm computation among multiple frames(visible in the videos).
A Star (A*)
Jump Point Search Plus (JPS+)
This is algorithm is an improvement over A* for static maps, it needs to compute some data at initialization, if some cell of the map changes we it needs to be recomputed.
There is a very interesting GDC talk by Steve Rabin about how to combine JPS+ with goal bounds in order to improve performance drastically. You can find it here.