迷宫求解器陷入死循环 [英] Maze solver gets stuck in a loop at a dead-end

问题描述

我正在使用迷宫求解器算法，并且一切正常，直到遇到死角并陷入循环为止，喜欢.问题似乎是，当它想在那儿转弯时没有足够的空间，因此它转了一圈，因为它面对着前面的墙，因此陷入了无休止的循环.

这是我正在使用的两个代码，但是第一个是最相关的代码.

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

解决方案

而不是使用

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);
        }

现在，它不会一次检查一件事，而是会检查是否不仅有墙壁还有一个角落.

谢谢大家的帮助:)

I'm working in a Maze solver algorithm and everything is working fine until it hits a dead-end and gets stuck in a loop, like this. The problem seems to be that when it want to turn around there aint enough space for it so instead it makes another turn since it faces a wall in front and thus gets stuck in an endless loop.

Here are the two codes I'm working with but the first one is the most relevant one.

SimpleWindow is the main window where everything gets drawn etc, and the maze class is the file which generates the mazes and values for example wallAtLeft, wallInFront, atExit (these are all boolean)

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);
    }

}

}

Here is the program that draws everything:

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);
}

}

The maze class with descriptions if it is needed. Note that only some of the methods are needed for this. http://pastebin.com/gxSeEc2U

This is the turtle class I'm using: http://pastebin.com/0RqbVudn

解决方案

Instead of using

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

I replaced it with this:

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

Now instead of checking one thing at a time it checks if there is a CORNER not only a wall.

Thank you all for the help on the way :)

这篇关于迷宫求解器陷入死循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！