2016-09-29 82 views
0

我需要爲一個項目編寫一個帶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)); 
} 
+1

您應該在每個符號之前和之後留出空格('+ - =/* ...') –

+1

問題是什麼? – Tempux

+0

爲了得到一個很好的答案,你需要讓你的問題更清晰。提供一個明確的問題,你的答案將對你更有幫助。 – Cutter

回答

1

這裏是一個JAVA實現Dijkstra的最短路徑算法:

// A Java program for Dijkstra's single source shortest path algorithm. 
// The program is for adjacency matrix representation of the graph. 

class ShortestPath 
{ 
    /* A utility function to find the vertex with minimum distance value, 
     from the set of vertexes not yet included in shortest path tree */ 
    static final int V = 9; 
    int minDistance(int dist[], boolean sptSet[]) 
    { 
     // Initialize min value 
     int min = Integer.MAX_VALUE, min_index = -1; 

     for(int v = 0; v < V; v++) 
     { 
      if(sptSet[v] == false && dist[v] <= min) 
      { 
       min = dist[v]; 
       min_index = v; 
      } 
     } 
     return min_index; 
    } 

    // A utility function to print the constructed distance array 
    void printSolution(int dist[], int n) 
    { 
     System.out.println("Vertex Distance from Source"); 
     for(int i = 0; i < V; i++) 
      System.out.println(i+" \t\t "+dist[i]); 
    } 

    /* Function that implements Dijkstra's single source shortest path 
     algorithm for a graph represented using adjacency matrix 
     representation */ 
    void dijkstra(int graph[][], int src) 
    { 
     int dist[] = new int[V]; /* The output array, dist[i] will hold 
            the shortest distance from src to i */ 
     /* sptSet[i] will be true if vertex i is included in shortest 
      path tree or shortest distance from src to i is finalized */ 
     Boolean sptSet[] = new Boolean[V]; 

     for(int i = 0; i < V; i++) 
     { 
      dist[i] = Integer.MAX_VALUE; 
      sptSet[i] = false; 
     } 

     // Distance of source vertex from itself is always 0 
     dist[src] = 0; 

     //Find shortest path for all vertexes 
     for(int count = 0; count < V-1; count++) 
     { 
      /* Pick the minimum distance vertex from the set of vertexes 
       not yet processed. u is always equal to src in first 
       iteration. */ 
      int u = minDistance(dist, sptSet); 

      // Mark the picked vertex as processed 
      sptSet[u] = true; 

      /* Update dist value of the adjacent vertexes of the 
       picked vertex. */ 
      for(int v = 0; v < V; v++) 
      { 
       /* Update dist[v] only if it is not in sptSet, there is an 
        edge from u to v, and total weight of path from src to 
        v through u is smaller than current value of dist[v] */ 
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
            && dist[u]+graph[u][v] < dist[v]) 
         dist[v] = dist[u] + graph[u][v]; 
      } 
     } 

     // print the constructed distance array 
     printSolution(dist, V); 
    } 
    public static void main(String[] args) 
    { 
     // Create an example graph 
     int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0}, 
            {4, 0, 8, 0, 0, 0, 0, 11, 0}, 
            {0, 0, 7, 0, 9, 14, 0, 0, 0}, 
            {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
            {0, 0, 0, 9, 0, 10, 0, 0, 0}, 
            {0, 0, 4, 14, 10, 0, 2, 0, 0}, 
            {0, 0, 0, 0, 0, 2, 0, 1, 6}, 
            {8, 11, 0, 0, 0, 0, 1, 0, 7}, 
            {0, 0, 2, 0, 0, 0, 6, 7, 0}}; 
     ShortestPath t = new ShortestPath(); 
     t.dijkstra(graph, 0); 
    } 
} 

代碼是非常自我解釋。一些要注意的要點:

  • 這裏我拍了一個9X9的二維數組。 9行代表圖中的9個節點。每列表示其他節點與相應節點之間的連接。
  • 曲線A非零值[i] [j]位置表示有Ĵ之間的連接。並且該值表示從ij的成本。
  • 甲在零圖表[i] [j]位置是指Ĵ沒有連接。
  • src代表從其中計算到所有其他點的距離的來源。
  • 請記住,您的網格代表一個圖形,其中頂點/節點是單元格,邊緣是相鄰的單元格。

希望這有助於!如果您在理解算法時遇到任何問題,請告訴我。祝你好運!

+2

非常感謝您的幫助。我只是不明白你的實現中的兩件事。第一個是dijkstra函數的第二個參數,我知道你在上面解釋過它,但是它代表我在圖[i] [j]中開始的節點嗎?第二件事是內循環(在dijkstra函數中),我應該獲得當前單元格的所有鄰居並將它們添加到dist [v]中嗎?感謝您的幫助 – amine

+1

第二個參數表示源節點,我們將從中找出所有其他節點的距離。比方說,我有節點(1,2,3,4,5),我想要找出節點1的距離2,3,4,5。然後,1是源節點。 V代表節點的數量。對於你的情況,它將是50.我的代碼中有一個小錯誤,現在它已被糾正。謝謝你指出! –