A* search algorithm For PathFinding

Download Game

Download Source Code

1. Created a square grid at least 15x15 nodes in size.

a. Randomly (or via the mouse) marked some of the nodes as "impassable".

b. Visualized the grid.

2. Implemented the A* pathfinding algorithm to find the shortest distance between two nodes.

a. Randomly select a 'start' and 'goal' node. ( and via the mouse the Impassable nodes)

b. For the heuristic function, I chose Manhattan distance.

c. Visualized the 'start' and 'goal' nodes, the calculated path, and every node that A* put on the 'open' list.

d. Made sure the case where there is NO VALID PATH is handled.

Start Node:

Goal Node:

Impassable Node:

Open List Node: Node that was put in Frontier to process but skipped because it was far away from the goal - Manhatten distance Heuristics.

Normal Tile:

A * Algorithm used:

Heuristics will make the frontier expand towards the goal more than it expands in other directions.

Comparision of the algorithm without heuristics to with heuristics: It wastes some computation time in calculating paths that are not likely to find the goal. Without heuristics, although the algorithm finds the goal path eventually, it takes longer compared to the one with heuristics.

Two instances of A* Path Finding with same Start and Finish tile locations in both.