#include "maze.hpp"
#include <assert.h>
#include <algorithm>
#include <optional>
#include <utility>
/**
* @file
* @brief Procedurally generate a maze and translate it to object and light models.
*
* This is the most messy part, but requires mostly trivial math.
* As only done at startup, no performance concerns here.
*/
/** @brief Local helper for discrete 2D coordinate. */
struct Coord : public vertex2_t<dcoord_t> {
bool operator==(const Coord& other) const {
return this->x == other.x && this->y == other.y;
}
};
/** @brief Two 2D integer coordinates span an area, inclusive per convention. */
struct Area {
enum Corner { TR = 0, BR, BL, TL };
enum Side { T = 0, R, B, L };
Coord start;
Coord end;
Area(Coord start, Coord end) : start(start), end(end) {
assert(start.x <= end.x && start.y <= end.y);
}
dcoord_t width() const {
return end.x - start.x + 1;
}
dcoord_t height() const {
return end.y - start.y + 1;
}
Coord dir() const {
return Coord{end.x - start.x, end.y - start.y};
}
vertex2_t<fcoord_t> center() const {
return {(fcoord_t)start.x + ((fcoord_t)(width() - 1) / 2.0F),
(fcoord_t)start.y + ((fcoord_t)(height() - 1) / 2.0F)};
}
bool operator==(const Area& other) const {
return this->start == other.start && this->end == other.end;
}
bool borders(const Coord& c) const {
return ((c.x == this->start.x || c.x == this->end.x) && c.y >= this->start.y && c.y <= this->end.y) ||
((c.y == this->start.y || c.y == this->end.y) && c.x >= this->start.x && c.x <= this->end.x);
}
static vertex_t get_vertex(const Coord& pos, const vertex_t& off, const vertex_t& scale) {
return vertex_t{(fcoord_t)pos.x * scale.x + off.x, (fcoord_t)pos.y * scale.y + off.y, off.z};
}
ray_t get_ray(const vertex_t& off, const vertex_t& scale) const {
return ray_t{get_vertex(start, off, scale), get_vertex(dir(), off * -2.0F, scale),
get_vertex(end, off * -1.0F, scale)};
}
ray_t get_ray_x(const vertex_t& off, const vertex_t& scale) const {
return ray_t{get_vertex(start, {off.x, off.y, off.z >= 0.0F ? 0.0F : -off.z}, scale),
{(fcoord_t)dir().x * scale.x - (off.x * 2.0F), 0.0F, off.z < 0.0F ? std::fabs(off.z) : off.z},
get_vertex(end, {-off.x, off.y, off.z >= 0.0F ? off.z : 0.0F}, scale)};
}
ray_t get_ray_y(const vertex_t& off, const vertex_t& scale) const {
return ray_t{get_vertex(start, {off.x, off.y, off.z >= 0.0F ? 0.0F : -off.z}, scale),
{0.0F, (fcoord_t)dir().y * scale.y - (off.y * 2.0F), off.z < 0.0F ? std::fabs(off.z) : off.z},
get_vertex(end, {off.x, -off.y, off.z >= 0.0F ? off.z : 0.0F}, scale)};
}
Area get_corner(Coord split, Corner corner) const {
switch (corner) {
case Corner::TR:
return Area{Coord{split.x, split.y}, Coord{end.x, end.y}};
case Corner::BR:
return Area{Coord{split.x, start.y}, Coord{end.x, split.y}};
case Corner::BL:
return Area{Coord{start.x, start.y}, Coord{split.x, split.y}};
case Corner::TL:
return Area{Coord{start.x, split.y}, Coord{split.x, end.y}};
default:
assert(false);
return Area{{}, {}};
}
}
Area get_corner(dcoord_t split, Side corner) const {
switch (corner) {
case Side::T:
return Area{Coord{start.x, split}, Coord{end.x, end.y}};
case Side::R:
return Area{Coord{split, start.y}, Coord{end.x, end.y}};
case Side::B:
return Area{Coord{start.x, start.y}, Coord{end.x, split}};
case Side::L:
return Area{Coord{start.x, start.y}, Coord{split, end.y}};
default:
assert(false);
return Area{{}, {}};
}
}
Area get_border(Side corner) const {
switch (corner) {
case Side::T:
return Area{Coord{start.x, end.y}, Coord{end.x, end.y}};
case Side::R:
return Area{Coord{end.x, start.y}, Coord{end.x, end.y}};
case Side::B:
return Area{Coord{start.x, start.y}, Coord{end.x, start.y}};
case Side::L:
return Area{Coord{start.x, start.y}, Coord{start.x, end.y}};
default:
assert(false);
return Area{{}, {}};
}
}
};
/** @brief Tree of rooms per level, each one possibly subdivided by splits. */
struct Room : public Area {
static int get_id() {
static int last_id = 0;
return last_id++;
}
std::pair<int, int> id; ///< iteration depth, auto increment
const Room* parent;
std::vector<std::unique_ptr<Room>> children{};
Room(Coord start, Coord end, int depth, const Room* p) : Area(start, end), id({depth, get_id()}), parent(p) {}
Room(Area area, int depth, const Room* p) : Room(area.start, area.end, depth, p) {}
};
/** @brief Initial maze generation yields a tree of rooms plus door positions. */
struct Maze {
Room room;
std::vector<Coord> doors{};
Maze(Coord dim) : room({0, 0}, dim, 0, nullptr) {}
};
/**
* @brief Basis for the level is a generated maze, which consists of subdivided rooms, walls, and doors.
*
* https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method
*/
class MazeGenerator {
private:
PRNG rnd;
void generate_r(Room* room, std::vector<Coord>* doors) {
if (room->width() > med.x && room->height() > med.y) {
split_x(room, doors);
} else if (room->height() > max.y) {
split_h(room, doors);
} else if (room->width() > max.x) {
split_v(room, doors);
}
}
void split_x(Room* room, std::vector<Coord>* doors) {
Coord split;
Coord split_x_start, split_x_end;
Coord split_y_start, split_y_end;
do {
split = {rnd.get(room->start.x + min.x, room->end.x - min.x),
rnd.get(room->start.y + min.y, room->end.y - min.y)};
split_y_start = Coord{room->start.x, split.y};
split_y_end = Coord{room->end.x, split.y};
split_x_start = Coord{split.x, room->start.y};
split_x_end = Coord{split.x, room->end.y};
} while (std::find(doors->begin(), doors->end(), split_y_start) != doors->end() ||
std::find(doors->begin(), doors->end(), split_y_end) != doors->end() ||
std::find(doors->begin(), doors->end(), split_x_start) != doors->end() ||
std::find(doors->begin(), doors->end(), split_x_end) != doors->end());
const int omit_door = (int)rnd.get(4U);
for (const auto side : {Area::Side::T, Area::Side::R, Area::Side::B, Area::Side::L}) {
if (side == omit_door) {
continue;
}
switch (side) {
case Area::Side::T:
doors->push_back(Coord{split.x, rnd.get(split.y + 1, room->end.y - 1)});
break;
case Area::Side::B:
doors->push_back(Coord{split.x, rnd.get(room->start.y + 1, split.y - 1)});
break;
case Area::Side::L:
doors->push_back(Coord{rnd.get(room->start.x + 1, split.x - 1), split.y});
break;
case Area::Side::R:
doors->push_back(Coord{rnd.get(split.x + 1, room->end.x - 1), split.y});
break;
}
}
for (const auto corner : {Area::Corner::TR, Area::Corner::BR, Area::Corner::BL, Area::Corner::TL}) {
room->children.push_back(std::make_unique<Room>(room->get_corner(split, corner), room->id.first + 1, room));
generate_r(room->children.back().get(), doors);
}
std::shuffle(room->children.begin(), room->children.end(), PRNG(rnd));
}
void split_h(Room* room, std::vector<Coord>* doors) {
dcoord_t split_y{};
Coord split_start, split_end;
do {
split_y = rnd.get(room->start.y + min.y, room->end.y - min.y);
split_start = Coord{room->start.x, split_y};
split_end = Coord{room->end.x, split_y};
} while (std::find(doors->begin(), doors->end(), split_start) != doors->end() ||
std::find(doors->begin(), doors->end(), split_end) != doors->end());
doors->push_back(Coord{rnd.get(room->start.x + 1, room->end.x - 1), split_y});
for (const auto corner : {Area::Side::T, Area::Side::B}) {
room->children.push_back(
std::move(std::make_unique<Room>(room->get_corner(split_y, corner), room->id.first + 1, room)));
generate_r(room->children.back().get(), doors);
}
std::shuffle(room->children.begin(), room->children.end(), PRNG(rnd));
}
void split_v(Room* room, std::vector<Coord>* doors) {
dcoord_t split_x{};
Coord split_start, split_end;
do {
split_x = rnd.get(room->start.x + min.x, room->end.x - min.x);
split_start = Coord{split_x, room->start.y};
split_end = Coord{split_x, room->end.y};
} while (std::find(doors->begin(), doors->end(), split_start) != doors->end() ||
std::find(doors->begin(), doors->end(), split_end) != doors->end());
doors->push_back(Coord{split_x, rnd.get(room->start.y + 1, room->end.y - 1)});
for (const auto corner : {Area::Side::L, Area::Side::R}) {
room->children.push_back(
std::move(std::make_unique<Room>(room->get_corner(split_x, corner), room->id.first + 1, room)));
generate_r(room->children.back().get(), doors);
}
std::shuffle(room->children.begin(), room->children.end(), PRNG(rnd));
}
public:
const Coord min, med, max;
MazeGenerator(PRNG&& seed, Coord min, Coord med, Coord max) : rnd(seed), min(min), med(med), max(max) {
assert(min.x >= 5 && min.y >= 5); // 3 + 2
assert(med.x >= min.x * 2 && med.y >= min.y * 2);
assert(max.x > med.x && max.y > med.y);
}
std::unique_ptr<const Maze> generate(Coord dim) {
assert(dim.x >= min.x + 2 && dim.y >= min.y + 2); // TODO: suffices?
std::unique_ptr<Maze> maze = std::make_unique<Maze>(dim);
generate_r(&maze->room, &maze->doors);
return maze;
}
};
Level::Level(PRNG&& seed, fcoord_t radius, res_t res, vertex2_t<fcoord_t> viewport)
: texture_factory(PRNG(seed.last()), res, viewport), light_factory(PRNG(seed.last()), radius) {}
/**
* @brief From a tree of rooms and doors, generate a level by building models for walls and lights.
*
* One of the most messy parts, but requires mostly trivial math.
*/
class LevelGenerator {
private:
const PRNG::result_type seed;
PRNG rnd;
MazeGenerator generator;
const vertex2_t<dcoord_t> dim;
const vertex_t tile_dim;
std::unique_ptr<Level> generate(const Maze& maze) {
std::unique_ptr<Level> level = std::make_unique<Level>(
PRNG(rnd), (fcoord_t)generator.med.x * tile_dim.x / 2.0F, res_t{dim.x * 2, dim.y * 2},
vertex2_t<fcoord_t>{(fcoord_t)dim.x * tile_dim.x, (fcoord_t)dim.y * tile_dim.y});
collect_rooms(&maze.room, level->rooms);
generate_r(level.get(), &maze.room, maze.doors);
level->start = pick_start(&maze.room);
level->end = pick_end(&maze.room);
const vertex_t end_pos{level->end.x * tile_dim.x, level->end.y * tile_dim.y, tile_dim.z / 2.0F};
level->lights.push_back({end_pos, level->light_factory.make(tile_dim.x, vertex_t::setted(-1.5F))});
level->lights.push_back({end_pos, level->light_factory.make((fcoord_t)generator.max.x * tile_dim.x / 4.0F,
vertex_t::setted(1.01F))});
return level;
}
void collect_rooms(const Room* room, std::vector<vertex_t>& rooms) const {
if (room->children.empty()) {
const vertex2_t<fcoord_t> center = room->center();
rooms.push_back({center.x * tile_dim.x, center.y * tile_dim.y, tile_dim.z / 2.0F});
}
for (const auto& child : room->children) {
collect_rooms(child.get(), rooms);
}
}
vertex2_t<fcoord_t> pick_start(const Room* room) const {
while (!room->children.empty()) { // first leaf
room = room->children.front().get();
}
return room->center();
}
vertex2_t<fcoord_t> pick_end(const Room* room) const {
while (!room->children.empty()) { // last leaf
room = room->children.back().get();
}
return room->center();
}
void generate_r(Level* level, const Room* room, const std::vector<Coord>& doors) {
if (!room->children.empty()) {
for (const auto& child : room->children) {
generate_r(level, child.get(), doors);
}
return;
}
const vertex_t wall_dim{tile_dim.x / 4.0F, tile_dim.y / 4.0F, tile_dim.z};
generate_walls(level, room, doors, wall_dim);
#if USE_LIGHTS
generate_lights(level, room, doors, wall_dim);
#endif
}
void generate_walls(Level* level, const Room* room, const std::vector<Coord>& doors,
const vertex_t& wall_dim) const {
const vertex_t margin = micro_coord; // for more deterministic clipping
const Texture* texture = level->texture_factory.make(room->id);
const ray_t inside_ray = room->get_ray((wall_dim - margin).with_z(), tile_dim);
level->objects.push_back(std::make_unique<SidedAxisPlane>(inside_ray.pos, inside_ray.dir, true, texture));
for (const auto side : {Area::Side::T, Area::Side::B, Area::Side::L, Area::Side::R}) {
const Area border = room->get_border(side);
const std::optional<std::pair<Coord, const Room*>> door_pos =
find_door(border.start, border.end, room, doors);
const bool dir_pos = side == Area::Side::B || side == Area::Side::L;
ray_t border_ray{};
switch (side) {
case Area::Side::T:
border_ray = border.get_ray_x({wall_dim.x, -wall_dim.y, wall_dim.z}, tile_dim);
break;
case Area::Side::B:
border_ray = border.get_ray_x({wall_dim.x, wall_dim.y, wall_dim.z}, tile_dim);
break;
case Area::Side::L:
border_ray = border.get_ray_y({wall_dim.x, wall_dim.y - margin.y, wall_dim.z}, tile_dim);
break;
case Area::Side::R:
border_ray = border.get_ray_y({-wall_dim.x, wall_dim.y - margin.y, wall_dim.z}, tile_dim);
break;
}
assert((border_ray.dst - border_ray.pos - border_ray.dir).len() == 0.0F);
if (!door_pos.has_value()) {
level->objects.push_back(
std::make_unique<SidedAxisPlane>(border_ray.pos, border_ray.dir, dir_pos, texture));
continue;
}
assert(door_pos.value().second != nullptr);
const Texture* texture_x = level->texture_factory.make(door_pos.value().second->id, room->id, 0);
const Texture* texture_y = level->texture_factory.make(door_pos.value().second->id, room->id, 1);
const Area door = Area{door_pos.value().first, door_pos.value().first};
ray_t door_ray{};
switch (side) {
case Area::Side::T:
door_ray = door.get_ray_x({-tile_dim.x / 2.0F, -wall_dim.y, -wall_dim.z}, tile_dim);
break;
case Area::Side::B:
door_ray = door.get_ray_x({-tile_dim.x / 2.0F, wall_dim.y, -wall_dim.z}, tile_dim);
break;
case Area::Side::L:
door_ray = door.get_ray_y({wall_dim.x, -tile_dim.y / 2.0F + margin.y, -wall_dim.z}, tile_dim);
break;
case Area::Side::R:
door_ray = door.get_ray_y({-wall_dim.x, -tile_dim.y / 2.0F + margin.y, -wall_dim.z}, tile_dim);
break;
}
level->objects.push_back(
std::make_unique<SidedAxisPlane>(border_ray.pos, border_ray.pos.to(door_ray.pos), dir_pos, texture));
level->objects.push_back(
std::make_unique<SidedAxisPlane>(door_ray.dst, door_ray.dst.to(border_ray.dst), dir_pos, texture));
if (side == Area::Side::B) {
ray_t floor_ray = door.get_ray({-tile_dim.x / 2.0F, -wall_dim.y, 0.0F}, tile_dim);
ray_t side_ray = door.get_ray_y({-tile_dim.x / 2.0F, -wall_dim.y - margin.y, 1.0F}, tile_dim); // L
ray_t side_n_ray = door.get_ray_y({tile_dim.x / 2.0F, -wall_dim.y - margin.y, 1.0F}, tile_dim); // R
level->objects.push_back(
std::make_unique<SidedAxisPlane>(floor_ray.pos, floor_ray.dir, true, texture_y));
level->objects.push_back(std::make_unique<SidedAxisPlane>(side_ray.pos, side_ray.dir, true, texture_x));
level->objects.push_back(
std::make_unique<SidedAxisPlane>(side_n_ray.pos, side_n_ray.dir, false, texture_x));
} else if (side == Area::Side::L) {
ray_t floor_ray = door.get_ray({-wall_dim.x, -tile_dim.y / 2.0F, 0.0F}, tile_dim);
ray_t side_ray = door.get_ray_x({-wall_dim.x, -tile_dim.y / 2.0F, 1.0F}, tile_dim); // B
ray_t side_n_ray = door.get_ray_x({wall_dim.x, tile_dim.y / 2.0F, 1.0F}, tile_dim); // T
level->objects.push_back(
std::make_unique<SidedAxisPlane>(floor_ray.pos, floor_ray.dir, true, texture_x));
level->objects.push_back(std::make_unique<SidedAxisPlane>(side_ray.pos, side_ray.dir, true, texture_x));
level->objects.push_back(
std::make_unique<SidedAxisPlane>(side_n_ray.dst, side_n_ray.dir * -1.0F, false, texture_x));
}
}
}
void generate_lights(Level* level, const Room* room, const std::vector<Coord>& doors, const vertex_t& wall_dim) {
std::vector<Area::Side> sides{Area::Side::T, Area::Side::B, Area::Side::L, Area::Side::R};
std::shuffle(sides.begin(), sides.end(), PRNG(rnd));
sides.resize(rnd.get(0U, 4U));
for (const auto side : sides) {
const Area border = room->get_border(side);
const std::optional<std::pair<Coord, const Room*>> door_pos =
find_door(border.start, border.end, room, doors);
const Coord room_pos{rnd.get(room->start.x + 1, room->end.x - 1),
rnd.get(room->start.y + 1, room->end.y - 1)};
const vertex_t pos{(fcoord_t)room_pos.x * tile_dim.x, (fcoord_t)room_pos.y * tile_dim.y, wall_dim.z / 2.0F};
const vertex_t off{tile_dim.x / 4.0F, tile_dim.y / 4.0F, 0.0F}; // proximity to wall
const fcoord_t radius = level->light_factory.get_radius();
vertex_t light_pos{};
switch (side) {
case Area::Side::T:
if (!door_pos.has_value() || std::fabs((fcoord_t)door_pos->first.x * tile_dim.x - pos.x) > radius) {
light_pos = {pos.x, (fcoord_t)room->end.y * tile_dim.y - wall_dim.y - off.y, pos.z};
} else {
continue;
}
break;
case Area::Side::B:
if (!door_pos.has_value() || std::fabs((fcoord_t)door_pos->first.x * tile_dim.x - pos.x) > radius) {
light_pos = {pos.x, (fcoord_t)room->start.y * tile_dim.y + wall_dim.y + off.y, pos.z};
} else {
continue;
}
break;
case Area::Side::L:
if (!door_pos.has_value() || std::fabs((fcoord_t)door_pos->first.y * tile_dim.y - pos.y) > radius) {
light_pos = {(fcoord_t)room->start.x * tile_dim.x + wall_dim.x + off.x, pos.y, pos.z};
} else {
continue;
}
break;
case Area::Side::R:
if (!door_pos.has_value() || std::fabs((fcoord_t)door_pos->first.y * tile_dim.y - pos.y) > radius) {
light_pos = {(fcoord_t)room->end.x * tile_dim.x - wall_dim.x - off.x, pos.y, pos.z};
} else {
continue;
}
break;
default:
assert(false);
break;
}
level->lights.push_back({light_pos, level->light_factory.make({room->id.first, room->id.second + side})});
}
}
static std::optional<std::pair<Coord, const Room*>> find_door(Coord start, Coord end, const Room* curr,
const std::vector<Coord>& doors) {
const Room* root = curr;
while (root->parent != nullptr) {
root = root->parent;
}
for (auto x = start.x; x <= end.x; ++x) {
for (auto y = start.y; y <= end.y; ++y) {
Coord pos = Coord{x, y};
assert(curr->borders(pos));
if (std::find(doors.begin(), doors.end(), pos) != doors.end()) {
return std::pair<Coord, const Room*>(pos, find_room(pos, root, curr));
}
}
}
return std::nullopt;
}
static const Room* find_room(Coord door, const Room* root, const Room* curr) {
if (root->borders(door) && root != curr && root->children.empty()) {
return root;
}
for (const auto& child : root->children) {
const Room* result = find_room(door, child.get(), curr);
if (result != nullptr) {
return result;
}
}
return nullptr;
}
public:
LevelGenerator(PRNG::result_type seed, vertex2_t<dcoord_t> min, vertex2_t<dcoord_t> med, vertex2_t<dcoord_t> max,
vertex2_t<dcoord_t> dim, vertex_t tile_dim)
: seed(seed),
rnd(seed),
generator{PRNG(rnd), {min.x, min.y}, {med.x, med.y}, {max.x, max.y}},
dim{dim},
tile_dim{tile_dim} {}
std::unique_ptr<Level> generate() {
LOG("Generating level: %u", seed);
std::unique_ptr<const Maze> maze = generator.generate({dim.x, dim.y});
std::unique_ptr<Level> level = generate(*maze);
LOG("Scene %d/%d with %zu rooms, %zu objects, %zu lights, %zu textures", dim.x, dim.y, level->rooms.size(),
level->objects.size(), level->lights.size(), level->texture_factory.size());
return level;
}
};
std::unique_ptr<const Level> generate(PRNG::result_type seed, vertex2_t<dcoord_t> min, vertex2_t<dcoord_t> med,
vertex2_t<dcoord_t> max, vertex2_t<dcoord_t> dim, vertex_t tile_dim) {
return LevelGenerator(seed, min, med, max, dim, tile_dim).generate();
}
