Генерация лабиринта

416

17 марта 2018, 17:27

Требуется написать алгоритм генерации лабиринта размером 10x10 и реализовать интерфейс прохождения кратчайшего пути между двумя точками. Обозначения: "# - стена . - дорога @ - начало маршрута X - конец маршрута"

public interface Navigator {
char[][] searchRoute(char[][] map);
}

Если маршрут проложить невозможно, метод searchRoute должен возвращать null. Пример: ввод:

...@.     или    ..X..
.####            #####
.....            .....
####.            .@...
.X...            .....

вывод:

+++@.     или     null
+####
+++++
####+
.X+++

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

Answer 1

Воспользуйтесь алгоритмом A* для поиска пути. И генерации лабиринта.

Суть простая. Заполняете поле случайными "весами". По алгоритму, ищете 2-3 оптимальных пути. Их делаете неприкасаемыми, а остальное поле заполняете как угодно. Но правда маршрут всегда можно будет проложить.