我需要爲一個項目編寫一個帶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