Mostly functioning world collisions

8 files changed, 105 insertions, 37 deletions

diff --git a/src/Entities/Player.cpp b/src/Entities/Player.cpp
index fb88222..fd22247 100644
--- a/src/Entities/Player.cpp
+++ b/src/Entities/Player.cpp
@@ -3,6 +3,7 @@
 namespace MC::Entities {
 
 void Player::update(const Time& time, GFX::Window& window, GFX::Camera& camera, World::World& world) {
+    auto origin = m_transform.position();
     auto r = window.mouse_delta();
 
     auto key = [&](Int k) -> Real { return window.key(k, GLFW_PRESS); };
@@ -16,12 +17,9 @@ void Player::update(const Time& time, GFX::Window& window, GFX::Camera& camera,
     auto rotation_speed = 0.1f;
 
     auto direction = m_transform.right() * x + Vec3(0, y, 0) + m_transform.forward() * z;
-    auto destination = m_transform.position() + direction * move_speed;
+    auto destination = origin + direction * move_speed;
 
-    auto collision_domain = terrain_collision_domain(m_transform.position(), destination, world);
-    for (auto collision : collision_domain) {
-        destination = collision_reposition(m_transform.position(), destination, collision);
-    }
+    destination = process_collisions(world, origin, destination);
 
     move_to(destination);
     rotate({r.y() * rotation_speed, r.x() * rotation_speed, 0.0f});
@@ -50,19 +48,51 @@ AABB Player::bounds() const {
     return bounding_box_for_position(m_transform.position());
 }
 
-void Player::update_camera_position(GFX::Camera& camera) {
-    auto camera_position = m_transform.position();
-    camera_position.y() += 1.5;
+#define STUCK_THRESHOLD 100
 
-    camera.set_position(camera_position);
-    camera.set_angles(m_transform.rotation());
+Position::World Player::process_collisions(World::World& world, Position::World from, Position::World to) {
+    auto current_box = bounding_box_for_position(from);
+
+    // All the blocks we could theoretically collide with.
+    auto collision_domain = terrain_collision_domain(from, to, world);
+
+    // Sort the pushouts by magnitude, and apply the biggest one.
+    // If we apply a pushout, we need to check again for collisions,
+    // since we might have slid into another block. (up to STUCK_THRESHOLD times)
+    // If there are no pushouts, we have no collisions,
+    // and the player can move freely to the proposed position.
+
+    std::vector<Vec3> pushouts;
+    for (UInt stuck = 0; stuck < STUCK_THRESHOLD; stuck++) {
+        // Find the pushout vector for each block we're colliding with.
+        for (auto possible_collision : collision_domain) {
+            auto pushout = current_box.pushout(to - from, possible_collision);
+            if (!pushout.is_zero()) pushouts.push_back(pushout);
+        }
+
+        if (pushouts.empty()) return to;
+
+        std::sort(pushouts.begin(), pushouts.end(), [=](const Vec3& a, const Vec3& b) -> bool {
+            return a.magnitude_squared() > b.magnitude_squared();
+        });
+
+        to += pushouts[0];
+        pushouts.clear();
+    }
+
+    // We got stuck, don't move.
+    return from;
 }
 
 std::vector<AABB> Player::terrain_collision_domain(
     Position::World from, Position::World to,
     World::World& world
 ) {
-    auto domain_box = bounding_box_for_position(from).unite(bounding_box_for_position(to));
+    // Make the box a bit bigger so we don't clip through blocks.
+    auto domain_box = bounding_box_for_position(from)
+        .unite(bounding_box_for_position(to))
+        .unite(AABB{{1, 1, 1}});
+
     std::vector<AABB> colliding_blocks;
 
     // TODO: Unbind from chunks and loop through all the
@@ -71,7 +101,7 @@ std::vector<AABB> Player::terrain_collision_domain(
     // since right now if you're fast enough you can clip
     // through whole chunks.
     auto add_colliding = [&](Position::World chunk_pos, Position::BlockLocal pos, World::Chunk::BlockData& b) {
-        if (b.type == World::BlockType::Air) return;
+        if (!b.type.is_solid()) return;
         auto block_bounds = World::Chunk::block_bounds(pos).offset(chunk_pos);
         if (domain_box.collides(block_bounds)) colliding_blocks.push_back(block_bounds);
     };
@@ -82,6 +112,9 @@ std::vector<AABB> Player::terrain_collision_domain(
         chunk_from.chunk->for_each([&](auto p, auto b) { add_colliding(position, p, b); });
     }
 
+    if (World::ChunkIndex::from_position(to) == World::ChunkIndex::from_position(from))
+        return colliding_blocks;
+
     auto chunk_to = world.chunks().find(to);
     if (chunk_to.chunk.has_value()) {
         auto position = chunk_to.chunk.value().position();
@@ -91,6 +124,14 @@ std::vector<AABB> Player::terrain_collision_domain(
     return colliding_blocks;
 }
 
+void Player::update_camera_position(GFX::Camera& camera) {
+    auto camera_position = m_transform.position();
+    camera_position.y() += 1.5;
+
+    camera.set_position(camera_position);
+    camera.set_angles(m_transform.rotation());
+}
+
 AABB Player::bounding_box_for_position(Position::World position) {
     Vec3 box_start = {
         position.x() - s_bounds.max.x() / 2,
@@ -106,10 +147,4 @@ Position::World Player::position_for_bounding_box(AABB box) {
     return {center.x(), box.min.y(), center.z()};
 }
 
-Position::World Player::collision_reposition(Position::World from, Position::World to, AABB colliding) {
-    if (from == to) return from;
-    auto resulting_bounding_box = bounding_box_for_position(from).collision_response(to - from, colliding);
-    return position_for_bounding_box(resulting_bounding_box); // Ugly, we convert to AABB and back.
-}
-
 }
diff --git a/src/Entities/Player.hpp b/src/Entities/Player.hpp
index 3ae10ff..95e3d64 100644
--- a/src/Entities/Player.hpp
+++ b/src/Entities/Player.hpp
@@ -1,6 +1,5 @@
 #pragma once
 
-#include "../Common/FlexArray.hpp"
 #include "../Time.hpp"
 #include "../Transform.hpp"
 #include "../GFX/Camera.hpp"
@@ -11,7 +10,6 @@
 #include "../World/Position.hpp"
 
 namespace MC::Entities {
-
 class Player {
 public:
     explicit Player(Position::World position) : m_transform(position) {}
@@ -25,21 +23,19 @@ public:
     void rotate_to(Rotation to);
 
     AABB bounds() const;
-private:
-    void update_camera_position(GFX::Camera& camera);
 
-    static constexpr UInt MaxCollidingTerrain = 34;
+private:
+    static Position::World process_collisions(World::World& world, Position::World from, Position::World to);
     static std::vector<AABB> terrain_collision_domain(Position::World from, Position::World to, World::World& world);
 
+    void update_camera_position(GFX::Camera& camera);
+
     // Creates a bounding box where `position` is at the center of the bottom face.
     static AABB bounding_box_for_position(Position::World position);
     // Returns position of the center of the bottom face of `box`.
     static Position::World position_for_bounding_box(AABB box);
 
-    static Position::World collision_reposition(Position::World from, Position::World to, AABB colliding);
-
     Transform m_transform;
-
     static inline AABB s_bounds{{0.35, 1.8, 0.35}};
 };
 
diff --git a/src/Math/AABB.cpp b/src/Math/AABB.cpp
index ea48f71..08c9903 100644
--- a/src/Math/AABB.cpp
+++ b/src/Math/AABB.cpp
@@ -3,10 +3,10 @@
 #include "AABB.hpp"
 #include "Ray.hpp"
 
-// Returns new AABB after colliding with `against`.
+// Returns a pushout vector for avoiding collision with `against`.
 // Algorithm is kind of based on "https://www.gamedev.net/tutorials/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084/",
 // but very different (and mine's better :3).
-AABB AABB::collision_response(Vector<3> v, AABB against) const {
+Vec3 AABB::pushout(Vector<3> v, AABB against) const {
     auto origin = center();
     Ray ray{origin, v};
 
@@ -14,7 +14,7 @@ AABB AABB::collision_response(Vector<3> v, AABB against) const {
 
     auto expanded_target = against.sum(*this);
     auto raycast = ray.cast(expanded_target, v_magnitude);
-    if (!raycast.hit) return offset(v);
+    if (!raycast.hit) return {};
 
     // Slide along the collision plane.
 
@@ -25,6 +25,6 @@ AABB AABB::collision_response(Vector<3> v, AABB against) const {
     // Project the remaining velocity onto the plane, to which the normal is perpendicular.
     auto projected_velocity = v_remaining - v_remaining.project_onto(raycast.normal);
 
-    auto result = raycast.point + projected_velocity;
-    return from_center(result, size());
+    auto resulting_point = raycast.point + projected_velocity;
+    return resulting_point - (v + origin);
 }
diff --git a/src/Math/AABB.hpp b/src/Math/AABB.hpp
index 53ce6d2..4ad5534 100644
--- a/src/Math/AABB.hpp
+++ b/src/Math/AABB.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <array>
+#include <vector>
 #include "Vector.hpp"
 #include "../Common/Lambda.hpp"
 
@@ -41,6 +42,13 @@ struct AABB {
         return intersects_on_x(other) && intersects_on_y(other) && intersects_on_z(other);
     }
 
+    Bool collides(std::vector<AABB> others) {
+        for (auto& other : others) {
+            if (collides(other)) return true;
+        }
+        return false;
+    }
+
     std::array<Vector<3>, 8> corners() const {
         return {{
             {min.x(), min.y(), min.z()},
@@ -68,7 +76,7 @@ struct AABB {
         };
     }
 
-    AABB collision_response(Vector<3> v, AABB against) const;
+    Vec3 pushout(Vector<3> v, AABB against) const;
 
     Vector<3> min, max;
 };
diff --git a/src/Math/Ray.hpp b/src/Math/Ray.hpp
index c2c2274..db37ac2 100644
--- a/src/Math/Ray.hpp
+++ b/src/Math/Ray.hpp
@@ -36,9 +36,12 @@ struct Ray {
         // by the ray at the biggest smaller `t` value.
         // Since a plane always has two normals, we know which one to pick by looking
         // at the direction of the ray.
-        hit.normal = smaller_t_values.zip(direction, [=](Real t, Real d) {
-            return Math::floats_equal(t, biggest_min_t) ? Math::sign(d) : 0;
-        });
+        for (U8 a = 0; a < 3; a++) {
+            if (Math::floats_equal(smaller_t_values[a], biggest_min_t)) {
+                hit.normal[a] = Math::sign(direction[a]);
+                break;
+            }
+        }
 
         // If the smallest `t` is negative, the ray is pointing away from the AABB.
         // If the biggest `t` is smaller than the smallest `t`, the ray is missing the AABB,
diff --git a/src/Math/Vector.hpp b/src/Math/Vector.hpp
index acbfa98..7d07d5c 100644
--- a/src/Math/Vector.hpp
+++ b/src/Math/Vector.hpp
@@ -68,8 +68,12 @@ struct Vector {
         return reduce([](auto x, auto y) { return x + y; });
     }
 
+    T magnitude_squared() const {
+        return map([](auto x) { return x * x;}).sum();
+    }
+
     T magnitude() const {
-        return sqrt(map([](auto x) { return x * x;}).sum());
+        return sqrt(magnitude_squared());
     }
 
     Vector normalize() const {
@@ -81,6 +85,10 @@ struct Vector {
         return (*this - other).magnitude();
     }
 
+    T distance_squared(const Vector other) const {
+        return (*this - other).magnitude_squared();
+    }
+
     Vector<3, T> any_orthogonal() {
         if (Vector a{y(), -x(), 0.0f}; a != zero()) return a;
         if (Vector b{z(), 0.0f, -x()}; b != zero()) return b;
diff --git a/src/World/BlockType.hpp b/src/World/BlockType.hpp
index 2a9a652..cfac43b 100644
--- a/src/World/BlockType.hpp
+++ b/src/World/BlockType.hpp
@@ -26,6 +26,16 @@ public:
 
     operator Value() const { return m_block; }
 
+    Bool is_solid() const {
+	switch (m_block) {
+	case Air:
+	case Water:
+	    return false;
+	default:
+	    return true;
+	}
+    }
+
     Bool is_translucent() const { return opacity() != 1.0; }
 
     Real opacity() const {
@@ -58,4 +68,4 @@ private:
     Value m_block;
 };
 
-}
\ No newline at end of file
+}
diff --git a/src/World/ChunkIndex.hpp b/src/World/ChunkIndex.hpp
index bc61f3d..da23e3d 100644
--- a/src/World/ChunkIndex.hpp
+++ b/src/World/ChunkIndex.hpp
@@ -31,6 +31,14 @@ struct ChunkIndex {
         return {chunk_x, chunk_y};
     }
 
+    static ChunkIndex from_position(Position::World pos) {
+        return from_position(pos.round_to_block());
+    }
+
+    Bool operator==(const ChunkIndex& other) const {
+        return x == other.x && y == other.y;
+    }
+
     I32 x, y;
 };