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.
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:
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.
- Breath first
- Depth first
- A* (brute force)
- A* (using quicksort)
- A* (using binary HEAP)
- Bidirectional search
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.