diff --git a/temp/CirclePhysics.h b/temp/CirclePhysics.h index 9241142..de7baaa 100644 --- a/temp/CirclePhysics.h +++ b/temp/CirclePhysics.h @@ -1,377 +1,445 @@ #pragma once #include +#include namespace zp::physics { inline constexpr f32 EPSILON = 0.0001f; - inline constexpr fvec2 GRAVITY = fvec2(0.0f, 9.81f) * 2.0f; - inline constexpr ui32 ITERATIONS = 2; + inline constexpr fvec2 GRAVITY = fvec2(0.0f, 9.81f) * 8.0f; + inline constexpr ui32 POSITION_ITERATIONS = 8; + inline constexpr ui32 VELOCITY_ITERATIONS = 2; inline constexpr ui32 SUBSTEPS = 6; inline constexpr f32 MAX_STEP_DISPLACEMENT = 3.0f; inline constexpr f32 MAX_CORRECTION = 2.0f; } namespace zp { using namespace physics; // Coefficient of restitution: // // 1.0 = perfectly elastic // 0.0 = completely inelastic inline constexpr f32 WALL_RESTITUTION = 0.25f; inline constexpr f32 CIRCLE_RESTITUTION = 0.20f; inline constexpr f32 CIRCLE_MASS = 10.0f; - inline constexpr f32 CIRCLE_DAMPING = 0.5f; // between [0, 1] + inline constexpr f32 CIRCLE_DAMPING = 0.95f; // between [0, 1] + inline constexpr f32 CIRCLE_RADIUS = 4.0f; + inline constexpr f32 WALL_RADIUS = 1.0f; + inline constexpr f32 SPATIAL_CELL_SIZE = CIRCLE_RADIUS * 2.0f; + inline constexpr f32 WALL_GRID_MARGIN = CIRCLE_RADIUS + WALL_RADIUS; struct Circle { fvec2 Pos, Vel; f32 Radius = 1; struct { RGB Fill = WHITE; RGB Frame = DARK_GREY; } Color; }; struct Wall { fvec2 Start, End; f32 Radius = 1; + size_t LastQueryStamp = 0; RGB Color = BLACK; }; class CirclePhysics { public: CirclePhysics() = default; static_assert(CIRCLE_MASS > 0.0f); private: std::vector m_CircleList; std::vector m_WallList; + std::unordered_map> m_SpatialGrid; + std::unordered_map> m_WallGrid; + bool m_WallGridDirty = true; + size_t m_WallQueryStamp = 0; public: constexpr const std::vector& circles() const { return m_CircleList; } constexpr const std::vector& walls() const { return m_WallList; } public: inline void createCircle(const fvec2& pos, const f32 radius, const RGB& fill, const RGB& frame) { if (!(radius > 0.0f)) return; Circle circle; circle.Pos = pos; circle.Radius = radius; circle.Color = { fill, frame }; m_CircleList.push_back(circle); } inline void createWall(const fvec2& start, const fvec2& end, const f32 radius, const RGB& color) { if ((end - start).mag2() < EPSILON) return; if (!(radius > 0.0f)) return; Wall wall; wall.Start = start; wall.End = end; wall.Radius = radius; wall.Color = color; m_WallList.push_back(wall); + m_WallGridDirty = true; } inline void update(SDLPixelEngine& e) { const f32 dt = std::min(e.deltaTime(), 1.0f / 30.0f); + const f32 subDt = dt / SUBSTEPS; for (ui32 step = 0; step < SUBSTEPS; ++step) { - integrate(dt); - solveCircleCollisions(dt); + integrate(subDt); + solveCircleCollisions(subDt); } removeOffscreen(e); } inline void reset() { m_CircleList.clear(); m_WallList.clear(); + m_SpatialGrid.clear(); + m_WallGrid.clear(); + m_WallGridDirty = true; + m_WallQueryStamp = 0; } constexpr void drawCircle(SDLPixelEngine& e, const Circle& circle) const { e.draw().fillCircle(circle.Pos, circle.Radius, circle.Color.Fill); e.draw().circle(circle.Pos, circle.Radius, circle.Color.Frame); if (circle.Radius > 2) drawVelocityLine(e, circle, circle.Color.Frame); } constexpr void drawWalls(SDLPixelEngine& e) const { for (const auto& wall : m_WallList) { f32 nx = -(wall.End.y - wall.Start.y); f32 ny = (wall.End.x - wall.Start.x); const f32 d = std::sqrt(nx * nx + ny * ny); nx /= d; ny /= d; const fvec2 v0{ wall.Start.x + nx * wall.Radius, wall.Start.y + ny * wall.Radius }; const fvec2 v1{ wall.End.x + nx * wall.Radius, wall.End.y + ny * wall.Radius }; const fvec2 v2{ wall.End.x - nx * wall.Radius, wall.End.y - ny * wall.Radius }; const fvec2 v3{ wall.Start.x - nx * wall.Radius, wall.Start.y - ny * wall.Radius }; // render wall Box box = { v0, v1, v2, v3 }; box.color() = wall.Color; e.draw().fillBox(box); e.draw().fillCircle(wall.Start, wall.Radius, wall.Color); e.draw().fillCircle(wall.End, wall.Radius, wall.Color); } } private: inline void integrate(const f32 dt) { const f32 frameDamping = std::pow(CIRCLE_DAMPING, dt); const f32 maxSpeed = MAX_STEP_DISPLACEMENT / dt; for (auto& circle : m_CircleList) { circle.Vel += GRAVITY * dt; circle.Vel *= frameDamping; const f32 speed = circle.Vel.mag(); if (speed > maxSpeed) circle.Vel *= maxSpeed / speed; circle.Pos += circle.Vel * dt; } } - inline void solveCircleCollisions(const f32 dt) + inline static long long spatialKey(const long long x, const long long y) { - constexpr f32 SLOP = 0.01f; - constexpr f32 PERCENT = 1.0f; - - constexpr f32 InvMass = 1 / CIRCLE_MASS; - constexpr f32 INV_MASS_SUM = InvMass + InvMass; + return x * 100000LL + y; + } - const f32 restThreshold = 2.0f * GRAVITY.mag() * dt; + inline void buildSpatialGrid() + { + m_SpatialGrid.clear(); - // ------------------------- - // Position solver - // ------------------------- + for (size_t index = 0; index < m_CircleList.size(); ++index) + { + const auto& circle = m_CircleList[index]; + const auto cellX = static_cast(std::floor(circle.Pos.x / SPATIAL_CELL_SIZE)); + const auto cellY = static_cast(std::floor(circle.Pos.y / SPATIAL_CELL_SIZE)); + m_SpatialGrid[spatialKey(cellX, cellY)].push_back(index); + } + } - for (ui32 iteration = 0; iteration < ITERATIONS; ++iteration) + template + inline void forEachNearbyPair(Callback callback) + { + for (size_t i = 0; i < m_CircleList.size(); ++i) { - /* Circle vs circle */ + const auto& circle = m_CircleList[i]; + const auto cellX = static_cast(std::floor(circle.Pos.x / SPATIAL_CELL_SIZE)); + const auto cellY = static_cast(std::floor(circle.Pos.y / SPATIAL_CELL_SIZE)); - for (size_t i = 0; i < m_CircleList.size(); ++i) + for (long long offsetY = -1; offsetY <= 1; ++offsetY) { - for (size_t j = i + 1; j < m_CircleList.size(); ++j) + for (long long offsetX = -1; offsetX <= 1; ++offsetX) { - Circle& a = m_CircleList[i]; - Circle& b = m_CircleList[j]; - - const fvec2 delta = b.Pos - a.Pos; - const f32 radiusSum = a.Radius + b.Radius; - const f32 distanceSq = delta.mag2(); - - if (distanceSq >= radiusSum * radiusSum) + const auto found = m_SpatialGrid.find(spatialKey(cellX + offsetX, cellY + offsetY)); + if (found == m_SpatialGrid.end()) continue; - f32 distance = std::sqrt(distanceSq); - fvec2 normal; - - if (distance < EPSILON) + for (const size_t j : found->second) { - // deterministic, but different for each pair - const f32 theta = static_cast((i * 31 + j * 17) % 360) * math::TAU / 360.0f; - normal = math::toCartesian(1.0f, theta); - distance = 0.0f; + if (j > i) + callback(m_CircleList[i], m_CircleList[j], i, j); } - else - normal = delta / distance; + } + } + } + } - const f32 penetration = radiusSum - distance; - const f32 correction = - std::min(std::max(penetration - SLOP, 0.0f), MAX_CORRECTION) * PERCENT / INV_MASS_SUM; + inline void buildWallGrid() + { + m_WallGrid.clear(); - a.Pos -= normal * correction * InvMass; - b.Pos += normal * correction * InvMass; - } + for (size_t index = 0; index < m_WallList.size(); ++index) + { + const auto& wall = m_WallList[index]; + const auto minX = static_cast( + std::floor((std::min(wall.Start.x, wall.End.x) - WALL_GRID_MARGIN) / SPATIAL_CELL_SIZE)); + const auto maxX = static_cast( + std::floor((std::max(wall.Start.x, wall.End.x) + WALL_GRID_MARGIN) / SPATIAL_CELL_SIZE)); + const auto minY = static_cast( + std::floor((std::min(wall.Start.y, wall.End.y) - WALL_GRID_MARGIN) / SPATIAL_CELL_SIZE)); + const auto maxY = static_cast( + std::floor((std::max(wall.Start.y, wall.End.y) + WALL_GRID_MARGIN) / SPATIAL_CELL_SIZE)); + + for (long long cellY = minY; cellY <= maxY; ++cellY) + { + for (long long cellX = minX; cellX <= maxX; ++cellX) + m_WallGrid[spatialKey(cellX, cellY)].push_back(index); } + } - /* Circle vs wall */ + m_WallGridDirty = false; + } + + template + inline void forEachNearbyWall(const Circle& circle, Callback callback) + { + if (m_WallGridDirty) + buildWallGrid(); - for (size_t i = 0; i < m_CircleList.size(); ++i) + const auto cellX = static_cast(std::floor(circle.Pos.x / SPATIAL_CELL_SIZE)); + const auto cellY = static_cast(std::floor(circle.Pos.y / SPATIAL_CELL_SIZE)); + const size_t queryStamp = ++m_WallQueryStamp; + + for (long long offsetY = -1; offsetY <= 1; ++offsetY) + { + for (long long offsetX = -1; offsetX <= 1; ++offsetX) { - Circle& circle = m_CircleList[i]; + const auto found = m_WallGrid.find(spatialKey(cellX + offsetX, cellY + offsetY)); + if (found == m_WallGrid.end()) + continue; - for (const auto& wall : m_WallList) + for (const size_t wallIndex : found->second) { + Wall& wall = m_WallList[wallIndex]; + if (wall.LastQueryStamp == queryStamp) + continue; + + wall.LastQueryStamp = queryStamp; + callback(wall); + } + } + } + } + + inline void solveCircleCollisions(const f32 dt) + { + constexpr f32 SLOP = 0.01f; + constexpr f32 InvMass = 1 / CIRCLE_MASS; + constexpr f32 INV_MASS_SUM = InvMass + InvMass; + const f32 restThreshold = 2.0f * GRAVITY.mag() * dt; + + for (ui32 iteration = 0; iteration < POSITION_ITERATIONS; ++iteration) + { + buildSpatialGrid(); + forEachNearbyPair([&](Circle& a, Circle& b, const size_t i, const size_t j) { + const fvec2 delta = b.Pos - a.Pos; + const f32 radiusSum = a.Radius + b.Radius; + const f32 distanceSq = delta.mag2(); + if (distanceSq >= radiusSum * radiusSum) + return; + + f32 distance = std::sqrt(distanceSq); + fvec2 normal; + if (distance < EPSILON) + { + const f32 theta = static_cast((i * 31 + j * 17) % 360) * + math::TAU / 360.0f; + normal = math::toCartesian(1.0f, theta); + distance = 0.0f; + } + else + normal = delta / distance; + + const f32 penetration = radiusSum - distance; + const f32 correction = + std::min(std::max(penetration - SLOP, 0.0f), MAX_CORRECTION) / INV_MASS_SUM; + a.Pos -= normal * correction * InvMass; + b.Pos += normal * correction * InvMass; + }); + + for (auto& circle : m_CircleList) + { + forEachNearbyWall(circle, [&](Wall& wall) { const fvec2 wallVector = wall.End - wall.Start; const f32 wallLengthSq = wallVector.mag2(); - if (wallLengthSq < EPSILON) - continue; + return; const fvec2 toCircle = circle.Pos - wall.Start; f32 t = wallVector.dot(toCircle) / wallLengthSq; t = std::max(0.0f, std::min(1.0f, t)); const fvec2 closestPoint = wall.Start + wallVector * t; const fvec2 delta = circle.Pos - closestPoint; const f32 distanceSq = delta.mag2(); const f32 collisionRadius = circle.Radius + wall.Radius; - if (distanceSq >= collisionRadius * collisionRadius) - continue; + return; const f32 distance = std::sqrt(distanceSq); const auto normal = wallContactNormal(delta, distance, wallVector); if (!normal) - continue; + return; const f32 penetration = collisionRadius - distance; circle.Pos += *normal * std::max(penetration - SLOP, 0.0f); - } + }); } - } - // ------------------------- - // Velocity Solver - // ------------------------- - - /* Circle vs circle */ - - for (ui32 iteration = 0; iteration < ITERATIONS; ++iteration) + for (ui32 iteration = 0; iteration < VELOCITY_ITERATIONS; ++iteration) { - for (size_t i = 0; i < m_CircleList.size(); ++i) - { - for (size_t j = i + 1; j < m_CircleList.size(); ++j) - { - Circle& a = m_CircleList[i]; - Circle& b = m_CircleList[j]; - - const fvec2 delta = b.Pos - a.Pos; - const f32 distanceSq = delta.mag2(); - const f32 radiusSum = a.Radius + b.Radius; - - // Position solver should already have - // separated these, but allow a small - // tolerance. - if (distanceSq > radiusSum * radiusSum) - continue; - - const f32 distance = std::sqrt(distanceSq); - if (distance < EPSILON) - continue; - - const fvec2 normal = delta / distance; - const fvec2 relativeVelocity = b.Vel - a.Vel; - const f32 velocityAlongNormal = relativeVelocity.dot(normal); - - // Moving apart. - if (velocityAlongNormal >= 0.0f) - continue; - - const f32 e = (-velocityAlongNormal < restThreshold) ? 0.0f : CIRCLE_RESTITUTION; - const f32 impulseMagnitude = -(1 + e) * velocityAlongNormal / INV_MASS_SUM; - const fvec2 impulse = normal * impulseMagnitude; - a.Vel -= impulse * InvMass; - b.Vel += impulse * InvMass; - } - } - - /* Circle vs wall */ + buildSpatialGrid(); + forEachNearbyPair([&](Circle& a, Circle& b, const size_t, const size_t) { + const fvec2 delta = b.Pos - a.Pos; + const f32 distanceSq = delta.mag2(); + const f32 radiusSum = a.Radius + b.Radius; + if (distanceSq > radiusSum * radiusSum) + return; + + const f32 distance = std::sqrt(distanceSq); + if (distance < EPSILON) + return; + + const fvec2 normal = delta / distance; + const fvec2 relativeVelocity = b.Vel - a.Vel; + const f32 velocityAlongNormal = relativeVelocity.dot(normal); + if (velocityAlongNormal >= 0.0f) + return; + + const f32 e = (-velocityAlongNormal < restThreshold) ? 0.0f : CIRCLE_RESTITUTION; + const f32 impulseMagnitude = -(1 + e) * velocityAlongNormal / INV_MASS_SUM; + const fvec2 impulse = normal * impulseMagnitude; + a.Vel -= impulse * InvMass; + b.Vel += impulse * InvMass; + }); - for (size_t i = 0; i < m_CircleList.size(); ++i) + for (auto& circle : m_CircleList) { - Circle& circle = m_CircleList[i]; - - for (const auto& wall : m_WallList) - { + forEachNearbyWall(circle, [&](Wall& wall) { const fvec2 wallVector = wall.End - wall.Start; const f32 wallLengthSq = wallVector.mag2(); - if (wallLengthSq < EPSILON) - continue; + return; const fvec2 toCircle = circle.Pos - wall.Start; f32 t = wallVector.dot(toCircle) / wallLengthSq; t = std::max(0.0f, std::min(1.0f, t)); const fvec2 closestPoint = wall.Start + wallVector * t; const fvec2 delta = circle.Pos - closestPoint; const f32 distanceSq = delta.mag2(); const f32 collisionRadius = circle.Radius + wall.Radius; - if (distanceSq > collisionRadius * collisionRadius) - continue; + return; const f32 distance = std::sqrt(distanceSq); const auto normal = wallContactNormal(delta, distance, wallVector); if (!normal) - continue; + return; const f32 velocityAlongNormal = circle.Vel.dot(*normal); if (velocityAlongNormal >= 0.0f) - continue; // moving apart + return; const f32 e = (-velocityAlongNormal < restThreshold) ? 0.0f : WALL_RESTITUTION; circle.Vel -= *normal * ((1 + e) * velocityAlongNormal); - } + }); } } } inline void removeOffscreen(SDLPixelEngine& e) { const auto screenRect = e.screenRect(); std::erase_if(m_CircleList, [&](const Circle& c) { return !utils::isPointInsideBox(screenRect, c.Pos, c.Radius); }); } constexpr void drawVelocityLine(SDLPixelEngine& e, const Circle& circle, const RGB& color) const { const f32 speedSq = circle.Vel.mag2(); if (speedSq > EPSILON * EPSILON) { const fvec2 dir = circle.Vel / std::sqrt(speedSq); e.draw().line(circle.Pos, circle.Pos + dir * circle.Radius, color); } else e.draw().point(circle.Pos, color); } inline static std::optional wallContactNormal(const fvec2& delta, const f32 distance, const fvec2& wallVector) { // Standard case: The circle center does not lie on the wall segment. if (distance > EPSILON) return delta / distance; // Fallback: The midpoint lies (almost) exactly on the wall line; // in this case, the perpendicular to the wall is the only sensible direction. const fvec2 perpendicular(-wallVector.y, wallVector.x); const f32 length = perpendicular.mag(); if (length < EPSILON) return std::nullopt; return perpendicular / length; } }; } diff --git a/temp/MazeAndCircles.cpp b/temp/MazeAndCircles.cpp index f7ffa81..174fe08 100644 --- a/temp/MazeAndCircles.cpp +++ b/temp/MazeAndCircles.cpp @@ -1,350 +1,353 @@ #include "MazeAndCircles.h" #include zp::MazeAndCircles::MazeAndCircles(const i32 width, const i32 height) : SDLPixelEngine("SDLPixelEngine", width, height) { } zp::MazeAndCircles::MazeAndCircles(const std::string& title, const i32 width, const i32 height) : SDLPixelEngine(title, width, height) { } bool zp::MazeAndCircles::onCreate() { screenColor() = LIGHT_BLUE; loadBackground("why_so_alone_.png"); initMaze(); return true; } bool zp::MazeAndCircles::onUpdate() { setBackground(); generateMaze(); drawMaze(); drawMazeWalls(); updateCircles(); drawCircles(); const i32 posX = Maze.position().x + Maze.totalWidth() + 40; const i32 posY = Maze.position().y + 30; drawInfo({ posX, posY }); return true; } bool zp::MazeAndCircles::onInput() { // Maze if (getKey(Key::LEFT).Held) Maze.generationDelay() -= 1.0f * deltaTime(); if (getKey(Key::RIGHT).Held) Maze.generationDelay() += 1.0f * deltaTime(); if (Maze.generationDelay() < 0) Maze.generationDelay() = 0; if (getKey(Key::RETURN).Pressed) reset(); // circles if (!Maze.isGenerating()) { + if (getMouse(Button::LEFT).Pressed) + createCircles(getMousePos(), 3); + if (getMouse(Button::LEFT).Held) { - if (delayThis(3)) + if (delayThis(0.05f)) createCircles(getMousePos(), 3); } } return true; } void zp::MazeAndCircles::initMaze() { // Maze WallWeight = 1; WallColor = RGB(BLACK, 200); - CircleRadius = 4; + CircleRadius = CIRCLE_RADIUS; CircleFill = ORANGE; CircleFrame = BLACK; Maze.init(*this, 12, 16, 35, static_cast(WallWeight) + 1, false); Maze.position() = { 170, 100 }; MazeWallList.clear(); Maze.color().Free = RGB(); Maze.color().Visited = RGB(LIGHT_BLUE, 150); Maze.color().Background = RGB(); Maze.generationDelay() = 0.0f; // physics DoMazePhysics = false; Physic.reset(); createOuterWalls(); } void zp::MazeAndCircles::generateMaze() { Maze.generate(*this); if (!Maze.isGenerating() && !DoMazePhysics) { getMazeWalls(); DoMazePhysics = true; } } void zp::MazeAndCircles::drawMaze() { Maze.draw(*this); } void zp::MazeAndCircles::drawMazeWalls() { if (!Maze.isGenerating()) Physic.drawWalls(*this); } void zp::MazeAndCircles::createCircles(const fvec2& pos, const i32 N) { for (i32 i = 0; i < N; i++) Physic.createCircle(pos, CircleRadius, CircleFill, CircleFrame); } void zp::MazeAndCircles::updateCircles() { if (DoMazePhysics) Physic.update(*this); } void zp::MazeAndCircles::drawCircles() { for (auto& circle : Physic.circles()) Physic.drawCircle(*this, circle); } void zp::MazeAndCircles::reset() { initMaze(); } void zp::MazeAndCircles::createOuterWalls() { // set Dimensions constexpr i32 outerGap = 50; fvec2 startA = { Maze.position().x - 1, Maze.position().y - outerGap }; fvec2 endA = { Maze.position().x - 1, Maze.position().y }; fvec2 startB = { Maze.position().x - 1 + Maze.totalWidth(), Maze.position().y - outerGap }; fvec2 endB = { Maze.position().x - 1 + Maze.totalWidth(), Maze.totalHeight() + outerGap + 11 }; // create walls Physic.createWall(startA, endA, WallWeight, WallColor); Physic.createWall(startB, endB, WallWeight, WallColor); } void zp::MazeAndCircles::getMazeWalls() { for (i32 y = 0; y < Maze.height() - 1; y++) { for (i32 x = 0; x < Maze.width(); x++) { const fvec2 origin = { x * Maze.cellStride() + Maze.position().x - Maze.pathGap() / 2, y * Maze.cellStride() + Maze.position().y - Maze.pathGap() / 2 }; const fvec2 size = { Maze.cellStride(), Maze.cellStride() }; const frect cellRect = { origin, size }; const WallType wall = static_cast(Maze.array()(x, y)); MazeWallList.push_back(std::make_pair(cellRect, wall)); } } exportMazeWallsToPhysics(); } void zp::MazeAndCircles::loadBackground(const std::string& fileName) { Background = { getRenderer() }; Background.load(fileName); } void zp::MazeAndCircles::setBackground() { Background.fillWindow(); } void zp::MazeAndCircles::drawInfo(const fvec2& pos) { fvec2 p = pos; f32 tabX = 0, tabY = 0, tabX2 = 0; const RGB colorA = RGB(RED, 200); const RGB colorB = RGB(DARK_RED, 200); screenFont().setSize(18); screenFont().setColor(colorA); tabY = fontSize() * 1.0f; tabX = 190.0f; // Maze info drawString(p, "Maze Size:"); p.x += tabX; drawString(p, std::to_string(Maze.width()) + ", " + std::to_string(Maze.height())); p.x = pos.x; p.y += tabY; drawString(p, "Maze Cells:"); p.x += tabX; drawString(p, std::to_string(Maze.size())); p.x = pos.x; p.y += tabY; if (Maze.isGenerating()) { drawString(p, "Generation Delay:"); p.x += tabX; drawString(p, utils::toString(Maze.generationDelay(), 1, 2)); p.x = pos.x; } // active status screenFont().setSize(24); screenFont().setColor(colorB); tabY = fontSize() * 1.0f; tabX = 200; p.y += tabY; if (Maze.isGenerating()) drawString(p, "Generating Maze"); if (!Maze.isGenerating()) drawString(p, "Drop Circles with Mouse"); p.y += tabY * 2; // debug info screenFont().setSize(18); screenFont().setColor(colorA); tabY = fontSize() * 1.0f; tabX = 200; tabX2 = 75; // active circles count drawString(p, "Circle count: "); p.x += tabX; drawString(p, std::to_string(std::size(Physic.circles()))); p.x = pos.x; p.y += tabY; } void zp::MazeAndCircles::exportMazeWallsToPhysics() { for (const auto& mazeWall : MazeWallList) { f32 x0 = mazeWall.first.origin().x; f32 y0 = mazeWall.first.origin().y; f32 x1 = x0 + mazeWall.first.size().x; f32 y1 = y0 + mazeWall.first.size().y; if (x0 > x1) std::swap(x0, x1); if (y0 > y1) std::swap(y0, y1); switch (mazeWall.second) { case WallType::CLOSED: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); // left and right side Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); Physic.createWall(fvec2(x1, y0), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_RIGHT: // right side Physic.createWall(fvec2(x1, y0), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_LEFT_RIGHT: // left and right side Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); Physic.createWall(fvec2(x1, y0), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_LEFT_1: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); // left side Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_LEFT_2: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); // left side Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_LEFT_3: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); // left side Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_LEFT_1: // left Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_LEFT_2: // left Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_LEFT_3: // left Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_LEFT_4: // left Physic.createWall(fvec2(x0, y0), fvec2(x0, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_1: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_2: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_3: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); break; case WallType::CLOSED_BOTTOM_4: // bottom side Physic.createWall(fvec2(x0, y1), fvec2(x1, y1), WallWeight, WallColor); break; default: break; } } } diff --git a/temp/MazeAndCircles.h b/temp/MazeAndCircles.h index 91bc7c3..2518683 100644 --- a/temp/MazeAndCircles.h +++ b/temp/MazeAndCircles.h @@ -1,97 +1,99 @@ +// not modified + #pragma once #include #include "MazeGenerator.h" #include "CirclePhysics.h" namespace zp { enum class WallType { CLOSED = 0, CLOSED_RIGHT = 1, CLOSED_LEFT_RIGHT = 2, CLOSED_BOTTOM_LEFT_1 = 17, CLOSED_BOTTOM_LEFT_2 = 18, CLOSED_BOTTOM_LEFT_3 = 19, CLOSED_LEFT_1 = 20, CLOSED_LEFT_2 = 21, CLOSED_LEFT_3 = 22, CLOSED_LEFT_4 = 23, CLOSED_BOTTOM_1 = 24, CLOSED_BOTTOM_2 = 25, CLOSED_BOTTOM_3 = 26, CLOSED_BOTTOM_4 = 27, CLEAR_1 = 28, CLEAR_2 = 29, CLEAR_3 = 30, }; class MazeAndCircles : public SDLPixelEngine { public: MazeAndCircles() = default; MazeAndCircles(const i32 width, const i32 height); MazeAndCircles(const std::string& title, const i32 width, const i32 height); private: virtual bool onCreate() override; virtual bool onUpdate() override; virtual bool onInput() override; private: // Maze MazeGenerator Maze; using Wall = std::pair; std::vector MazeWallList; f32 WallWeight = 0; RGB WallColor; std::pair CurrentCell; // circles CirclePhysics Physic; f32 CircleRadius = 0; RGB CircleFill; RGB CircleFrame; bool DoMazePhysics = false; // common SDLImage Background; public: void getMazeWalls(); public: // Maze void initMaze(); void generateMaze(); void drawMaze(); void drawMazeWalls(); // Circles void createCircles(const fvec2& pos, const i32 N); void updateCircles(); void drawCircles(); // Common void loadBackground(const std::string& fileName); void setBackground(); void reset(); void drawInfo(const fvec2& pos); private: void createOuterWalls(); void exportMazeWallsToPhysics(); }; } diff --git a/temp/MazeGenerator.h b/temp/MazeGenerator.h index dc53ba3..1bbc84c 100644 --- a/temp/MazeGenerator.h +++ b/temp/MazeGenerator.h @@ -1,259 +1,261 @@ +// not modified + #pragma once #include #include namespace zp { // Some bit fields for convenience enum { CELL_PATH_N = 0x01, CELL_PATH_E = 0x02, CELL_PATH_S = 0x04, CELL_PATH_W = 0x08, CELL_VISITED = 0x10, }; // Colors of the maze struct MazeColor { RGB Background; RGB Visited; RGB Free; RGB TopOfStack; }; class MazeGenerator { public: constexpr MazeGenerator() = default; private: Array2D m_MazeArray; i32 m_VisitedCells = 0; std::stack m_CellStack; i32 m_PathWidth = 0; // Path thickness i32 m_PathGap = 0; // Passage width, additional gap i32 m_CellStride = 0; // Distance from one cell to the next. ivec2 m_MazePosition; // top left pos of the rendered maze f32 m_GenerationDelay = 0; bool m_IsGenerating = false; MazeColor m_Color; public: constexpr Array2D array() const { return m_MazeArray; } constexpr ivec2 position() const { return m_MazePosition; } constexpr ivec2& position() { return m_MazePosition; } constexpr i32 width() const { return m_MazeArray.width(); } constexpr i32 height() const { return m_MazeArray.height(); } constexpr i32 totalWidth() const { return m_MazeArray.width() * m_CellStride; } constexpr i32 totalHeight() const { return m_MazeArray.height() * m_CellStride ; } constexpr size_t size() const { return m_MazeArray.size(); } constexpr i32 pathWidth() const { return m_PathWidth; } constexpr i32 pathGap() const { return m_PathGap; } constexpr i32 cellStride() const { return m_CellStride; } constexpr f32 generationDelay() const { return m_GenerationDelay; } constexpr f32& generationDelay() { return m_GenerationDelay; } constexpr bool isGenerating() const { return m_IsGenerating; } constexpr bool& isGenerating() { return m_IsGenerating; } constexpr MazeColor color() const { return m_Color; } constexpr MazeColor& color() { return m_Color; } public: inline void init( SDLPixelEngine& e, const i32 width, const i32 height, const i32 pathWidth, const i32 pathGap, const bool fullScreen) { // Maze parameters m_PathWidth = pathWidth; m_PathGap = pathGap; m_CellStride = m_PathWidth + m_PathGap; // Distance from one cell to the next. // Maze dimensions if (fullScreen) { const i32 w = e.screenWidth() / m_CellStride; const i32 h = e.screenHeight() / m_CellStride; m_MazeArray = { w, h }; } else { m_MazeArray = { width, height }; } m_Color.Background = GREY; m_Color.Visited = LIGHT_BLUE; m_Color.TopOfStack = WHITE; // reset maze reset(); } inline void reset() { // Clear stack while (!m_CellStack.empty()) m_CellStack.pop(); // Clear array m_MazeArray.clear(); // Choose a starting cell const i32 x = Random().uniformInt(m_MazeArray.width() - 1); const i32 y = Random().uniformInt(m_MazeArray.height() - 1); m_CellStack.push(Coord(x, y)); m_MazeArray(x, y) = CELL_VISITED; m_VisitedCells = 1; m_IsGenerating = true; } constexpr void generate(SDLPixelEngine& e) { if (e.delayThis(m_GenerationDelay)) { // Do Maze Algorithm if (m_VisitedCells < m_MazeArray.size()) { // Create a set of unvisted neighbours std::vector neighbours; // North neighbour if (m_CellStack.top().Y > 0 && (cellOffset(0, -1) & CELL_VISITED) == 0) neighbours.push_back(0); // East neighbour if (m_CellStack.top().X < m_MazeArray.width() - 1 && (cellOffset(1, 0) & CELL_VISITED) == 0) neighbours.push_back(1); // South neighbour if (m_CellStack.top().Y < m_MazeArray.height() - 1 && (cellOffset(0, 1) & CELL_VISITED) == 0) neighbours.push_back(2); // West neighbour if (m_CellStack.top().X > 0 && (cellOffset(-1, 0) & CELL_VISITED) == 0) neighbours.push_back(3); // Are there any neighbours available? if (!neighbours.empty()) { // Choose one available neighbour at random const i32 next_cell_dir = neighbours[Random().uniformInt(neighbours.size() - 1)]; // Create a path between the neighbour and the current cell switch (next_cell_dir) { case 0: // North cellOffset(0, -1) |= CELL_VISITED | CELL_PATH_S; cellOffset(0, 0) |= CELL_PATH_N; m_CellStack.push(Coord(m_CellStack.top().X + 0, m_CellStack.top().Y - 1)); break; case 1: // East cellOffset(+1, 0) |= CELL_VISITED | CELL_PATH_W; cellOffset(0, 0) |= CELL_PATH_E; m_CellStack.push(Coord(m_CellStack.top().X + 1, m_CellStack.top().Y + 0)); break; case 2: // South cellOffset(0, +1) |= CELL_VISITED | CELL_PATH_N; cellOffset(0, 0) |= CELL_PATH_S; m_CellStack.push(Coord(m_CellStack.top().X + 0, m_CellStack.top().Y + 1)); break; case 3: // West cellOffset(-1, 0) |= CELL_VISITED | CELL_PATH_E; cellOffset(0, 0) |= CELL_PATH_W; m_CellStack.push(Coord(m_CellStack.top().X - 1, m_CellStack.top().Y + 0)); break; } m_VisitedCells++; } else { // No available neighbours so backtrack! m_CellStack.pop(); } } else { // m_MazeArray generation is done, set generate flag m_IsGenerating = false; } } } constexpr void draw(SDLPixelEngine& e) { // Draw background const frect background = { m_MazePosition, ivec2(m_MazeArray.width() * m_CellStride, (m_MazeArray.height() - 1) * m_CellStride) - ivec2(m_PathGap, m_PathGap) }; e.draw().fillRectangle(background, m_Color.Background); // Draw Maze for (int y = 0; y < m_MazeArray.height() - 1; y++) { for (int x = 0; x < m_MazeArray.width(); x++) { const ivec2 cellPos( x * m_CellStride + m_MazePosition.x, y * m_CellStride + m_MazePosition.y); // Draw Cell if (m_MazeArray(x, y) & CELL_VISITED) e.draw().fillRectangle(cellPos, ivec2(m_PathWidth, m_PathWidth), m_Color.Visited); else e.draw().fillRectangle(cellPos, ivec2(m_PathWidth, m_PathWidth), m_Color.Free); // Draw passageways between cells if (m_MazeArray(x, y) & CELL_PATH_S) // South e.draw().fillRectangle( ivec2(cellPos.x, cellPos.y + m_PathWidth), ivec2(m_PathWidth, m_CellStride - m_PathWidth), m_Color.Visited); if (m_MazeArray(x, y) & CELL_PATH_E) // East e.draw().fillRectangle( ivec2(cellPos.x + m_PathWidth, cellPos.y), ivec2(m_CellStride - m_PathWidth, m_PathWidth), m_Color.Visited); // Current cell / top of stack if (!m_CellStack.empty() && m_IsGenerating) // Draw only if stack is not empty && maze is generating { const ivec2 stackPos( m_CellStack.top().X * m_CellStride + m_MazePosition.x, m_CellStack.top().Y * m_CellStride + m_MazePosition.y); e.draw().fillRectangle(stackPos, ivec2(m_PathWidth, m_PathWidth), m_Color.TopOfStack); } } } } private: constexpr i32 cellOffset(const i32 x, const i32 y) const { return m_MazeArray(m_CellStack.top().X + x, m_CellStack.top().Y + y); } constexpr i32& cellOffset(const i32 x, const i32 y) { return m_MazeArray(m_CellStack.top().X + x, m_CellStack.top().Y + y); } }; }