Делаем "односвязный" лабиринт и решаем его
Приложение на C++ позволяет сгенерировать "односвязный" двумерный лабиринт, в котором каждая клетка связана с каждой, показать его картинкой BMP, сохранить эту картинку и сделать двумерный массив данных для ваших программ, работающих с лабиринтами...
Класс myBitmap даёт возможность создать Bitmap-картинку нужного размера (метод create) и сохранить её в файл (saveBitmap).
Класс mazeGenerator генерирует квадратный лабиринт со стороной _size и позволяет получить его в виде массива байтов (метод getMaze) или массива целых значений (метод getTextMaze).
Класс mazeSolver решает лабиринт, то есть, находит путь из одной произвольной точки в другую (метод solve; путь всегда есть, так как лабиринт таким и генерировался) и рисует картинку лабиринта и пути (метод display).
Как сохранить это в виде двумерной матрицы лабиринта - показано в main, также код пишется в файл data.txt текущей папки.
Картинка выводится на экране консоли, а также пишется в файл data.bmp текущей папки.
Как хранится лабиринт "в числах"?
В младшем полубайте просто хранятся направления, как можно пойти из данной клетки.
При этом, направления кодируются в порядке "вверх - направо - вниз - налево" (по часовой стрелке), то есть, младший бит - это вверх, второй справа - правая сторона и т.д.
Например, метод getTextMaze + запись в файл data.txt, выполненная из функции main, дали такой результат (двумерную матрицу лабиринта):
{
{6,10,10,12 },
{7,12,2,9 },
{5,3,10,12 },
{3,10,8,1 }
}
А вот картинка маленького лабиринта размером 4x4:
генерация и кодирование лабиринта
Смотрим на левый верхний угол. Этой клетке соответствует число 6.
Действительно, в двоичном коде это 0000 0110 (записал как 2 полубайта).
По младшему полубайту 0110 видно, что пути вверх нет, вправо и вниз - есть (единицы), влево тоже нет. Нижняя правая клетка имеет код 1 или 0000 0001, "включено" только направление вверх.
Проверьте другие клетки, не забывая, что направления считаются по битам справа налево в порядке "вверх-направо-вниз-налево".
Старший полубайт используется при составлении путей, так что лишней памяти не требуется.
Обратите внимание, что в файл пишется не полный код лабиринта, а только младшие полубайты. Если нужен полный, пригодный для поиска путей, уберите &0x0F в фунции getTextMaze.
Вот полный код приложения (Visual Studio):
//Visual Studio 2015
#define _CRT_SECURE_NO_WARNINGS
#include <locale.h>
#include <windows.h>
#include <iostream>
#include <string>
using namespace std;
const int CELL_SIZE = 8; //размер клетки лабиринта
const int START_X = 10; //откуда рисуем картинку
const int START_Y = 60;
enum directions { NO_DIR, UP_DIR = 1, RIGHT_DIR = 2, DOWN_DIR = 4, LEFT_DIR = 8 };
class myBitmap {
private:
HBITMAP bmp; //дескриптор
HDC hdc; //контекст устройства
HPEN pen; //перо
void *pBits; //картинка
int width, height; //размеры в px
public:
myBitmap() : pen( NULL ) { //конструктор
}
~myBitmap() { //деструктор
DeleteObject (pen);
DeleteDC (hdc);
DeleteObject (bmp);
}
bool create ( int w, int h ) { //создать BMP размером w*h
width = w; height = h;
BITMAPINFO bi;
ZeroMemory( &bi, sizeof( bi ) );
bi.bmiHeader.biSize = sizeof( bi.bmiHeader );
bi.bmiHeader.biBitCount = sizeof(DWORD)*8;
bi.bmiHeader.biCompression = BI_RGB;
bi.bmiHeader.biPlanes = 1;
bi.bmiHeader.biWidth = w;
bi.bmiHeader.biHeight = -h;
HDC dc = GetDC(GetConsoleWindow());
bmp = CreateDIBSection( dc, &bi, DIB_RGB_COLORS, &pBits, NULL, 0 );
if (!bmp) return false;
hdc = CreateCompatibleDC (dc);
SelectObject (hdc, bmp);
ReleaseDC (GetConsoleWindow(), dc);
return true;
}
void clear() { //очистить
ZeroMemory(pBits, width*height*sizeof(DWORD));
}
void setPenColor (DWORD color) { //установить цвет пера
if (pen) DeleteObject (pen);
pen = CreatePen (PS_SOLID, 1, color);
SelectObject(hdc, pen);
}
void saveBitmap (string path) { //сохранить в файл
BITMAPFILEHEADER fileheader;
BITMAPINFO infoheader;
BITMAP bitmap;
DWORD wb;
GetObject( bmp, sizeof(bitmap), &bitmap);
DWORD* dwpBits = new DWORD[bitmap.bmWidth*bitmap.bmHeight];
ZeroMemory (dwpBits, bitmap.bmWidth*bitmap.bmHeight*sizeof(DWORD));
ZeroMemory (&infoheader, sizeof(BITMAPINFO));
ZeroMemory (&fileheader, sizeof(BITMAPFILEHEADER));
infoheader.bmiHeader.biBitCount = sizeof(DWORD)*8;
infoheader.bmiHeader.biCompression = BI_RGB;
infoheader.bmiHeader.biPlanes = 1;
infoheader.bmiHeader.biSize = sizeof(infoheader.bmiHeader);
infoheader.bmiHeader.biHeight = bitmap.bmHeight;
infoheader.bmiHeader.biWidth = bitmap.bmWidth;
infoheader.bmiHeader.biSizeImage = bitmap.bmWidth*bitmap.bmHeight*sizeof(DWORD);
fileheader.bfType = 0x4D42;
fileheader.bfOffBits = sizeof(infoheader.bmiHeader) + sizeof(BITMAPFILEHEADER);
fileheader.bfSize = fileheader.bfOffBits + infoheader.bmiHeader.biSizeImage;
GetDIBits (hdc, bmp, 0, height, (LPVOID)dwpBits, &infoheader, DIB_RGB_COLORS);
HANDLE file = CreateFile(path.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
WriteFile (file, &fileheader, sizeof(BITMAPFILEHEADER), &wb, NULL);
WriteFile (file, &infoheader.bmiHeader, sizeof(infoheader.bmiHeader), &wb, NULL);
WriteFile (file, dwpBits, bitmap.bmWidth*bitmap.bmHeight*4, &wb, NULL);
CloseHandle (file);
delete [] dwpBits;
}
HDC getDC() const { return hdc; }
int getWidth() const { return width; }
int getHeight() const { return height; }
};
class mazeGenerator {
private:
BYTE *_maze; //лабиринт
int _size, _cX, _cY; //размер и счётчики клеток
myBitmap _bmp; //картинка
void generate() { //выделение памяти и вызов генерации
killArray();
_maze = new BYTE [_size*_size];
ZeroMemory (_maze, _size*_size);
_cX = rand()%_size;
_cY = rand()%_size;
make_generate();
}
void make_generate() { //генерация лабиринта
while (true) {
int d = getDirection();
if (d<UP_DIR) return;
switch (d) {
case UP_DIR:
_maze[_cX +_size*_cY] |= UP_DIR; _cY--;
_maze[_cX +_size*_cY] = DOWN_DIR | DOWN_DIR << 4;
break;
case RIGHT_DIR:
_maze[_cX+_size*_cY] |= RIGHT_DIR; _cX++;
_maze[_cX+_size*_cY] = LEFT_DIR | LEFT_DIR << 4;
break;
case DOWN_DIR:
_maze[_cX+_size*_cY] |= DOWN_DIR; _cY++;
_maze[_cX+_size*_cY] = UP_DIR | UP_DIR << 4;
break;
case LEFT_DIR:
_maze[_cX+_size*_cY] |= LEFT_DIR; _cX--;
_maze[_cX+_size*_cY] = RIGHT_DIR | RIGHT_DIR << 4;
break;
}
}
}
int getDirection() { //выбор направления
int d = 1 << rand() % 4;
while( true ) {
for (int x=0; x<4; x++) {
if (testDir(d)) return d;
d <<= 1;
if (d>8) d=1;
}
d = (_maze[_cX+_size*_cY]&0xf0)>>4;
if (!d) return -1;
switch (d) {
case UP_DIR: _cY--; break;
case RIGHT_DIR: _cX++; break;
case DOWN_DIR: _cY++; break;
case LEFT_DIR: _cX--; break;
}
d = 1 << rand()%4;
}
}
bool testDir (int d) { //проверка, свободно ли направление
switch (d) {
case UP_DIR: return (_cY-1>-1 && !_maze[_cX+_size*(_cY-1)]);
case RIGHT_DIR: return (_cX+1<_size && !_maze[_cX+1+_size*_cY]);
case DOWN_DIR: return (_cY+1<_size && !_maze[_cX+_size*(_cY+1)]);
case LEFT_DIR: return (_cX-1>-1 && !_maze[_cX-1+_size*_cY]);
}
return false;
}
void killArray() { //освобождение памяти
if (_maze) delete [] _maze;
}
public:
mazeGenerator() { //конструктор
_maze = 0;
}
~mazeGenerator() { //деструктор
killArray();
}
BYTE *getMaze() const { //получить код лабиринта
return _maze;
}
void getTextMaze (int *text) const { //получить числа лабиринта в память text
int k=0;
for (int y=0; y<_size; y++)
for (int x=0; x<_size; x++)
text[k++]=(int)_maze[x+_size*y]&0x0f;
}
void create( int size ) { //создать лабиринт
_size = size;
generate();
}
};
class mazeSolver {
private:
BYTE *_maze, *_points; //лабиринт и путь
int _size, _sx, _sy, _ex, _ey, //размер, начало и конец пути
_lastDir; //последнее направление
myBitmap _bmp; //картинка
char _filename[128]; //имя файла
int invert (int d) { //обратное направление
switch (d) {
case UP_DIR: return DOWN_DIR;
case DOWN_DIR: return UP_DIR;
case LEFT_DIR: return RIGHT_DIR;
case RIGHT_DIR: return LEFT_DIR;
}
return NO_DIR;
}
void updatePosition (int d) { //изменение позиции по направлению
switch (d) {
case UP_DIR: _sy--; break;
case RIGHT_DIR: _sx++; break;
case DOWN_DIR: _sy++; break;
case LEFT_DIR: _sx--;
}
}
bool findTheWay() { //найти путь
while (true) {
int d = getDirection();
if (d<UP_DIR) return false; //тупичок Гоблина
_lastDir = invert(d);
_maze[_sx+_size*_sy] |= d;
_points[_sx+_size*_sy] = d;
updatePosition (d);
if (_sx==_ex &&_sy==_ey) return true; //найдено
_maze[_sx+_size*_sy] |= _lastDir << 4;
}
}
int getDirection() { //получение направления
int d = 1 << rand()%4;
while (true) {
for (int x=0; x<4; x++) {
if (testDirection(d)) return d;
d<<=1;
if (d>8) d=1;
}
d = (_maze[_sx+_size*_sy]&0xf0)>>4;
if (!d) return -1;
_points[_sx+_size*_sy]=0;
updatePosition(d);
_lastDir=invert (d);
d = 1 << rand()% 4;
}
}
bool testDirection (int d) { //проверка, свободно ли направление
if (d==_lastDir || !(_maze[_sx+_size*_sy]&d)) return false;
switch (d) {
case UP_DIR:
return _sy-1>-1 && !(_maze[_sx+_size*(_sy-1)]&0xf0);
case RIGHT_DIR:
return _sx+1<_size && !(_maze[_sx+1+_size*_sy]&0xf0);
case DOWN_DIR:
return _sy+1<_size && !(_maze[_sx+_size*(_sy+1)]&0xf0);
case LEFT_DIR:
return _sx-1>-1 && !(_maze[_sx-1+_size*_sy]&0xf0);
}
return false;
}
void display() { //показать на картинке _bmp
_bmp.setPenColor(RGB(0,255,0)); //зелёный цвет
_bmp.clear();
HDC dc = _bmp.getDC();
//отрисовка лабиринта:
for (int y=0; y<_size; y++) {
int yy = y*_size;
for (int x=0; x<_size; x++) {
BYTE b = _maze[x+yy];
int nx = x*CELL_SIZE, ny = y*CELL_SIZE;
if (!(b&UP_DIR)) {
MoveToEx (dc, nx, ny, NULL);
LineTo (dc, nx+CELL_SIZE+1, ny);
}
if (!(b&RIGHT_DIR)) {
MoveToEx (dc, nx + CELL_SIZE, ny, NULL);
LineTo (dc,nx+CELL_SIZE, ny+CELL_SIZE+1);
}
if (!(b&DOWN_DIR)) {
MoveToEx (dc, nx, ny + CELL_SIZE, NULL);
LineTo (dc, nx+CELL_SIZE+1, ny+CELL_SIZE);
}
if (!(b&LEFT_DIR)) {
MoveToEx (dc, nx, ny, NULL);
LineTo (dc, nx, ny+CELL_SIZE+1);
}
}
}
drawEndPoints (dc); //нарисовать начало и конец пути
_bmp.setPenColor(RGB(255,0,0)); //красный цвет пера
//отрисовка пути:
for (int y=0; y<_size; y++) {
int yy = y*_size;
for (int x = 0; x < _size; x++) {
BYTE d = _points[x+yy];
if (!d) continue;
int nx = x*CELL_SIZE+CELL_SIZE/2, ny = y*CELL_SIZE+CELL_SIZE/2;
MoveToEx (dc, nx, ny, NULL);
switch( d ) {
case UP_DIR: LineTo( dc, nx, ny - CELL_SIZE - 1 ); break;
case RIGHT_DIR: LineTo( dc, nx + CELL_SIZE + 1, ny ); break;
case DOWN_DIR: LineTo( dc, nx, ny + CELL_SIZE + 1 ); break;
case LEFT_DIR: LineTo( dc, nx - CELL_SIZE - 1, ny ); break;
}
}
}
_bmp.saveBitmap(_filename); //сохранить в файл
BitBlt (GetDC(GetConsoleWindow()), START_X, START_Y, START_X+_size*CELL_SIZE+1, START_Y+_size*CELL_SIZE+1,
_bmp.getDC(), 0, 0, SRCCOPY); //вывести
}
void drawEndPoints (HDC dc) { //изобразить начало и конец пути
RECT rc;
int x = 1+_sx*CELL_SIZE, y=1+_sy* CELL_SIZE;
SetRect (&rc, x, y, x+CELL_SIZE-1, y+CELL_SIZE-1);
FillRect (dc, &rc, (HBRUSH)GetStockObject(WHITE_BRUSH));
x=1+_ex*CELL_SIZE, y=1+_ey*CELL_SIZE;
SetRect (&rc, x, y, x+CELL_SIZE-1, y+CELL_SIZE-1);
FillRect (dc, &rc, (HBRUSH)GetStockObject(WHITE_BRUSH));
}
void killPoints() { if( _points ) delete [] _points; }
public:
mazeSolver(char *filename="") { //конструктор
_points = 0;
if (strlen(filename)==0) strcpy (_filename,"noname.bmp");
else strcpy (_filename,filename);
}
~mazeSolver() { //деструктор
killPoints();
}
void solve (BYTE* maze, int size, int sX, int sY, int eX, int eY) {
_lastDir = NO_DIR; _maze = maze; _size = size;
_sx = sX; _sy = sY; _ex = eX; _ey = eY;
_bmp.create (_size*CELL_SIZE+1,_size*CELL_SIZE+1);
for (int y=0; y<_size; y++)
for (int x=0; x<_size; x++)
_maze[x+_size* y] &= 0x0f;
_maze[_sx+_size*_sy] |= UP_DIR << 4;
killPoints();
_points = new BYTE[_size*_size];
ZeroMemory (_points, _size*_size );
findTheWay();
_sx = sX; _sy = sY;
display();
}
void imageClear() {
HDC dc = GetDC(GetConsoleWindow());
RECT rc;
int x = START_X, y=START_Y;
SetRect (&rc, x, y, x+_size*CELL_SIZE+1, y+_size*CELL_SIZE+1);
FillRect (dc, &rc, (HBRUSH)GetStockObject(BLACK_BRUSH));
}
};
int main() {
mazeGenerator mg;
mazeSolver ms("data.bmp");
setlocale(LC_ALL,"Russian");
ShowWindow (GetConsoleWindow(), SW_MAXIMIZE); Sleep (500);
srand (GetTickCount());
int size;
while (true) {
cout << "Введите размер лабиринта - чётное число больше 2 (0 для выхода): ";
cin >> size;
cout << "Смотрите файлы data.bmp, data.txt в папке приложения";
if (!size || size<3) return 0;
if (size%2==1) size++;
if (size>=3) {
mg.create (size);
//как получить это в виде чисел:
int *maze = new int [size*size*sizeof(int)];
mg.getTextMaze (maze);
FILE *out = fopen("data.txt", "wt");
fprintf (out,"{\n");
for (int y=0; y<size; y++) {
fprintf (out," {");
for (int x=0; x<size; x++)
fprintf (out,"%d%c",maze[x+size*y],(x<size-1?',':' '));
fprintf (out,"}%c\n",(y<size-1?',':' '));
}
fprintf (out,"}");
fclose(out);
delete[] maze;
//как решить лабиринт:
int sx, sy, ex, ey;
while (true) {
sx=rand()%size; sy=rand()%size; //случайное начало пути
ex=rand()%size; ey=rand()%size; //случайный конец пути
if (ex!=sx || ey!=sy) break;
}
ms.solve (mg.getMaze(), size, sx, sy, ex, ey);
cout << endl;
}
system("pause");
system("cls");
ms.imageClear();
}
return 0;
}
Можно просто вставить его в файл пустого проекта.
Вот скриншот работы приложения:
скриншот приложения составления и решения лабиринта
P.S. Если новый Studio 2015 "ругается" ошибками на устаревшие функции - посмотрите здесь.
20.03.2015, 20:20 [12182 просмотра]