Hello. I’m trying to implement the A* algorithm for my game. I am following this awesome tutorial: http://theory.stanford.edu/~amitp/GameProgramming/
I understand the theory and the method used, but my implementation of the algorithm doesn’t work. I’m using the pseucode from that tutorial: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html
This is my code:
List<Graph> open;
List<Graph> close;
private void createRouteAStar(Unit u)
{
open = new ArrayList<Graph>();
close = new ArrayList<Graph>();
u.ai_route_endX = 8;
u.ai_route_endY = 12;
List<Graph> neigh;
int index;
int i;
boolean finish = false;
Graph current;
int cost;
Graph start = new Graph(u.xMap, u.yMap, 0, ManhattanDistance(u.xMap, u.yMap, u.ai_route_endX, u.ai_route_endY));
current = start;
open.add(current);
while(!finish)
{
index = findLowerF();
current = new Graph(open, index);
// System.out.println(current.x);
// System.out.println(current.y);
if (current.x == u.ai_route_endX && current.y == u.ai_route_endY)
{
close.add(current);
System.out.println(current.parent.x);
System.out.println(current.parent.y);
finish = true;
}
else
{
close.add(current);
open.remove(open.indexOf(current));
neigh = current.getNeighbors(u.ai_route_endX, u.ai_route_endY);
for (i = 0; i < neigh.size(); i++)
{
cost = current.g + ManhattanDistance(current.x, current.y, neigh.get(i).x, neigh.get(i).y);
if (open.contains(neigh.get(i)) && cost < neigh.get(i).g)
{
open.remove(open.indexOf(neigh));
}
else if (close.contains(neigh.get(i)) && cost < neigh.get(i).g)
{
close.remove(close.indexOf(neigh));
}
else if (!open.contains(neigh.get(i)) && !close.contains(neigh.get(i)))
{
neigh.get(i).g = cost;
neigh.get(i).f = cost + ManhattanDistance(neigh.get(i).x, neigh.get(i).y, u.ai_route_endX, u.ai_route_endY);
neigh.get(i).setParent(current);
open.add(neigh.get(i));
}
}
}
}
List<Graph> result;
result = returnPath();
for (i=0; i < result.size(); i++)
{
System.out.println(result.get(i).toString());
}
}
private List<Graph> returnPath()
{
int i;
List<Graph> aux = new ArrayList<Graph>();
for (i=0; i < close.size(); i++)
{
if (close.get(i).parent != null)
{
if (!aux.contains(close.get(i).parent))
{
aux.add(close.get(i).parent);
}
}
}
aux.add(close.get(close.size()-1));
return aux;
}
private int findLowerF()
{
int i;
int min = 10000;
int minIndex = -1;
for (i=0; i < open.size(); i++)
{
if (open.get(i).f < min)
{
min = open.get(i).f;
minIndex = i;
// System.out.println("min");
// System.out.println(min);
}
}
return minIndex;
}
The class Graph has the following code:
public class Graph {
int x, y;
int f,g,h;
Graph parent;
public Graph(int x, int y, int g, int h)
{
this.x = x;
this.y = y;
this.g = g;
this.h = h;
this.f = g + h;
}
public Graph(List<Graph> list, int index)
{
this.x = list.get(index).x;
this.y = list.get(index).y;
this.g = list.get(index).g;
this.h = list.get(index).h;
this.f = list.get(index).f;
this.parent = list.get(index).parent;
}
public Graph(Graph gp)
{
this.x = gp.x;
this.y = gp.y;
this.g = gp.g;
this.h = gp.h;
this.f = gp.f;
}
@Override
public String toString() {
return "Graph [x=" + x + ", y=" + y + "]";
}
public Graph(Graph gp, Graph parent)
{
this.x = gp.x;
this.y = gp.y;
this.g = gp.g;
this.h = gp.h;
this.f = g + h;
this.parent = parent;
}
public List<Graph> getNeighbors(int endX, int endY)
{
List<Graph> aux = new ArrayList<Graph>();
aux.add(new Graph(x+1, y, g, ManhattanDistance(x+1, y, endX, endY)));
aux.add(new Graph(x-1, y, g, ManhattanDistance(x-1, y, endX, endY)));
aux.add(new Graph(x, y+1, g, ManhattanDistance(x, y+1, endX, endY)));
aux.add(new Graph(x, y-1, g, ManhattanDistance(x, y-1, endX, endY)));
return aux;
}
public void setParent(Graph g)
{
parent = g;
}
public boolean eq(Graph gp)
{
return (x == gp.x && y == gp.y);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Graph other = (Graph) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
private int ManhattanDistance(int ax, int ay, int bx, int by)
{
return Math.abs(ax-bx) + Math.abs(ay-by);
}
The return path shows this information:
Graph [x=18, y=5]
Graph [x=17, y=5]
Graph [x=18, y=6]
Graph [x=16, y=5]
Graph [x=17, y=6]
Graph [x=18, y=7]
Graph [x=15, y=5]
Graph [x=16, y=6]
Graph [x=17, y=7]
Graph [x=18, y=8]
Graph [x=14, y=5]
Graph [x=15, y=6]
Graph [x=16, y=7]
Graph [x=17, y=8]
Graph [x=18, y=9]
Graph [x=13, y=5]
Graph [x=14, y=6]
Graph [x=15, y=7]
Graph [x=16, y=8]
Graph [x=17, y=9]
Graph [x=18, y=10]
Graph [x=12, y=5]
Graph [x=13, y=6]
Graph [x=14, y=7]
Graph [x=15, y=8]
Graph [x=16, y=9]
Graph [x=17, y=10]
Graph [x=18, y=11]
Graph [x=11, y=5]
Graph [x=12, y=6]
Graph [x=13, y=7]
Graph [x=14, y=8]
Graph [x=15, y=9]
Graph [x=16, y=10]
Graph [x=17, y=11]
Graph [x=10, y=5]
Graph [x=11, y=6]
Graph [x=12, y=7]
Graph [x=13, y=8]
Graph [x=14, y=9]
Graph [x=15, y=10]
Graph [x=16, y=11]
Graph [x=9, y=5]
Graph [x=10, y=6]
Graph [x=11, y=7]
Graph [x=12, y=8]
Graph [x=13, y=9]
Graph [x=14, y=10]
Graph [x=15, y=11]
Graph [x=8, y=5]
Graph [x=9, y=6]
Graph [x=10, y=7]
Graph [x=11, y=8]
Graph [x=12, y=9]
Graph [x=13, y=10]
Graph [x=14, y=11]
Graph [x=8, y=6]
Graph [x=9, y=7]
Graph [x=10, y=8]
Graph [x=11, y=9]
Graph [x=12, y=10]
Graph [x=13, y=11]
Graph [x=8, y=7]
Graph [x=9, y=8]
Graph [x=10, y=9]
Graph [x=11, y=10]
Graph [x=12, y=11]
Graph [x=8, y=8]
Graph [x=9, y=9]
Graph [x=10, y=10]
Graph [x=11, y=11]
Graph [x=8, y=9]
Graph [x=9, y=10]
Graph [x=10, y=11]
Graph [x=8, y=10]
Graph [x=9, y=11]
Graph [x=8, y=11]
Graph [x=8, y=12]
I want to know if you can see something strange. I’ve been a pair of days trying to fix the code but I’m not able to see what’s the problem. I can’t understand it and I need help. 
Any contribution is appreciated. Thank you!