A* .*;
- Without cornering rules imposed:
- View VB.Net code
- View Java code
- View C++ code
- View Javascript code
- Click here to run the code and view the Javascript example results in a new window.
- With cornering rules imposed:
- View VB.Net code
- View Java code
A* Example 1
The map for this example is a 13x13 grid that looks like this:
All gray squares represent walls or obstacles, all white squares are open space with which to navigate. The yellow circle in square number 53 is the starting location, and the blue circle in square 73 is the goal.
In the Map() array, 1's represent the walls or obstacles, 0's are the open space.
Without cornering rules, diagonal moves from one white square to any connected white square is a valid move.
With cornering rules, not all diagonal moves from one white square to any connected white square are valid. Basically, if the path is to go around a corner, it really has to go "around" the corner, not cut through it (e.g.; this is a more realistic constraint for the algorithm). The changes are made to the AddChildrenToFringe() routine.
The StartLocation and GoalLocation values can be changed to any white square values on the grid (NOTE: if you set either to gray square values the code throws an exception).
Example Results: Without Cornering Rules
53, 67, 81, 82, 70, 83, 57, 95, 96, 44, 109, 31, 32, 33, 47, 60, 73, fringeList 73, 60, 16, 0, 48, 47, 15, 2, 48, 60, 16, 2, 123, 109, 11, 4, 19, 31, 12, 4, 19, 32, 13, 4, 20, 32, 13, 4, 19, 33, 14, 4, 20, 33, 14, 4, 21, 33, 14, 4, 94, 81, 3, 5, 94, 82, 4, 5, 94, 95, 8, 5, 108, 95, 8, 5, 108, 96, 9, 5, 30, 44, 10, 5, 108, 109, 11, 5, 122, 109, 11, 5, 18, 31, 12, 5, 30, 31, 12, 5, 18, 32, 13, 5, 80, 67, 2, 6, 80, 81, 3, 6, 93, 81, 3, 6, 121, 109, 11, 6, 17, 31, 12, 6, 40, 53, 1, 7, 66, 53, 1, 7, 66, 67, 2, 7, 79, 67, 2, 7, closedList 53, 0, 0, 7, 67, 53, 1, 6, 81, 67, 2, 5, 82, 81, 3, 4, 70, 82, 4, 3, 83, 82, 4, 3, 57, 70, 5, 3, 95, 81, 3, 4, 96, 82, 4, 4, 44, 57, 7, 4, 109, 95, 8, 4, 31, 44, 10, 4, 32, 44, 10, 4, 33, 32, 13, 3, 47, 33, 14, 2, 60, 47, 15, 1, 73, 60, 16, 0, A* shortest route: 53, 67, 81, 82, 70, 57, 44, 32, 33, 47, 60, 73,
In this example, the closedList(,) array looks like this:
To trace the A* path, we're just following the progression of parent nodes from the first column to each succeeding row in the second column. In this case, two of the rows don't match up. These two represent places where the A* algorithm changed its mind about which way to go, and are removed them from the final solution path.
Example Results: Without Cornering Rules
53, 40, 66, 67, 80, 81, 82, 83, 70, 57, 95, 96, 44, 109, 31, 19, 33, 32, 20, 21, 22, 23, 94, 108, 122, 123, 124, 125, 112, 99, 86, 73, fringeList 73, 86, 31, 0, 87, 99, 30, 1, 87, 86, 31, 1, 100, 112, 29, 2, 100, 99, 30, 2, 100, 86, 31, 2, 113, 125, 28, 3, 113, 112, 29, 3, 113, 99, 30, 3, 126, 125, 28, 4, 126, 112, 29, 4, 18, 31, 15, 5, 30, 31, 15, 5, 18, 19, 16, 5, 18, 32, 18, 5, 24, 23, 22, 5, 136, 122, 25, 5, 136, 123, 26, 5, 137, 123, 26, 5, 136, 124, 27, 5, 137, 124, 27, 5, 138, 124, 27, 5, 137, 125, 28, 5, 138, 125, 28, 5, 139, 125, 28, 5, 93, 80, 5, 6, 93, 81, 6, 6, 121, 109, 14, 6, 17, 31, 15, 6, 93, 94, 23, 6, 121, 108, 24, 6, 121, 122, 25, 6, 134, 122, 25, 6, 135, 122, 25, 6, 135, 123, 26, 6, 79, 66, 3, 7, 79, 67, 4, 7, 79, 80, 5, 7, 92, 80, 5, 7, 27, 40, 2, 8, closedList 53, 0, 0, 7, 40, 53, 1, 7, 66, 53, 1, 7, 67, 66, 3, 6, 80, 66, 3, 6, 81, 80, 5, 5, 82, 81, 6, 4, 83, 82, 7, 3, 70, 83, 8, 3, 57, 70, 9, 3, 95, 81, 6, 4, 96, 82, 7, 4, 44, 57, 10, 4, 109, 95, 11, 4, 31, 44, 13, 4, 19, 31, 15, 4, 33, 19, 16, 3, 32, 31, 15, 4, 20, 19, 16, 4, 21, 20, 19, 4, 22, 21, 20, 4, 23, 22, 21, 4, 94, 80, 5, 5, 108, 95, 11, 5, 122, 109, 14, 5, 123, 122, 25, 4, 124, 123, 26, 4, 125, 124, 27, 4, 112, 125, 28, 3, 99, 112, 29, 2, 86, 99, 30, 1, 73, 86, 31, 0, A* shortest route: 53, 66, 80, 81, 95, 109, 122, 123, 124, 125, 112, 99, 86, 73,
Note how the cornering rules affected the outcome. The algorithm decided to take an entirely different path.