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

Обновлено: 06.07.2024

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

if (x, y вне лабиринта) возвращает false
если (x, y — цель), верните true
если (x, y не открыт) вернуть false
пометить x, y как часть пути решения
if (FIND-PATH (к северу от x, y) == true) возвращает true
if (FIND-PATH (к востоку от x, y) == true) возвращает true
if (FIND-PATH (к югу от x, y) == true) возвращает true
if (FIND-PATH (West of x, y) == true) возвращает true
снять отметку x, y как часть пути решения
вернуть ложь

Я видел по крайней мере два других вопроса с этим алгоритмом, но я почти уверен, что проблемы не были точно такими же.

Пример лабиринта (где e — вход, а x — выход):

Решение

Ваша первая регистрация bool path(. ) находит х false и выходит, и основная программа получает false результат звонка path Печатает, что он должен и выходит.

Попробуем сделать элегантную алгоритмическую игрушку — лабиринт. Сначала специальный алгоритм будет рисовать для нас случайный лабиринт, а потом мы сделаем так, чтобы его можно было пройти.

Что тут будет интересного:

Алгоритм создания случайного лабиринта. Оказывается, есть довольно простые закономерности, по которым можно сгенерировать проходимый лабиринт
Много вложенных циклов и функций, каждая из которых делает что-то простое, но вместе получается нечто сложное и прекрасное

За основу мы возьмём код Сергея Григоровича и адаптируем его под нашу задачу.

Можно создавать лабиринты любой степени сложности.

Логика проекта

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

Чтобы понять, готов лабиринт или нет, используем такое свойство лабиринта: если на всех чётных ячейках нет стен, значит, этот лабиринт можно пройти.

👉 Чётные места — это такие места в лабиринте, которые по оси X и Y одновременно имеют чётные координаты. Например, клетка с координатами (2,6) чётная, потому что 2 и 6 чётные числа, а с координатами (2,7) — нет.

Подготовка

Проект пока будет состоять из двух частей:

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

Дальше мы добавим скрипт, который нарисует наш лабиринт, а потом научим делать всё остальное.

Сейчас сделаем первую часть: напишем HTML-код.

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

Создаём скрипт

За создание будет отвечать отдельный скрипт — назовём его generateMaze.js и сразу добавим его в HTML-файл:

Теперь напишем сам скрипт. Чтобы было потом проще его вызывать, сделаем весь скрипт одной большой функцией generateMaze() , а внутри распишем всё, что нужно.

Чтобы скрипт создавал лабиринт нужного нам размера, объявим функцию так:

function generateMaze (columnsNumber, rowsNumber) <>

Всё остальное будем писать внутри этой функции.

Делаем карту и заполняем её стенами

Нам нужно завести отдельную переменную, в которой будет храниться вся карта лабиринта, и на первом этапе заполнить её полностью стенами, чтобы трактору было что чистить:

Готовим трактор к выезду

Чтобы наш трактор работал как нужно, мы должны сделать несколько подготовительных вещей: научиться проверять числа на чётность и выбирать случайные координаты лабиринта на карте.

Проверка на чётность делается просто — объявляем новую функцию и передаём ей число на проверку. Если вернёт true — число чётное.

Со случайными координатами тоже всё легко: берём случайное число в диапазоне от 0 до размера массива, получаем значение ячейки с нужным индексом и возвращаем его:

Ставим трактор в лабиринт

Теперь у нас есть всё что нужно для установки трактора. Единственное сложное место в коде — получение стартовых координат. Для этого мы делаем сложный трюк:

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

Очищаем клетку с трактором

Чтобы трактор не стоял в стене, нам нужно очистить клетку, на которой оказался трактор. Для этого напишем функцию setField() — она записывает переданное значение по нужным координатам. Смысл её в том, что она сразу проверяет, а правильные ли координаты мы ей передали. Если с координатами всё в порядке, то она сработает; если координат таких в лабиринте нет, то она не будет ничего менять и записывать.

Проверяем, лабиринт готов или нет

Чтобы лабиринт был готов, каждая чётная клетка в нём должна быть пустой. Зная это, напишем простую функцию с проверкой:

Запускаем трактор

Задача трактора — двигаться, очищать и менять направление до тех пор, пока лабиринт не будет готов. Запишем это на языке JavaScript:

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

Выбираем направления и очищаем лабиринт

