迷宮求解器被困在死循環中

我正在迷宮求解器算法中工作，一切正常，直到它遇到死角並陷入循環，like this。問題似乎是，當它想要在那裏轉換足夠的空間時，它會轉向另一個轉彎，因爲它面對着前面的牆壁，因此陷入了無限循環。迷宮求解器被困在死循環中

下面是我正在使用的兩個代碼，但第一個代碼是最相關的代碼。

SimpleWindow就是一切都被繪製等主窗口中，並且maze類是生成例如wallAtLeft，wallInFront，atExit迷宮和值的文件（這些都是布爾型）

import se.lth.cs.ptdc.window.SimpleWindow; 
import se.lth.cs.ptdc.maze.*; 

public class MazeTurtle extends Turtle { 
protected int Maze; 

public MazeTurtle(SimpleWindow w, int x, int y) { 
    super(w, x, y); 
} 

public void walk(Maze maze) { 
    Maze m = new Maze(4); 
    Turtle t = new Turtle(w, m.getXEntry(), m.getYEntry()); 
    int x1 = m.getXEntry(); 
    int y1 = m.getYEntry(); 
    int dir = t.getDirection(); 
    t.penDown(); 

    while ((m.atExit(x1, y1)) == false) { 
     if (m.wallAtLeft(dir, x1, y1) == true) { 
      t.forward(1); 
      SimpleWindow.delay(10); 
     } 

     else if (m.wallAtLeft(dir, x1, y1) == false) { 
      t.left(90); 
      t.forward(1); 
      SimpleWindow.delay(10); 
     } 

     if (m.wallInFront(dir, x1, y1) == true) { 
      t.left(-90); 
      t.forward(1); 
      SimpleWindow.delay(10); 
     } 

     x1 = t.getX(); 
     y1 = t.getY(); 
     dir = t.getDirection(); 
     System.out.println("X: " + x1 + "Y: " + y1); 
    } 

} 

}

這裏是吸引一切的程序：

import se.lth.cs.ptdc.window.SimpleWindow; 
import se.lth.cs.ptdc.maze.*; 

public class MazeTest { 

public static void main(String args[]) { 

    Maze m = new Maze(4); 
    SimpleWindow w = new SimpleWindow(600, 600, "MazeTest"); 
    MazeTurtle t = new MazeTurtle(w, m.getXEntry(), m.getYEntry()); 
    t.penDown(); 
    m.draw(w); 
    t.walk(m); 
} 

}

迷宮類與描述，如果需要的話。請注意，這隻需要一些方法。 http://pastebin.com/gxSeEc2U

這是我使用的龜類：http://pastebin.com/0RqbVudn

來源

2012-11-08 Rob

不要使用過小走廊;-) – Aubin

有多寬是一個「走廊」？ – GSP

那麼我只能使用這些預定的迷宮。總共有5個。它完成了前3個，沒有任何問題，但是在第4個和第5箇中，它陷入了死衚衕。 – Rob

代替使用

if (m.wallInFront(dir, x1, y1) == true) { 
     t.left(-90); 
     SimpleWindow.delay(10);

我取代它與此：

if (m.wallInFront(dir, x1, y1) && m.wallAtLeft(dir, x1, y1) == true) { 
      t.left(-90); 
      SimpleWindow.delay(10); 
     }

現在，而不是檢查一個它一次檢查是否有一個角落不僅僅是一堵牆。

謝謝大家的幫助的方式:)

來源

2012-11-08 19:02:52 Rob

我想你不應該調用下面部分t.forward(1);，因爲有可能改變方向後再次是牆。

if (m.wallInFront(dir, x1, y1) == true) { 
     t.left(-90); 
     //t.forward(1); 
     SimpleWindow.delay(10); 
    }

我只是假設forward(1)試圖移動一個步驟，並且可以得到的成問題，如果不存在空間（在前壁）

來源

2012-11-08 17:59:43

那麼，你說得對，我並不需要't。但是問題依然存在，導致它與自己的尾巴相撞。（類似於遊戲「Snake」） – Rob

@Rob：我認爲如果它不向後移動（由於牆有兩次左右），你需要處理。我認爲你可以設置一個移動計數器並使用：如果轉動，則增加1，如果移動，則復位爲0.完成後，如果移動計數爲2，則添加一個額外的移動步驟。如果仍然有一堵牆，那麼假設它是死路一條，轉兩圈並開始後退。 –

算法看起來很穩定（「跟着左牆」）。如果執行得當，當面對死衚衕時，烏龜會向右轉兩次並開始回溯。 – bdares

迷宮求解器被困在死循環中

回答

相關問題