Wall-la-la-paper

МЭЙЗ

Как сделать лабиринт ?

Почти все в своей жизни решали или хотя бы пробовали решить лабиринт. А вот у вас никогда не было вопроса, а кто их делает-то? Есть ли реальная работа по созданию лабиринтов? Если есть, то сколько за неё платят? На эти вопросы я отвечать не собираюсь, скажу лишь, что если бы были такие вакансии, я бы за них поборолся. Дело в том, что существует уйма алгоритмов по автоматической генерации лабиринтов, поэтому моя новая работа превратилась бы в пассивный доход, где я ничего толком не делаю.

В данной статье я разберу один из алгоритмов. Примерный перевод названия “Рекурсивный поиск с возвратом”. Он безумно простой. Представьте, что вы прокладываете лабиринт. Выбрав этот алгоритм, вы будете идти куда захотите, то тех пор, пока не заблудитесь, а как только попадёте в тупик, то сделаете пару шагов назад и опять “пойдёте куда глаза глядят”.

А теперь представьте, что это всё делает программа =)

А конкретно как ?

Будущий лабиринт состоит из клеток с четырьмя стенами у каждой. Вам нужно отслеживать, на каких клетках вы уже были, а на каких не были. Собственно алгоритм:

  1. Клетку начала лабиринта пометьте как посещённую и нынешнюю.
  2. Пока есть непосящённые клетки:
    1. Если нынешняя клетка имеет соседние непосещённые клетки:
      1. Выберите случайную из них.
      2. Внесите в стэк нынешнюю клетку.
      3. Уберите стену между нынешней и выбранной клеткой.
      4. Сделайте выбранную клетку нынешней.
    2. Иначе, если в стэке есть клетки:
      1. Возьмите последнюю клетку из стэка.
      2. Сделайте её нынешней.

Вот. Сделать лабиринт очень не сложно =)

Рабочая версия