БлогNot. Делаем "односвязный" лабиринт и решаем его

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Делаем "односвязный" лабиринт и решаем его

Приложение на 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 "ругается" ошибками на устаревшие функции - посмотрите здесь.


теги: числа графика алгоритм c++

20.03.2015, 20:20; рейтинг: 8237

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

Наверх Яндекс.Метрика
© PerS
вход