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