我需要为一个项目编写一个带AI的蛇游戏。我在编码在50x50 2d阵列上实现的最短路径算法时遇到了问题。我已经为AStar寻路算法编写了代码(请参阅下面的代码),但它似乎不起作用。有人可以帮我纠正我的代码,也可以有人帮我编写Dijktra的算法,因为我正在努力编写它的二维数组。值得一提的是,最短路径算法适用于我的蛇找到在2d板上获得苹果的最短路径。希望有人能帮忙。 只是为了让我的问题更加清楚:我的问题是我需要找到2d数组上两点之间的最短路径,因为我是编码的初学者,我需要编写一个算法的代码来找到最短路径点和终点,如Dijktra或AStar。在二维数组上实现星型算法
//implementing a*
public int manhattenDistance(Point current, Point goal){
return Math.abs(current.getX()-goal.getX())+Math.abs(current.getY()-goal.getY());
}
public ArrayList<Point> aStar(Point myHead, Point apple){
ArrayList<Point> closedSer=new ArrayList<>();
ArrayList<Point> openSet=new ArrayList<>();
openSet.add(myHead);
ArrayList<Point> cameFrom=new ArrayList<>();
int[][] gscore=new int[50][50];
for(int i=0;i<gscore.length;i++){
for(int j=0;j<gscore.length;j++)
gscore[i][j]=Integer.MAX_VALUE;
}
gscore[myHead.getX()][myHead.getY()]=0;
int[][] fscore=new int[50][50];
for(int i=0;i<fscore.length;i++){
for(int j=0;j<fscore.length;j++)
fscore[i][j]=Integer.MAX_VALUE;
}
fscore[myHead.getX()][myHead.getY()]=manhattenDistance(myHead,apple);
while(!openSet.isEmpty()){
Point current; int[] fscores=new int[openSet.size()];
for (int i=0;i<openSet.size();i++){
Point p=openSet.get(i);
fscores[i]=manhattenDistance(p,apple);
}int min=fscores[0], index=openSet.size();
for(int i=0;i<fscores.length-1;i++){
if(fscores[i]<fscores[i+1]) {
min = fscores[i];
index = i;
}if(fscores[i+1]<min){
min=fscores[i+1]; index=i+1;
}
}
current=openSet.get(index-1);
if(current==apple) return cameFrom;//.toArray(new Point[cameFrom.size()]);// reconstructpath(cameFrom,current);
openSet.remove(index-1);
closedSer.add(current);
Point[] currentNeighbourstemp=current.getNeighbours();
ArrayList<Point> currentNeighbours=new ArrayList<>();
for(Point n:currentNeighbourstemp)
if(isOnBoard(n)) currentNeighbours.add(n);
/*for(int i=0;i<currentNeighbours.length;i++){
for(int j=0; j<openSet.size();j++)
if(currentNeighbours[i]==openSet.get(j)) continue;;
}*/
for (Point neighbour:currentNeighbours){
Double tentative_gscore=gscore[neighbour.getX()][neighbour.getY()]+distanceBetween(neighbour,current);
boolean in=false;
for(int i=0;i<openSet.size();i++){//checking if in oppenset
if(neighbour==openSet.get(i)) in=true;
}
if(!in) openSet.add(neighbour);
else if(tentative_gscore>=gscore[neighbour.getX()][neighbour.getY()]) continue;
gscore[neighbour.getX()][neighbour.getY()]=tentative_gscore.intValue();
fscore[neighbour.getX()][neighbour.getY()]=gscore[neighbour.getX()][neighbour.getY()]+manhattenDistance(neighbour,apple);
}
}
return cameFrom;//.toArray(new Point[cameFrom.size()]);
}
public Double distanceBetween(Point a,Point b){
return Math.sqrt((b.getX()-a.getX())*(b.getX()-a.getX())+(b.getY()-a.getY())*(b.getY()-a.getY()));
}
public static float invSqrt(float x) {
float xhalf=0.5f*x;
int i=Float.floatToIntBits(x);
i=0x5f3759df-(i>>1);
x=Float.intBitsToFloat(i);
x=x*(1.5f-xhalf*x*x);
return x;
}
public float gravityDistance(Point that,Point th){
if(this.equals(that)) return Float.MAX_VALUE;
return 20.0f*invSqrt(Math.abs(th.x-that.x)+Math.abs(th.y-that.y));
}
您应该在每个符号之前和之后留出空格('+ - =/* ...') –
问题是什么? – Tempux
为了得到一个很好的答案,你需要让你的问题更清晰。提供一个明确的问题,你的答案将对你更有帮助。 – Cutter