Home >> Programs >> PathFinding Algorithms

We had to implement a A* path finding algorithm for a schoolproject. I decided to go a little further with the project and I have implemented multiple pathfinding algorithms.

General information

Name:
Written in:
Platform:
PathFinding Algorithms
C++
PC

Description

NPC's in games have to walk around in the virtual worlds they are in. They can just walk randomly about but that is not the most interesting thing they can do for players. To get from point A to B is possible in multiple ways. The following algorithms are implemented:

  • Breath first
  • Depth first
  • A* (brute force)
  • A* (using quicksort)
  • A* (using binary HEAP)
  • Bidirectional search


The above algorithms all have advantages and disadvantages with certain problems. The best in most cases is the A* algortihm. The Binary HEAP variant is the quickest of the three A* algorithms.

The application uses a textfile with an ascii field. There are walls and empty spaces. The application searches the shortest paths using the above algorithms.

Screenshots



Download

Changelog v1.1 Download offline
Application files Download offline