I have an implementation of Astar but it seems to plot an odd path to the target. It appears to evaluate node correctly, but I'm not sure if it is working right because the path list at the end contains nodes with equal G scores.
Here is my code
startNode = getTile(new Point(3,6));
targetNode = getTile(new Point(1,4));
ArrayList<Node> closedList;
void AStar() {
closedList = new ArrayList<>();
ArrayList<Node> openList = new ArrayList<>();
startNode.g = 0;
startNode.h = heuristic(startNode,targetNode);
startNode.f = startNode.g+startNode.h;
Log.d("COST",startNode.h+"");
cost = startNode.h;
openList.add(startNode);
while (!openList.isEmpty()) {
//Find the node with the lowest f value
int lowestFcost = openList.get(0).f;
Node processNode = openList.get(0);
for(int i = 1;i<openList.size();i++){
if(openList.get(i).f < lowestFcost){
lowestFcost = openList.get(i).f;
processNode = openList.get(i);
}
}
if (processNode.equals(targetNode)) {
path(processNode);
return;
}
openList.remove(processNode);
closedList.add(processNode);
for (Node n:nextNodes(processNode)) {
//check if n is in the closed list
if(closedList.contains(n)){
// skip forloop once
Log.d("SKIPLOOP","true");
}else {
if (!openList.contains(n)) {
openList.add(n);
} else {
for (Node n2 : openList) {
if (n2.equals(n)) {
if (processNode.g<n.g) {
//better g score
n2.g = heuristic(processNode,startNode);
n2.h = heuristic(processNode,targetNode);
n2.f = n2.g+n2.h;
n2.parent = processNode;
Log.d("NODE","XY:"+n2.getPosition().toString()+" Gcost:"+n2.g+" Fcost:"+n2.f+" Hcost:"+n2.h);
//n2.view.setBackgroundColor(getResources().getColor(R.color.primary_light,null));
}
}
}
}
}
}
}
new ToastEasy(getApplicationContext(),"Not Possible to reach Target");
}
private Node getTile(Point tilePosition){
Node tile = null;
for (Node t:MapTileList) {
if(tilePosition.equals(t.getPosition())){
tile = t;
break;
}
}
return tile;
}
private ArrayList<Node> nextNodes(Node node){
ArrayList<Node>NextNodeList = new ArrayList<>();
if(node.getPosition().x-1 >= 0 ){
//Add a left Node
Node n = getTile(new Point(node.getPosition().x-1,node.getPosition().y));
//n.parent = node;
n.g = heuristic(n,startNode);
n.h = heuristic(n,targetNode);
n.f = n.g+n.h;
n.view.setBackgroundColor(getResources().getColor(R.color.green,null));
NextNodeList.add(n); //Left Node
}
if(node.getPosition().y-1 >= 0){
//Add a top Node
Node n = getTile(new Point(node.getPosition().x,node.getPosition().y-1));
//n.parent = node;
n.g = heuristic(n,startNode);
n.h = heuristic(n,targetNode);
n.f = n.g+n.h;
n.view.setBackgroundColor(getResources().getColor(R.color.green,null));
NextNodeList.add(n); //Top Node
}
if(node.getPosition().x+1 <= cols ){
//Add a Right Node
Node n = getTile(new Point(node.getPosition().x+1,node.getPosition().y));
//n.parent = node;
n.g = heuristic(n,startNode);
n.h = heuristic(n,targetNode);
n.f = n.g+n.h;
n.view.setBackgroundColor(getResources().getColor(R.color.green,null));
NextNodeList.add(n);
}
if(node.getPosition().y+1 <= rows) {
//Add a Bottom Node
Node n = getTile(new Point(node.getPosition().x, node.getPosition().y + 1));
//n.parent = node;
n.g = heuristic(n,startNode);
n.h = heuristic(n,targetNode);
n.f = n.g+n.h;
n.view.setBackgroundColor(getResources().getColor(R.color.green,null));
NextNodeList.add(n);
}
return NextNodeList;
}
void path(Node node){
int lastCost = 0;
ArrayList<Node>Path = new ArrayList<>();
for (Node node1 : closedList) {
if(node1.parent != null){
node1.view.setBackgroundColor(getResources().getColor(R.color.black,null));
Path.add(node1);
//Log.d("PATHLIST",Path.get(i).getPosition()+" Gcost"+Path.get(i).g+" Hcost"+Path.get(i).h+" Fcost"+Path.get(i).f);
}
}
Log.d("PATHLIST",Path.size()+"");
}
private int heuristic(Node node1, Node node2){
return Math.abs((node1.getPosition().x-node2.getPosition().x))
+
Math.abs((node1.getPosition().y-node2.getPosition().y));
}
I'm following this tutorial here: https://algorithmsinsight.wordpress.com/graph-theory-2/a-star-in-general/implementing-astar-for-pathfinding and here: https://algorithmsinsight.wordpress.com/graph-theory-2/a-star-in-general/
Any help to confirm the correctness of this code would be greatly appreciated.
Thanks!
My Node Class
import android.graphics.Point;
import android.widget.ImageButton;
import android.widget.TextView;
public class Node {
Point position;
public int f,g,h;
public Node parent;
public ImageButton view;
public Node(Point position, int f, int g, int h, Node parent, ImageButton view) {
this.position = position;
this.f = f;
this.g = g;
this.h = h;
this.parent = parent;
this.view = view;
}
public Point getPosition(){
return this.position;
}
}
So after a week of tinkering. I do believe I have cracked the nut!
The tutorial that I was trying to follow lead me around in circles and eventually I gave up on trying to update nodes G value as stated in the tutorials. Instead, I created a new hybrid cost value, I call the Bcost. Because I'm Brett ;P. I wont post the entire code here, but I will post a link to the test session where you can launch it in Android Studio and try it for yourself. The new Bcost makes the algorithm way more efficient and as you'll see, it barely ever chooses a node that isnt the best next node. I think it's probably 50-100% faster. However, my nextnodes() function is horribly bloated and if anyone wants to take a stab at making that method cleaner. I would love to see how you accomplish that.