-1
У меня проблема с моим алгоритмом AStar. Дело в том, что: Если у меня есть начальная точка (10,10), и точка цели остается над начальной точкой (5,5), все отлично работает. Но если цель находится под или справа от начальной точки (15,12), алгоритм говорит, что пути нет.AStar иногда нет способа
Я не знаю, почему ?????
Просьба помочь мне! Я не могу найти ошибку!
Алгоритм:
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);
}
}
}
}
И один другой класс:
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;
}
}
Если я пишу все пункты в списке watchedRasterPoints я могу видеть, что алгоритм добавляет все точки, которые имеют около 1 более крупные координаты x или y в качестве начальной точки в дополнение ко всем остальным точкам и слева до начальной точки. Он также, но их в открытом списке.
У вас есть идея?
Thx
Лит
У вас есть 'de.nkpmedia.rccar. floor.laserscanner.LaserPoint' в вашем примере, сделав это не-mcve (http://stackoverflow.com/help/mcve). Почему бы не попробовать отладить ваш код, переходя по строкам ... – alterfox
Я сделал. Но я не нашел ошибку. Но теперь я знаю ошибку! Возвраты в функции расширения неверны! Они завершили целую функцию и из-за этого тоже цикл (для (точка RasterPoint: currentPoint.getSuccessorPoints (this.raster, this))) теперь она работает – Leet
Там вы идете. Вы не нашли ошибку, работали над ней и обнаружили ошибку. – alterfox