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

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

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

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


algorithm cellular-automata maze
person Eric Thoma    schedule 18.05.2012    source источник
comment
Что за правило 1234/3? (Google мне не помогает.)   -  person Taymon    schedule 18.05.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

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

person CheeseWarlock    schedule 18.05.2012

arrow_upward
1
arrow_downward

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

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

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

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

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

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

  1. привидение на машине / внешний пользователь
  2. FPGA
  3. программирование ЦП общего назначения
person andrew cooke    schedule 18.05.2012

arrow_upward
0
arrow_downward

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

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

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

person Samy Arous    schedule 18.05.2012
comment
Это полезно для определения количества путей и общей сложности, но клеточные автоматы не создают лабиринты с какими-либо решениями, хотя Дейкстры можно использовать для поиска частичного решения и решения, где изменить лабиринт, чтобы оно было сложным. - person CheeseWarlock; 18.05.2012
comment
И Дейкстра, и A * скажут вам, существует ли решение, и если его нет, мы все равно можем его сгенерировать :) - person Samy Arous; 18.05.2012