src/world/world.cpp

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