Visual Studio 2015
Coding & Scripting Languages:
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.