AStar Search Logic (Bug)
I have been working on a simple implementation of the A* Search Algorithm. I thought it was working, but apparently I didn't test it enough with different terrain movement costs (grass is easier to pass through than mountains, etc.). And now I'm wondering if my logic is even correct:
loop through each waypoint:
do until next waypoint is found:
dofor each adjacent node:
if checked node is on the closed list:
if checked node is not on the open list:
make the checked node's parent = the current node
put the checked node on the open list
checked node g cost = parent node g cost + 1 (straight) or sqrt of 2 (diagonal)
if checked node is on the open list:
if the checked node's g cost < the parent node's g cost:
--Should Idothis next line?--
switch the two nodes (in terms of parent)
-
checked node g cost = parent node g cost + 1 (straight) or sqrt of 2 (diagonal)
let h cost = distance between current node and next waypoint
let f cost = g cost + h cost
make the current node the node with the lowest f cost
put it on the closed list and remove it from the open
I think that just about covers it.
I can't seem to find good documentation on A*, so I tried several similar ways (particularly regarding the parent values), but none seem to work. The full source code can be found at http://students.hightechhigh.org/~dturnbull/11thGradeDP/Programming/AStar/AStar.zip (along with the Jar itself). A screenshot of the bug and the corresponding debug log can be found at http://students.hightechhigh.org/~dturnbull/11thGradeDP/Programming/AStar/Debug/.
(In the screenshot, the other two paths should have the same f cost as going through the middle disregarding terrain cost. Why then, would it choose to go through the high movement cost terrain?)
Can someone please point me in the right direction?
[2331 byte] By [
DMTNTJGDa] at [2007-11-26 16:38:04]
# 3
First I'd like to say that, considering you're an 11th grade student, you really did a nice job! Your aplication looks nice and you have even commented your code with Javadoc standards.
But now the criticism. ; )
You have one big problem: your AStar class. It's far too big (almost 2000 lines!) and has far too much responsibility: it's handling events, the GUI, game logic, etc. Some of the methods are over 100 lines long(!), making them very hard to follow.
It's best to create a non-GUI application first and when your game logic is done (and works), build a GUI around it [1].
When creating a larger application, it can be helpfull to underline all nouns and verbs in the problem description: the nouns are your classes and the verbs are the methods from those classes.
You could end up with these five classes:
_
| |
| + TerrainType: enum |
|_|
| |
| - cost: int |
| - passable: boolean |
| - label: char|
|_|
| |
| -TerrainType(cost: int, passable: boolean, label: char) << constr >> |
| + getCost(): int|
| + isPassable(): boolean |
| + getLabel(): char|
| + toString(): String |
|_|
__
||
| + Coordinate|
|__|
||
| x: int |
| y: int |
| Direction: enum|
|__|
||
| + Coordinate(x: int, y: int): << constr >> |
| + distance(that: Coordinate): int |
| + equals(o: Object): boolean|
| + get(direction: Direction): Coordinate|
| + toString(): String|
|__|
__
| |
| + Tile|
|__|
| |
| - coordinate: Coordinate |
| - terrainType: TerrainType|
|__|
| |
| + Tile(x: int, y: int, type: char): << constr >> |
| + equals(o: Object): boolean |
| + getCoordinate(): Coordinate|
| + getTerrainType(): TerrainType|
| + hashCode(): int|
| + toString(): String|
|__|
||
| + Path|
||
||
| - tiles: List<Tile>|
| - end: Coordinate |
| - cost: int|
| - estimate: int|
||
||
| + Path(end: Coordinate): << constr >> |
| + Path(that: Path): << constr >>|
| + add(tile: Tile): void|
| + compareTo(that: Path): int |
| + contains(tile: Tile): boolean|
| + getLastTile(): Tile|
| + reachedEndCoordinate(): boolean|
| + toString(): String|
||
||
| + Grid|
||
||
| - grid: Tile[][] |
| - width: int |
| - height: int |
||
||
| + Grid(width: int, height: int, data: String[]): << constr >> |
| + findPath(start: Coordinate, end: Coordinate): Path |
| + getNeighbours(tile: Tile): List<Tile>|
| + getTile(c: Coordinate): Tile|
| - processData(data: String[]): void|
| + toString(): String|
||
Note that the TerrainType is an enum [2].
I used the following data for the grid:// 'b'=brick, 'X'=building, 'm'=mud, '.'=dummy
String[] data = {
"bbbbbbbbbbbbbbbb",
"bXXXXbXXXXXXXXXb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XmX.......Xb",
"bX..XmX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bX..XbX.......Xb",
"bXXXXbXXXXXXXXXb",
"bbbbbbbbbbbbbbbb"
}
And the algorithm in the Grid class for finding a 'cheapest' path between two points (the A* algorithm) could be written as:public Path findPath(Coordinate start, Coordinate end) {
Queue<Path> allPaths = new PriorityQueue<Path>();
Set<Tile> visited = new HashSet<Tile>();
Path firstPath = new Path(end);
firstPath.add(getTile(start));
allPaths.offer(firstPath);
visited.add(getTile(start));
while(!allPaths.isEmpty()) {
Path cheapestPath = allPaths.poll();
Tile lastTile = cheapestPath.getLastTile();
List<Tile> neighbours = getNeighbours(lastTile);
for(Tile tile : neighbours) {
if(visited.add(tile)) {
Path copy = new Path(cheapestPath);
copy.add(tile);
allPaths.add(copy);
if(copy.reachedEndCoordinate()) return copy;
}
}
}
return null;
}
Due to the fact that all paths are stored in a PriorityQueue, I always get the cheapest path. Of course the Path class needs to implement the Comparable interface in order to let the PriorityQueue order the paths correctly [3].
So, I'm sorry I cannot help you with the bug in your code, but perhaps this is of help to you.
Good luck.
[1] Google for "MVC pattern".
[2] If you're new to enum's, read this tutorial: http://java.sun.com/docs/books/tutorial/java/javaOO/enum.html
[3] This tutorial explain how to do that: http://java.sun.com/docs/books/tutorial/collections/interfaces/order.html
# 5
Perfect! Sorry it took me so long to respond.
Prometheuzz, I will definitely take your advice, but it might take me a second version to do so. I also found your links extremely helpful.
Horstmeyer, I took your suggestion to add the terrain cost to the G cost rather than the F, and my bug seems to be fixed.
>Perhaps your Line 4 should read:
>if checked node is NOT on the closed list:
I seem to have made another mistake in pseudocode. In my Java code, it reads:
!terrain[temp[0]][temp[1]].closed
where temp is the checked node. That's what my pseudocode should say. Sorry about that.
Thanks for the great help!
