Java решает лабиринт с рекурсивной задачей

Question

У меня есть задание, где я должен быть в состоянии отобразить путь лабиринта от входа до выхода, и я получил его до определенной степени, но когда лабиринт усложняется с тупиками и так далее Программа переходит в бесконечную рекурсию. Если бы вы могли оказать мне какую-либо помощь, чтобы указать мне правильное направление, это было бы очень ценно.

В настоящее время теорию можно найти в классе Room.

Вот класс Room, в котором хранятся ссылки на каждую комнату, соединяющую лабиринт, что-то вроде связанного списка, связанного в 6 направлениях: север, юг, восток, запад, вверх и вниз.

import java.util.ArrayList;

public class OurRoom
{
    private OurRoom exits[];
    private String name;
    private static ArrayList<OurRoom> list;

    public OurRoom()
    {
        this(null);
    }

    public OurRoom(String name)
    {
        this.name = name;
        this.list = new ArrayList<OurRoom>();
        exits = new OurRoom[Direction.values().length];
        for(OurRoom exit : exits)
        {
            exit = null;
        }
    }       


    public void connectTo(OurRoom theOtherRoom, Direction direction)
    {
        exits[direction.ordinal()] = theOtherRoom;
        theOtherRoom.exits[direction.getOpposite().ordinal()] = this;
    }

    public OurRoom getExit(Direction direction)
    {
        return exits[direction.ordinal()];
    }

    public boolean lookExit(Direction direction)
    {
        return exits[direction.ordinal()] != null;
    }

    public String getName() {
        return name;
    }

    public OurRoom solveRecursively(OurRoom exit) {
        list.add(this);
        if(this == exit) {
            return this;
        }else { 
            OurRoom temp = null;            
            if(lookExit(Direction.east)) {
                temp = exits[Direction.east.ordinal()].solveRecursively(exit);              
            }   
            else if(lookExit(Direction.up)) {
                temp = exits[Direction.up.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.south)) {
                temp = exits[Direction.south.ordinal()].solveRecursively(exit);             
            }           
            else if(lookExit(Direction.down)) {
                temp = exits[Direction.down.ordinal()].solveRecursively(exit);
            }
            else if(lookExit(Direction.west)) {
                temp = exits[Direction.west.ordinal()].solveRecursively(exit);      
            }   
            else if(lookExit(Direction.north)) {
                temp = exits[Direction.north.ordinal()].solveRecursively(exit); 
            }
            return temp;
        }
    }

    public ArrayList<OurRoom> getList() {
        return list;
    }

}

Вот Направление enum

public enum Direction
{
    north, south, east, west, up, down;

    public Direction getOpposite()
    {
        switch(this)
        {
            case north:
                return south;
            case south:
                return north;
            case east:
                return west;
            case west:
                return east;
            case up:
                return down;
            case down:
                return up;
            default:
                return this;
        }
    }
}

А вот пример того, как строится лабиринт.

import java.util.ArrayList;
import java.util.Iterator;

public class OurMaze
{
    private OurRoom entrance, exit;

    public OurMaze()
    {
        this(1);
    }

    public OurMaze(int mazeNumber)
    {
        entrance = null;
        exit = null;
        switch(mazeNumber)
        {
        case 0:
            break;
        case 1:
            this.buildMaze1();
            break;             
        default:
        }
    }

    public OurRoom getEntrance()
    {
        return entrance;
    }

    public OurRoom getExit()
    {
        return exit;
    }

    public Iterator<OurRoom> findPathRecursively() {
        entrance.solveRecursively(exit);
        ArrayList<OurRoom> list = entrance.getList();       
        return list.iterator();
    }

    private void buildMaze1()
    {
        OurRoom room1, room2;

        room1 = new OurRoom("Room 1");
        room2 = new OurRoom("Room 2");
        room1.connectTo(room2, Direction.north);

        entrance = room1;
        exit = room2;
    }

    public static void main(String[] args) {
        OurMaze maze = new OurMaze(1);      
    }
}

Answer 1

Вам просто нужно сохранить двумерный массив со значениями, указывающими, была ли ячейка посещена или нет: вы не хотите проходить через одну и ту же ячейку дважды.

Кроме того, это просто ширинаfirst-search (глубина-first-search тоже подойдет, если вам не нужен кратчайший путь).

Некоторые ссылки
http://en.wikipedia.org/wiki/Flood_fill
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Пример процедуры поиска.

    void dfs(int i, int j) {
        if cell(i, j) is outside of maze or blocked {
            return
        }
        if visited[i][j] {
            return
        }
        visited[i][j] = true;
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

Сам путь можно найти, если, как и с visited, для каждой ячейки, в которой вы храните ячейку, из которой вы пришли к ней.Таким образом, печать будет выглядеть так (просто псевдокод).

var end = exit_point;
while (end != start_point) {
   print end;
   end = came_from[end];
}

edit
Код выше для двумерного лабиринта, и я только что заметил, что у вас естьразмерная версия.Но третью координату легко ввести в приведенном выше примере.
Дайте мне знать, если возникнут какие-либо трудности.

Answer 2

Другие описали соответствующие подходы к решению этой проблемы, но я думаю, что стоит точно указать , почему ваша программа не будет масштабироваться до более сложных лабиринтов.

Как намекнул Даффимо,проблема в том, что ваш алгоритм не выполняет никакого обратного отслеживания правильно - когда он берет ветку, которая оказывается тупиком, и возвращается к предыдущему квадрату, он вообще этого не помнит.И так как он пытается выйти в фиксированном порядке, он всегда повторяет попытку неудачного выхода немедленно.

Посмотрите, как определена функция solveRecursively, и вы увидите это излюбая заданная комната, только одно направление когда-либо будет испробовано.Если у комнаты есть выход на восток, то даже не имеет значения, есть ли у нее какие-либо другие выходы, так как блок if-else не будет никогда учитывать их.

Так, как он поворачиваетсяваша логика решения потерпит неудачу (т.е. войдет в бесконечный цикл между двумя комнатами) в любом случае, когда правильное решение не является «первым» выходом из каждой комнаты в порядке, который вы там определили.

(Быстрое решение - сохранить простой логический флаг для каждой комнаты / направления. Установите его перед вызовом рекурсивного вызова, затем, если вы снова окажетесь в этой комнате, вы знаете что направление не работает и может позволить блоку if провалиться, чтобы попробовать один из других выходов. Рефакторинг этого для использования типичной логики BFS, как предполагает Никита, был бы лучше в целом)

Answer 3

При решении лабиринта представьте его в виде 6-ти графного графика, где каждый узел представляет собой комнату, а каждый край представляет собой движение в одном из шести направлений. Затем вы можете применить некоторые из известных алгоритмов для поиска кратчайших путей.

Эта страница описывает различные решения для поиска путей по графам, которые структурированы как таковые. Ваш график проще, чем те, которые описывают карты реального мира, поскольку стоимость путешествия по любому краю равна стоимости путешествия по любому другому краю.

Обязательно посмотрите алгоритм Дейкстры .

Answer 4

Держу пари, что вам нужно какое-то дерево, чтобы отслеживать, где вы были.

Когда рекурсия не удалась, это обычно означает, что человек, пишущий метод, не выразил условие остановкидолжным образом.Что у тебя?

Я думаю, что это была первая игра, которую я когда-либо встречал на компьютере.Это был мэйнфрейм IBM в школе, где я получил степень бакалавра.Ввод / вывод был на бумажном телетайпе.Много слез слез было заплакано на счетах, которые были смыты в этой игре-лабиринте.Большое удовольствие.