Проблема о разрешении лабиринта с возвратом Java - PullRequest
Новая
       42

Проблема о разрешении лабиринта с возвратом Java

1 голос
/ 18 марта 2019

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

Я разработал код и работает для некоторых простых сценариев, но не удается,по крайней мере, еще один комплекс.

Прежде чем я раскрою код и конкретную проблему, я хочу объяснить, как он работает.

О КОДЕ

Итак, у меня есть два метода initializeMaze1 и initializedMaze2 , который просто загружает некоторые предустановленные сценарии (начальная точка, некоторые стены и конечная точка).

У меня нетпроблемы с первым, но это меняется со вторым.

Эти методы дают мне целую матрицу, которая представляет сущности (стены, начальная точка ...).

Iесть также метод печати для удаления.

И, наконец, метод лабиринта, который является кодом возврата.Параметры:

  1. Сгенерированный лабиринт (который делается методами, о которых я говорил ранее).
  2. Положение "игрока" в строках лабиринта.
  3. Положение "игрока" в столбцах лабиринта.
  4. Решение.Это еще одна матрица, которая будет указывать путь игрока, поэтому я отмечу движения там, и у меня будет разбит оригинальный лабиринт.

Теперь я собираюсь поговоритьболее подробно о коде обратного хода.

BACKTRACKING CODE

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

У меня есть метод isFactible , который анализирует движение и говорит, нормально ли это или нет (если происходит сбойсо стеной или если выходит за пределы).

Если не является способным, то пытается другим движением (увеличивает итерационную переменную цикла for).

Если не является допустимым имы заканчиваем цикл, помечаем фактическую позицию и возвращаем ложное значение (так что другой контекст узнает об этом).

Если это допустимо, мы отметим новую позицию и нам нужноОтношение между двумя возможностями:

  • Позиция, которую мы собираемся переместить, является концом (объективным или выходным), поэтому мы добились успеха.
  • Позиция, которой мы являемсядвигаться, это не конец, поэтому мы снова рекурсивно вызываем новую позицию, которую мы уже переместили.

Теперь я собираюсь поговорить о найденных проблемах.

ПРОБЛЕМЫ

Когда я загружаю второй лабиринт, у нас есть такой сценарий:

S: Старт.E: Пусто.W: Стена.F: Готово.

| S | E | W | W |

| E | E | E | E | Вот проблема

| E | E | W | W |

| W | E | E | F |

Итаккод пытается переместиться сначала вправо, если нет, пытается вниз, если нет, пытается влево, а если нет, пытается вверх.У нас есть это предустановленное движение.

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

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

Но я не думаю, что это хорошее решение.

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

Благодарю вас.

КОД 

import java.util.List;
import java.util.ArrayList;

