src/world/world.cpp

   1 #include "Entity.hpp"
   2 #include "EntityController.hpp"
   3 #include "EntityDerivative.hpp"
   4 #include "EntityState.hpp"
   5 #include "Player.hpp"
   6 #include "World.hpp"
   7
   8 #include "ChunkIndex.hpp"
   9 #include "EntityCollision.hpp"
  10 #include "WorldCollision.hpp"
  11 #include "../app/Assets.hpp"
  12 #include "../graphics/Format.hpp"
  13 #include "../graphics/Viewport.hpp"
  14
  15 #include <algorithm>
  16 #include <cmath>
  17 #include <iostream>
  18 #include <limits>
  19 #include <glm/gtx/io.hpp>
  20 #include <glm/gtx/quaternion.hpp>
  21 #include <glm/gtx/transform.hpp>
  22
  23
  24 namespace blank {
  25
  26 Entity::Entity() noexcept
  27 : ctrl(nullptr)
  28 , model()
  29 , id(-1)
  30 , name("anonymous")
  31 , bounds()
  32 , state()
  33 , heading(0.0f, 0.0f, -1.0f)
  34 , max_vel(5.0f)
  35 , max_force(25.0f)
  36 , ref_count(0)
  37 , world_collision(false)
  38 , dead(false)
  39 , owns_controller(false) {
  40
  41 }
  42
  43 Entity::~Entity() noexcept {
  44         UnsetController();
  45 }
  46
  47 Entity::Entity(const Entity &other) noexcept
  48 : ctrl(other.ctrl)
  49 , model(other.model)
  50 , id(-1)
  51 , name(other.name)
  52 , bounds(other.bounds)
  53 , state(other.state)
  54 , max_vel(other.max_vel)
  55 , max_force(other.max_force)
  56 , ref_count(0)
  57 , world_collision(other.world_collision)
  58 , dead(other.dead)
  59 , owns_controller(false) {
  60
  61 }
  62
  63 void Entity::SetController(EntityController *c) noexcept {
  64         UnsetController();
  65         ctrl = c;
  66         owns_controller = true;
  67 }
  68
  69 void Entity::SetController(EntityController &c) noexcept {
  70         UnsetController();
  71         ctrl = &c;
  72         owns_controller = false;
  73 }
  74
  75 void Entity::UnsetController() noexcept {
  76         if (ctrl && owns_controller) {
  77                 delete ctrl;
  78         }
  79         ctrl = nullptr;
  80 }
  81
  82 glm::vec3 Entity::ControlForce(const EntityState &s) const noexcept {
  83         if (HasController()) {
  84                 return GetController().ControlForce(*this, s);
  85         } else {
  86                 return -s.velocity;
  87         }
  88 }
  89
  90 void Entity::Position(const glm::ivec3 &c, const glm::vec3 &b) noexcept {
  91         state.chunk_pos = c;
  92         state.block_pos = b;
  93 }
  94
  95 void Entity::Position(const glm::vec3 &pos) noexcept {
  96         state.block_pos = pos;
  97         state.AdjustPosition();
  98 }
  99
 100 void Entity::TurnHead(float dp, float dy) noexcept {
 101         SetHead(state.pitch + dp, state.yaw + dy);
 102 }
 103
 104 void Entity::SetHead(float p, float y) noexcept {
 105         state.pitch = p;
 106         state.yaw = y;
 107         // TODO: I feel like this could be delayed
 108         UpdateModel();
 109 }
 110
 111 glm::mat4 Entity::Transform(const glm::ivec3 &reference) const noexcept {
 112         return state.Transform(reference);
 113 }
 114
 115 glm::mat4 Entity::ViewTransform(const glm::ivec3 &reference) const noexcept {
 116         glm::mat4 transform = view_local;
 117         transform[3] += glm::vec4(state.RelativePosition(reference), 0.0f);
 118         return transform;
 119 }
 120
 121 Ray Entity::Aim(const Chunk::Pos &chunk_offset) const noexcept {
 122         glm::mat4 transform = ViewTransform(chunk_offset);
 123         return Ray{ glm::vec3(transform[3]), -glm::vec3(transform[2]) };
 124 }
 125
 126 void Entity::UpdateModel() noexcept {
 127         state.AdjustHeading();
 128         if (model) {
 129                 Part::State &body_state = model.BodyState();
 130                 Part::State &eyes_state = model.EyesState();
 131                 if (&body_state != &eyes_state) {
 132                         body_state.orientation = glm::quat(glm::vec3(0.0f, state.yaw, 0.0f));
 133                         eyes_state.orientation = glm::quat(glm::vec3(state.pitch, 0.0f, 0.0f));
 134                 } else {
 135                         eyes_state.orientation = glm::quat(glm::vec3(state.pitch, state.yaw, 0.0f));
 136                 }
 137         }
 138 }
 139
 140 void Entity::Update(float dt) {
 141         UpdateView();
 142         UpdateHeading();
 143         if (HasController()) {
 144                 GetController().Update(*this, dt);
 145         }
 146 }
 147
 148 void Entity::UpdateView() noexcept {
 149         // create local transform
 150         view_local = Transform(ChunkCoords());
 151         // clear the translation part
 152         view_local[3] = glm::vec4(0.0f, 0.0f, 0.0f, 1.0f);
 153         // add the model's eyes translation, if any
 154         if (model) {
 155                 view_local *= model.EyesTransform();
 156         }
 157 }
 158
 159 void Entity::UpdateHeading() noexcept {
 160         speed = length(Velocity());
 161         if (speed > std::numeric_limits<float>::epsilon()) {
 162                 heading = Velocity() / speed;
 163         } else {
 164                 speed = 0.0f;
 165                 // use -Z (forward axis) of local view transform
 166                 heading = -glm::vec3(view_local[2]);
 167         }
 168 }
 169
 170
 171 EntityController::~EntityController() {
 172
 173 }
 174
 175 bool EntityController::MaxOutForce(
 176         glm::vec3 &out,
 177         const glm::vec3 &add,
 178         float max
 179 ) noexcept {
 180         if (iszero(add) || any(isnan(add))) {
 181                 return false;
 182         }
 183         float current = iszero(out) ? 0.0f : length(out);
 184         float remain = max - current;
 185         if (remain <= 0.0f) {
 186                 return true;
 187         }
 188         float additional = length(add);
 189         if (additional > remain) {
 190                 out += normalize(add) * remain;
 191                 return true;
 192         } else {
 193                 out += add;
 194                 return false;
 195         }
 196 }
 197
 198
 199 EntityState::EntityState()
 200 : chunk_pos(0)
 201 , block_pos(0.0f)
 202 , velocity(0.0f)
 203 , orient(1.0f, 0.0f, 0.0f, 0.0f)
 204 , pitch(0.0f)
 205 , yaw(0.0f) {
 206
 207 }
 208
 209 void EntityState::AdjustPosition() noexcept {
 210         while (block_pos.x >= Chunk::width) {
 211                 block_pos.x -= Chunk::width;
 212                 ++chunk_pos.x;
 213         }
 214         while (block_pos.x < 0) {
 215                 block_pos.x += Chunk::width;
 216                 --chunk_pos.x;
 217         }
 218         while (block_pos.y >= Chunk::height) {
 219                 block_pos.y -= Chunk::height;
 220                 ++chunk_pos.y;
 221         }
 222         while (block_pos.y < 0) {
 223                 block_pos.y += Chunk::height;
 224                 --chunk_pos.y;
 225         }
 226         while (block_pos.z >= Chunk::depth) {
 227                 block_pos.z -= Chunk::depth;
 228                 ++chunk_pos.z;
 229         }
 230         while (block_pos.z < 0) {
 231                 block_pos.z += Chunk::depth;
 232                 --chunk_pos.z;
 233         }
 234 }
 235
 236 void EntityState::AdjustHeading() noexcept {
 237         glm::clamp(pitch, -PI_0p5, PI_0p5);
 238         while (yaw > PI) {
 239                 yaw -= PI_2p0;
 240         }
 241         while (yaw < -PI) {
 242                 yaw += PI_2p0;
 243         }
 244 }
 245
 246 glm::mat4 EntityState::Transform(const glm::ivec3 &reference) const noexcept {
 247         const glm::vec3 translation = RelativePosition(reference);
 248         glm::mat4 transform(toMat4(orient));
 249         transform[3] = glm::vec4(translation, 1.0f);
 250         return transform;
 251 }
 252
 253
 254 Player::Player(Entity &e, ChunkIndex &c)
 255 : entity(e)
 256 , chunks(c)
 257 , inv_slot(0) {
 258
 259 }
 260
 261 Player::~Player() {
 262
 263 }
 264
 265 bool Player::SuitableSpawn(BlockLookup &spawn_block) const noexcept {
 266         if (!spawn_block || spawn_block.GetType().collide_block) {
 267                 return false;
 268         }
 269
 270         BlockLookup head_block(spawn_block.Next(Block::FACE_UP));
 271         if (!head_block || head_block.GetType().collide_block) {
 272                 return false;
 273         }
 274
 275         return true;
 276 }
 277
 278 void Player::Update(int dt) {
 279         chunks.Rebase(entity.ChunkCoords());
 280 }
 281
 282
 283 World::World(const BlockTypeRegistry &types, const Config &config)
 284 : config(config)
 285 , block_type(types)
 286 , chunks(types)
 287 , players()
 288 , entities()
 289 , light_direction(config.light_direction)
 290 , fog_density(config.fog_density) {
 291
 292 }
 293
 294 World::~World() {
 295
 296 }
 297
 298
 299 Player *World::AddPlayer(const std::string &name) {
 300         for (Player &p : players) {
 301                 if (p.Name() == name) {
 302                         return nullptr;
 303                 }
 304         }
 305         Entity &entity = AddEntity();
 306         entity.Name(name);
 307         entity.Bounds({ { -0.4f, -0.9f, -0.4f }, { 0.4f, 0.9f, 0.4f } });
 308         entity.WorldCollidable(true);
 309         ChunkIndex &index = chunks.MakeIndex(entity.ChunkCoords(), 6);
 310         players.emplace_back(entity, index);
 311         return &players.back();
 312 }
 313
 314 Player *World::AddPlayer(const std::string &name, std::uint32_t id) {
 315         for (Player &p : players) {
 316                 if (p.Name() == name) {
 317                         return nullptr;
 318                 }
 319         }
 320         Entity *entity = AddEntity(id);
 321         if (!entity) {
 322                 return nullptr;
 323         }
 324         entity->Name(name);
 325         entity->Bounds({ { -0.4f, -0.9f, -0.4f }, { 0.4f, 0.9f, 0.4f } });
 326         entity->WorldCollidable(true);
 327         ChunkIndex &index = chunks.MakeIndex(entity->ChunkCoords(), 6);
 328         players.emplace_back(*entity, index);
 329         return &players.back();
 330 }
 331
 332 Entity &World::AddEntity() {
 333         if (entities.empty()) {
 334                 entities.emplace_back();
 335                 entities.back().ID(1);
 336                 return entities.back();
 337         }
 338         if (entities.back().ID() < std::numeric_limits<std::uint32_t>::max()) {
 339                 std::uint32_t id = entities.back().ID() + 1;
 340                 entities.emplace_back();
 341                 entities.back().ID(id);
 342                 return entities.back();
 343         }
 344         std::uint32_t id = 1;
 345         auto position = entities.begin();
 346         auto end = entities.end();
 347         while (position != end && position->ID() == id) {
 348                 ++id;
 349                 ++position;
 350         }
 351         auto entity = entities.emplace(position);
 352         entity->ID(id);
 353         return *entity;
 354 }
 355
 356 Entity *World::AddEntity(std::uint32_t id) {
 357         if (entities.empty() || entities.back().ID() < id) {
 358                 entities.emplace_back();
 359                 entities.back().ID(id);
 360                 return &entities.back();
 361         }
 362
 363         auto position = entities.begin();
 364         auto end = entities.end();
 365         while (position != end && position->ID() < id) {
 366                 ++position;
 367         }
 368         if (position != end && position->ID() == id) {
 369                 return nullptr;
 370         }
 371         auto entity = entities.emplace(position);
 372         entity->ID(id);
 373         return &*entity;
 374 }
 375
 376 Entity &World::ForceAddEntity(std::uint32_t id) {
 377         if (entities.empty() || entities.back().ID() < id) {
 378                 entities.emplace_back();
 379                 entities.back().ID(id);
 380                 return entities.back();
 381         }
 382
 383         auto position = entities.begin();
 384         auto end = entities.end();
 385         while (position != end && position->ID() < id) {
 386                 ++position;
 387         }
 388         if (position != end && position->ID() == id) {
 389                 return *position;
 390         }
 391         auto entity = entities.emplace(position);
 392         entity->ID(id);
 393         return *entity;
 394 }
 395
 396
 397 namespace {
 398
 399 struct Candidate {
 400         Chunk *chunk;
 401         float dist;
 402 };
 403
 404 bool CandidateLess(const Candidate &a, const Candidate &b) {
 405         return a.dist < b.dist;
 406 }
 407
 408 std::vector<Candidate> candidates;
 409
 410 }
 411
 412 bool World::Intersection(
 413         const Ray &ray,
 414         const glm::mat4 &M,
 415         const Chunk::Pos &reference,
 416         WorldCollision &coll
 417 ) {
 418         candidates.clear();
 419
 420         for (Chunk &cur_chunk : chunks) {
 421                 float cur_dist;
 422                 if (cur_chunk.Intersection(ray, M * cur_chunk.Transform(reference), cur_dist)) {
 423                         candidates.push_back({ &cur_chunk, cur_dist });
 424                 }
 425         }
 426
 427         if (candidates.empty()) return false;
 428
 429         std::sort(candidates.begin(), candidates.end(), CandidateLess);
 430
 431         coll.chunk = nullptr;
 432         coll.block = -1;
 433         coll.depth = std::numeric_limits<float>::infinity();
 434
 435         for (Candidate &cand : candidates) {
 436                 if (cand.dist > coll.depth) continue;
 437                 WorldCollision cur_coll;
 438                 if (cand.chunk->Intersection(ray, M * cand.chunk->Transform(reference), cur_coll)) {
 439                         if (cur_coll.depth < coll.depth) {
 440                                 coll = cur_coll;
 441                         }
 442                 }
 443         }
 444
 445         return coll.chunk;
 446 }
 447
 448 bool World::Intersection(
 449         const Ray &ray,
 450         const glm::mat4 &M,
 451         const Entity &reference,
 452         EntityCollision &coll
 453 ) {
 454         coll.entity = nullptr;
 455         coll.depth = std::numeric_limits<float>::infinity();
 456         for (Entity &cur_entity : entities) {
 457                 if (&cur_entity == &reference) {
 458                         continue;
 459                 }
 460                 float cur_dist;
 461                 glm::vec3 cur_normal;
 462                 if (blank::Intersection(ray, cur_entity.Bounds(), M * cur_entity.Transform(reference.ChunkCoords()), &cur_dist, &cur_normal)) {
 463                         // TODO: fine grained check goes here? maybe?
 464                         if (cur_dist < coll.depth) {
 465                                 coll.entity = &cur_entity;
 466                                 coll.depth = cur_dist;
 467                                 coll.normal = cur_normal;
 468                         }
 469                 }
 470         }
 471
 472         return coll.entity;
 473 }
 474
 475 bool World::Intersection(const Entity &e, const EntityState &s, std::vector<WorldCollision> &col) {
 476         AABB box = e.Bounds();
 477         Chunk::Pos reference = s.chunk_pos;
 478         glm::mat4 M = s.Transform(reference);
 479         return Intersection(box, M, reference, col);
 480 }
 481
 482 bool World::Intersection(
 483         const AABB &box,
 484         const glm::mat4 &M,
 485         const glm::ivec3 &reference,
 486         std::vector<WorldCollision> &col
 487 ) {
 488         bool any = false;
 489         for (Chunk &cur_chunk : chunks) {
 490                 if (manhattan_radius(cur_chunk.Position() - reference) > 1) {
 491                         // chunk is not one of the 3x3x3 surrounding the entity
 492                         // since there's no entity which can extent over 16 blocks, they can be skipped
 493                         continue;
 494                 }
 495                 if (cur_chunk.Intersection(box, M, cur_chunk.Transform(reference), col)) {
 496                         any = true;
 497                 }
 498         }
 499         return any;
 500 }
 501
 502 void World::Update(int dt) {
 503         float fdt(dt * 0.001f);
 504         for (Entity &entity : entities) {
 505                 entity.Update(fdt);
 506         }
 507         for (Entity &entity : entities) {
 508                 Update(entity, fdt);
 509         }
 510         for (Player &player : players) {
 511                 player.Update(dt);
 512         }
 513         for (auto iter = entities.begin(), end = entities.end(); iter != end;) {
 514                 if (iter->CanRemove()) {
 515                         iter = RemoveEntity(iter);
 516                 } else {
 517                         ++iter;
 518                 }
 519         }
 520 }
 521
 522 void World::Update(Entity &entity, float dt) {
 523         EntityState state(entity.GetState());
 524
 525         EntityDerivative a(CalculateStep(entity, state, 0.0f, EntityDerivative()));
 526         EntityDerivative b(CalculateStep(entity, state, dt * 0.5f, a));
 527         EntityDerivative c(CalculateStep(entity, state, dt * 0.5f, b));
 528         EntityDerivative d(CalculateStep(entity, state, dt, c));
 529
 530         EntityDerivative f;
 531         constexpr float sixth = 1.0f / 6.0f;
 532         f.position = sixth * ((a.position + 2.0f * (b.position + c.position)) + d.position);
 533         f.velocity = sixth * ((a.velocity + 2.0f * (b.velocity + c.velocity)) + d.velocity);
 534
 535         state.block_pos += f.position * dt;
 536         state.velocity += f.velocity * dt;
 537         state.AdjustPosition();
 538
 539         entity.SetState(state);
 540 }
 541
 542 EntityDerivative World::CalculateStep(
 543         const Entity &entity,
 544         const EntityState &cur,
 545         float dt,
 546         const EntityDerivative &delta
 547 ) {
 548         EntityState next(cur);
 549         next.block_pos += delta.position * dt;
 550         next.velocity += delta.velocity * dt;
 551         next.AdjustPosition();
 552
 553         if (dot(next.velocity, next.velocity) > entity.MaxVelocity() * entity.MaxVelocity()) {
 554                 next.velocity = normalize(next.velocity) * entity.MaxVelocity();
 555         }
 556
 557         EntityDerivative out;
 558         out.position = next.velocity;
 559         out.velocity = CalculateForce(entity, next); // by mass = 1kg
 560         return out;
 561 }
 562
 563 glm::vec3 World::CalculateForce(
 564         const Entity &entity,
 565         const EntityState &state
 566 ) {
 567         glm::vec3 force(ControlForce(entity, state) + CollisionForce(entity, state) + Gravity(entity, state));
 568         if (dot(force, force) > entity.MaxControlForce() * entity.MaxControlForce()) {
 569                 return normalize(force) * entity.MaxControlForce();
 570         } else {
 571                 return force;
 572         }
 573 }
 574
 575 glm::vec3 World::ControlForce(
 576         const Entity &entity,
 577         const EntityState &state
 578 ) {
 579         return entity.ControlForce(state);
 580 }
 581
 582 namespace {
 583
 584 std::vector<WorldCollision> col;
 585
 586 }
 587
 588 glm::vec3 World::CollisionForce(
 589         const Entity &entity,
 590         const EntityState &state
 591 ) {
 592         col.clear();
 593         if (entity.WorldCollidable() && Intersection(entity, state, col)) {
 594                 // determine displacement for each cardinal axis and move entity accordingly
 595                 glm::vec3 min_pen(0.0f);
 596                 glm::vec3 max_pen(0.0f);
 597                 for (const WorldCollision &c : col) {
 598                         if (!c.Blocks()) continue;
 599                         glm::vec3 local_pen(c.normal * c.depth);
 600                         // swap if neccessary (normal may point away from the entity)
 601                         if (dot(c.normal, state.RelativePosition(c.ChunkPos()) - c.BlockCoords()) > 0) {
 602                                 local_pen *= -1;
 603                         }
 604                         min_pen = min(min_pen, local_pen);
 605                         max_pen = max(max_pen, local_pen);
 606                 }
 607                 glm::vec3 correction(0.0f);
 608                 // only apply correction for axes where penetration is only in one direction
 609                 for (std::size_t i = 0; i < 3; ++i) {
 610                         if (min_pen[i] < -std::numeric_limits<float>::epsilon()) {
 611                                 if (max_pen[i] < std::numeric_limits<float>::epsilon()) {
 612                                         correction[i] = -min_pen[i];
 613                                 }
 614                         } else {
 615                                 correction[i] = -max_pen[i];
 616                         }
 617                 }
 618                 // correction may be zero in which case normalize() returns NaNs
 619                 if (dot(correction, correction) < std::numeric_limits<float>::epsilon()) {
 620                         return glm::vec3(0.0f);
 621                 }
 622                 glm::vec3 normal(normalize(correction));
 623                 glm::vec3 normal_velocity(normal * dot(state.velocity, normal));
 624                 // apply force proportional to penetration
 625                 // use velocity projected onto normal as damper
 626                 constexpr float k = 1000.0f; // spring constant
 627                 constexpr float b = 10.0f; // damper constant
 628                 const glm::vec3 x(-correction); // endpoint displacement from equilibrium in m
 629                 const glm::vec3 v(normal_velocity); // relative velocity between endpoints in m/s
 630                 return (((-k) * x) - (b * v)); // times 1kg/s, in kg*m/s²
 631         } else {
 632                 return glm::vec3(0.0f);
 633         }
 634 }
 635
 636 glm::vec3 World::Gravity(
 637         const Entity &entity,
 638         const EntityState &state
 639 ) {
 640         return glm::vec3(0.0f);
 641 }
 642
 643 World::EntityHandle World::RemoveEntity(EntityHandle &eh) {
 644         // check for player
 645         for (auto player = players.begin(), end = players.end(); player != end;) {
 646                 if (&player->GetEntity() == &*eh) {
 647                         chunks.UnregisterIndex(player->GetChunks());
 648                         player = players.erase(player);
 649                         end = players.end();
 650                 } else {
 651                         ++player;
 652                 }
 653         }
 654         return entities.erase(eh);
 655 }
 656
 657
 658 void World::Render(Viewport &viewport) {
 659         DirectionalLighting &entity_prog = viewport.EntityProgram();
 660         entity_prog.SetLightDirection(light_direction);
 661         entity_prog.SetFogDensity(fog_density);
 662
 663         for (Entity &entity : entities) {
 664                 entity.Render(entity.Transform(players.front().GetEntity().ChunkCoords()), entity_prog);
 665         }
 666 }
 667
 668 }