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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Create a website or blog at WordPress.com

Up ↑