LEE algorithm - pathfinding implementation
project timescale: december 2013 - january 2014
The general theory behind Lee’s algorithm is to create a grid with a start position and a goal position. From the start position the program expands out in a wave. Each grid position the wave meets is assigned a value which is the distance from the start. This continues until the wave meets the goal or it cannot expand further. If it cannot expand further then no path exists otherwise it traces back to the start. It does this by starting at the goal position and checking every neighbouring position for the lowest value. The position with the lowest value then has its neighbours checked, once again looking for the lowest value. This continues until the value is zero, meaning we have found the start.
This is the pseudo code for Lee’s algorithm:
1. Set up the grid.
a. Create a 2-dimension array for the grid.
b. Select start point and assign it the value 0.
c. Select a destination.
d. Place any obstructions to the path.
2. Use wave expansion to move outwards from the start position until the goal is found.
a. Get the current node which will be initialised to the start position.
b. Assign all unlabelled neighbours of the current node with the value of their distance from the start.
c. Repeat this until the goal has been reached or it is discovered that there is no path.
3. Backtrace from the goal to the start.
a. Get the current node which will be initialised to the goal position.
b. Fine the neighbouring node with a value less than that of the current node.
c. Add this node to path.
This is the pseudo code for Lee’s algorithm:
1. Set up the grid.
a. Create a 2-dimension array for the grid.
b. Select start point and assign it the value 0.
c. Select a destination.
d. Place any obstructions to the path.
2. Use wave expansion to move outwards from the start position until the goal is found.
a. Get the current node which will be initialised to the start position.
b. Assign all unlabelled neighbours of the current node with the value of their distance from the start.
c. Repeat this until the goal has been reached or it is discovered that there is no path.
3. Backtrace from the goal to the start.
a. Get the current node which will be initialised to the goal position.
b. Fine the neighbouring node with a value less than that of the current node.
c. Add this node to path.