Javafx 2D 迷宫标准解决方案不起作用

Question

我查看了很多线程，发现我认为是标准 Java 迷宫的解决方案我的 solveMaze 方法是：

    if (done(r, c)) {// if within Goal stop and return this maze
        return this;
    } else if (r > 1 && getCell(r - 1, c) == ' ') {
        setCell(r - 1, c, '*');
        return solveMaze(r - 1, c);
    } else if (r < maxRow - 1 && getCell(r + 1, c) == ' ') {
        setCell(r + 1, c, '*');
        return solveMaze(r + 1, c);
    } else if (c < maxCol - 1 && getCell(r, c + 1) == ' ') {
        setCell(r, c + 1, '*');
        return solveMaze(r, c + 1);

    } else if (c > 1 && getCell(r, c - 1) == ' ') {
        setCell(r, c - 1, '*');
        return solveMaze(r, c - 1);
    } else {
        return null;// solveMaze(r, c);
    }

但它没有达到目标，而是在中途结束 end result of maze

我猜这是因为该方法必须 return 一些东西，而我最后 return null，但我也试图使它成为一个 void 方法并且它做同样的事情.我试图摆脱 r 和 c 的限制，然后我得到数组越界异常。

我只是不明白为什么代码在本质上是标准代码时不起作用。

这里是空的：

    if (done(r, c)) {// if within Goal stop and return this maze
        return ;
    } else if (r > 1 && getCell(r - 1, c) == ' ') {
        setCell(r - 1, c, '*');
         solveMaze(r - 1, c);
    } else if (r < maxRow - 1 && getCell(r + 1, c) == ' ') {
        setCell(r + 1, c, '*');
         solveMaze(r + 1, c);
    } else if (c < maxCol - 1 && getCell(r, c + 1) == ' ') {
        setCell(r, c + 1, '*');
         solveMaze(r, c + 1);

    } else if (c > 1 && getCell(r, c - 1) == ' ') {
        setCell(r, c - 1, '*');
         solveMaze(r, c - 1);
    }

我也试过做不等于，因为墙被指定为 - 和 |我有

    if (done(r, c)) {// if within Goal stop and return this maze
        return this;
    } else if (r > 1 && getCell(r - 1, c) != '|' && getCell(r - 1, c) != '*' && getCell(r, c + 1) != '+'
            && getCell(r, c + 1) != 'S') {
        System.out.println(getCell(r - 1, c) + "r " + r + " c " + c);
        setCell(r - 1, c, '*');
        return solveMaze(r - 1, c);
    } else if (r < maxRow - 1 && getCell(r + 1, c) != '|' && getCell(r + 1, c) != '*' && getCell(r, c + 1) != '+'
            && getCell(r, c + 1) != 'S') {
        System.out.println(getCell(r + 1, c) + "r " + r + " c " + c);
        setCell(r + 1, c, '*');
        return solveMaze(r + 1, c);
    } else if (c < maxCol - 1 && getCell(r, c + 1) != '-' && getCell(r, c + 1) != '*' && getCell(r, c + 1) != '+'
            && getCell(r, c + 1) != 'S') {
        System.out.println(getCell(r, c + 1) + "r " + r + " c " + c);
        setCell(r, c + 1, '*');
        return solveMaze(r, c + 1);

    } else if (c > 1 && getCell(r, c - 1) != '-' && getCell(r, c - 1) != '*' && getCell(r, c + 1) != '+'
            && getCell(r, c + 1) != 'S') {
        System.out.println(getCell(r, c - 1) + "r " + r + " c " + c);
        setCell(r, c - 1, '*');
        return solveMaze(r, c - 1);
    } else {
        System.out.println(getCell(r, c) + "r " + r + " c " + c);
        return null;// solveMaze(r, c);
    }
}

接下来我应该尝试什么？谢谢

Answer 1

您的代码以特定优先级解决迷宫问题，即 U、D、R、L，但不会回溯找到所有解决方案。

根据地图和您的优先级，您的代码从一开始就先进入 R（它不能向上或向下），然后一有机会就向上，直到撞墙，然后停止（当没有有效动作了）。

您需要删除不允许回溯的 else if 结构。回溯时，清除位置（被标记为*，需要恢复回空space）。

下面应该可以工作，但没有测试（你可能需要一个静态布尔 solved 变量，它允许所有递归到 return 立即：if (solved) return;.

if (solved)
    return;
if (done(r, c)) {// if within Goal stop and return this maze
    solved=true;
    return ;
} 
if (r > 1 && getCell(r - 1, c) == ' ') {  // Try up first
    setCell(r - 1, c, '*');
    solveMaze(r - 1, c);
    setCell(r - 1, c, ' ');  // Restore the cell back to open and keep trying
} 
if (r < maxRow - 1 && getCell(r + 1, c) == ' ') {  // Down
    setCell(r + 1, c, '*');
    solveMaze(r + 1, c);
    setCell(r + 1, c, ' ');  // Restore the cell back to open and keep trying
} 
if (c < maxCol - 1 && getCell(r, c + 1) == ' ') {  // Right
    setCell(r, c + 1, '*');
    solveMaze(r, c + 1);
    setCell(r, c + 1, ' ');
} 
if (c > 1 && getCell(r, c - 1) == ' ') {  // Left
    setCell(r, c - 1, '*');
     solveMaze(r, c - 1);
    setCell(r, c - 1, ' ');
}

Answer 2

if (solved)
        return null;
    if (done(r, c)) {// if within Goal stop and return this maze
        solved = true;
        return null;
    }
    if (r > 1 && getCell(r - 1, c) == ' ') {// Up goes first
        setCell(r - 1, c, '*');
        solveMaze(r - 1, c);
        if (solved)
            return null;
        setCell(r - 1, c, ' ');
    }
    if (r < maxRow - 1 && getCell(r + 1, c) == ' ') {// Down
        setCell(r + 1, c, '*');
        solveMaze(r + 1, c);
        if (solved)
            return null;
        setCell(r + 1, c, ' ');
    }
    if (c < maxCol - 1 && getCell(r, c + 1) == ' ') {// Right
        setCell(r, c + 1, '*');
        solveMaze(r, c + 1);
        if (solved)
            return null;
        setCell(r, c + 1, ' ');
    }
    if (c > 1 && getCell(r, c - 1) == ' ') { // Left
        setCell(r, c - 1, '*');
        solveMaze(r, c - 1);
        if (solved)
            return null;
        setCell(r, c - 1, ' ');
    }

    return null;

Javafx 2D 迷宫标准解决方案不起作用

Javafx 2D maze standard solution not working

java

algorithm

maze

javafx