[Задача] Побудувати лабіринт

Задача

Згенерувати лабіринт в якому можна було б дістатися у будь-яку клітину.

Рішення

Насправді існує більше одного алгоритму рішення цієї проблеми, деякі можна знайти ось тут – https://en.wikipedia.org/wiki/Maze_generation_algorithm. До того ж важливо знати що вимоги до лабіринту можуть бути змінені. Наприклад має бути необхідним щоб був лише один вхід та вихід, чи щоб вхід/вихід були у заданих точках. І так далі.

Спосіб який пояснюю далі на мою думку є найпростішим для розуміння, саме через те я на ньому і зупинився :)

Використовує цей спосіб техніку пошуку з вертанням в якому для усих знайдених, але ще не обролених шляхів зберігаємо їх і повертаємося щоб їх обробити коли зайшли в тупик.

Отже послідовність приблизно така:

  1. Вибираємо випадкову позицію в лабіринті, робимо її поточною та додаємо її в пройдений шлях, клітинку позначаємо як відвідану. Зменшуємо кількість невідвіданих клітин на одну.
  2. Якщо обробили усі клітини – ми завершили генерацію лабіринту.
  3. Для поточної клітини визначаємо напрямки у яких з неї можна переміститися: у напрямку (північ/вгору, південь/вниз, захід/вліво, схід/вправо) можна переміститися лише якщо там є невідвідана клітинка.
  4. Додаємо поточну клітину у пройдений шлях.
  5. Якщо можливих напрямків нема переходимо до кроку 9.
  6. З усих можливих напрямків випадковим чином вибираємо один і прибираємо відповідні стіни у поточної клітини та сусідньої для неї клітини у обраному напрямку. Наприклад, якщо вибрали йти вправо то у поточної клітини прибираємо східну стіну, а у клітини зправа від неї прибираємо ліву стіну.
  7. Робимо клітину до якої переходимо поточною і позначаємо її як відвідану.
  8. Повертаємося до кроку 2.
  9. Прибираємо останню клітину з пройдено шляху.
  10. Якщо у пройденому шляху ще лишилися клітини робимо останню з них поточною. <– Саме тут відбувається вертання звідки і походить назва алгоритму
  11. Повертаємося до кроку 2.

Реалізація

В моєму коді нижче я зберігаю кожну клітинку лабіринту у чарунці двомірного масиву цілих чисел. Значення числа показує які у клітинки є стіни. Навіть якусь кривеньку функцію відобреаження додав, але вона буде працювати лише з певними шрифтами (у мене Lucida Console).

#include "stdafx.h"

#include "time.h"

#include <array>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define WALL_NORTH 1
#define WALL_SOUTH 2
#define WALL_EAST  4
#define WALL_WEST  8
#define WALLS_ALL (WALL_NORTH | WALL_SOUTH | WALL_EAST | WALL_WEST)

#define DIR_NORTH 1
#define DIR_SOUTH 2
#define DIR_EAST  4
#define DIR_WEST  8

struct Cell
{
  Cell() : walls(WALLS_ALL), visited(false) {}

  int walls;
  bool visited;
};

struct CellCoords
{
  CellCoords(int _x, int _y) : x(_x), y(_y) {}
  int x, y;
};

class Maze
{
public:
  Maze(int w, int h)
  :
  w_(w), h_(h)
  {
    for (int x = 0; x < h; ++x)
    {
      cells_.push_back(vector<Cell>(w));
    }
  }

