A* Pathfinding

Engine/Framework:

Visual Studio 2015

 

Coding & Scripting Languages:

C++

 

Target Platform:
Windows PC

​

Development Time:

1 month

​

Completed On:
2016

Goals and Objectives

1. Implement shortest-path algorithms in C++ • Dijkstra’s Algorithm. • A* (Astar) & variants
2. Justify use of data structures used within the algorithms.
3. Compare performance of previously implement solutions

Reasons for Shortest-Path

• Shortest-path algorithms integral for a games developer.
• Multiple variants allows for performance testing.
• Project I’m working on requires a pathfinding solution.
• Usage of grids instead of general purpose graphs

Choosing data structures

Using arrays to hold information such as the grid, path, open nodes and closed nodes. Unlike vectors arrays need to have a constant size meaning I could not change them during runtime. I could directly access an element of an array from memory while that would not be as simple in a vector or other container classes. Arrays are more memory compact.
Using a priority queue for the main data holder.

  • Insertion and extraction less time consuming (from O(n) to O(1)).

  • Automatic ordering of data makes calculating path much faster.

  • Most of the program time is spent making a new node and then deleting it.

  • 40% for making a new node, 18% for deletion versus only 0.7% for push back and 7% for heap adjustments.