Последнее, что нам осталось сделать — написать логику движения трактора. Так как он будет постоянно работать с клетками лабиринта, напишем сначала функцию, которая получает значение любой клетки по её координатам. Логика будет такая же, как и в функции setField() — сначала проверяем правильность координат и только потом возвращаем значение.

Логика работы трактора будет такая:

Трактор может ходить на две любые клетки в любом направлении: вверх, вниз, влево или вправо.
Если в выбранном направлении через две клетки есть стена, то очищаем обе и меняем направление. Если через две клетки стены нет, то просто меняем направление.
Там, где прошёл трактор, появляется свободное место.

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

Рисуем лабиринт

Сейчас рисунок лабиринта у нас хранится в массиве.

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

У нас уже есть функция, которая проверяет, готов лабиринт или нет. Всё, что нам нужно, — это поместить код вывода на консоль в самый конец этой функции. Вот что у нас получится в итоге:

Запускаем генератор

Для запуска добавляем в HTML-файл скрипт запуска нашей основной функции:

Наш лабиринт в консоли браузера.

Таких алгоритмов существует уже очень много, поэтому представленная нами подборка не претендует на полноту — в комментариях вы можете поделиться ссылками на известные вам способы генерации лабиринтов.

Также существуют уже готовые решения для генерации лабиринтов: генератор Oblige, который используется в DOOM, DOOM II и Heretic, и др.

Алгоритм Эллера

Хранить карту лабиринта можно, например, в двух двумерных массивах: для вертикальных стенок и горизонтальных, соответственно.

Ответ на вопрос о хранении карт таких лабиринтов очевиден: в виде двумерного boolean массива, где, например, 1 — это непроходимая клетка (стена), 0 — свободная.

Наивный алгоритм

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

Естественно, возникают два вопроса: не будут ли комнаты пересекаться и как проложить между ними переходы? Ответ на первый вопрос зависит от ваших требований к лабиринту: если вы не хотите, чтобы комнаты пересекались, напишите функцию, которая проверяет пару комнат на пересечение и при появлении на карте очередной комнаты делайте проверку.

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

Лабиринт на таблице

У описанного выше алгоритма есть один явный недостаток: проверять, пересекаются ли комнаты, приходится отдельной функцией. Возникает вопрос, можно ли не делать это лишнее действие. Оказывается, можно— и алгоритм описан ниже.

BSP деревья

Генерация лабиринтов с использованием клеточного автомата

Генерация в трехмерном пространстве

Каждый из модулей хранит информацию о своих входах и выходах, а также их ориентации: прежде чем соединить очередную пару элементарных частей, их нужно правильно ориентировать. В частности, автор предлагает хранить x-, y- и z- ориентацию модулей, чтобы затем соединять их по таким правилам: их y-оси должны совпадать, а x и z — иметь противоположное направление. Это, естественно, ставит вопрос о хранении информации о сгенерированной карте. Кроме того, не решена проблема с пересечением помещений — поэтому эта статья может являться лишь отправной точкой для исследования вопросов генерации трехмерных алгоритмов.

Что дальше?

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

Разработка программы, моделирующей поиск пути в лабиринте на языке С++ с графикой в программе C++Builder

Нашел я на диске у себя очень простую программу, моделирующую поиск пути роботом в лабиринте. Не помню, зачем я ее вообще делал, нет ни пояснений, ни комментариев, возможно, алгоритм разрабатывал для другой программы. В любом случае, робот бегает шустро, в углах и тупиках не застревает, дорогу находит. Поэтому добавил комментарии и выкладываю программу здесь, возможно, кому-то пригодится.
Сделана программа в C++Builder, графический интерфейс есть. Сам лабиринт не генерируется, хранится в коде программе. Это массив чисел 12 на 12. Число 0 означает свободную ячейку, 1 – стену, 2 – робота.
Лабиринт будем выводить в графической сетке, это компонент TDrawGrid. Похожа на StringGrid, но в ячейках можно выводить рисунки. Мы выводить ничего не будем, а будем просто заливать ячейку соответствующим цветом.
На каждом шаге всю сетку будем перерисовывать (Repaint), при этом для каждой ячейки вызывается функция DrawCell, вот ее-то и будем использовать для заливки разных ячеек. Будем сравнивать их координаты с элементами массива и, в зависимости от числа, хранящегося в массиве, определять, что это за ячейка.
Форма в режиме разработки выглядит так

