a* ALGORITHM - PATHFINDING IMPLEMENTATION
PROJECT TIMESCALE: november 2013 - december 2013
The A* algorithm is a more complicated way of finding a path. Although more complex, it runs faster than Lee’s algorithm and finds the shortest path. It also works by creating a grid with a start and goal position. Unlike Lee’s algorithm though, rather than expand outwards in a wave looking for the target; it assign values to every position on the grid. These values are the goal, heuristic and fitness. The goal is the movement cost to move from the starting point to a given square on the grid, following the path generated to get there. The heuristic is an estimated movement cost to move from that given square on the grid to the final destination. The fitness is the sum of the goal and heuristic added together. The algorithm uses an open list and a closed list. The open list stores nodes that are potentially on the path, whilst the closed list are the nodes we know to be on the path. The node with the lowest fitness value is taken from the open list and added to the closed list.
This is the pseudo code for A* Pathfinding:
1. Let the current node be the start position.
2. Assign fitness, goal and heuristic values to the current node.
3. Add the current node to the open list. At this, the current node is the only node on the open list.
4. Get the best node from the open list which is the node with the lowest fitness value.
a. If the best node is the goal position, then exit the loop.
b. If the open list is empty, then exit the loop.
5. Get a valid node connected to the best node.
a. Assign fitness, goal and heuristic values to the valid node.
b. Check whether the valid node is on the open or closed list.
i. If so, check whether the new path has a lower fitness value.
1. If so, update the path.
ii. Otherwise add the valid node to the open list.
c. Repeat step 5 for all valid children of the best node.
6. Repeat from step 4.
This is the pseudo code for A* Pathfinding:
1. Let the current node be the start position.
2. Assign fitness, goal and heuristic values to the current node.
3. Add the current node to the open list. At this, the current node is the only node on the open list.
4. Get the best node from the open list which is the node with the lowest fitness value.
a. If the best node is the goal position, then exit the loop.
b. If the open list is empty, then exit the loop.
5. Get a valid node connected to the best node.
a. Assign fitness, goal and heuristic values to the valid node.
b. Check whether the valid node is on the open or closed list.
i. If so, check whether the new path has a lower fitness value.
1. If so, update the path.
ii. Otherwise add the valid node to the open list.
c. Repeat step 5 for all valid children of the best node.
6. Repeat from step 4.