Разработка программы, моделирующей поиск пути в лабиринте на языке С++ с графикой в программе C++Builder
Нашел я на диске у себя очень простую программу, моделирующую поиск пути роботом в лабиринте. Не помню, зачем я ее вообще делал, нет ни пояснений, ни комментариев, возможно, алгоритм разрабатывал для другой программы. В любом случае, робот бегает шустро, в углах и тупиках не застревает, дорогу находит. Поэтому добавил комментарии и выкладываю программу здесь, возможно, кому-то пригодится.Сделана программа в C++Builder, графический интерфейс есть. Сам лабиринт не генерируется, хранится в коде программе. Это массив чисел 12 на 12. Число 0 означает свободную ячейку, 1 – стену, 2 – робота.
Лабиринт будем выводить в графической сетке, это компонент TDrawGrid. Похожа на StringGrid, но в ячейках можно выводить рисунки. Мы выводить ничего не будем, а будем просто заливать ячейку соответствующим цветом.
На каждом шаге всю сетку будем перерисовывать (Repaint), при этом для каждой ячейки вызывается функция DrawCell, вот ее-то и будем использовать для заливки разных ячеек. Будем сравнивать их координаты с элементами массива и, в зависимости от числа, хранящегося в массиве, определять, что это за ячейка.
Форма в режиме разработки выглядит так
То есть поясняющая надпись, сама сетка (dg), кнопка старта (btnStart) и внизу StatusBar (sb) с одной панелью. В статусбаре будем выводить координаты робота на каждом шаге.
В сетке нужно установить число столбцов и строк – ColCount, RowCount, равное 12, а также высоту и ширину по умолчанию – DefaultColWidth, DefaultRowHeight, в данном случае 25.
Для поиска пути используем правило «правой руки» - для того, чтобы найти выход из лабиринта, нужно все время поворачивать направо, куда идет стена по правой руке, туда и идти самому. Это не самый быстрый способ, но самый надежный. Могут быть ситуации, когда робот, находясь в двух шагах от выхода, попрется по правой руке на противоположный конец лабиринта, при этом обыскивая вся углы и тупики. Но мы же не делаем (пока) сложных интеллектуально-искусственных алгоритмов, поэтому пускай блуждает по всем закоулкам.
Для шага робота будем использовать рекурсивную функцию Step. Аргументами для нее будут новые и старые координаты, а также направления движения робота по горизонтали и вертикали.
Чтобы сделать шаг, робот должен иметь какое-то направление, иначе он будет топтаться на месте в некоторых ситуациях. В соответствии с направлением движения определяем свободную ячейку вблизи робота. Сначала смотрим ячейку справа. Если она свободна, то поворачиваем. Срабатывает правило «правой руки». Если она занята (стена), то смотрим вперед по ходу движения. Если путь свободен, идем вперед. Если стена, смотрим ячейку слева. Если она свободна, поворачиваем налево. Если же и она занята, значит, нам встретился тупик, придется идти назад.
В коде проверяем все варианты направлений, затем ищем свободные ячейки. Из-за этого и получилось много кода. Если найдете лучший вариант – замечательно.
Вот такая получилась картинка работающей программы:
Добавим возможность пользователю переместить робота на новое место. Для этого надо кликнуть мышью на пустую ячейку лабиринта, затем нажать кнопку старта. Можно наблюдать, как робот ищет путь в разные стороны, в зависимости от своего начального положения. Можно еще поменять стартовое направление по умолчанию. Я сделал направление влево.
Код программы (frmMain.cpp – файл главной формы приложения):
//---------------------------------------------------------------------------Что тут можно еще сделать.
#include <vcl.h>
#pragma hdrstop
#include "frmMain.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
Tfrm *frm;
//лабиринт - массив 12 на 12
//1 - стена, 0 - свободная ячейка
//2 - робот
int a[12][12] = {
{1,1,1,1,1,1,0,1,1,1,1,1},
{1,0,0,0,0,1,0,1,1,1,1,1},
{1,1,0,1,0,1,0,1,1,1,1,1},
{1,1,0,1,0,0,0,0,1,1,1,1},
{1,1,0,1,1,0,1,1,1,1,1,1},
{1,1,0,1,1,2,1,1,1,1,0,1},
{1,1,0,0,1,1,1,1,1,0,0,1},
{1,1,0,1,1,0,0,0,1,0,1,1},
{1,0,0,0,1,0,1,1,1,0,0,0},
{1,0,1,0,0,0,0,0,0,0,1,1},
{1,0,1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1,1,1}
};
//текущие координаты
int curX;
int curY;
//---------------------------------------------------------------------------
__fastcall Tfrm::Tfrm(TComponent* Owner)
: TForm(Owner)
{
//начальные текущие координаты
curX = 5;
curY = 5;
//вывод на панель статусбара координат робота
frm->sb->Panels->Items[0]->Text = "x = "+ IntToStr(curX)+" y = "+IntToStr(curY);
}
//рекурсивная функция шаг робота
//аргументы - новые координаты, старые координаты, направление движения по горизонтали
//и вертикали
void Step(int x, int y, int oldX, int oldY, int dirX, int dirY)
{
//очищаем место, где стоял робот
a[oldX][oldY] = 0;
//перемещаем робота на новое место
a[x][y] = 2;
//записываем новые координаты как текущие
curX = x;
curY = y;
//перерисовываем сетку
frm->dg->Repaint();
//вывод на панель статусбара координат робота
frm->sb->Panels->Items[0]->Text = "x = "+ IntToStr(curX)+" y = "+IntToStr(curY);
//обновляем статусбар
frm->sb->Refresh();
//ожидание 300 мс
Sleep(300);
//если робот на краю, значит, выход найден
if(x==0||x==11||y==0||y==11)
{
ShowMessage("Дошел!");
return;
}
//робот движется по вертикали
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 = "+IntToStr(curY);
}
//---------------------------------------------------------------------------
Во-первых, не зашивать лабиринт жестко в код, лучше хранить его отдельно в файле. Еще лучше – генерировать случайным образом (потом займемся этим).
Во-вторых, сделать размер лабиринта тоже динамическим, то есть его может указывать пользователь при запуске.
В-третьих, неплохо бы доработать сам алгоритм поиска. Например, отучить робота залезать в тупики, научить искать ближайший к нему выход, а не у черта на куличках (хотя в реальной жизни это тоже не всегда срабатывает). Но тут у нас же есть рекурсия, надо ее использовать.
Пока все, потом еще что-нибудь придумаю.
В ВК выложил видео работы программы