A* Pathfinding

One of the university modules, required to implement A* pathfinding algorithm. For this task I implemented Node based A* algorithm which is designed to work on any type of navigation network (2D/3D grid, waypoints, etc.) as long as it is possible to test a distance between them (which is required for ‘best-first’ part of A*). This is possible because of class base structure where Node class can be overloaded and inherited by any other type of class which is part of navigation network. The only disadvantage is that for regular grids, there is a simpler implementation, however it does not have the same portability as my current implementation.

In order to test the implementation, maze was procedurally generated using deep-first maze algorithm, which has one very valuable feature – there is always a path between any two points. Also it is easy to add shortcuts in the maze which allow to test how good the pathfinding algorithm is in finding them.

Screenshots

Finding path through the maze.

Found path with all searched nodes highlighted.

Leave a Reply

Your email address will not be published. Required fields are marked *