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