Java-迷宮廣度第一搜索最短路徑

Question

我似乎有一個問題，理解如何檢索我正在實現的廣度優先搜索算法發現的最短路徑。目前該算法的工作原理是它可以找到迷宮的出口，如果它能夠到達它。在另一篇文章中，有人提到在一個節點被標記爲已訪問後保留父節點。 我試圖通過在Point結構中包含一個父點來跟蹤父項的一個簡單實現，但是當我標記網格上的路徑時，它標記了它到目前爲止已經通過的所有路徑，我相信我可能已經搞砸了以某種方式記錄父母的記錄。

任何人都有任何線索，我哪裏出了問題。 也許我錯過了一些簡單的東西？該代碼包含在下面作爲參考。

迷宮是2D整數網格。假設1是牆壁，0是可移動路徑。

Point類包含： Point Parent int x，y;沒有更多。

public Point BFS(int x, int y){ 
    Queue<Point> Path = new Queue<>(); 

    Path.enqueue(new Point(x,y));//push current on queue 

    Point Cur = Path.front();//make current point 
    //test code for recursive backcall of path 
     Cur.setParent(null); 
    //test code for recursive backcall of path 


    Point end = new Point(mWidth-2, mHeight-2);//set goal 

    while((!Path.isEmpty())){ 
     Point old = Cur; 

     Cur = Path.dequeue(); 
     Cur.setParent(old); 

     if(Cur.compareto(end)){ 
      return Cur;//return Point then traverse up from here calling Cur.Parent to get path. 
     } 
     else if(Maze[Cur.getX()][Cur.getY()]==1){//Enque all possible paths 

      Maze[Cur.getX()][Cur.getY()] = 2;//mark as visitied 
      if(Cur.getX()-1>=0) 
       if(Maze[Cur.getX()-1][Cur.getY()]==1) 
        Path.enqueue(new Point(Cur.getX()-1,Cur.getY())); 

      if(Cur.getX()+1<mWidth) 
       if(Maze[Cur.getX()+1][Cur.getY()]==1) 
        Path.enqueue(new Point(Cur.getX()+1,Cur.getY())); 

      if(Cur.getY()-1>=0) 
       if(Maze[Cur.getX()][Cur.getY()-1]==1) 
        Path.enqueue(new Point(Cur.getX(),Cur.getY()-1)); 

      if(Cur.getY()+1<mHeight) 
       if(Maze[Cur.getX()][Cur.getY()+1]==1) 
        Path.enqueue(new Point(Cur.getX(),Cur.getY()+1)); 
     } 

    } 
    return null; 
} 

Answer 1

看起來像old多次迭代後不再是父項。

Point next = new Point(Cur.getX()-1,Cur.getY()); 
next.setParent(Cur); 
Path.enqueue(next); 

然後，當你發現到最後，你應該能夠通過調用的getParent（），直到它得到的路徑回到開始：您可以將當點到隊列代替，例如設置父null。