  void Generate()
  {
    int unvisited = w_ * h_;

    CellCoords currCell(rand() % h_, rand() % w_);

    stack<CellCoords> trail;
    trail.push(currCell);
    cells_[currCell.x][currCell.y].visited = true;
    --unvisited;

    while (unvisited > 0)
    {
      vector<int> dirs;

      if ((currCell.x > 0) && (!cells_[currCell.x - 1][currCell.y].visited))
      {
        dirs.push_back(DIR_NORTH);
      }
      
      if ((currCell.x < h_ - 1) && (!cells_[currCell.x + 1][currCell.y].visited))
      {
        dirs.push_back(DIR_SOUTH);
      }

      if ((currCell.y > 0) && (!cells_[currCell.x][currCell.y - 1].visited))
      {
        dirs.push_back(DIR_WEST);
      }

      if ((currCell.y < w_ - 1) && (!cells_[currCell.x][currCell.y + 1].visited))
      {
        dirs.push_back(DIR_EAST);
      }

      trail.push(currCell);

      if (!dirs.empty())
      {
        switch (dirs[rand() % dirs.size()])
        {
        case DIR_NORTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_NORTH;
          cells_[--currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          break;

        case DIR_SOUTH:
          cells_[currCell.x][currCell.y].walls &= ~WALL_SOUTH;
          cells_[++currCell.x][currCell.y].walls &= ~WALL_NORTH;
          break;

        case DIR_EAST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_EAST;
          cells_[currCell.x][++currCell.y].walls &= ~WALL_WEST;
          break;

        default: // case DIR_WEST:
          cells_[currCell.x][currCell.y].walls &= ~WALL_WEST;
          cells_[currCell.x][--currCell.y].walls &= ~WALL_EAST;
          break;
        }

        cells_[currCell.x][currCell.y].visited = true;
        --unvisited;
      }
      else
      {
        trail.pop();

        if (!trail.empty())
        {
          currCell = trail.top();
          trail.pop();
        }
      }
    }

    // add random entrance and exit
    cells_[rand() % h_][0].walls &= ~WALL_WEST;
    cells_[rand() % h_][w_ - 1].walls &= ~WALL_EAST;
  }

  int GetWidth() const { return w_; }
  int GetHeight() const { return h_; }

  vector<Cell>& operator[](unsigned i) { return cells_[i]; }

private:
  int w_, h_;
  vector<vector<Cell>> cells_;
};

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// |c|d|
// -----
// where a, b, c, d are walls value for the cells.
char getWallChar(int a, int b, int c, int d)
{
  const char aWallChars[] = 
  { 
    ' ',    '\xb3', '\xc4', '\xda', 
    '\xb3', '\xb3', '\xc0', '\xc3', 
    '\xc4', '\xbf', '\xc4', '\xc2', 
    '\xd9', '\xb4', '\xc1', '\xc5' 
  };
  bool bWallToWest = (a & WALL_SOUTH) || (c & WALL_NORTH);
  bool bWallToNorth = (a & WALL_EAST) || (b & WALL_WEST);
  bool bWallToEast = (b & WALL_SOUTH) || (d & WALL_NORTH);
  bool bWallToSouth = (c & WALL_EAST) || (d & WALL_WEST);

  int nIndex = ((bWallToWest ? 1 : 0) << 3) |
    ((bWallToNorth ? 1 : 0) << 2) |
    ((bWallToEast ? 1 : 0) << 1) |
    (bWallToSouth ? 1 : 0);
  
  return aWallChars[nIndex];
}

// Finds out what wall character to draw for cells
// -----
// |a|b|
// -----
// where a, b are walls value for the cells.
char getVerticalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_EAST) || (b & WALL_WEST))
  {
    ch = '\xb3';
  }

  return ch;
}

// Finds out what wall character to draw for cells
// ---
// |a|
// ---
// |b|
// ---
// where a, b are walls value for the cells.
char getHorizontalWallChar(int a, int b)
{
  char ch = ' ';

  if ((a & WALL_SOUTH) || (b & WALL_NORTH))
  {
    ch = '\xc4';
  }

  return ch;
}

void drawMaze(Maze& a)
{
  int h = a.GetHeight();
  int w = a.GetWidth();

  // draw top row
  for (int y = 0; y < w; ++y)
  {
    if (0 == y)
    {
      // top left corner
      cout << getWallChar(0, 0, 0, a[0][y].walls);
    }
    cout << getHorizontalWallChar(0, a[0][y].walls);
    cout << getWallChar(0, 0, a[0][y].walls, (y == w - 1) ? 0 : a[0][y + 1].walls);
  }
  cout << endl;

  // for the rest of the matrix only draw walls on south, east and south-east
  for (int x = 0; x < h; ++x)
  {
    // draw vertical walls
    for (int y = 0; y < w; ++y)
    {
      if (y == 0)
      {
        // leftmost column
        cout << getVerticalWallChar(0, a[x][y].walls);
      }

      // labyrinth cell - just empty room
      cout << ' ';
      
      // cout << hex << a[x][y].walls; // show cell walls value

      cout << getVerticalWallChar(a[x][y].walls, (y == w - 1) ? 0 : a[x][y + 1].walls);
    }
    cout << endl;

    // draw bottom wall
    for (int y = 0; y < w; ++y)
    {
      bool bLastRow = x == h - 1;
      if (y == 0)
      {
        // leftmost column
        cout << getWallChar(0, a[x][0].walls, 0, bLastRow ? 0 : a[x + 1][0].walls);
      }

      cout << getHorizontalWallChar(a[x][y].walls, bLastRow ? 0 : a[x + 1][y].walls);
      
      bool bLastColumn = y == w - 1;
      cout << getWallChar(a[x][y].walls, 
                          bLastColumn ? 0 : a[x][y + 1].walls, 
                          bLastRow ? 0 : a[x + 1][y].walls,
                          (bLastColumn || bLastRow) ? 0 : a[x + 1][y + 1].walls);
    }
    cout << endl;
  }

  cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
  srand(time(NULL));

  int w = 10, h = 7;
  
  Maze m(w, h);
  m.Generate();
  
  drawMaze(m);

  return 0;
}

Приклад згенерованого лабіринту

┌───┬─┬─────────────┐
│   │ │             │
│ │ │ │ ┌───────┐ ──┤
│ │   │ │       │   │
│ └───┤ └─┐ ──┐ └─┬─┤
│     │   │   │   │ │
├───┐ ├── │ │ ├─┐ │ │
│   │ │   │ │ │ │ │ │
│ │ │ │ ──┴─┤ │ │ │ │
│ │   │     │ │   │ │
│ └───┴──── │ │ ──┘ │
│           │ │
│ ──────────┘ ├──── │
              │     │
──────────────┴─────┘

Залишити відповідь

Зайти з допомогою: