Лабиринт в Java

Програмиране

1. Въведение

В тази статия ще разгледаме възможните начини за навигация в лабиринт, използвайки Java.

Считайте лабиринта за черно-бяло изображение, с черни пиксели, представляващи стени, и бели пиксели, представляващи път. Два бели пиксела са специални, като единият е влизане в лабиринта, а друг изход.

Като се има предвид такъв лабиринт, ние искаме да намерим път от входа до изхода.

2. Моделиране на лабиринта

Ще считаме лабиринта за двумерно цяло число. Значението на числовите стойности в масива ще бъде съгласно следното споразумение:

  • 0 -> Път
  • 1 -> Стена
  • 2 -> Лабиринт
  • 3 -> Изход от лабиринт
  • 4 -> Клетъчна част от пътя от влизане до излизане

Ще моделираме лабиринта като графика . Влизането и излизането са двата специални възела, между които трябва да се определи пътят.

Типичната графика има две свойства, възли и ръбове. Ръбът определя свързаността на графиката и свързва един възел с друг.

Следователно ще приемем четири неявни ръба от всеки възел, свързвайки дадения възел с неговия ляв, десен, горен и долен възел.

Нека дефинираме сигнатурата на метода:

public List solve(Maze maze) { }

Входът за метода е лабиринт, който съдържа 2D масив, с конвенцията за именуване, дефинирана по-горе.

Отговорът на метода е списък с възли, който формира път от възела към изхода.

3. Рекурсивен Backtracker (DFS)

3.1. Алгоритъм

Един доста очевиден подход е да се изследват всички възможни пътища, които в крайна сметка ще намерят път, ако той съществува. Но такъв подход ще има експоненциална сложност и няма да се мащабира добре.

Възможно е обаче да персонализирате решението за груба сила, споменато по-горе, чрез проследяване и маркиране на посетени възли, за да получите път в разумен срок. Този алгоритъм е известен също като търсене с дълбочина.

Този алгоритъм може да бъде очертан като:

  1. Ако сме на стената или на вече посетен възел, върнете неуспех
  2. Иначе ако сме изходният възел, тогава връщаме успеха
  3. В противен случай добавете възела в списъка с пътища и рекурсивно пътувайте във всички четири посоки. Ако се върне неуспех, премахнете възела от пътя и върнете неуспеха. Списъкът с пътища ще съдържа уникален път, когато бъде намерен изходът

Нека приложим този алгоритъм към лабиринта, показан на Фигура-1 (а), където S е началната точка, а E е изходът.

За всеки възел обхождаме всяка посока по ред: отдясно, отдолу, отляво, отгоре.

В 1 (b) изследваме пътека и удряме стената. След това се връщаме, докато се намери възел, който има нестенни съседи, и изследваме друг път, както е показано в 1 (c).

Отново удряме стената и повтаряме процеса, за да намерим най-накрая изхода, както е показано в 1 (d):

3.2. Изпълнение

Нека сега видим изпълнението на Java:

Първо, трябва да дефинираме четирите посоки. Можем да го определим като координати. Тези координати, когато се добавят към която и да е координата, ще върнат една от съседните координати:

private static int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

Също така се нуждаем от полезен метод, който ще добави две координати:

private Coordinate getNextCoordinate( int row, int col, int i, int j) { return new Coordinate(row + i, col + j); }

Вече можем да дефинираме метода за разрешаване на подпис . Логиката тук е проста - ако има път от влизане до изход, върнете пътя, в противен случай върнете празен списък:

public List solve(Maze maze) { List path = new ArrayList(); if ( explore( maze, maze.getEntry().getX(), maze.getEntry().getY(), path ) ) { return path; } return Collections.emptyList(); }

Нека дефинираме метода за изследване , посочен по-горе. Ако има път, върнете true, със списъка с координати в пътя на аргумента . Този метод има три основни блока.

Първо, изхвърляме невалидни възли, т.е. възлите, които са извън лабиринта или са част от стената. След това маркираме текущия възел като посетен, за да не посещаваме същия възел отново и отново.

И накрая, рекурсивно се движим във всички посоки, ако изходът не е намерен:

private boolean explore( Maze maze, int row, int col, List path) { if ( !maze.isValidLocation(row, col) || maze.isWall(row, col) || maze.isExplored(row, col) ) { return false; } path.add(new Coordinate(row, col)); maze.setVisited(row, col, true); if (maze.isExit(row, col)) { return true; } for (int[] direction : DIRECTIONS) { Coordinate coordinate = getNextCoordinate( row, col, direction[0], direction[1]); if ( explore( maze, coordinate.getX(), coordinate.getY(), path ) ) { return true; } } path.remove(path.size() - 1); return false; }

Това решение използва размер на стека до размера на лабиринта.

4. Вариант - Най-кратък път (BFS)

4.1. Алгоритъм

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

In DFS, one child and all its grandchildren were explored first, before moving on to another child. Whereas in BFS, we'll explore all the immediate children before moving on to the grandchildren. This will ensure that all nodes at a particular distance from the parent node, are explored at the same time.

The algorithm can be outlined as follows:

  1. Add the starting node in queue
  2. While the queue is not empty, pop a node, do following:
    1. If we reach the wall or the node is already visited, skip to next iteration
    2. If exit node is reached, backtrack from current node till start node to find the shortest path
    3. Else, add all immediate neighbors in the four directions in queue

One important thing here is that the nodes must keep track of their parent, i.e. from where they were added to the queue. This is important to find the path once exit node is encountered.

Following animation shows all the steps when exploring a maze using this algorithm. We can observe that all the nodes at same distance are explored first before moving onto the next level:

4.2. Implementation

Lets now implement this algorithm in Java. We will reuse the DIRECTIONS variable defined in previous section.

Lets first define a utility method to backtrack from a given node to its root. This will be used to trace the path once exit is found:

private List backtrackPath( Coordinate cur) { List path = new ArrayList(); Coordinate iter = cur; while (iter != null) { path.add(iter); iter = iter.parent; } return path; }

Нека сега дефинираме основния метод за решаване. Ще използваме повторно трите блока, използвани в изпълнението на DFS, т.е. проверяваме възел, маркираме посетен възел и обхождаме съседни възли.

Ще направим само една малка модификация. Вместо рекурсивно обхождане, ще използваме структура от данни на FIFO, за да проследяваме съседите и да ги итерираме:

public List solve(Maze maze) { LinkedList nextToVisit = new LinkedList(); Coordinate start = maze.getEntry(); nextToVisit.add(start); while (!nextToVisit.isEmpty()) { Coordinate cur = nextToVisit.remove(); if (!maze.isValidLocation(cur.getX(), cur.getY()) || maze.isExplored(cur.getX(), cur.getY()) ) { continue; } if (maze.isWall(cur.getX(), cur.getY())) { maze.setVisited(cur.getX(), cur.getY(), true); continue; } if (maze.isExit(cur.getX(), cur.getY())) { return backtrackPath(cur); } for (int[] direction : DIRECTIONS) { Coordinate coordinate = new Coordinate( cur.getX() + direction[0], cur.getY() + direction[1], cur ); nextToVisit.add(coordinate); maze.setVisited(cur.getX(), cur.getY(), true); } } return Collections.emptyList(); }

5. Заключение

В този урок ние описахме два основни алгоритма за графика за търсене с дълбочина и за търсене с широчина за решаване на лабиринт. Докоснахме и как BFS дава най-краткия път от входа до изхода.

За по-нататъшно четене потърсете други методи за решаване на лабиринт, като алгоритъм A * и Dijkstra.

Както винаги, пълният код може да бъде намерен в GitHub.