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