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

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

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

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

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

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

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

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

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;
}