I have a very bi problem with my AStar algorithm. The point is: If I have a start point (10,10) and the aim point is left over the start point (5,5) everything works great. But if the aim point is under or right to the startpoint (15,12) the algorithm says there is no way.
I don't know why?????
Pleas help me! I can't find the bug!
The algorithm:
import java.util.LinkedList;
public class AStar
{
private OpenList openlist = new OpenList();
private LinkedList<RasterPoint> closedList = new LinkedList<RasterPoint>();
private LinkedList<LinkedList<RasterPoint>> raster;
private RasterPoint endPoint;
public LinkedList watchedRasterPoints = new LinkedList();
public LinkedList testP = new LinkedList();
private RasterPoint startPoint;
public RasterPoint findWayTo(LinkedList<LinkedList<RasterPoint>> raster,int startX,int startY,int endX, int endY)
{
this.raster = raster;
if(startX < 0 && startX >= raster.size()) return null;
if(endX < 0 && endX >= raster.size()) return null;
if(startY < 0 && startY >= raster.get(0).size()) return null;
if(endY < 0 && endY >= raster.get(0).size()) return null;
startPoint = raster.get(startX).get(startY);
startPoint.setfValue(0);
this.openlist.add(startPoint);
endPoint = raster.get(endX).get(endY);
// diese Schleife wird durchlaufen bis entweder
// - die optimale Lösung gefunden wurde oder
// - feststeht, dass keine Lösung existiert
// die Open List ist leer, es existiert kein Pfad zum Ziel
int num = 0;
while(this.openlist.size() != 0 && num < 1000)
{
// Knoten mit dem geringsten f Wert aus der Open List entfernen
RasterPoint currentPoint = this.openlist.popMinPoint();
// Wurde das Ziel gefunden?
if(currentPoint == endPoint)
{
return endPoint;
}
// Der aktuelle Knoten soll durch nachfolgende Funktionen
// nicht weiter untersucht werden damit keine Zyklen entstehen
this.closedList.add(currentPoint);
// Wenn das Ziel noch nicht gefunden wurde: Nachfolgeknoten
// des aktuellen Knotens auf die Open List setzen
if(this.testP.contains(currentPoint))
{
System.out.println("Go");
}
this.expand(currentPoint);
num++;
}
return null;
}
private void expand(RasterPoint currentPoint)
{
for(RasterPoint point : currentPoint.getSuccessorPoints(this.raster, this))
{
this.watchedRasterPoints.add(point);
// wenn der Nachfolgeknoten bereits auf der Closed List ist - tue nichts
if(this.closedList.contains(point))
{
return;
}
// g Wert für den neuen Weg berechnen: g Wert des Vorgängers plus
// die Kosten der gerade benutzten Kante
int gValue = currentPoint.getgValue() + 1;
// wenn der Nachfolgeknoten bereits auf der Open List ist,
// aber der neue Weg nicht besser ist als der alte - tue nichts
if(this.openlist.contains(point) && gValue >= point.getgValue())
{
return;
}
// Vorgängerzeiger setzen und g Wert merken
point.setPreRasterPoint(currentPoint);
point.setgValue(gValue);
// f Wert des Knotens in der Open List aktualisieren
// bzw. Knoten mit f Wert in die Open List einfügen
point.setfValue(gValue+point.calcHValue(this.endPoint));
if(this.openlist.contains(point))
{
int position = this.openlist.indexOf(point);
this.openlist.set(position, point);
}
else
{
this.openlist.add(point);
}
}
}
}
And one other class:
import java.util.ArrayList;
import java.util.LinkedList;
import de.nkpmedia.rccar.floor.laserscanner.LaserPoint;
public class RasterPoint
{
private boolean isWall;
private LaserPoint laserPoint;
private int fValue = 0;
private int gValue = 0;
private int x;
private int y;
/**
* @return the preRasterPoint
*/
public RasterPoint getPreRasterPoint()
{
return preRasterPoint;
}
/**
* @param preRasterPoint the preRasterPoint to set
*/
public void setPreRasterPoint(RasterPoint preRasterPoint)
{
this.preRasterPoint = preRasterPoint;
}
private RasterPoint preRasterPoint;
/**
* @return the gValue
*/
public int getgValue()
{
return gValue;
}
/**
* @param gValue the gValue to set
*/
public void setgValue(int gValue)
{
this.gValue = gValue;
}
public RasterPoint(int rasterNumX, int rasterNumY)
{
this.x = rasterNumX;
this.y = rasterNumY;
}
/**
* @return the x
*/
public int getRasterX()
{
return x;
}
/**
* @param x the x to set
*/
public void setRasterX(int x)
{
this.x = x;
}
/**
* @return the y
*/
public int getRasterY()
{
return y;
}
/**
* @param y the y to set
*/
public void setRasterY(int y)
{
this.y = y;
}
/**
* @return the fValue
*/
public int getfValue()
{
return fValue;
}
/**
* @param fValue the fValue to set
*/
public void setfValue(int fValue)
{
this.fValue = fValue;
}
public void setWall(boolean b)
{
this.isWall = b;
}
public void setLaserPoint(LaserPoint point)
{
this.laserPoint = point;
}
/**
* @return the isWall
*/
public boolean isWall()
{
return isWall;
}
/**
* @return the laserPoint
*/
public LaserPoint getLaserPoint()
{
return laserPoint;
}
public ArrayList<RasterPoint> getSuccessorPoints(LinkedList<LinkedList<RasterPoint>> raster, AStar aStar)
{
ArrayList<RasterPoint> successors = new ArrayList<RasterPoint>();
if(this.x-1 >= 0 && this.x-1 < raster.size() && this.y >= 0 && this.y < raster.get(0).size()) successors.add(raster.get(this.x-1).get(this.y));
if(this.x+1 >= 0 && this.x+1 < raster.size() && this.y >= 0 && this.y < raster.get(0).size()) successors.add(raster.get(this.x+1).get(this.y));
if(this.x >= 0 && this.x < raster.size() && this.y-1 >= 0 && this.y-1 < raster.get(0).size()) successors.add(raster.get(this.x).get(this.y-1));
if(this.x >= 0 && this.x < raster.size() && this.y+1 >= 0 && this.y+1 < raster.get(0).size()) successors.add(raster.get(this.x).get(this.y+1));
if(aStar.testP.contains(this))
{
System.out.println(successors.size());
}
return successors;
}
public int calcHValue(RasterPoint endPoint)
{
double l = Math.sqrt(Math.pow((double)endPoint.getRasterX() - (double)this.x,2) + Math.pow((double)endPoint.getRasterY() - (double)this.y,2));
return (int) l;
}
}
If I paint all the points in the watchedRasterPoints list I can see that the algorithm adds all points which have an about 1 bigger x or y coordinates as the start point in addition to all the other points over and left to the startpoint. He also but them in the openlist.
Do you have an idea?
Thx
leet
If I write it this way it works :D The return were wrong (what a bug grrrrrr)