public class maze {

private static final int START = 1;
private static final int END = 2;
private static final int WALL = 3;
private static final int EMPTY = 0;
private static final int MOVE_RIGHT = 5;
private static final int MOVE_DOWN = 6;
private static final int MOVE_LEFT = 7;
private static final int MOVE_UP = 8;

public static void main(String[] args)
{
    int[][] solution = {{1,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
    showInitializationMessage();
    print(solution);
    if(maze(initializeMaze2(),0, 0, solution))
    {
        print(solution);
    }
    else
    {
        System.out.println("There is no solution");
    }
}

private static void showInitializationMessage()
{
    System.out.println("MAZE APPLICATION");
    System.out.println("_________________");
    System.out.println();
    System.out.println();
}

private static void print(int[][] solution)
{
    for(int i=0; i<solution.length;i++)
    {
        for(int j=0;j<solution.length;j++)
        {
            System.out.print(solution[i][j]);
        }
        System.out.println();
    }
    System.out.println();
    System.out.println("____________________");
    System.out.println();
}

private static int[][] initializeMaze1()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=WALL;
    maze[2][1]=EMPTY;
    maze[3][1]=WALL;

    //Setting column 2
    maze[0][2]=EMPTY;
    maze[1][2]=WALL;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=EMPTY;
    maze[1][3]=EMPTY;
    maze[2][3]=EMPTY;
    maze[3][3]=END;

    return maze;


}

private static int[][] initializeMaze2()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=EMPTY;
    maze[2][1]=EMPTY;
    maze[3][1]=EMPTY;

    //Setting column 2
    maze[0][2]=WALL;
    maze[1][2]=EMPTY;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=WALL;
    maze[1][3]=EMPTY;
    maze[2][3]=WALL;
    maze[3][3]=END;

    return maze;


}

private static boolean checkNotOutOfBounds(int[][] maze,int stepX, int stepY, int movement )
{
    if(movement==MOVE_RIGHT)
    {
        if(stepY+1>maze.length-1)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(stepX+1>maze[0].length)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(stepY-1<0)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(stepX-1<0)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkNotCollideWithObstacle(int[][] maze, int stepX, int stepY , int movement)
{
    if(movement==MOVE_RIGHT)
    {
        if(maze[stepX][stepY+1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(maze[stepX+1][stepY]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(maze[stepX][stepY-1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(maze[stepX-1][stepY]==WALL)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement)
{
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) && checkNotCollideWithObstacle(maze, stepX, stepY, movement))
    {
        return true;
    }
    return false;
}

private static boolean isFactible(int[][] maze,int stepX, int stepY, int[][] solution, int attemp)
{
    if(attemp==0)
    {
        //MOVE RIGHT
        return checkValidMovement(maze, stepX, stepY, MOVE_RIGHT);
    }
    else if(attemp==1)
    {
        //MOVE DOWN
        return checkValidMovement(maze, stepX, stepY, MOVE_DOWN);
    }
    else if(attemp==2)
    {
        //MOVE LEFT
        return checkValidMovement(maze, stepX, stepY, MOVE_LEFT);
    }
    else if(attemp==3)
    {
        //MOVE UP
        return checkValidMovement(maze, stepX, stepY, MOVE_UP);
    }
    return false;
}

private static boolean maze(int[][] maze,int stepX, int stepY, int[][] solution)
{

    boolean success =false;
    for(int attempt=0; attempt<4 && !success; attempt++)
    {
        //solution[stepX][stepY]=attempt???
        if(isFactible(maze,stepX, stepY, solution,attempt))
        {
            mark(solution,stepX, stepY,attempt);
            print(solution);
            int updatedStepX = updateStepX(stepX, stepY, maze, attempt);
            int updatedStepY = updateStepY(stepX, stepY, maze, attempt);

            if(maze[updatedStepX][updatedStepY]==END)
            {
                success=true;
            }
            else
            {
                success = maze(maze, updatedStepX, updatedStepY, solution);
            }
        }

    }
    if(!success)
    {
        solution[stepX][stepY]=0;
        print(solution);



    }
    return success;
}

private static void mark(int[][] solution, int stepX, int stepY, int attempt)
{
    if(attempt==0)
    {
        solution[stepX][stepY+1]=1;
    }
    else if(attempt==1)
    {
        solution[stepX+1][stepY]=1;
    }
    else if(attempt==2)
    {
        solution[stepX][stepY-1]=1;
    }
    else if(attempt==3)
    {
        solution[stepX-1][stepY]=1;
    }
}

private static int updateStepX(int oldStepX, int oldStepY, int[][] maze, int attemp)
{
    int updatedStepX=0;
    if(attemp==1)
    {
        updatedStepX=oldStepX+1;
    }
    else if(attemp==3)
    {
        updatedStepX=oldStepX-1;
    }
    else
    {
        updatedStepX=oldStepX;
    }

    return updatedStepX;
}

private static int updateStepY(int oldStepX, int oldStepY, int[][] maze, int attempt)
{
    int updatedStepY=0;

    if(attempt==0)
    {
        updatedStepY=oldStepY+1;
    }
    else if(attempt==2)
    {
        updatedStepY=oldStepY-1;
    }
    else
    {
        updatedStepY=oldStepY;
    }

    return updatedStepY;
}

}

Ответы [ 3 ]

2 голосов
/ 18 марта 2019

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

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

Когда вы возвращаетесь в какое-то место (следует разрешить повторное посещение), обращайтесь с уже опробованным направлением так же, как со стеной, т. Е. Оно недопустимо.

Если у вас больше нет действительных указаний, верните путь, которым вы пришли.

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

1 голос
/ 18 марта 2019

Как сказал DrPhill, вы должны отслеживать, где вы были.Вы уже делаете это в функции mark, но вы не используете эту информацию в функции checkValidMovement.

Вы должны изменить эту функцию, чтобы она выглядела примерно так: 

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement, int[][] solution)
  {
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) 
        && checkNotCollideWithObstacle(maze, stepX, stepY, movement)
        && isNotYetVisited(maze, stepX, stepY, movement, solution))
    {
      return true;
    }
    return false;
  }

где isNotYetVisited функция возвращает false, если solution на следующем шаге не равен 1.

Надеюсь, это поможет.

1 голос
/ 18 марта 2019

Я думаю, что самый простой способ сделать это - просто запомнить координаты вашего последнего присутствия.Если нет никаких других правильных ходов, кроме возврата назад, вернитесь назад и отметьте место, на котором вы были, в качестве стены.Наконец вы доберетесь до [F].

...