Генерация лабиринтов: алгоритм Эллера

1. Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.

2. Присвойте ячейкам, не входящим в множество, свое уникальное множество.

3. Создайте правые границы, двигаясь слева направо:

   1. Случайно решите добавлять границу или нет 

      1. Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)

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

4. Создайте границы снизу, двигаясь слева направо:

   • Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей)

     1. Если ячейка в своем множестве одна, то не создавайте границу снизу

     2. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу

5. Решите, будете ли вы дальше добавлять строки или хотите закончить лабиринт

   1. Если вы хотите добавить еще одну строку, то:

      1. Выведите текущую строку

      2. Удалите все правые границы

      3. Удалите ячейки с нижней границей из их множества

      4. Удалите все нижние границы

      5. Продолжайте с шага 2

   2. Если вы решите закончить лабиринт, то:

      1. Добавьте нижнюю границу к каждой ячейке

      2. Двигаясь слева направо:

         1. Если текущая ячейка и ячейка справа члены разных множеств, то:

            1. Удалите правую границу

            2. Объедините множества текущей ячейки и ячейки справа

            3. Выведите завершающую строку

/* Метод генерации лабиринта */
void Maze::generateMaze() {
	  /* Шаг 1 */
    fillEmptyValue();
    for (int j = 0; j < rows_ - 1; j++) {
      	/* Шаг 2 */
        assignUniqueSet();
      	/* Шаг 3 */
        addingVerticalWalls(j);
      	/* Шаг 4 */
        addingHorizontalWalls(j);
        checkedHorizontalWalls(j);
      	/* Шаг 5.1*/
        preparatingNewLine(j);
    }
  	/* Шаг 5.2 */
    addingEndLine();
}

/* Заполним вектор пустым значением */
void Maze::fillEmptyValue() {
    for (int i = 0; i < cols_; i++) {
        sideLine_.push_back(kEmpty);
    }
}

constexpr int kEmpty = 0;

/* Присваиваем ячейкам свое уникальное множество */
void Maze::assignUniqueSet() {
    for (int i = 0; i < cols_; i++) {
      	/* Проверяем на пустую ячейку */
        if (sideLine_[i] == kEmpty) {
          	/* Присваиваем ячейки уникальное множество */
            sideLine_[i] = counter_;
            counter_++;
        }
    }
}

counter_ - это счетчик генерации уникальных множеств.

Под номером я понимаю расположение ячейки в лабиринте. Не стоит путать это с множеством

/* Добавление правой вертикальной стенки */
void Maze::addingVerticalWalls(int row) {
    for (int i = 0; i < cols_ - 1; i++) {
      	/* Ставим стенку или нет */
        bool choise = randomBool();
      	/* Проверка условия для предотовращения зацикливания */
        if (choise == true || sideLine_[i] == sideLine_[i + 1]) {
            v_walls_(row, i) = true;
        } else {
          	/* Объединение ячеек в одно множество */
            mergeSet(i, sideLine_[i]);
        }
    }
  	/* Добавление правой стенки в последней ячейки */
    v_walls_(row, cols_ - 1) = true;
}

/* Объединение ячеек в одно множество */
void Maze::mergeSet(int index, int element) {
    int mutableSet = sideLine_[index + 1];
    for (int j = 0; j < cols_; j++) {
      	/* Проверка ячеек на одно множество */
        if (sideLine_[j] == mutableSet) {
          	/* Объединение ячейки в множество */
            sideLine_[j] = element;
        }
    }
}

/* Добавление нижней горизонтальной стенки */
void Maze::addingHorizontalWalls(int row) {
    for (int i = 0; i < cols_; i++) {
      	/* Ставим стенку или нет */
        bool choise = randomBool();
      	/* Проверка, что множество имеет более одной ячейки (это предовратит замкнутые области  */
        if (calculateUniqueSet(sideLine_[i]) != 1 && choise == true) {
          	/* Ставим горизонтальную стенку */
            h_walls_(row, i) = true;
        }
    }
}

/* Подсчет ячеек, которые содержаться в уникальном множестве */
int Maze::calculateUniqueSet(int element) {
    int countUniqSet = 0;
    for (int i = 0; i < cols_; i++) {
        if (sideLine_[i] == element) {
            countUniqSet++;
        }
    }
    return countUniqSet;
}

/* Проверка условие 4.1 и 4.2 */
void Maze::checkedHorizontalWalls(int row) {
    for (int i = 0; i < cols_; i++) {
        if (calculateHorizontalWalls(sideLine_[i], row) == 0) {
            h_walls_(row, i) = false;
        }
    }
}

/* Подсчет горизонтальных стен у ячеек уникального множества */
int Maze::calculateHorizontalWalls(int element, int row) {
    int countHorizontalWalls = 0;
    for (int i = 0; i < cols_; i++) {
        if (sideLine_[i] == element && h_walls_(row, i) == false) {
            countHorizontalWalls++;
        }
    }
    return countHorizontalWalls;
}

void Maze::preparatingNewLine(int row) {
    for (int i = 0; i < cols_; i++) {
        if (h_walls_(row, i) == true) {
          	/* Присваиваем ячейки пустое множество */
            sideLine_[i] = kEmpty;
        }
    }
}

1 или 7 (все ячейки принадлежащие к множеству 1 изменить на 7)

/* Добавление последней строки */
void Maze::addingEndLine() {
    assignUniqueSet();
    addingVerticalWalls(rows_ - 1);
    checkedEndLine();
}

/* Проверка условий на добавление последней строки */
void Maze::checkedEndLine() {
    for (int i = 0; i < cols_ - 1; i++) {
      	/* Проверка условия пункта 5.2.1 */
        if (sideLine_[i] != sideLine_[i + 1]) {
          	/* Убираем вертикальную стенку */
            v_walls_(rows_ - 1, i) = false;
          	/* Объединяем множества */
            mergeSet(i, sideLine_[i]);
        }
      	/* Добавляем горизонтальные стенки */
        h_walls_(rows_ - 1, i) = true;
    }
  	/* Добавляем горизонтальную стенку в последней ячейке */
    h_walls_(rows_ - 1, cols_ - 1) = true;
}