Неидеальный лабиринт Поколение
Я кодировал алгоритм A* для проекта. Одним из требований этого проекта является случайное создание 50 лабиринтов.
Я немного застрял, потому что это не похоже на обычные поколения лабиринтов. В поколениях лабиринтов вы блокировали и разблокировали стены, в то время как в моем случае мне нужно было блокировать и разблокировать плитки. Это также не может быть идеальным (должно быть несколько путей). Я действительно не смог найти алгоритм онлайн или описание, которое подходит для этого случая. Каков будет лучший способ сделать это? Я также хотел бы указать начальную + конечную точку, если это возможно, если нет, то просто начальную точку. Спасибо!
Это пример лабиринта, который я создал вручную (в меньшем масштабе):
2 ответа
Вы можете сделать это с помощью структуры данных union-find, аналогично использованию алгоритма Крускала для создания лабиринта:
- Выберите начальную и конечную точки
- Отметьте все ячейки, кроме начала и конца, как заблокированные, и поместите каждую ячейку в свой собственный набор
- Случайно разблокировать ячейки. Когда вы разблокируете ячейку, объедините ее набор с наборами любых разблокированных ячеек, к которым она подключена.
- Остановитесь, когда набор начальной ячейки объединится с набором конечной ячейки.
Теперь будет путь от начала до конца. Если вы хотите убедиться, что лабиринт немного более открыт, вы можете случайно разблокировать ячейки, например, до тех пор, пока, по крайней мере, 70% не будут разблокированы.
Результат не будет похож на традиционный лабиринт, но, вероятно, будет хорошим для A* тестирования.
Вы можете случайным образом назначить значение (которое представляет заблокированный или незаблокированный) для каждой плитки. После этого назначьте начальную и конечную точку.
Результат может выглядеть так.
Если вы предпочитаете использовать алгоритмы генерации лабиринтов, используйте один из широко доступных ресурсов, таких как: 1, 2