Как я могу гарантировать, что лабиринт, созданный клеточными автоматами, решаем / интересен?

Я пишу алгоритм создания лабиринта, и эта статья в Википедии привлекла мое внимание. Я решил реализовать это в Java, что было легко. Проблема, с которой я сталкиваюсь, заключается в том, что, хотя создается лабиринтная картинка, лабиринт часто не решаем и не часто интересен. Под интересным я подразумеваю, что существует огромное количество недоступных мест, и часто есть много решений.

Я реализовал правило 1234/3 (хотя его легко можно изменить, см. Комментарии для объяснения) с примерно 50/50 в начале. Лабиринты всегда достигают равновесия, когда между t-шагами нет изменений.

У меня вопрос, есть ли способ гарантировать разрешимость лабиринтов с фиксированной начальной и конечной точки? Кроме того, есть ли способ сделать лабиринт более интересным для решения (меньше / одно решение и мало / нет недоступных мест)? Если это невозможно с клеточными автоматами, пожалуйста, сообщите мне. Спасибо.

Источник

3 ответа

Решение

Я не думаю, что можно обеспечить разрешимый, интересный лабиринт с помощью простых клеточных автоматов, если только нет каких-то определенных критериев, которые можно поставить в исходное состояние. Тот факт, что ячейки не знают общей формы, потому что каждая ячейка не сможет координироваться с группой в целом.

Если вы настаиваете на их использовании, вы можете сделать некоторую комбинацию модификации и нахождения пути после завершения генерации, но другие методы (такие как показанные в статье Википедии или в этом вопросе) проще реализовать и не приведут к стенам которые занимают целую клетку (если вы этого не хотите).

Источник

Корень проблемы в том, что "качество лабиринта" является глобальной мерой, но ваши автоматные ячейки ограничены очень локальным знанием системы.

Чтобы решить эту проблему, у вас есть три варианта:

  1. добавить глобальную информацию извне. генерируйте лабиринты, используя автомат и случайные начальные данные, затем измеряйте качество лабиринта (например, используя заливку или набор других методов решения лабиринта) и повторяйте, пока не получите желаемый результат.

  2. использовать гораздо более сложный набор явных правил и состояний. Вы можете разработать набор правил / значений ячеек, которые кодируют как наличие стен, так и длину / качество путей. например, -1 будет стеной, а положительное значение будет суммой всех соседей сверху и слева. тогда положительные значения кодируют расстояние пути сверху слева примерно. этого недостаточно, но это показывает общую идею... вам нужно закодировать алгоритм о лабиринте "напрямую" в правилах системы.

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

если это поможет, вы можете провести параллель между вышеупомянутым и:

  1. призрак в машине / внешний пользователь
  2. FPGA
  3. программирование процессора общего назначения
Источник

Запустите алгоритм поиска пути по нему. Дейкстра даст вам верный способ вычислить все решения. A* даст вам одно хорошее решение.

Сложность лабиринта может быть измерена скоростью, с которой эти алгоритмы ее решают.

Вы можете добавить несколько тупиков, чтобы закрыть некоторые решения.

Источник
Другие вопросы по тегам