Перемещение по лабиринту

#include "maze_gen.hpp"
#include <random>
#include <stdexcept>
 
 
namespace mz {
 
std::vector<std::vector<bool>> generate(std::size_t width, std::size_t height) {
 
 
 
  // Инициализируем размер конечной матрицы maze
  // Ячейки будут представлять из себя фрагменты 2x2 + 1 одно значение сверху и слева для стен
  const std::size_t output_height = height * 2 + 1;
  const std::size_t output_width  = width * 2 + 1;
  // Инициализируем указатель на лабиринт
  std::vector<std::vector<bool>> maze;
  // Зарезервируем размер лабиринта по высоте
  maze.reserve(output_height);
 
  // Инициализируем построчно пустой лабиринт со стенами по периметру и "опорами" (стенами) в нижнем правом углу ячеек 2x2
  // #######
  // #     #
  // # # # #
  // #     #
  // #######
  for (std::size_t i = 0; i < output_height; ++i) {
    std::vector<bool> row;
    row.reserve(output_width);
    for (std::size_t j = 0; j < output_width; ++j)
      // Если этот элемент в строке является ячейкой в левом верхнем углу области 2x2 - то это пустая ячейка в лабиринте
      if ((i % 2 == 1) && (j % 2 == 1))
        row.push_back(false);
      else
        // Если это область для стены справа или область для стены снизу - то инициализируем этот элемент пустой ячейкой в лабиринте
        if (((i % 2 == 1) && (j % 2 == 0) && (j != 0) && (j != output_width - 1))
          || ((j % 2 == 1) && (i % 2 == 0) && (i != 0) && (i != output_height - 1)))
          row.push_back(false);
        else
          // Во всех остальных случаях устанавливаем стену
          row.push_back(true);
    maze.push_back(std::move(row));
  }
 
  //1. Создаём первую строку лабиринта. Ни одна ячейка не будет принадлежать какому - либо множеству.
  // Инициализируем вспомогательную строку, которая будет содержать в себе принадлежность ко множеству для ячейки из алгоритма
  std::vector<std::size_t> row_set;
  row_set.reserve(width);
  // 0 - будет означать, что ячейка не принадлежит никакому множеству
  for (std::size_t i = 0; i < width; ++i)
    row_set.push_back(0);
  // Счетчик для множеств
  std::size_t set = 1;
  // Генератор случайных чисел
  std::random_device rd;
  std::mt19937       mt(rd());
  // от 0 до 2 (2 не входит) и после привидения к int будет либо 0 - где стены нет, либо 1 - стену решили установить
  std::uniform_int_distribution<int> dist(0, 2);
  // Организуем цикл алгоритма Эллера
  for (std::size_t i = 0; i < height; ++i) {
    //2. Присвоить каждой ячейке, которая не входит ни в одно множество, своё уникальное множество.
    for (std::size_t j = 0; j < width; ++j)
      if (row_set[j] == 0)
        row_set[j] = set++;
 
    //3. Создаём правые стены для ячеек, двигаясь слева направо, следующим образом :
    for (std::size_t j = 0; j < width - 1; ++j) {
      //    Случайным образом решаем, добавлять стену или нет
      const auto right_wall = dist(mt);
      //        Если текущая ячейка и ячейка справа являются членами одного и того же множества, всегда создаём между ними стену(чтобы предотвратить петли)
      if ((right_wall == 1) || (row_set[j] == row_set[j + 1]))
        maze.at(i * 2 + 1 /*верхний ряд в i-ом ряду ячеек 2x2*/).at(j * 2 + 2 /*Правый столбец в (i;j) ячейке 2x2*/) = true; /*Создаем стену*/
      else {
        //      * Если не добавляем стену, то объединяем множества, к которым относятся текущая ячейка и ячейка справа
        const auto changing_set = row_set[j + 1];
        for (std::size_t l = 0; l < width; ++l)
          if (row_set[l] == changing_set)
            row_set[l] = row_set[j];
      }
    }
 
    //4. Создаём нижние стены, двигаясь слева направо :
    for (std::size_t j = 0; j < width; ++j) {
      //    * Случайным образом решаем, добавлять нижнюю стену или нет.
      const auto bottom_wall = dist(mt);
      //        * Если ячейка является единственным членом своего множества, то не создаём нижнюю стену
      std::size_t count_current_set = 0;
      for (std::size_t l = 0; l < width; ++l)
        // считаем количество ячеек текущего множества
        if (row_set[j] == row_set[l])
          count_current_set++;
      //        * Если ячейка является единственным членом своего множества, которая не имеет нижней стены, то не создаём нижнюю стену
      if ((bottom_wall == 1) && (count_current_set != 1))
        maze.at(i * 2 + 2).at(j * 2 + 1) = true;
    }
 
    //5. Продолжаем добавлять строки 
    //  * Если вы решите добавить еще одну строку :
    if (i != height - 1) {
      //Каждая область имеет по крайней мере одну ячейку без нижней стены(это предотвратит создание изолированных областей)
      for (std::size_t j = 0; j < width; ++j) {
        std::size_t count_hole = 0;
        for (std::size_t l = 0; l < width; ++l)
          if ((row_set[l] == row_set[j]) && (maze.at(i * 2 + 2).at(l * 2 + 1) == false))
            count_hole++;
        if (count_hole == 0)
          maze.at(i * 2 + 2).at(j * 2 + 1) = false;
      }
 
      //        * скопируем текущую строку
      //        * удаляем в новой строку все правые стены
      /// Правые стенки в инициализированном массиве уже отсутствуют в каждой новой строке
      //        * удаляем ячейки с нижней стеной из их множества
      for (std::size_t j = 0; j < width; ++j)
        if (maze.at(i * 2 + 2 /* Проверим надичие нижней стены у текущего ряда*/).at(j * 2 + 1) == true)
          // Если стенка есть, то удаляем ячейку из множества
          row_set[j] = 0;
      //        * удаляем все нижние стены
      /// Нижние стены в каждом новом ряду ячеек отсутствуют (заложено при инициализации)
    }
    //      * продолжить с шага 2.
  }
 
  //    * Закончиваем лабиринт :
  //        *добавляем нижнюю стену каждой ячейке
  /// Нижняя стена построена при инициализации лабиринта
  //        * перемещаемся слева направо :
  for (std::size_t j = 0; j < width - 1; ++j) {
    //          *Если текущая ячейка и ячейка справа являются членами разных множеств, то :
    if (row_set[j] != row_set[j + 1])
      //            *удалить правую стену
      maze.at(output_height - 2).at(j * 2 + 2) = false;
    //          * объединить множества, к которым принадлежат текущая ячейка и ячейка справа
    /// Это делать не обязательно, так как row_set мы больше не будем использовать,
    /// а все множества в конечном итоге станут одним, после удаления стен
    //          * вывод итоговой строки
  }
  // вернем указатель на полученный лабиринт
  return maze;
}
}// namespace mz