Pathfinding

There Course: CS380

Instructor: Iker Silvano

Type: Solo project

Language: C++

Overview

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.