src/world/world.cpp

   1 #include "Entity.hpp"
   2 #include "EntityCollision.hpp"
   3 #include "EntityController.hpp"
   4 #include "EntityDerivative.hpp"
   5 #include "EntityState.hpp"
   6 #include "Player.hpp"
   7 #include "World.hpp"
   8
   9 #include "ChunkIndex.hpp"
  10 #include "EntityCollision.hpp"
  11 #include "WorldCollision.hpp"
  12 #include "../app/Assets.hpp"
  13 #include "../geometry/const.hpp"
  14 #include "../geometry/distance.hpp"
  15 #include "../geometry/rotation.hpp"
  16 #include "../graphics/Format.hpp"
  17 #include "../graphics/Viewport.hpp"
  18
  19 #include <algorithm>
  20 #include <cmath>
  21 #include <iostream>
  22 #include <limits>
  23 #include <glm/gtx/euler_angles.hpp>
  24 #include <glm/gtx/io.hpp>
  25 #include <glm/gtx/projection.hpp>
  26 #include <glm/gtx/quaternion.hpp>
  27 #include <glm/gtx/rotate_vector.hpp>
  28 #include <glm/gtx/transform.hpp>
  29
  30
  31 namespace blank {
  32
  33 namespace {
  34
  35 /// used as a buffer for merging collisions
  36 std::vector<WorldCollision> col;
  37
  38 }
  39
  40 Entity::Entity() noexcept
  41 : steering(*this)
  42 , ctrl(nullptr)
  43 , model()
  44 , id(-1)
  45 , name("anonymous")
  46 , bounds()
  47 , radius(0.0f)
  48 , state()
  49 , heading(0.0f, 0.0f, -1.0f)
  50 , max_vel(5.0f)
  51 , max_force(25.0f)
  52 , ref_count(0)
  53 , world_collision(false)
  54 , dead(false)
  55 , owns_controller(false) {
  56
  57 }
  58
  59 Entity::~Entity() noexcept {
  60         UnsetController();
  61 }
  62
  63 Entity::Entity(const Entity &other) noexcept
  64 : steering(*this)
  65 , ctrl(other.ctrl)
  66 , model(other.model)
  67 , id(-1)
  68 , name(other.name)
  69 , bounds(other.bounds)
  70 , state(other.state)
  71 , model_transform(1.0f)
  72 , view_transform(1.0f)
  73 , speed(0.0f)
  74 , heading(0.0f, 0.0f, -1.0f)
  75 , max_vel(other.max_vel)
  76 , max_force(other.max_force)
  77 , ref_count(0)
  78 , world_collision(other.world_collision)
  79 , dead(other.dead)
  80 , owns_controller(false) {
  81
  82 }
  83
  84 void Entity::SetController(EntityController *c) noexcept {
  85         UnsetController();
  86         ctrl = c;
  87         owns_controller = true;
  88 }
  89
  90 void Entity::SetController(EntityController &c) noexcept {
  91         UnsetController();
  92         ctrl = &c;
  93         owns_controller = false;
  94 }
  95
  96 void Entity::UnsetController() noexcept {
  97         if (ctrl && owns_controller) {
  98                 delete ctrl;
  99         }
 100         ctrl = nullptr;
 101 }
 102
 103 glm::vec3 Entity::ControlForce(const EntityState &s) const noexcept {
 104         return steering.Force(s);
 105 }
 106
 107 void Entity::Position(const glm::ivec3 &c, const glm::vec3 &b) noexcept {
 108         state.pos.chunk = c;
 109         state.pos.block = b;
 110 }
 111
 112 void Entity::Position(const glm::vec3 &pos) noexcept {
 113         state.pos.block = pos;
 114         state.AdjustPosition();
 115 }
 116
 117 void Entity::TurnHead(float dp, float dy) noexcept {
 118         SetHead(state.pitch + dp, state.yaw + dy);
 119 }
 120
 121 void Entity::SetHead(float p, float y) noexcept {
 122         state.pitch = p;
 123         state.yaw = y;
 124 }
 125
 126 glm::mat4 Entity::Transform(const glm::ivec3 &reference) const noexcept {
 127         return glm::translate(glm::vec3((state.pos.chunk - reference) * ExactLocation::Extent())) * model_transform;
 128 }
 129
 130 glm::mat4 Entity::ViewTransform(const glm::ivec3 &reference) const noexcept {
 131         return Transform(reference) * view_transform;
 132 }
 133
 134 Ray Entity::Aim(const ExactLocation::Coarse &chunk_offset) const noexcept {
 135         glm::mat4 transform = ViewTransform(chunk_offset);
 136         return Ray{ glm::vec3(transform[3]), -glm::vec3(transform[2]) };
 137 }
 138
 139 void Entity::Update(World &world, float dt) {
 140         if (HasController()) {
 141                 GetController().Update(*this, dt);
 142         }
 143         steering.Update(world, dt);
 144         UpdatePhysics(world, dt);
 145         UpdateTransforms();
 146         UpdateHeading();
 147         UpdateModel(dt);
 148 }
 149
 150 void Entity::UpdatePhysics(World &world, float dt) {
 151         EntityState s(state);
 152
 153         EntityDerivative a(CalculateStep(world, s, 0.0f, EntityDerivative()));
 154         EntityDerivative b(CalculateStep(world, s, dt * 0.5f, a));
 155         EntityDerivative c(CalculateStep(world, s, dt * 0.5f, b));
 156         EntityDerivative d(CalculateStep(world, s, dt, c));
 157
 158         EntityDerivative f;
 159         constexpr float sixth = 1.0f / 6.0f;
 160         f.position = sixth * (a.position + 2.0f * (b.position + c.position) + d.position);
 161         f.velocity = sixth * (a.velocity + 2.0f * (b.velocity + c.velocity) + d.velocity);
 162
 163         s.pos.block += f.position * dt;
 164         s.velocity += f.velocity * dt;
 165         limit(s.velocity, max_vel);
 166         world.ResolveWorldCollision(*this, s);
 167         s.AdjustPosition();
 168
 169         SetState(s);
 170 }
 171
 172 EntityDerivative Entity::CalculateStep(
 173         World &world,
 174         const EntityState &cur,
 175         float dt,
 176         const EntityDerivative &delta
 177 ) const {
 178         EntityState next(cur);
 179         next.pos.block += delta.position * dt;
 180         next.velocity += delta.velocity * dt;
 181         limit(next.velocity, max_vel);
 182         world.ResolveWorldCollision(*this, next);
 183         next.AdjustPosition();
 184
 185         EntityDerivative out;
 186         out.position = next.velocity;
 187         out.velocity = ControlForce(next) + world.GravityAt(next.pos); // by mass = 1kg
 188         return out;
 189 }
 190
 191
 192 void Entity::UpdateTransforms() noexcept {
 193         // model transform is the one given by current state
 194         model_transform = state.Transform(state.pos.chunk);
 195         // view transform is either the model's eyes transform or,
 196         // should the entity have no model, the pitch (yaw already is
 197         // in model transform)
 198         if (model) {
 199                 view_transform = model.EyesTransform();
 200         } else {
 201                 view_transform = toMat4(glm::quat(glm::vec3(state.pitch, state.yaw, 0.0f)));
 202         }
 203 }
 204
 205 void Entity::UpdateHeading() noexcept {
 206         speed = length(Velocity());
 207         if (speed > std::numeric_limits<float>::epsilon()) {
 208                 heading = Velocity() / speed;
 209         } else {
 210                 speed = 0.0f;
 211                 // use -Z (forward axis) of model transform (our "chest")
 212                 heading = -glm::vec3(model_transform[2]);
 213         }
 214 }
 215
 216 void Entity::UpdateModel(float dt) noexcept {
 217         // first, sanitize the pitch and yaw fields of state (our input)
 218         // those indicate the head orientation in the entity's local cosystem
 219         state.AdjustHeading();
 220         // TODO: this flickers horrible and also shouldn't be based on velocity, but on control force
 221         //OrientBody(dt);
 222         OrientHead(dt);
 223 }
 224
 225 void Entity::OrientBody(float dt) noexcept {
 226         // maximum body rotation per second (due to velocity orientation) (90°)
 227         constexpr float max_body_turn_per_second = PI_0p5;
 228         const float max_body_turn = max_body_turn_per_second * dt;
 229         // minimum speed to apply body correction
 230         constexpr float min_speed = 0.0625f;
 231         // use local Y as up
 232         const glm::vec3 up(model_transform[1]);
 233         if (speed > min_speed) {
 234                 // check if our orientation and velocity are aligned
 235                 const glm::vec3 forward(-model_transform[2]);
 236                 // facing is local -Z rotated about local Y by yaw and transformed into world space
 237                 const glm::vec3 facing(normalize(glm::vec3(glm::vec4(rotateY(glm::vec3(0.0f, 0.0f, -1.0f), state.yaw), 0.0f) * transpose(model_transform))));
 238                 // only adjust if velocity isn't almost parallel to up
 239                 float vel_dot_up = dot(Velocity(), up);
 240                 if (std::abs(1.0f - std::abs(vel_dot_up)) > std::numeric_limits<float>::epsilon()) {
 241                         // get direction of velocity projected onto model plane
 242                         glm::vec3 direction(normalize(Velocity() - (Velocity() * vel_dot_up)));
 243                         // if velocity points away from our facing (with a little bias), flip it around
 244                         // (the entity is "walking backwards")
 245                         if (dot(facing, direction) < -0.1f) {
 246                                 direction = -direction;
 247                         }
 248                         // calculate the difference between forward and direction
 249                         const float absolute_difference = std::acos(dot(forward, direction));
 250                         // if direction is clockwise with respect to up vector, invert the angle
 251                         const float relative_difference = dot(cross(forward, direction), up) < 0.0f
 252                                 ? -absolute_difference
 253                                 : absolute_difference;
 254                         // only correct by half the difference max
 255                         const float correction = glm::clamp(relative_difference * 0.5f, -max_body_turn, max_body_turn);
 256                         if (ID() == 1) {
 257                                 std::cout << "orientation before: " << state.orient << std::endl;
 258                                 std::cout << "up:        " << up << std::endl;
 259                                 std::cout << "forward:   " << forward << std::endl;
 260                                 std::cout << "facing:    " << facing << std::endl;
 261                                 std::cout << "direction: " << direction << std::endl;
 262                                 std::cout << "difference: " << glm::degrees(relative_difference) << "°" << std::endl;
 263                                 std::cout << "correction: " << glm::degrees(correction) << "°" << std::endl;
 264                                 std::cout << std::endl;
 265                         }
 266                         // now rotate body by correction and head by -correction
 267                         state.orient = rotate(state.orient, correction, up);
 268                         state.yaw -= correction;
 269                 }
 270         }
 271 }
 272
 273 void Entity::OrientHead(float dt) noexcept {
 274         // maximum yaw of head (60°)
 275         constexpr float max_head_yaw = PI / 3.0f;
 276         // use local Y as up
 277         const glm::vec3 up(model_transform[1]);
 278         // if yaw is bigger than max, rotate the body to accomodate
 279         if (std::abs(state.yaw) > max_head_yaw) {
 280                 float deviation = state.yaw < 0.0f ? state.yaw + max_head_yaw : state.yaw - max_head_yaw;
 281                 // rotate the entity by deviation about local Y
 282                 state.orient = rotate(state.orient, deviation, up);
 283                 // and remove from head yaw
 284                 state.yaw -= deviation;
 285                 // shouldn't be necessary if max_head_yaw is < PI, but just to be sure :p
 286                 state.AdjustHeading();
 287         }
 288         // update model if any
 289         if (model) {
 290                 model.EyesState().orientation = glm::quat(glm::vec3(state.pitch, state.yaw, 0.0f));
 291         }
 292 }
 293
 294
 295 EntityCollision::EntityCollision(Entity *e, float d, const glm::vec3 &n)
 296 : depth(d)
 297 , normal(n)
 298 , entity(e) {
 299         if (entity) {
 300                 entity->Ref();
 301         }
 302 }
 303
 304 EntityCollision::~EntityCollision() {
 305         if (entity) {
 306                 entity->UnRef();
 307         }
 308 }
 309
 310 EntityCollision::EntityCollision(const EntityCollision &other)
 311 : depth(other.depth)
 312 , normal(other.normal)
 313 , entity(other.entity) {
 314         if (entity) {
 315                 entity->Ref();
 316         }
 317 }
 318
 319 EntityCollision &EntityCollision::operator =(const EntityCollision &other) {
 320         if (entity) {
 321                 entity->UnRef();
 322         }
 323         depth = other.depth;
 324         normal = other.normal;
 325         entity = other.entity;
 326         if (entity) {
 327                 entity->Ref();
 328         }
 329         return *this;
 330 }
 331
 332
 333 EntityController::~EntityController() {
 334
 335 }
 336
 337
 338 EntityState::EntityState()
 339 : pos()
 340 , velocity(0.0f)
 341 , orient(1.0f, 0.0f, 0.0f, 0.0f)
 342 , pitch(0.0f)
 343 , yaw(0.0f) {
 344
 345 }
 346
 347 void EntityState::AdjustPosition() noexcept {
 348         pos.Correct();
 349 }
 350
 351 void EntityState::AdjustHeading() noexcept {
 352         pitch = glm::clamp(pitch, -PI_0p5, PI_0p5);
 353         while (yaw > PI) {
 354                 yaw -= PI_2p0;
 355         }
 356         while (yaw < -PI) {
 357                 yaw += PI_2p0;
 358         }
 359 }
 360
 361 glm::mat4 EntityState::Transform(const glm::ivec3 &reference) const noexcept {
 362         const glm::vec3 translation = RelativePosition(reference);
 363         glm::mat4 transform(toMat4(orient));
 364         transform[3] = glm::vec4(translation, 1.0f);
 365         return transform;
 366 }
 367
 368
 369 Player::Player(Entity &e, ChunkIndex &c)
 370 : entity(e)
 371 , chunks(c)
 372 , inv_slot(0) {
 373
 374 }
 375
 376 Player::~Player() {
 377
 378 }
 379
 380 bool Player::SuitableSpawn(BlockLookup &spawn_block) const noexcept {
 381         if (!spawn_block || spawn_block.GetType().collide_block) {
 382                 return false;
 383         }
 384
 385         BlockLookup head_block(spawn_block.Next(Block::FACE_UP));
 386         if (!head_block || head_block.GetType().collide_block) {
 387                 return false;
 388         }
 389
 390         return true;
 391 }
 392
 393 void Player::Update(int dt) {
 394         chunks.Rebase(entity.ChunkCoords());
 395 }
 396
 397
 398 Steering::Steering(const Entity &e)
 399 : entity(e)
 400 , target_entity(nullptr)
 401 , target_velocity(0.0f)
 402 , accel(1.0f)
 403 , speed(entity.MaxVelocity())
 404 , wander_radius(1.0f)
 405 , wander_dist(2.0f)
 406 , wander_disp(1.0f)
 407 , wander_pos(1.0f, 0.0f, 0.0f)
 408 , obstacle_dir(0.0f)
 409 , enabled(0) {
 410
 411 }
 412
 413 Steering::~Steering() {
 414         ClearTargetEntity();
 415 }
 416
 417 Steering &Steering::SetTargetEntity(Entity &e) noexcept {
 418         ClearTargetEntity();
 419         target_entity = &e;
 420         e.Ref();
 421         return *this;
 422 }
 423
 424 Steering &Steering::ClearTargetEntity() noexcept {
 425         if (target_entity) {
 426                 target_entity->UnRef();
 427                 target_entity = nullptr;
 428         }
 429         return *this;
 430 }
 431
 432 void Steering::Update(World &world, float dt) {
 433         if (AnyEnabled(WANDER)) {
 434                 UpdateWander(world, dt);
 435         }
 436         if (AnyEnabled(OBSTACLE_AVOIDANCE)) {
 437                 UpdateObstacle(world);
 438         }
 439 }
 440
 441 void Steering::UpdateWander(World &world, float dt) {
 442         glm::vec3 displacement(
 443                 world.Random().SNorm() * wander_disp,
 444                 world.Random().SNorm() * wander_disp,
 445                 world.Random().SNorm() * wander_disp
 446         );
 447         if (!iszero(displacement)) {
 448                 wander_pos = normalize(wander_pos + displacement * dt) * wander_radius;
 449         }
 450 }
 451
 452 void Steering::UpdateObstacle(World &world) {
 453         if (!entity.Moving()) {
 454                 obstacle_dir = glm::vec3(0.0f);
 455                 return;
 456         }
 457         AABB box(entity.Bounds());
 458         box.min.z = -entity.Speed();
 459         box.max.z = 0.0f;
 460         glm::mat4 transform(find_rotation(glm::vec3(0.0f, 0.0f, -1.0f), entity.Heading()));
 461         transform[3] = glm::vec4(entity.Position(), 1.0f);
 462         // check if that box intersects with any blocks
 463         col.clear();
 464         if (!world.Intersection(box, transform, entity.ChunkCoords(), col)) {
 465                 obstacle_dir = glm::vec3(0.0f);
 466                 return;
 467         }
 468         // if so, pick the nearest collision
 469         const WorldCollision *nearest = nullptr;
 470         glm::vec3 difference(0.0f);
 471         float distance = std::numeric_limits<float>::infinity();
 472         for (const WorldCollision &c : col) {
 473                 // diff points from block to state
 474                 glm::vec3 diff = entity.GetState().RelativePosition(c.ChunkPos()) - c.BlockCoords();
 475                 float dist = length2(diff);
 476                 if (dist < distance) {
 477                         nearest = &c;
 478                         difference = diff;
 479                         distance = dist;
 480                 }
 481         }
 482         if (!nearest) {
 483                 // intersection test lied to us
 484                 obstacle_dir = glm::vec3(0.0f);
 485                 return;
 486         }
 487         // and try to avoid it
 488         float to_go = dot(difference, entity.Heading());
 489         glm::vec3 point(entity.Position() + entity.Heading() * to_go);
 490         obstacle_dir = normalize(point - nearest->BlockCoords()) * (entity.Speed() / std::sqrt(distance));
 491 }
 492
 493 glm::vec3 Steering::Force(const EntityState &state) const noexcept {
 494         glm::vec3 force(0.0f);
 495         if (!enabled) {
 496                 return force;
 497         }
 498         const float max = entity.MaxControlForce();
 499         if (AnyEnabled(HALT)) {
 500                 if (SumForce(force, Halt(state), max)) {
 501                         return force;
 502                 }
 503         }
 504         if (AnyEnabled(TARGET_VELOCITY)) {
 505                 if (SumForce(force, TargetVelocity(state, target_velocity), max)) {
 506                         return force;
 507                 }
 508         }
 509         if (AnyEnabled(OBSTACLE_AVOIDANCE)) {
 510                 if (SumForce(force, ObstacleAvoidance(state), max)) {
 511                         return force;
 512                 }
 513         }
 514         if (AnyEnabled(EVADE_TARGET)) {
 515                 if (HasTargetEntity()) {
 516                         if (SumForce(force, Evade(state, GetTargetEntity()), max)) {
 517                                 return force;
 518                         }
 519                 } else {
 520                         std::cout << "Steering: evade enabled, but target entity not set" << std::endl;
 521                 }
 522         }
 523         if (AnyEnabled(PURSUE_TARGET)) {
 524                 if (HasTargetEntity()) {
 525                         if (SumForce(force, Pursuit(state, GetTargetEntity()), max)) {
 526                                 return force;
 527                         }
 528                 } else {
 529                         std::cout << "Steering: pursuit enabled, but target entity not set" << std::endl;
 530                 }
 531         }
 532         if (AnyEnabled(WANDER)) {
 533                 if (SumForce(force, Wander(state), max)) {
 534                         return force;
 535                 }
 536         }
 537         return force;
 538 }
 539
 540 bool Steering::SumForce(glm::vec3 &out, const glm::vec3 &in, float max) noexcept {
 541         if (iszero(in) || any(isnan(in))) {
 542                 return false;
 543         }
 544         float current = iszero(out) ? 0.0f : length(out);
 545         float remain = max - current;
 546         if (remain <= 0.0f) {
 547                 return true;
 548         }
 549         float additional = length(in);
 550         if (additional > remain) {
 551                 out += normalize(in) * remain;
 552                 return true;
 553         } else {
 554                 out += in;
 555                 return false;
 556         }
 557 }
 558
 559 glm::vec3 Steering::Halt(const EntityState &state) const noexcept {
 560         return state.velocity * -accel;
 561 }
 562
 563 glm::vec3 Steering::TargetVelocity(const EntityState &state, const glm::vec3 &vel) const noexcept {
 564         return (vel - state.velocity) * accel;
 565 }
 566
 567 glm::vec3 Steering::Seek(const EntityState &state, const ExactLocation &loc) const noexcept {
 568         const glm::vec3 diff(loc.Difference(state.pos).Absolute());
 569         if (iszero(diff)) {
 570                 return glm::vec3(0.0f);
 571         } else {
 572                 return TargetVelocity(state, normalize(diff) * speed);
 573         }
 574 }
 575
 576 glm::vec3 Steering::Flee(const EntityState &state, const ExactLocation &loc) const noexcept {
 577         const glm::vec3 diff(state.pos.Difference(loc).Absolute());
 578         if (iszero(diff)) {
 579                 return glm::vec3(0.0f);
 580         } else {
 581                 return TargetVelocity(state, normalize(diff) * speed);
 582         }
 583 }
 584
 585 glm::vec3 Steering::Arrive(const EntityState &state, const ExactLocation &loc) const noexcept {
 586         const glm::vec3 diff(loc.Difference(state.pos).Absolute());
 587         const float dist = length(diff);
 588         if (dist < std::numeric_limits<float>::epsilon()) {
 589                 return glm::vec3(0.0f);
 590         } else {
 591                 const float att_speed = std::min(dist * accel, speed);
 592                 return TargetVelocity(state, diff * att_speed / dist);
 593         }
 594 }
 595
 596 glm::vec3 Steering::Pursuit(const EntityState &state, const Entity &other) const noexcept {
 597         const glm::vec3 diff(state.Diff(other.GetState()));
 598         if (iszero(diff)) {
 599                 return TargetVelocity(state, other.Velocity());
 600         } else {
 601                 const float time_estimate = length(diff) / speed;
 602                 ExactLocation prediction(other.ChunkCoords(), other.Position() + (other.Velocity() * time_estimate));
 603                 return Seek(state, prediction);
 604         }
 605 }
 606
 607 glm::vec3 Steering::Evade(const EntityState &state, const Entity &other) const noexcept {
 608         const glm::vec3 diff(state.Diff(other.GetState()));
 609         if (iszero(diff)) {
 610                 return TargetVelocity(state, -other.Velocity());
 611         } else {
 612                 const float time_estimate = length(diff) / speed;
 613                 ExactLocation prediction(other.ChunkCoords(), other.Position() + (other.Velocity() * time_estimate));
 614                 return Flee(state, prediction);
 615         }
 616 }
 617
 618 glm::vec3 Steering::Wander(const EntityState &state) const noexcept {
 619         return TargetVelocity(state, normalize(entity.Heading() * wander_dist + wander_pos) * speed);
 620 }
 621
 622 glm::vec3 Steering::ObstacleAvoidance(const EntityState &state) const noexcept {
 623         return obstacle_dir;
 624 }
 625
 626
 627 World::World(const BlockTypeRegistry &types, const Config &config)
 628 : config(config)
 629 , block_type(types)
 630 , chunks(types)
 631 , players()
 632 , entities()
 633 , rng(
 634 #ifdef BLANK_PROFILING
 635 0
 636 #else
 637 std::time(nullptr)
 638 #endif
 639 )
 640 , light_direction(config.light_direction)
 641 , fog_density(config.fog_density) {
 642         for (int i = 0; i < 4; ++i) {
 643                 rng.Next<int>();
 644         }
 645 }
 646
 647 World::~World() {
 648         for (Entity &e : entities) {
 649                 e.Kill();
 650         }
 651         std::size_t removed = 0;
 652         do {
 653                 removed = 0;
 654                 for (auto e = entities.begin(), end = entities.end(); e != end; ++e) {
 655                         if (e->CanRemove()) {
 656                                 e = RemoveEntity(e);
 657                                 end = entities.end();
 658                                 ++removed;
 659                         }
 660                 }
 661         } while (removed > 0 && !entities.empty());
 662 }
 663
 664
 665 Player *World::AddPlayer(const std::string &name) {
 666         for (Player &p : players) {
 667                 if (p.Name() == name) {
 668                         return nullptr;
 669                 }
 670         }
 671         Entity &entity = AddEntity();
 672         entity.Name(name);
 673         entity.Bounds({ { -0.4f, -0.9f, -0.4f }, { 0.4f, 0.9f, 0.4f } });
 674         entity.WorldCollidable(true);
 675         ChunkIndex &index = chunks.MakeIndex(entity.ChunkCoords(), 6);
 676         players.emplace_back(entity, index);
 677         return &players.back();
 678 }
 679
 680 Player *World::AddPlayer(const std::string &name, std::uint32_t id) {
 681         for (Player &p : players) {
 682                 if (p.Name() == name) {
 683                         return nullptr;
 684                 }
 685         }
 686         Entity *entity = AddEntity(id);
 687         if (!entity) {
 688                 return nullptr;
 689         }
 690         entity->Name(name);
 691         entity->Bounds({ { -0.4f, -0.9f, -0.4f }, { 0.4f, 0.9f, 0.4f } });
 692         entity->WorldCollidable(true);
 693         ChunkIndex &index = chunks.MakeIndex(entity->ChunkCoords(), 6);
 694         players.emplace_back(*entity, index);
 695         return &players.back();
 696 }
 697
 698 Entity &World::AddEntity() {
 699         if (entities.empty()) {
 700                 entities.emplace_back();
 701                 entities.back().ID(1);
 702                 return entities.back();
 703         }
 704         if (entities.back().ID() < std::numeric_limits<std::uint32_t>::max()) {
 705                 std::uint32_t id = entities.back().ID() + 1;
 706                 entities.emplace_back();
 707                 entities.back().ID(id);
 708                 return entities.back();
 709         }
 710         std::uint32_t id = 1;
 711         auto position = entities.begin();
 712         auto end = entities.end();
 713         while (position != end && position->ID() == id) {
 714                 ++id;
 715                 ++position;
 716         }
 717         auto entity = entities.emplace(position);
 718         entity->ID(id);
 719         return *entity;
 720 }
 721
 722 Entity *World::AddEntity(std::uint32_t id) {
 723         if (entities.empty() || entities.back().ID() < id) {
 724                 entities.emplace_back();
 725                 entities.back().ID(id);
 726                 return &entities.back();
 727         }
 728
 729         auto position = entities.begin();
 730         auto end = entities.end();
 731         while (position != end && position->ID() < id) {
 732                 ++position;
 733         }
 734         if (position != end && position->ID() == id) {
 735                 return nullptr;
 736         }
 737         auto entity = entities.emplace(position);
 738         entity->ID(id);
 739         return &*entity;
 740 }
 741
 742 Entity &World::ForceAddEntity(std::uint32_t id) {
 743         if (entities.empty() || entities.back().ID() < id) {
 744                 entities.emplace_back();
 745                 entities.back().ID(id);
 746                 return entities.back();
 747         }
 748
 749         auto position = entities.begin();
 750         auto end = entities.end();
 751         while (position != end && position->ID() < id) {
 752                 ++position;
 753         }
 754         if (position != end && position->ID() == id) {
 755                 return *position;
 756         }
 757         auto entity = entities.emplace(position);
 758         entity->ID(id);
 759         return *entity;
 760 }
 761
 762
 763 namespace {
 764
 765 struct Candidate {
 766         Chunk *chunk;
 767         float dist;
 768 };
 769
 770 bool CandidateLess(const Candidate &a, const Candidate &b) {
 771         return a.dist < b.dist;
 772 }
 773
 774 std::vector<Candidate> candidates;
 775
 776 }
 777
 778 bool World::Intersection(
 779         const Ray &ray,
 780         const ExactLocation::Coarse &reference,
 781         WorldCollision &coll
 782 ) {
 783         candidates.clear();
 784
 785         for (Chunk &cur_chunk : chunks) {
 786                 float cur_dist;
 787                 if (cur_chunk.Intersection(ray, reference, cur_dist)) {
 788                         candidates.push_back({ &cur_chunk, cur_dist });
 789                 }
 790         }
 791
 792         if (candidates.empty()) return false;
 793
 794         std::sort(candidates.begin(), candidates.end(), CandidateLess);
 795
 796         coll.chunk = nullptr;
 797         coll.block = -1;
 798         coll.depth = std::numeric_limits<float>::infinity();
 799
 800         for (Candidate &cand : candidates) {
 801                 if (cand.dist > coll.depth) continue;
 802                 WorldCollision cur_coll;
 803                 if (cand.chunk->Intersection(ray, reference, cur_coll)) {
 804                         if (cur_coll.depth < coll.depth) {
 805                                 coll = cur_coll;
 806                         }
 807                 }
 808         }
 809
 810         return coll.chunk;
 811 }
 812
 813 bool World::Intersection(
 814         const Ray &ray,
 815         const Entity &reference,
 816         EntityCollision &coll
 817 ) {
 818         coll = EntityCollision(nullptr, std::numeric_limits<float>::infinity(), glm::vec3(0.0f));
 819         for (Entity &cur_entity : entities) {
 820                 if (&cur_entity == &reference) {
 821                         continue;
 822                 }
 823                 float cur_dist;
 824                 glm::vec3 cur_normal;
 825                 if (blank::Intersection(ray, cur_entity.Bounds(), cur_entity.Transform(reference.ChunkCoords()), &cur_dist, &cur_normal)) {
 826                         // TODO: fine grained check goes here? maybe?
 827                         if (cur_dist < coll.depth) {
 828                                 coll = EntityCollision(&cur_entity, cur_dist, cur_normal);
 829                         }
 830                 }
 831         }
 832
 833         return coll;
 834 }
 835
 836 bool World::Intersection(const Entity &e, const EntityState &s, std::vector<WorldCollision> &col) {
 837         glm::ivec3 reference = s.pos.chunk;
 838         glm::mat4 M = s.Transform(reference);
 839
 840         ExactLocation::Coarse begin(reference - 1);
 841         ExactLocation::Coarse end(reference + 2);
 842
 843         bool any = false;
 844         for (ExactLocation::Coarse pos(begin); pos.z < end.y; ++pos.z) {
 845                 for (pos.y = begin.y; pos.y < end.y; ++pos.y) {
 846                         for (pos.x = begin.x; pos.x < end.x; ++pos.x) {
 847                                 Chunk *chunk = chunks.Get(pos);
 848                                 if (chunk && chunk->Intersection(e, M, chunk->Transform(reference), col)) {
 849                                         any = true;
 850                                 }
 851                         }
 852                 }
 853         }
 854         return any;
 855 }
 856
 857 bool World::Intersection(
 858         const AABB &box,
 859         const glm::mat4 &M,
 860         const glm::ivec3 &reference,
 861         std::vector<WorldCollision> &col
 862 ) {
 863         bool any = false;
 864         for (Chunk &cur_chunk : chunks) {
 865                 if (manhattan_radius(cur_chunk.Position() - reference) > 1) {
 866                         // chunk is not one of the 3x3x3 surrounding the entity
 867                         // since there's no entity which can extent over 16 blocks, they can be skipped
 868                         // TODO: change to indexed (like with entity)
 869                         continue;
 870                 }
 871                 if (cur_chunk.Intersection(box, M, cur_chunk.Transform(reference), col)) {
 872                         any = true;
 873                 }
 874         }
 875         return any;
 876 }
 877
 878 void World::Update(int dt) {
 879         float fdt(dt * 0.001f);
 880         for (Entity &entity : entities) {
 881                 entity.Update(*this, fdt);
 882         }
 883         for (Player &player : players) {
 884                 player.Update(dt);
 885         }
 886         for (auto iter = entities.begin(), end = entities.end(); iter != end;) {
 887                 if (iter->CanRemove()) {
 888                         iter = RemoveEntity(iter);
 889                 } else {
 890                         ++iter;
 891                 }
 892         }
 893 }
 894
 895 void World::ResolveWorldCollision(
 896         const Entity &entity,
 897         EntityState &state
 898 ) {
 899         col.clear();
 900         if (!entity.WorldCollidable() || !Intersection(entity, state, col)) {
 901                 // no collision, no fix
 902                 return;
 903         }
 904         glm::vec3 correction = CombinedInterpenetration(state, col);
 905         // correction may be zero in which case normalize() returns NaNs
 906         if (iszero(correction)) {
 907                 return;
 908         }
 909         // if entity is already going in the direction of correction,
 910         // let the problem resolve itself
 911         if (dot(state.velocity, correction) >= 0.0f) {
 912                 return;
 913         }
 914         // apply correction, maybe could use some damping, gotta test
 915         state.pos.block += correction;
 916         // kill velocity?
 917         glm::vec3 normal_velocity(proj(state.velocity, correction));
 918         state.velocity -= normal_velocity;
 919 }
 920
 921 glm::vec3 World::CombinedInterpenetration(
 922         const EntityState &state,
 923         const std::vector<WorldCollision> &col
 924 ) noexcept {
 925         // determine displacement for each cardinal axis and move entity accordingly
 926         glm::vec3 min_pen(0.0f);
 927         glm::vec3 max_pen(0.0f);
 928         for (const WorldCollision &c : col) {
 929                 if (!c.Blocks()) continue;
 930                 glm::vec3 normal(c.normal);
 931                 // swap if neccessary (normal may point away from the entity)
 932                 if (dot(normal, state.RelativePosition(c.ChunkPos()) - c.BlockCoords()) < 0) {
 933                         normal = -normal;
 934                 }
 935                 // check if block surface is "inside"
 936                 Block::Face coll_face = Block::NormalFace(normal);
 937                 BlockLookup neighbor(c.chunk, c.BlockPos(), coll_face);
 938                 if (neighbor && neighbor.FaceFilled(Block::Opposite(coll_face))) {
 939                         // yep, so ignore this contact
 940                         continue;
 941                 }
 942                 glm::vec3 local_pen(normal * c.depth);
 943                 min_pen = min(min_pen, local_pen);
 944                 max_pen = max(max_pen, local_pen);
 945         }
 946         glm::vec3 pen(0.0f);
 947         // only apply correction for axes where penetration is only in one direction
 948         for (std::size_t i = 0; i < 3; ++i) {
 949                 if (min_pen[i] < -std::numeric_limits<float>::epsilon()) {
 950                         if (max_pen[i] < std::numeric_limits<float>::epsilon()) {
 951                                 pen[i] = min_pen[i];
 952                         }
 953                 } else {
 954                         pen[i] = max_pen[i];
 955                 }
 956         }
 957         return pen;
 958 }
 959
 960 glm::vec3 World::GravityAt(const ExactLocation &loc) const noexcept {
 961         glm::vec3 force(0.0f);
 962         ExactLocation::Coarse begin(loc.chunk - 1);
 963         ExactLocation::Coarse end(loc.chunk + 2);
 964
 965         for (ExactLocation::Coarse pos(begin); pos.z < end.z; ++pos.z) {
 966                 for (pos.y = begin.y; pos.y < end.y; ++pos.y) {
 967                         for (pos.x = begin.x; pos.x < end.x; ++pos.x) {
 968                                 const Chunk *chunk = chunks.Get(pos);
 969                                 if (chunk) {
 970                                         force += chunk->GravityAt(loc);
 971                                 }
 972                         }
 973                 }
 974         }
 975
 976         return force;
 977 }
 978
 979 World::EntityHandle World::RemoveEntity(EntityHandle &eh) {
 980         // check for player
 981         for (auto player = players.begin(), end = players.end(); player != end;) {
 982                 if (&player->GetEntity() == &*eh) {
 983                         chunks.UnregisterIndex(player->GetChunks());
 984                         player = players.erase(player);
 985                         end = players.end();
 986                 } else {
 987                         ++player;
 988                 }
 989         }
 990         return entities.erase(eh);
 991 }
 992
 993
 994 void World::Render(Viewport &viewport) {
 995         DirectionalLighting &entity_prog = viewport.EntityProgram();
 996         entity_prog.SetFogDensity(fog_density);
 997
 998         glm::vec3 light_dir;
 999         glm::vec3 light_col;
1000         glm::vec3 ambient_col;
1001         for (Entity &entity : entities) {
1002                 glm::mat4 M(entity.Transform(players.front().GetEntity().ChunkCoords()));
1003                 if (!CullTest(entity.Bounds(), entity_prog.GetVP() * M)) {
1004                         GetLight(entity, light_dir, light_col, ambient_col);
1005                         entity_prog.SetLightDirection(light_dir);
1006                         entity_prog.SetLightColor(light_col);
1007                         entity_prog.SetAmbientColor(ambient_col);
1008                         entity.Render(M, entity_prog);
1009                 }
1010         }
1011 }
1012
1013 // this should interpolate based on the fractional part of entity's block position
1014 void World::GetLight(
1015         const Entity &e,
1016         glm::vec3 &dir,
1017         glm::vec3 &col,
1018         glm::vec3 &amb
1019 ) {
1020         BlockLookup center(chunks.Get(e.ChunkCoords()), e.Position());
1021         if (!center) {
1022                 // chunk unavailable, so make it really dark and from
1023                 // some arbitrary direction
1024                 dir = glm::vec3(1.0f, 2.0f, 3.0f);
1025                 col = glm::vec3(0.025f); // ~0.8^15
1026                 return;
1027         }
1028         glm::ivec3 base(center.GetBlockPos());
1029         int base_light = center.GetLight();
1030         int max_light = 0;
1031         int min_light = 15;
1032         glm::ivec3 acc(0, 0, 0);
1033         for (glm::ivec3 offset(-1, -1, -1); offset.z < 2; ++offset.z) {
1034                 for (offset.y = -1; offset.y < 2; ++offset.y) {
1035                         for (offset.x = -1; offset.x < 2; ++offset.x) {
1036                                 BlockLookup block(&center.GetChunk(), center.GetBlockPos() + offset);
1037                                 if (!block) {
1038                                         // missing, just ignore it
1039                                         continue;
1040                                 }
1041                                 // otherwise, accumulate the difference times direction
1042                                 acc += offset * (base_light - block.GetLight());
1043                                 max_light = std::max(max_light, block.GetLight());
1044                                 min_light = std::min(min_light, block.GetLight());
1045                         }
1046                 }
1047         }
1048         dir = acc;
1049         col = glm::vec3(std::pow(0.8f, 15 - max_light));
1050         amb = glm::vec3(std::pow(0.8f, 15 - min_light));
1051 }
1052
1053 namespace {
1054
1055 PrimitiveMesh::Buffer debug_buf;
1056
1057 }
1058
1059 void World::RenderDebug(Viewport &viewport) {
1060         PrimitiveMesh debug_mesh;
1061         PlainColor &prog = viewport.WorldColorProgram();
1062         for (const Entity &entity : entities) {
1063                 debug_buf.OutlineBox(entity.Bounds(), glm::vec4(1.0f, 0.0f, 0.0f, 1.0f));
1064                 debug_mesh.Update(debug_buf);
1065                 prog.SetM(entity.Transform(players.front().GetEntity().ChunkCoords()));
1066                 debug_mesh.DrawLines();
1067         }
1068 }
1069
1070 }