Constexpr Maze Generator C++23

constexpr_maze_gen.cpp

// https://godbolt.org/z/hfcnTfaz8
#include <cstdint>
#include <array>
#include <cstddef>
#include <ranges>
#include <algorithm>
#include <utility>
#include <format>
#include <string_view>
#include <print>



// Compile time / constexpr maze generator
// Input: size N x M
//        start_x, start_y
//        end_x, end_y
//        random_seed

enum class AllowedWay : uint8_t {
    None  = 0,
    Left  = 1 << 0,
    Right = 1 << 1,
    Up    = 1 << 2,
    Down  = 1 << 3,
};

constexpr AllowedWay operator | (AllowedWay a, AllowedWay b) {
    return static_cast<AllowedWay>(static_cast<uint8_t>(a) | static_cast<uint8_t>(b));
} 

constexpr std::pair<int32_t, int32_t> direction(AllowedWay dir) {
    switch (dir) {
    case AllowedWay::None:
        return {0, 0};
    case AllowedWay::Left:
        return {0, -1};   
    case AllowedWay::Right:
        return {0, +1};
    case AllowedWay::Up:
        return { -1, 0};
    case AllowedWay::Down:
        return {1, 0};
    }
}

constexpr AllowedWay opposite_direction(AllowedWay dir) {
    using enum AllowedWay;
    switch (dir) {
    case None:
        return None;
    case Left:
        return Right;   
    case Right:
        return Left;
    case Up:
        return Down;
    case Down:
        return Up;
    }
}

template <size_t N, size_t M>
struct Maze {
    std::array<AllowedWay, N * M> tiles {}; 


    template <class Self>
    constexpr decltype(auto) at(this Self&& self, size_t x, size_t y) {
        return std::forward_like<Self>(self.tiles)[x * M + y];
    }  
};

template <size_t M = 1'000'000'007, size_t a = 48271, size_t c = 1>
struct LCG {
    using result_type = size_t;

    constexpr explicit LCG(size_t seed) : current {seed} {}

    constexpr size_t operator () () {
        return (current = (current * a  + c) % M);
    }

    constexpr static size_t min() {
        return 0;
    }
    constexpr static size_t max() {
        return M - 1;
    }

    size_t current;
};

template <size_t N, size_t M>
requires (N > 0 && M > 0)
constexpr auto generate_maze(uint64_t random_seed = 42, size_t start_row = 0, size_t end_row = N - 1) -> Maze<N, M> {
    LCG random_gen{ random_seed } ;

    Maze<N, M> maze;

    static constexpr const auto is_valid = [](int32_t x, int32_t y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }; 

    static constexpr const std::array possible_direction { AllowedWay::Left, AllowedWay::Right, AllowedWay::Up, AllowedWay::Down };

    auto dfs = [&maze, &random_gen](this auto& self, int32_t current_x, int32_t current_y, AllowedWay arrive_direction) -> void {
        
        auto& current_tile =  maze.at(current_x, current_y);

        current_tile = current_tile | opposite_direction(arrive_direction);
        
        auto directions_to_check = possible_direction;
        for (auto& dir : directions_to_check) {
            size_t index = random_gen() % directions_to_check.size();
            std::ranges::swap(dir, directions_to_check[index]);
        }

        for (auto dir : directions_to_check) {
            auto [dx, dy] = direction(dir);
            int32_t next_x = current_x + dx;
            int32_t next_y = current_y + dy;
            if (is_valid(next_x, next_y) && maze.at(next_x, next_y) == AllowedWay::None) {
                current_tile = current_tile | dir;
                self(next_x, next_y, dir);
            }
        }
    };

    dfs(start_row, 0, AllowedWay::Right);
    maze.at(end_row, M - 1) = maze.at(end_row, M - 1) | AllowedWay::Right;
    
    return maze;
}





constexpr std::array<int, 4> random_permut() {
    std::array<int, 4> arr { 1, 2, 3, 4};
    LCG g{77};

    for (auto& item : arr) {
        size_t index = g() % arr.size();
        std::ranges::swap(item, arr[index]);
    }
    return arr;
}


template <size_t N, size_t M>
void print_maze(const Maze<N, M>& maze) {
    // ╔ ╗╚ ╝╠ ╣╦ ╩║═ ╬  ╞ ╡  ╥  ╨

    constexpr auto cell_symbol = [](AllowedWay dir) -> std::string_view  {
        using enum AllowedWay;
        switch (dir) {
        
        case Left:                    return "╡";
        case Right:                   return "╞";
        case Up:                      return "╨";
        case Down:                    return "╥";
        
        case Left | Right:            return "═";
        case Up | Down:               return "║";
        case Left | Up:               return "╝";
        case Left | Down:             return "╗";
        case Right | Up:              return "╚";
        case Right | Down:            return "╔";
        
        case Left | Right | Up:       return "╩";
        case Left | Right | Down:     return "╦";
        case Up | Down | Left:        return "╣";
        case Up | Down | Right:       return "╠";
        
        case Left | Right | Up | Down: return "╬";
        
        default:
            return " ";
        }
    };

    /*
     ═╗
     ╞╩
    */
    
    for (size_t x = 0; x < N; ++x) {
        for (size_t y = 0; y < M; ++y) {
            std::print("{}", cell_symbol(maze.at(x, y)));
        }
        std::print("\n");
    }

}      

int main() {
    constexpr auto maze = generate_maze<20, 50>(89);
    print_maze(maze);
}