Неидеальный лабиринт Поколение

Question

Я кодировал алгоритм A * для проекта.Одним из требований этого проекта является случайное создание 50 лабиринтов.

Я немного застрял, потому что это не похоже на обычные поколения лабиринтов.В поколениях лабиринтов вы блокировали и разблокировали стены, в то время как в моем случае мне нужно было блокировать и разблокировать плитки.Это также не может быть идеальным (должно быть несколько путей).Я действительно не смог найти алгоритм онлайн или описание, которое подходит для этого случая.Каков будет лучший способ сделать это?Я также хотел бы указать начальную + конечную точку, если это возможно, если нет, то просто начальную точку.Спасибо!

Это пример лабиринта, который я создал вручную (в меньшем масштабе):

Answer 1

Это можно сделать с помощью структуры данных для поиска объединения, аналогичной использованию алгоритма Крускала для создания лабиринта:

• Выбор начальной и конечной точек
• Отметка каждой ячейки, кроменачать и закончить как заблокированный, и поместить каждую ячейку в свой собственный набор
• Случайно разблокировать ячейки.Когда вы разблокируете ячейку, объедините ее набор с наборами любых разблокированных ячеек, к которым она подключена.
• Остановитесь, когда набор начальной ячейки объединится с набором конечной ячейки.

Тамтеперь будет путь от начала до конца.Если вы хотите убедиться, что лабиринт немного более открыт, вы можете случайно разблокировать ячейки, пока, скажем, не будет разблокировано, по крайней мере, 70%.

Результат не будет похож на традиционныйлабиринт, но это, вероятно, будет хорошо для A * тестирования.

Answer 2

Вы можете произвольно назначить значение (которое представляет заблокированный или неблокированный) для каждой плитки.После этого назначьте начальную и конечную точку.Результат может выглядеть следующим образом: this .
Если вы предпочитаете использовать алгоритмы генерации лабиринтов, используйте один из широко доступных ресурсов, таких как: 1 , 2