#algorithm #depth-first-search #maze
#алгоритм #поиск в глубину #Лабиринт
Вопрос:
Я пытаюсь внедрить алгоритм поиска в глубину в свою игру. Я изучал эту веб-страницу:http://www.mazeworks.com/mazegen/mazetut/index.htm , только чтобы обнаружить, что я не смог бы использовать его с блоками вместо стен. Под блоками я подразумеваю квадрат, который покрывает всю ячейку, а не только края. Я думал, что так будет проще сделать это, но теперь я не так уверен. Кто-нибудь делал это? Если да, то каким образом? (псевдокод в порядке). Или, я должен просто использовать метод walls, если это проще?
Комментарии:
1. Разве блок — это не просто ячейка, у которой есть все четыре стенки?
2. возможно, но что, если бы я мог удалить только весь блок, а не только одну из его стен… хотя вопрос хороший.
3. Без дополнительной информации о вашем конкретном приложении сложно сказать, можете ли вы применить этот алгоритм генерации лабиринта в глубину. Как вы говорите, он предназначен для работы с ячейками, которые имеют отдельные стены, а не «заблокированные» ячейки.
Ответ №1:
в зависимости от того, чего вы на самом деле хотите достичь, у меня есть для вас два решения. они оба в основном являются алгоритмом, представленным на веб-сайте, на который вы ссылались.
1.) в вашем лабиринте блоки находятся в заранее определенных положениях
- вы запускаете алгоритм на
2*k 1сетке - предположим, что нумерация ваших ячеек начинается сверху слева с (0,0). отметьте все ячейки с 2 нечетными координатами (
(2*p 1, 2*q 1); p,q < k) как блоки. - вы запускаете модифицированный алгоритм из своего источника для оставшихся ячеек («четных ячеек»). изменения заключаются в:
- начните с четной ячейки, выбранной случайным образом
- «соседняя ячейка» — это вторая, но следующая ячейка в любом направлении сетки; т.е. вы «перепрыгиваете» через кирпич.
- вместо того, чтобы разрушать стену между ячейками, вы превращаете блок в доступную ячейку. однако эта ячейка не будет учитываться при выборе и обратном отслеживании
2.) вместо стен, разделяющих ячейки, вам нужны блоки.
перед запуском алгоритма отметьте любое количество ячеек как блоки. действуйте, как указано в вашем исходном коде, но никогда не рассматривайте ни одну из ячеек блока. вам придется принять особые меры предосторожности, если вы хотите гарантировать полную доступность в вашем лабиринте. простой схемой было бы никогда не помечать ячейку как блок, который имеет более 1 блоков в качестве соседей.
надеюсь, эти идеи соответствуют вашим потребностям,
с наилучшими пожеланиями, Карстен