Добавим возможность пользователю переместить робота на новое место. Для этого надо кликнуть мышью на пустую ячейку лабиринта, затем нажать кнопку старта. Можно наблюдать, как робот ищет путь в разные стороны, в зависимости от своего начального положения. Можно еще поменять стартовое направление по умолчанию. Я сделал направление влево.
Код программы (frmMain.cpp – файл главной формы приложения):
//---------------------------------------------------------------------------

//робот движется по вертикали
if (dirX==0)
//направление вверх
if(dirY==-1)
//ячейка справ от робота свободна
if (a[x + 1][y] == 0)
//меняем направление двиежния - направо
dirX = 1;
//по вертикали нет движения
dirY = 0;
//вызываем функцию шага с новыми координатами
//и направлениями
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
//ячейка перед роботом (сверху от него) свободна
//меняем направления и вызываем функцию шага
if (a[x][y - 1] == 0)
dirX = 0;
dirY = -1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
//ячейка слева от робота свободна
//далее те же действия, что и в других вариантах
if (a[x - 1][y] == 0)
dirX = -1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
//ячейка позади робота (ниже его) свободна
//те же действия, что и выше
if (a[x][y + 1] == 0)
dirX = 0;
dirY = 1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
>

//робота двигается по вертикали вниз
//так же находим свободную ячейку начиная с правой от робота,
//против часовой стрелки, если смотреть по направлению робота
if(dirY==1)
if (a[x - 1][y] == 0)
dirX = -1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x][y + 1] == 0)
dirX = 0;
dirY = 1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x + 1][y] == 0)
dirX = 1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x][y - 1] == 0)
dirX = 0;
dirY = -1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
>
>
//робот движется по горизонтали
//действия те же, что и выше
//в зависимости от направления робота и наличия свободных ячеек рядом с ним
else
if(dirX==-1)
if (a[x][y - 1] == 0)
dirX = 0;
dirY = -1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x - 1][y] == 0)
dirX = -1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x][y + 1] == 0)
dirX = 0;
dirY = 1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x + 1][y] == 0)
dirX = 1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
>
if(dirX==1)
if (a[x][y + 1] == 0)
dirX = 0;
dirY = 1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x + 1][y] == 0)
dirX = 1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x][y - 1] == 0)
dirX = 0;
dirY = -1;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
if (a[x - 1][y] == 0)
dirX = -1;
dirY = 0;
Step(x + dirX, y + dirY, x, y, dirX, dirY);
return;
>
>
>

>
//---------------------------------------------------------------------------
//рисование ячейки сетки DrawGrid
//вызывается при перерисовывании всей сетки для каждой ячейки
void __fastcall Tfrm::dgDrawCell(TObject *Sender, int ACol, int ARow,
TRect &Rect, TGridDrawState State)
//если эта ячейка означает стену
//то выбираем серый цвет кисти
if(a[ACol][ARow]==1)
dg->Canvas->Brush->Color = clGray;
//заливаем область ячейки серым цветом
dg->Canvas->FillRect(Rect);
>
//ячейка с роботом - красная
if(a[ACol][ARow]==2)
dg->Canvas->Brush->Color = clRed;
dg->Canvas->FillRect(Rect);
>
//свободная ячейка белая
if(a[ACol][ARow]==0)
dg->Canvas->Brush->Color = clWhite;
dg->Canvas->FillRect(Rect);
>
>
//---------------------------------------------------------------------------
//кнопка старта
void __fastcall Tfrm::btnStartClick(TObject *Sender)
//вызываем рекурсинвую функцию шага с текущими координатами
//направление по умолчанию влево
//dirX=-1 dirY = 0
Step(curX, curY, curX, curY, -1, 0);
>
//---------------------------------------------------------------------------
//выбор пользователем положения робота
//клик мышкой на сетке
void __fastcall Tfrm::dgClick(TObject *Sender)
//определяем координаты робота по номеру ячейки
int x = dg->Col;
int y = dg->Row;
//если это не ткеущая кордината и не стена
if((x!=curX||y!=curY) &&(a[x][y]!=1))
//очищаем старое место с текущими координатами
a[curX][curY] = 0;
//устанавливаем новые текущие координаты
curX = x;
curY = y;
//ставим робота на новое место
a[curX][curY] = 2;
//перерисовываем сетку
dg->Repaint();
>
//вывод на панель статусбара координат робота
frm->sb->Panels->Items[0]->Text = "x = "+ IntToStr(curX)+" y separator" style="clear: both; text-align: center;">

Читайте также: