Pathfinding

This is a demo of AI pathfinding using various search algorithms.
It is written in C++, and uses Allegro.
Made in collaboration with Tim Robertson.

In this demo, a pink arrow starts in the top left, and then pathfinds its way to the bottom right.
You will see the search algorithm in action each time as it finds a path to the end.
Once the path is found, the arrow will travel along it. For the sake of time, I left this part out.

There are five different search algorithms used. They appear in the video in this order:
  1. Depth-First
  2. Dijkstra
  3. A* (A-Star)
  4. Node-Array A*
  5. Iterative Deepening A*

You can read about all of these on Wikipedia if you're interested in learning more.
The difference between normal A* and Node-Array / Iterative Deepening is as follows:

Node Array: this variation is designed to be extremely fast at the cost of memory usage by manipulating how data about the path is handled in the backend.
Iterative Deepening: this variation is designed to use as little memory as possible, however can take a long time to find a path if the destination is far away. It is extremely fast for short paths.

Also, this program runs at 120 fps, but my recording software only records at 60, so this video is sped-up to 120fps to match its realtime speed.  Note that drawing takes a relatively long time, and with path-drawing turned off, all these search algorithms are nearly instantaneous.