Есть ли алгоритм тестирования лабиринта на отсутствие замкнутых пространств?
Здравствуйте, товарищи, господа, братья!
Нашёл много примеров интересной генерации лабиринтов. Но не смог найти тестирования его под указанные далее требования.
Подкиньте, пожалуйста, в рунете ссылочку на пример алгоритма тестирования лабиринта на отсутсвие замкнутых пространств, желательно с пояснениями, ибо начинающий я в этом деле. Т.е. если мы не генерируем (да и в этом случае) лабиринт, т.е. возможны ошибки. Задача, проверить то, чтобы из любой его точки, можно бы попасть в любую другую.
С кодом разберусь, логика пока не ясна, кроме как обойти его весь, каждую из пройденных точек, отмечая как пройденную, а в случае недоступных - выдавать ошибку. Но чутьё подсказывает, что это неверный путь.
Было бы здорово, если бы была возможность отобразить "сплошную стену", проход в которой сделал бы лабиринт корректным.
Если лабиринт на сетке или графе (а как его еще можно задать-то, кстате), то простой волновой алгоритм. Проводим волной и смотрим, есть ли недоступные, можно ли дойти от конца до начала.
Ну самое простое. Лабирит разбивается на ячейки. Количество ячеек - известно (площадь лабиринта). Идем по всему лабиринту рекурсивно например (т.е. на каждом ветвлении идем по каждой ветке). И считаем количество пройденых уникальных ячеек. Если по итогу количество пройденых уникальных ячеек меньше чем площадь - то у нас есть замкнутое пространство.
Можно попытаться еще представить лабиринт в виде графа достижимостей точек. И уже анализировать граф.
Ну да, по сути первый вариант это о котором я думал..
А с графами не тяжелее исполнение будет? Про них много читал, даже что-то писал (из учебника), но плохо понимаю, как их тут можно применить, чтобы это было легко и в разработке и в исполнении.
SerYojik85: Ну фактически граф - это будет просто представление связности лабиринта. Есть варианты генерации - когда у вас сначала генерится граф, а потом на его основе - лабиринт. Если так - то конечно легче с графм работать
