Как вернуться в лабиринт?

Итак, я пишу программу, которая заставляет робота исследовать лабиринт, чтобы найти указанную пещеру. Есть четыре типа ячеек: Пещера, Старт, Стена и Проход. Роботы могут двигаться только в проход или пещеру. Я реализовал свой метод так, чтобы робот не мог переместиться в посещаемую ячейку или выйти за ее пределы. Но как только он перемещается в ячейку, где нет допустимой соседней ячейки, программа останавливается. Итак, как мне заставить моего робота вернуться туда, где есть действительная ячейка? Я использую рекурсию для этого. Ниже мой код. Любая помощь будет отличной. Благодарю вас!

public void explore (Cell cavern, Maze maze) throws InterruptedException {
    // for debugging
    System.out.println(row + " " + col);
    System.out.println(cavern.getRow() + " " + cavern.getCol());
    System.out.println(visited.toString());
     TimeUnit.MILLISECONDS.sleep(10); // delay program
    //base case
    if (row == cavern.getRow() && col == cavern.getCol()) {
        foundCavern = true;
        return;
    }
    else {
        // move right
        if ((col+1) < maze.getNumCols() && !visited.contains(maze.getCell(row, col+1)) && (maze.getCell(row, col+1).isPassage() || maze.getCell(row, col+1).isCavern())) {
            visited.add(maze.getCell(row, col+1));
            setRobotLocation(row,col+1);
            explore(cavern, maze);
        }
        // move down
        else if ((row+1) < maze.getNumRows() && !visited.contains(maze.getCell(row+1, col)) && (maze.getCell(row+1, col).isPassage() || maze.getCell(row+1, col).isCavern())) {
            visited.add(maze.getCell(row+1, col));
            setRobotLocation(row+1,col);
            explore(cavern, maze);
        }
        // move left
        else if ((col-1) >= 0 && !visited.contains(maze.getCell(row, col-1)) && (maze.getCell(row, col-1).isPassage() || maze.getCell(row, col-1).isCavern())) {
            visited.add(maze.getCell(row, col-1));
            setRobotLocation(row,col-1);
            explore(cavern, maze);
        }
        // move up
        else if ((row-1) >= 0 && !visited.contains(maze.getCell(row-1, col)) && (maze.getCell(row-1, col).isPassage() || maze.getCell(row-1, col).isCavern())) {
            visited.add(maze.getCell(row-1, col));
            setRobotLocation(row-1,col);
            explore(cavern, maze);
        }
        else {
            foundCavern = false;
            return;
        }
    }
}

java eclipse recursion maze
person JOH    schedule 23.11.2014    source источник
comment
Вместо использования рекурсии может быть проще просто сохранить сделанные вами ходы в стеке.   -  person azurefrog    schedule 23.11.2014
comment
Значит, мой посещенный список должен быть стеком? Я вроде понимаю, почему, но не могли бы вы дать мне некоторые подробности. Например, где я должен вставить свой код?   -  person JOH    schedule 23.11.2014
comment
Я думаю, вам следует избавиться от else и вместо этого проверить, нужно ли вам также продолжать движение в других направлениях, что означает, что когда вы вернетесь с explore вызова, вы все еще не нашли пещеру.   -  person benji    schedule 23.11.2014
comment
Каждый раз, когда вы делаете ход, которого раньше не делали, вы добавляете его позицию в стек. Затем, чтобы повторить свои шаги, вы просто удаляете последнее местоположение и перемещаетесь туда.   -  person azurefrog    schedule 23.11.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, вы находитесь в правильном направлении. Что, я думаю, вам следует делать, так это продолжать проверять все направления, если только вы не нашли пещеру. Прямо сейчас вы проверяете только одно направление на каждой итерации из-за предложения else. Поэтому, когда вызов explore возвращается, вы не можете продолжать проверять другое направление и, по сути, не возвращаетесь. Если вы заставите свою функцию explore возвращать поле Boolean, указывающее, достигли ли вы пещеры, изменение вашего кода может работать следующим образом:

// move right
if ... // your condition to check if moving right is possible and you didn't visit
// code to move right
found = explore()
//move down if didn't find cavern
if (!found) // and moving down is possible and didn't visit
// code to move down
found = explore()
// keep checking other directions
person benji    schedule 23.11.2014
comment
В этом столько смысла! Я попробую это, когда буду за своим ноутбуком, и я сообщу вам, как все идет. Благодарю вас! - person JOH; 23.11.2014
comment
На самом деле это не сработало для меня. Но я заставил его работать. Мне просто нужно было сохранить местоположение робота перед всеми операторами if и восстановить местоположение после каждого оператора if. Спасибо за помощь! Я очень ценю это. - person JOH; 23.11.2014
comment
Правильно, я пропустил утверждение, чтобы вернуть местоположение, когда исследование вернется. Но работает ли это с else? Или вам пришлось удалить его, как я предложил? - person benji; 23.11.2014
comment
Я удалил оператор else. Я инициализировал foundCavern значением false (вне функции), поэтому мне не нужно было устанавливать значение false, когда робот не находит пещеру. И я изменил все else if только на if. В противном случае он пропустил бы все остальные else if при возврате, как вы и сказали. Спасибо за помощь. Действительно помогло. - person JOH; 24.11.2014