hi i am implementing an a* path finder using the manhattan distance as a cost, can seem to wrap my head around it: heres the code for the search,
public LinkedList<MapNode> search(MapNode startNode, MapNode goalNode) {
LinkedList<MapNode> closedList = new LinkedList<MapNode>();
LinkedList<MapNode> openList = new LinkedList<MapNode>();
openList.add(startNode);
startNode.setPathParent(null);
while (!openList.isEmpty()) {
MapNode node = (MapNode) openList.removeFirst();
if (node == goalNode)
return constructPath(goalNode);
else {
closedList.add(node);
// add neighbors to the open list
Iterator<MapNode> i = getNeighbours(node, goalNode).iterator();
while (i.hasNext()) {
MapNode neighborNode = (MapNode) i.next();
if (!closedList.contains(neighborNode) && !openList.contains(neighborNode)) {
neighborNode.setPathParent(node);
openList.add(neighborNode);
}
}
}
}
// no path found
return null;
}
and heres my getneighbours() method:
public LinkedList<MapNode> getNeighbours(MapNode node, MapNode goalNode) {
Position positionCheck = new Position(0, 0);
for (int x = -1; x < 2; x++){
int newX = node.getPosition().getPositionX() + x;
if(newX<0 || newX >= Map.DIMENSION){continue;}
for (int y = -1; y < 2; y++){
int newY = node.getPosition().getPositionY() + y;
if(newY<0 || newY >= Map.DIMENSION){continue;}
positionCheck.setPositionX(newX);
positionCheck.setPositionY(newY);
if(!node.getPosition().equals(positionCheck)){
calculateCost(map.elementAt(positionCheck), goalNode);
neighbours.add(map.elementAt(positionCheck));
}
}
}
return neighbours;
}
It works but unfortunately its not using the manhattan principle, the output is this:
Shortest Delivery Point is: 6 miles! - 8,7 // using manhattan distance
S = Start, D=Destination, "."= path taken.
[3,4] ->
[4,3] ->
[5,4] ->
[6,5] ->
[ D ] ->
[0,0] [0,1] [0,2] [0,3] [0,4] [0,5] [0,6] [0,7]
[1,0] [1,1] [1,2] [1,3] [1,4] [1,5] [1,6] [1,7]
[2,0] [2,1] [2,2] [2,3] [2,4] [ S ] [2,6] [2,7]
[3,0] [3,1] [3,2] [3,3] [ . ] [3,5] [3,6] [3,7]
[4,0] [4,1] [4,2] [ . ] [4,4] [4,5] [4,6] [4,7]
[5,0] [5,1] [5,2] [5,3] [ . ] [5,5] [5,6] [5,7]
[6,0] [6,1] [6,2] [6,3] [6,4] [ . ] [6,6] [6,7]
[7,0] [7,1] [7,2] [7,3] [7,4] [7,5] [ D ] [7,7]
I was just wondering if anyone could spot what i cant, its the first time i've messed about with pathfinding so i am a bit niaeve. Thanks for the help..
The node that you take off the open list must be the node with the smallest F cost. That makes using a linked list a bad choice - you either have to search through it completely to extract a node, or you have to search through it completely to insert nodes. But, bad choice or not, it's not correct like this because you're doing neither.
Also, if a neighbour is already in the open list, you must compare the G scores and re-parent it if the new path is better.
Using a linked list for the closed set is also a bad choice, you only need "add" and "contains" on it, and contains is terrible for linked lists. This doesn't affect correctness though.