From 1cc08c51eb4b0f95c30c0a98ad1fc5ad3459b2df Mon Sep 17 00:00:00 2001 From: Nicolas James Date: Wed, 12 Feb 2025 18:05:18 +1100 Subject: initial commit --- src/shared/movement.cc | 490 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 490 insertions(+) create mode 100644 src/shared/movement.cc (limited to 'src/shared/movement.cc') diff --git a/src/shared/movement.cc b/src/shared/movement.cc new file mode 100644 index 0000000..985062c --- /dev/null +++ b/src/shared/movement.cc @@ -0,0 +1,490 @@ +#include "shared/movement.hh" + +namespace shared { +namespace movement { + +// Move a player into the correct neighbour chunk if they go over a border. +static void shift_chunk(shared::player& player) noexcept { + const bool g_x = (player.local_pos.x >= shared::world::chunk::WIDTH); + const bool l_x = (player.local_pos.x < 0.0f); + const bool g_z = (player.local_pos.z >= shared::world::chunk::WIDTH); + const bool l_z = (player.local_pos.z < 0.0f); + + player.chunk_pos.x += g_x - l_x; + player.local_pos.x += shared::world::chunk::WIDTH * (l_x - g_x); + player.chunk_pos.z += g_z - l_z; + player.local_pos.z += shared::world::chunk::WIDTH * (l_z - g_z); +} + +constexpr float epsilon = 0.001f; // counteract arithmetic errors +constexpr float epsilon2 = epsilon + 2 * epsilon * epsilon; + +bool intersect_aabbs(const aabb& a, const aabb& b) noexcept { + if (a.max.x < b.min.x || a.min.x > b.max.x) { + return false; + } + if (a.max.y < b.min.y || a.min.y > b.max.y) { + return false; + } + if (a.max.z < b.min.z || a.min.z > b.max.z) { + return false; + } + return true; +} + +static glm::vec3 plane_to_normal(const int plane) { + glm::vec3 normal{0.0f, 0.0f, 0.0f}; + normal[std::abs(plane) - 1] = std::signbit(plane) ? -1.0f : 1.0f; + return normal; +} + +std::optional intersect_ray_aabb(const line& line, + const aabb& aabb) noexcept { + float tmin = -std::numeric_limits::max(); + float tmax = std::numeric_limits::max(); + + int p = 0; + for (int i = 0; i < 3; ++i) { + if (std::abs(line.dir[i]) < epsilon) { + + // Ray is parallel to slab, no hit if origin not within slab. + if (line.origin[i] < aabb.min[i] || line.origin[i] > aabb.max[i]) { + return std::nullopt; + } + + } else { + // Intersection t value of ray with near and far plane of slab. + const float ood = 1.0f / line.dir[i]; + float t1 = (aabb.min[i] - line.origin[i]) * ood; + float t2 = (aabb.max[i] - line.origin[i]) * ood; + + if (t1 > t2) { + std::swap(t1, t2); + } + auto old = tmin; + tmin = std::max(tmin, t1); + if (tmin != old) { + p = (i + 1); + } + tmax = std::min(tmax, t2); + if (tmin > tmax) { + return std::nullopt; + } + } + } + + if (tmin <= 0.0f) { + return std::nullopt; + } + + return ray_aabb_ret{.position = line.origin + line.dir * tmin, + .time = tmin, + .normal = plane_to_normal(p)}; +} + +std::optional +intersect_moving_aabbs(const moving_aabb& a, const moving_aabb& b) noexcept { + + if (intersect_aabbs(a.aabb, b.aabb)) { + return std::nullopt; + } + + const glm::vec3 velocity = b.velocity - a.velocity; + float tfirst = 0.0f; + float tlast = 10.0f; + int p = 0; + + for (int i = 0; i < 3; ++i) { + if (velocity[i] < 0.0f) { + if (b.aabb.max[i] < a.aabb.min[i]) { + return std::nullopt; + } + if (a.aabb.max[i] < b.aabb.min[i]) { + const auto old = tfirst; + tfirst = std::max((a.aabb.max[i] - b.aabb.min[i]) / velocity[i], + tfirst); + if (tfirst != old) { + p = (i + 1); + } + } + if (b.aabb.max[i] > a.aabb.min[i]) { + tlast = std::min((a.aabb.min[i] - b.aabb.max[i]) / velocity[i], + tlast); + } + } else if (velocity[i] > 0.0f) { + if (b.aabb.min[i] > a.aabb.max[i]) { + return std::nullopt; + } + if (b.aabb.max[i] < a.aabb.min[i]) { + const auto old = tfirst; + tfirst = std::max((a.aabb.min[i] - b.aabb.max[i]) / velocity[i], + tfirst); + if (tfirst != old) { + p = -(i + 1); + } + } + if (a.aabb.max[i] > b.aabb.min[i]) { + tlast = std::min((a.aabb.max[i] - b.aabb.min[i]) / velocity[i], + tlast); + } + } else { + if (b.aabb.max[i] < a.aabb.min[i] || + b.aabb.min[i] > a.aabb.max[i]) { + return std::nullopt; + } + } + if (tfirst > tlast) { + return std::nullopt; + } + } + /* + if (tfirst < 0.0f || tfirst > 1.0f) { + return std::nullopt; + } + */ + + return moving_aabb_ret{.time = tfirst, .normal = plane_to_normal(p)}; +} + +static std::optional +get_ground(const aabb& player_aabb, const std::vector blockinfos, + bool (*delimit)(const enum shared::world::block::type) = + shared::world::block::is_tangible) noexcept { + + const moving_aabb player_moving_aabb{.aabb = player_aabb, + .velocity = {0.0f, -1.0f, 0.0f}}; + for (const auto& block_aabb : blockinfos) { + + if (!delimit(block_aabb.block)) { + continue; + } + + const struct moving_aabb block_moving_aabb { + .aabb = block_aabb.aabb, .velocity = { 0.0f, 0.0f, 0.0f } + }; + + if (const auto intersect = + intersect_moving_aabbs(player_moving_aabb, block_moving_aabb); + intersect.has_value()) { + + if (intersect->time >= 1.0f) { + continue; + } + + if (intersect->time <= epsilon2) { + return block_aabb.block; + } + } + } + return std::nullopt; +} + +// Only returns ground if we can collide with it. +static std::optional +get_collidable_ground(const aabb& player_aabb, + const std::vector blockinfo) noexcept { + + return get_ground(player_aabb, blockinfo, + shared::world::block::is_collidable); +} + +// Recursively resolve collisions against blocks, up to n times. +static void resolve_collisions(shared::player& player, aabb player_aabb, + const std::vector& blockinfos, + const float deltatime, + const int n = 3) noexcept { + + const moving_aabb player_moving_aabb{ + .aabb = player_aabb, .velocity = player.velocity * deltatime}; + + std::optional> collision; + for (const auto& block_aabb : blockinfos) { + if (!shared::world::block::is_collidable(block_aabb.block)) { + continue; + } + + const struct moving_aabb block_moving_aabb { + .aabb = block_aabb.aabb, .velocity = { 0.0f, 0.0f, 0.0f } + }; + const auto intersect = + intersect_moving_aabbs(player_moving_aabb, block_moving_aabb); + + if (!intersect.has_value() || intersect->time > 1.0f) { + continue; + } + + // Update collision if it doesn't exist or if this one is closer. + if (!collision.has_value() || intersect->time < collision->first.time) { + + collision = std::make_pair(intersect.value(), block_aabb.block); + } + } + + // No more collisions :) + if (!collision.has_value()) { + player.local_pos += player.velocity * deltatime; + return; + } + + const glm::vec3 collision_pos = + collision->first.time * player.velocity * deltatime; + const glm::vec3 offset = collision->first.normal * epsilon; + const float backoff = glm::dot(player.velocity, collision->first.normal); + +#ifndef NDEBUG + // clang-format off + shared::print::debug("Collision with n = " + std::to_string(n) + "\n"); + shared::print::message(" Unresolved player position: {" + std::to_string(player.local_pos.x) + ", " + std::to_string(player.local_pos.y) + ", " + std::to_string(player.local_pos.z) + "}\n", false); + shared::print::message(" Unresolved player velocity: {" + std::to_string(player.velocity.x) + ", " + std::to_string(player.velocity.y) + ", " + std::to_string(player.velocity.z) + "}\n", false); + shared::print::message(" Collision delta vector: {" + std::to_string(collision_pos.x) + ", " + std::to_string(collision_pos.y) + ", " + std::to_string(collision_pos.z) + "}\n", false); + shared::print::message(" Backoff: " + std::to_string(backoff) + "\n", false); + shared::print::message(" On ground before collision: " + std::to_string(get_collidable_ground(player_aabb, blockinfos).has_value()) + "\n", false); + shared::print::message(" Collision normal: {" + std::to_string(collision->first.normal.x) + ", " + std::to_string(collision->first.normal.y) + ", " + std::to_string(collision->first.normal.z) + "}\n", false); + // clang-format on +#endif + + // Quake engine's reflect velocity. + for (int i = 0; i < 3; ++i) { + player.velocity[i] -= collision->first.normal[i] * backoff; + if (std::abs(player.velocity[i]) <= epsilon) { + player.velocity[i] = 0.0f; + } + if (std::abs(collision_pos[i]) <= epsilon2) { + +#ifndef NDEBUG + shared::print::message( + " Ignored axis: " + std::to_string(i) + "\n", false); +#endif + + continue; + } + player.local_pos[i] += collision_pos[i] - offset[i]; + player_aabb.min[i] += collision_pos[i] - offset[i]; + player_aabb.max[i] += collision_pos[i] - offset[i]; + } + +#ifndef NDEBUG + // clang-format off + shared::print::message(" Resolved player position: {" + std::to_string(player.local_pos.x) + ", " + std::to_string(player.local_pos.y) + ", " + std::to_string(player.local_pos.z) + "}\n", false); + shared::print::message(" Resolved player velocity: {" + std::to_string(player.velocity.x) + ", " + std::to_string(player.velocity.y) + ", " + std::to_string(player.velocity.z) + "}\n", false); + shared::print::message(" On ground after collision: " + std::to_string(get_collidable_ground(player_aabb, blockinfos).has_value()) + "\n", false); + // clang-format on +#endif + + if (n <= 0) { + return; + } + resolve_collisions(player, player_aabb, blockinfos, + deltatime - collision->first.time * deltatime, n - 1); +} + +// Returns the highest friction value of a block that intersects an aabb. +static std::optional +get_intersect_friction(const aabb& aabb, + const std::vector& blockinfos) noexcept { + std::optional greatest_friction; + for (const auto& block_aabb : blockinfos) { + if (!intersect_aabbs(aabb, block_aabb.aabb)) { + continue; + } + const float friction = + shared::world::block::get_friction(block_aabb.block); + + if (!greatest_friction.has_value() || + friction > greatest_friction.value()) { + + greatest_friction = friction; + } + } + + return greatest_friction; +} + +// In air is slightly more complicated becase of edge cases involving water. +static bool is_in_air( + const aabb& aabb, const std::vector& blockinfos, + const std::optional& collidable_ground) noexcept { + if (!std::all_of(std::begin(blockinfos), std::end(blockinfos), + [&aabb](const auto& ba) { + if (!intersect_aabbs(aabb, ba.aabb)) { + return true; + } + return !shared::world::block::is_tangible(ba.block); + })) { + return false; + } + if (collidable_ground.has_value()) { + return false; + } + return true; +} + +static bool is_in_liquid(const aabb& aabb, + const std::vector& blockinfos) noexcept { + return std::any_of(std::begin(blockinfos), std::end(blockinfos), + [&aabb](const auto& ba) { + if (!intersect_aabbs(aabb, ba.aabb)) { + return false; + } + return shared::world::block::is_liquid(ba.block); + }); +} + +static bool +can_jump(const std::optional& collidable_ground, + const bool in_liquid) noexcept { + if (collidable_ground.has_value()) { + return true; + } + if (in_liquid) { + return true; + } + return false; +} + +// Move state is a cache of expensive operations that we use more than once. +struct move_state { + std::optional ground; + std::optional collidable_ground; + bool is_in_air; + bool is_in_liquid; + bool can_jump; +}; +static move_state +make_move_state(const aabb& player_aabb, + const std::vector& blockinfos) noexcept { + + const auto get_ground_ret = get_ground(player_aabb, blockinfos); + const auto get_collidable_ground_ret = + get_collidable_ground(player_aabb, blockinfos); + const bool is_in_air_ret = + is_in_air(player_aabb, blockinfos, get_collidable_ground_ret); + const bool is_in_liquid_ret = is_in_liquid(player_aabb, blockinfos); + const bool can_jump_ret = + can_jump(get_collidable_ground_ret, is_in_liquid_ret); + + return {.ground = get_ground_ret, + .collidable_ground = get_collidable_ground_ret, + .is_in_air = is_in_air_ret, + .is_in_liquid = is_in_liquid_ret, + .can_jump = can_jump_ret}; +} + +static float get_jump_magnitude(const shared::player& player, const aabb& aabb, + const std::vector& blockinfos, + const struct move_state& move_state) noexcept { + if (!move_state.can_jump) { + return 0.0f; + } + if (move_state.is_in_liquid) { + const struct aabb jump_aabb = { + .min = glm::vec3{0.0f, aabb.min.y + aabb.max.y / 5.0f, 0.0f}, + .max = aabb.max}; + if (player.velocity.y > 0.0f && + is_in_air(jump_aabb, blockinfos, + get_collidable_ground(jump_aabb, blockinfos))) { + return 1.0f; + } + return 0.5f; + } + if (player.velocity.y < 0.0f) { + return 0.0f; + } + return 8.0f; +} + +void move(shared::player& player, const std::vector& blockinfos, + const float deltatime) noexcept { + + constexpr glm::vec3 up = glm::vec3(0.0f, 1.0f, 0.0f); + const glm::vec3 front = shared::math::angle_to_dir(player.viewangles); + const glm::vec3 right = glm::normalize(glm::cross(front, up)); + + constexpr aabb player_aabb = {.min = {-shared::player::HALFWIDTH + epsilon, + 0.0f + epsilon, + -shared::player::HALFWIDTH + epsilon}, + .max = {shared::player::HALFWIDTH - epsilon, + shared::player::HEIGHT - epsilon, + shared::player::HALFWIDTH - epsilon}}; + + const auto move_state = make_move_state(player_aabb, blockinfos); + + // Some of velocity we want to add or remove should be scaled by our + // tickrate (eg, walking), while others such as jumping should not. + + const glm::vec3 scaled_acceleration = [&]() -> glm::vec3 { + glm::vec3 acceleration = {0.0f, 0.0f, 0.0f}; + if (player.commands & shared::player::mask::forward) { + acceleration += front; + } + if (player.commands & shared::player::mask::left) { + acceleration -= right; + } + if (player.commands & shared::player::mask::backward) { + acceleration -= front; + } + if (player.commands & shared::player::mask::right) { + acceleration += right; + } + acceleration.y = 0.0f; + if (acceleration != glm::vec3{}) { + acceleration = glm::normalize(acceleration); + } + acceleration *= 1.75f; + if (player.commands & shared::player::mask::sprint) { + acceleration *= 1.25f; + } + + // Increase movement when on the ground - heavily reduced with friction. + if (!move_state.is_in_air) { + acceleration *= 30.0f; + } + + // Gravity. + if (!move_state.collidable_ground.has_value()) { + acceleration -= 25.0f * up; + } + + return acceleration; + }(); + + const glm::vec3 constant_acceleration = [&]() -> glm::vec3 { + glm::vec3 acceleration = {0.0f, 0.0f, 0.0f}; + // Jumping - we have to adjust our magnitude based on our environment. + // Technically swimming is just lots of small jumps. + if (player.commands & shared::player::mask::jump) { + acceleration += get_jump_magnitude(player, player_aabb, blockinfos, + move_state) * + up; + } + return acceleration; + }(); + + // Our deceleration is the max friction of what we're in and what we're on. + const glm::vec3 scaled_deceleration = [&]() -> glm::vec3 { + const auto drag = get_intersect_friction(player_aabb, blockinfos); + + float max_friction = 0.0f; + if (move_state.collidable_ground.has_value()) { + const float friction = shared::world::block::get_friction( + move_state.collidable_ground.value()); + if (drag.has_value()) { + max_friction = std::max(friction, drag.value()); + } + } else if (drag.has_value()) { + max_friction = drag.value(); + } + + return player.velocity * max_friction; + }(); + + player.velocity += (scaled_acceleration - scaled_deceleration) * deltatime; + player.velocity += constant_acceleration; + + resolve_collisions(player, player_aabb, blockinfos, deltatime); + + shift_chunk(player); +} + +} // namespace movement +} // namespace shared -- cgit v1.2.3