Алгоритм построения либиринта
I will use google...
и всё такое...
и всё такое...
я нашел там алгоритмы какие то но не те
бляяяя
ВМК АЯ пролог ?
ВМК АЯ пролог ?
бляяяя
Я могу предложить тормозной алгоритм, который ещё и строит не слишком красивый лабиринт, наверно.
Я надеюсь, что ты знаешь, что такое "волна", и как её запрограммировать так, чтобы ещё и получать путь, при помощи которого была достигнута данная точка.
1) Строишь путь. Это будет тот самый Единственный Путь. Типа, раскидываешь точки по рандому, соединяешь их по алгоритму Брезенхейма и устраняешь самопересечения. Ну не знаю, поищи в гугле мб.
2) Закидываешь поле стенками по рандому, причём стенка не должна перекрывать Путь. После каждой закинутой стенки волной проверяешь достижимость любой точки лабиринта. Если перекрывает - обламываешься и повторяешь.
3) После того, как на втором пункте обломался несколько раз ("несколько" зависит от размеров лабиринта и подбирается экспериментально) переходишь к след. стадии.
4) Единственность Пути означает что для любых двух точек а, б, лежащих на Пути не существует пути от а до б, не проходящего через точки Пути. Берёшь любую точку Пути (А) дальше перебираешь все остальные (непомеченные Особым Образом, см. ниже) точки пути (Б) , помечаешь все остальные точки Пути как посещённые (это важно!) и ищешь путь из А до Б. Если не нашёл для любого Б, то помечаешь А Особым Образом, чтобы больше для неё этой операции не производить.
Если нашел, то выбираешь случайную границу между клеточками на этом пути и ставишь там стенку. Связность лабиринта при этом не нарушается, так как до каждой из этих двух клеток есть путь от Пути. Повторяешь процедуру для тех же А и Б.
5) после того, как все клетки Пути помечены Особым Образом, задача решена.
Комментарий по реализации: для пункта (4) рекомендую один раз сгенерить перестановку для всех точек Пути, после чего просто запустить двойной цикл.
Вот.
Я надеюсь, что ты знаешь, что такое "волна", и как её запрограммировать так, чтобы ещё и получать путь, при помощи которого была достигнута данная точка.
1) Строишь путь. Это будет тот самый Единственный Путь. Типа, раскидываешь точки по рандому, соединяешь их по алгоритму Брезенхейма и устраняешь самопересечения. Ну не знаю, поищи в гугле мб.
2) Закидываешь поле стенками по рандому, причём стенка не должна перекрывать Путь. После каждой закинутой стенки волной проверяешь достижимость любой точки лабиринта. Если перекрывает - обламываешься и повторяешь.
3) После того, как на втором пункте обломался несколько раз ("несколько" зависит от размеров лабиринта и подбирается экспериментально) переходишь к след. стадии.
4) Единственность Пути означает что для любых двух точек а, б, лежащих на Пути не существует пути от а до б, не проходящего через точки Пути. Берёшь любую точку Пути (А) дальше перебираешь все остальные (непомеченные Особым Образом, см. ниже) точки пути (Б) , помечаешь все остальные точки Пути как посещённые (это важно!) и ищешь путь из А до Б. Если не нашёл для любого Б, то помечаешь А Особым Образом, чтобы больше для неё этой операции не производить.
Если нашел, то выбираешь случайную границу между клеточками на этом пути и ставишь там стенку. Связность лабиринта при этом не нарушается, так как до каждой из этих двух клеток есть путь от Пути. Повторяешь процедуру для тех же А и Б.
5) после того, как все клетки Пути помечены Особым Образом, задача решена.
Комментарий по реализации: для пункта (4) рекомендую один раз сгенерить перестановку для всех точек Пути, после чего просто запустить двойной цикл.
Вот.
спасибо, попробую осилить
я сразу не вкурил, а замкнтуых помещений не будет при таком алгоритме?
//не вникал в алгоритм ФЖ.
есть алгоритм генерации лабиринта в прямоугольнике MxN со следующим свойством:
стены занимают одну ячейку, проходы занимают одну ячейку, стены четырёхсвязные,
между любыми двумя точками, которые "не стена" существует единственный путь в лабиринте, который их связывает.
+ в той же программе реализован алгоритм обхода лабиринта для поиска пути из точки А в точку Б.
типа вот такого:
реализация на паскале
есть алгоритм генерации лабиринта в прямоугольнике MxN со следующим свойством:
стены занимают одну ячейку, проходы занимают одну ячейку, стены четырёхсвязные,
между любыми двумя точками, которые "не стена" существует единственный путь в лабиринте, который их связывает.
+ в той же программе реализован алгоритм обхода лабиринта для поиска пути из точки А в точку Б.
типа вот такого:
реализация на паскале
Не, это не для АЯ Пролога. У нас только дабиринт занимал ячейки, а стенки - нет, они были между ячейками.
ФЖ правильно написал. только там надо только два первых шага использовать, остальное - лишнее.
Строишь правильный путь, а потом все остальные точки соединяешь с путём без самопересечений.
ФЖ правильно написал. только там надо только два первых шага использовать, остальное - лишнее.
Строишь правильный путь, а потом все остальные точки соединяешь с путём без самопересечений.
Создеаешь граф, в котором вершинами обозначены клеточки, а ребрами - перегородки. Строишь любое дерево, которое является подграфов этого графа (например, остов). Получаешь множество ребер, которые необходимо удалить и затем восстанавливаешь стенки. В итоге получается лабиринт, в котором между каждой парой точек есть ровно один путь. Качество лабиринта можно варьировать, изменяя принцип генерации дерева.
Оставить комментарий
3uxep
Есть поле MxNНа одной стороне указывается вход - на ПРОТИВОПОЛОЖНОЙ выход
Надо построить лабиринт имеющий единственный путь и он не должен иметь закрытых(замкнутых) комнат.
Хелп