Алгоритм генерации лабиринта с поиском по глубине с блоками вместо стен

Question

Я пытаюсь внедрить алгоритм поиска в глубину в мою игру. Я изучал эту веб-страницу: http://www.mazeworks.com/mazegen/mazetut/index.htm, но обнаружил, что не смог бы использовать ее с блоками вместо стен. Под блоками я подразумеваю квадрат, который охватывает всю клетку, а не только края. Я думал, что так будет проще, но теперь я не уверен. Кто-нибудь делал это? Если так, то как? (psuedocode в порядке). Или я должен просто пойти с методом стен, если это проще?

Answer 1

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

1.) в вашем лабиринте есть блоки на предопределенных позициях

• Вы запускаете алгоритм на 2*k+1 сетка
• Предположим, нумерация ваших клеток начинается сверху слева с (0,0). пометить все ячейки 2 нечетными координатами ((2*p+1, 2*q+1); p,q < k) как блоки.
• Вы запускаете модифицированный алгоритм из своего источника в оставшихся ячейках ("четные ячейки"). модификации:
  • начать с четной ячейки, выбранной наугад
  • "соседняя ячейка" - это вторая, но следующая ячейка в любом направлении сетки; то есть вы "перепрыгиваете" через кирпич.
  • вместо того, чтобы сбивать стену между ячейками, вы превращаете блок в доступную ячейку. однако эта ячейка не будет учитываться при отборе и возврате

2.) вместо стен, разделяющих клетки, вы хотите блоки.

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

надеюсь, что эти идеи соответствуют вашим потребностям,

С наилучшими пожеланиями, Карстен