A* .*;

 

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.

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}