src/collision.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "collision.h"
  21 #include <cmath>
  22 #include "mapblock.h"
  23 #include "map.h"
  24 #include "nodedef.h"
  25 #include "gamedef.h"
  26 #ifndef SERVER
  27 #include "client/clientenvironment.h"
  28 #include "client/localplayer.h"
  29 #endif
  30 #include "serverenvironment.h"
  31 #include "server/serveractiveobject.h"
  32 #include "util/timetaker.h"
  33 #include "profiler.h"
  34
  35 #ifdef __FAST_MATH__
  36 #warning "-ffast-math is known to cause bugs in collision code, do not use!"
  37 #endif
  38
  39 struct NearbyCollisionInfo
  40 {
  41         // node
  42         NearbyCollisionInfo(bool is_ul, int bouncy, const v3s16 &pos, const aabb3f &box) :
  43                         is_unloaded(is_ul), obj(nullptr), bouncy(bouncy), position(pos),
  44                         box(box)
  45         {
  46         }
  47
  48         // object
  49         NearbyCollisionInfo(ActiveObject *obj, int bouncy, const aabb3f &box) :
  50                         is_unloaded(false), obj(obj), bouncy(bouncy), box(box)
  51         {
  52         }
  53
  54         inline bool isObject() const { return obj != nullptr; }
  55
  56         bool is_unloaded;
  57         bool is_step_up = false;
  58         ActiveObject *obj;
  59         int bouncy;
  60         v3s16 position;
  61         aabb3f box;
  62 };
  63
  64 // Helper functions:
  65 // Truncate floating point numbers to specified number of decimal places
  66 // in order to move all the floating point error to one side of the correct value
  67 static inline f32 truncate(const f32 val, const f32 factor)
  68 {
  69         return truncf(val * factor) / factor;
  70 }
  71
  72 static inline v3f truncate(const v3f &vec, const f32 factor)
  73 {
  74         return v3f(truncate(vec.X, factor), truncate(vec.Y, factor),
  75                         truncate(vec.Z, factor));
  76 }
  77
  78 // Helper function:
  79 // Checks for collision of a moving aabbox with a static aabbox
  80 // Returns -1 if no collision, 0 if X collision, 1 if Y collision, 2 if Z collision
  81 // The time after which the collision occurs is stored in dtime.
  82 CollisionAxis axisAlignedCollision(const aabb3f &staticbox, const aabb3f &movingbox,
  83                 const v3f &speed, f32 *dtime)
  84 {
  85         // TimeTaker tt("axisAlignedCollision");
  86
  87         aabb3f relbox((movingbox.MaxEdge.X - movingbox.MinEdge.X) +
  88                                         (staticbox.MaxEdge.X -
  89                                                         staticbox.MinEdge
  90                                                                         .X), // sum of the
  91                                                                              // widths
  92                         (movingbox.MaxEdge.Y - movingbox.MinEdge.Y) +
  93                                         (staticbox.MaxEdge.Y - staticbox.MinEdge.Y),
  94                         (movingbox.MaxEdge.Z - movingbox.MinEdge.Z) +
  95                                         (staticbox.MaxEdge.Z - staticbox.MinEdge.Z),
  96                         std::max(movingbox.MaxEdge.X, staticbox.MaxEdge.X) -
  97                                         std::min(movingbox.MinEdge.X,
  98                                                         staticbox.MinEdge.X), // outer
  99                                                                               // bounding
 100                                                                               // 'box'
 101                                                                               // dimensions
 102                         std::max(movingbox.MaxEdge.Y, staticbox.MaxEdge.Y) -
 103                                         std::min(movingbox.MinEdge.Y,
 104                                                         staticbox.MinEdge.Y),
 105                         std::max(movingbox.MaxEdge.Z, staticbox.MaxEdge.Z) -
 106                                         std::min(movingbox.MinEdge.Z,
 107                                                         staticbox.MinEdge.Z));
 108
 109         const f32 dtime_max = *dtime;
 110         f32 inner_margin; // the distance of clipping recovery
 111         f32 distance;
 112         f32 time;
 113
 114         if (speed.Y) {
 115                 distance = relbox.MaxEdge.Y - relbox.MinEdge.Y;
 116                 *dtime = distance / std::abs(speed.Y);
 117                 time = std::max(*dtime, 0.0f);
 118
 119                 if (*dtime <= dtime_max) {
 120                         inner_margin = std::max(
 121                                         -0.5f * (staticbox.MaxEdge.Y -
 122                                                                 staticbox.MinEdge.Y),
 123                                         -2.0f);
 124
 125                         if ((speed.Y > 0 && staticbox.MinEdge.Y - movingbox.MaxEdge.Y >
 126                                                             inner_margin) ||
 127                                         (speed.Y < 0 && movingbox.MinEdge.Y - staticbox.MaxEdge.Y >
 128                                                                         inner_margin)) {
 129                                 if ((std::max(movingbox.MaxEdge.X + speed.X * time,
 130                                                      staticbox.MaxEdge.X) -
 131                                                                     std::min(movingbox.MinEdge.X + speed.X * time,
 132                                                                                     staticbox.MinEdge
 133                                                                                                     .X) -
 134                                                                     relbox.MinEdge.X <
 135                                                     0) &&
 136                                                 (std::max(movingbox.MaxEdge.Z + speed.Z * time,
 137                                                                  staticbox.MaxEdge.Z) -
 138                                                                                 std::min(movingbox.MinEdge.Z + speed.Z * time,
 139                                                                                                 staticbox.MinEdge
 140                                                                                                                 .Z) -
 141                                                                                 relbox.MinEdge.Z <
 142                                                                 0))
 143                                         return COLLISION_AXIS_Y;
 144                         }
 145                 } else {
 146                         return COLLISION_AXIS_NONE;
 147                 }
 148         }
 149
 150         // NO else if here
 151
 152         if (speed.X) {
 153                 distance = relbox.MaxEdge.X - relbox.MinEdge.X;
 154                 *dtime = distance / std::abs(speed.X);
 155                 time = std::max(*dtime, 0.0f);
 156
 157                 if (*dtime <= dtime_max) {
 158                         inner_margin = std::max(
 159                                         -0.5f * (staticbox.MaxEdge.X -
 160                                                                 staticbox.MinEdge.X),
 161                                         -2.0f);
 162
 163                         if ((speed.X > 0 && staticbox.MinEdge.X - movingbox.MaxEdge.X >
 164                                                             inner_margin) ||
 165                                         (speed.X < 0 && movingbox.MinEdge.X - staticbox.MaxEdge.X >
 166                                                                         inner_margin)) {
 167                                 if ((std::max(movingbox.MaxEdge.Y + speed.Y * time,
 168                                                      staticbox.MaxEdge.Y) -
 169                                                                     std::min(movingbox.MinEdge.Y + speed.Y * time,
 170                                                                                     staticbox.MinEdge
 171                                                                                                     .Y) -
 172                                                                     relbox.MinEdge.Y <
 173                                                     0) &&
 174                                                 (std::max(movingbox.MaxEdge.Z + speed.Z * time,
 175                                                                  staticbox.MaxEdge.Z) -
 176                                                                                 std::min(movingbox.MinEdge.Z + speed.Z * time,
 177                                                                                                 staticbox.MinEdge
 178                                                                                                                 .Z) -
 179                                                                                 relbox.MinEdge.Z <
 180                                                                 0))
 181                                         return COLLISION_AXIS_X;
 182                         }
 183                 } else {
 184                         return COLLISION_AXIS_NONE;
 185                 }
 186         }
 187
 188         // NO else if here
 189
 190         if (speed.Z) {
 191                 distance = relbox.MaxEdge.Z - relbox.MinEdge.Z;
 192                 *dtime = distance / std::abs(speed.Z);
 193                 time = std::max(*dtime, 0.0f);
 194
 195                 if (*dtime <= dtime_max) {
 196                         inner_margin = std::max(
 197                                         -0.5f * (staticbox.MaxEdge.Z -
 198                                                                 staticbox.MinEdge.Z),
 199                                         -2.0f);
 200
 201                         if ((speed.Z > 0 && staticbox.MinEdge.Z - movingbox.MaxEdge.Z >
 202                                                             inner_margin) ||
 203                                         (speed.Z < 0 && movingbox.MinEdge.Z - staticbox.MaxEdge.Z >
 204                                                                         inner_margin)) {
 205                                 if ((std::max(movingbox.MaxEdge.X + speed.X * time,
 206                                                      staticbox.MaxEdge.X) -
 207                                                                     std::min(movingbox.MinEdge.X + speed.X * time,
 208                                                                                     staticbox.MinEdge
 209                                                                                                     .X) -
 210                                                                     relbox.MinEdge.X <
 211                                                     0) &&
 212                                                 (std::max(movingbox.MaxEdge.Y + speed.Y * time,
 213                                                                  staticbox.MaxEdge.Y) -
 214                                                                                 std::min(movingbox.MinEdge.Y + speed.Y * time,
 215                                                                                                 staticbox.MinEdge
 216                                                                                                                 .Y) -
 217                                                                                 relbox.MinEdge.Y <
 218                                                                 0))
 219                                         return COLLISION_AXIS_Z;
 220                         }
 221                 }
 222         }
 223
 224         return COLLISION_AXIS_NONE;
 225 }
 226
 227 // Helper function:
 228 // Checks if moving the movingbox up by the given distance would hit a ceiling.
 229 bool wouldCollideWithCeiling(const std::vector<NearbyCollisionInfo> &cinfo,
 230                 const aabb3f &movingbox, f32 y_increase, f32 d)
 231 {
 232         // TimeTaker tt("wouldCollideWithCeiling");
 233
 234         assert(y_increase >= 0); // pre-condition
 235
 236         for (const auto &it : cinfo) {
 237                 const aabb3f &staticbox = it.box;
 238                 if ((movingbox.MaxEdge.Y - d <= staticbox.MinEdge.Y) &&
 239                                 (movingbox.MaxEdge.Y + y_increase >
 240                                                 staticbox.MinEdge.Y) &&
 241                                 (movingbox.MinEdge.X < staticbox.MaxEdge.X) &&
 242                                 (movingbox.MaxEdge.X > staticbox.MinEdge.X) &&
 243                                 (movingbox.MinEdge.Z < staticbox.MaxEdge.Z) &&
 244                                 (movingbox.MaxEdge.Z > staticbox.MinEdge.Z))
 245                         return true;
 246         }
 247
 248         return false;
 249 }
 250
 251 static inline void getNeighborConnectingFace(const v3s16 &p,
 252                 const NodeDefManager *nodedef, Map *map, MapNode n, int v, int *neighbors)
 253 {
 254         MapNode n2 = map->getNode(p);
 255         if (nodedef->nodeboxConnects(n, n2, v))
 256                 *neighbors |= v;
 257 }
 258
 259 collisionMoveResult collisionMoveSimple(Environment *env, IGameDef *gamedef,
 260                 f32 pos_max_d, const aabb3f &box_0, f32 stepheight, f32 dtime, v3f *pos_f,
 261                 v3f *speed_f, v3f accel_f, ActiveObject *self, bool collideWithObjects,
 262                 bool jesus)
 263 {
 264         static bool time_notification_done = false;
 265         Map *map = &env->getMap();
 266
 267         ScopeProfiler sp(g_profiler, "collisionMoveSimple()", SPT_AVG);
 268
 269         collisionMoveResult result;
 270
 271         /*
 272                 Calculate new velocity
 273         */
 274         if (dtime > 0.5f) {
 275                 if (!time_notification_done) {
 276                         time_notification_done = true;
 277                         infostream << "collisionMoveSimple: maximum step interval "
 278                                       "exceeded,"
 279                                       " lost movement details!"
 280                                    << std::endl;
 281                 }
 282                 dtime = 0.5f;
 283         } else {
 284                 time_notification_done = false;
 285         }
 286         *speed_f += accel_f * dtime;
 287
 288         // If there is no speed, there are no collisions
 289         if (speed_f->getLength() == 0)
 290                 return result;
 291
 292         // Limit speed for avoiding hangs
 293         speed_f->Y = rangelim(speed_f->Y, -5000, 5000);
 294         speed_f->X = rangelim(speed_f->X, -5000, 5000);
 295         speed_f->Z = rangelim(speed_f->Z, -5000, 5000);
 296
 297         *speed_f = truncate(*speed_f, 10000.0f);
 298
 299         /*
 300                 Collect node boxes in movement range
 301         */
 302         std::vector<NearbyCollisionInfo> cinfo;
 303         {
 304                 // TimeTaker tt2("collisionMoveSimple collect boxes");
 305                 ScopeProfiler sp2(g_profiler, "collisionMoveSimple(): collect boxes",
 306                                 SPT_AVG);
 307
 308                 v3f newpos_f = *pos_f + *speed_f * dtime;
 309                 v3f minpos_f(MYMIN(pos_f->X, newpos_f.X),
 310                                 MYMIN(pos_f->Y, newpos_f.Y) +
 311                                                 0.01f * BS, // bias rounding, player often
 312                                                             // at +/-n.5
 313                                 MYMIN(pos_f->Z, newpos_f.Z));
 314                 v3f maxpos_f(MYMAX(pos_f->X, newpos_f.X), MYMAX(pos_f->Y, newpos_f.Y),
 315                                 MYMAX(pos_f->Z, newpos_f.Z));
 316                 v3s16 min = floatToInt(minpos_f + box_0.MinEdge, BS) - v3s16(1, 1, 1);
 317                 v3s16 max = floatToInt(maxpos_f + box_0.MaxEdge, BS) + v3s16(1, 1, 1);
 318
 319                 bool any_position_valid = false;
 320                 jesus = jesus && g_settings->getBool("jesus");
 321
 322                 v3s16 p;
 323                 for (p.X = min.X; p.X <= max.X; p.X++)
 324                         for (p.Y = min.Y; p.Y <= max.Y; p.Y++)
 325                                 for (p.Z = min.Z; p.Z <= max.Z; p.Z++) {
 326                                         bool is_position_valid;
 327                                         MapNode n = map->getNode(p, &is_position_valid);
 328
 329                                         if (is_position_valid &&
 330                                                         n.getContent() !=
 331                                                                         CONTENT_IGNORE) {
 332                                                 // Object collides into walkable nodes
 333
 334                                                 any_position_valid = true;
 335                                                 const NodeDefManager *nodedef =
 336                                                                 gamedef->getNodeDefManager();
 337                                                 const ContentFeatures &f =
 338                                                                 nodedef->get(n);
 339
 340                                                 if (!(f.walkable || (jesus && f.isLiquid())))
 341                                                         continue;
 342
 343                                                 int n_bouncy_value = itemgroup_get(
 344                                                                 f.groups, "bouncy");
 345
 346                                                 int neighbors = 0;
 347                                                 if (f.drawtype == NDT_NODEBOX &&
 348                                                                 f.node_box.type ==
 349                                                                                 NODEBOX_CONNECTED) {
 350                                                         v3s16 p2 = p;
 351
 352                                                         p2.Y++;
 353                                                         getNeighborConnectingFace(p2,
 354                                                                         nodedef, map, n,
 355                                                                         1, &neighbors);
 356
 357                                                         p2 = p;
 358                                                         p2.Y--;
 359                                                         getNeighborConnectingFace(p2,
 360                                                                         nodedef, map, n,
 361                                                                         2, &neighbors);
 362
 363                                                         p2 = p;
 364                                                         p2.Z--;
 365                                                         getNeighborConnectingFace(p2,
 366                                                                         nodedef, map, n,
 367                                                                         4, &neighbors);
 368
 369                                                         p2 = p;
 370                                                         p2.X--;
 371                                                         getNeighborConnectingFace(p2,
 372                                                                         nodedef, map, n,
 373                                                                         8, &neighbors);
 374
 375                                                         p2 = p;
 376                                                         p2.Z++;
 377                                                         getNeighborConnectingFace(p2,
 378                                                                         nodedef, map, n,
 379                                                                         16, &neighbors);
 380
 381                                                         p2 = p;
 382                                                         p2.X++;
 383                                                         getNeighborConnectingFace(p2,
 384                                                                         nodedef, map, n,
 385                                                                         32, &neighbors);
 386                                                 }
 387                                                 std::vector<aabb3f> nodeboxes;
 388                                                 n.getCollisionBoxes(gamedef->ndef(),
 389                                                                 &nodeboxes, neighbors);
 390
 391                                                 // Calculate float position only once
 392                                                 v3f posf = intToFloat(p, BS);
 393                                                 for (auto box : nodeboxes) {
 394                                                         box.MinEdge += posf;
 395                                                         box.MaxEdge += posf;
 396                                                         cinfo.emplace_back(false,
 397                                                                         n_bouncy_value, p,
 398                                                                         box);
 399                                                 }
 400                                         } else {
 401                                                 // Collide with unloaded nodes (position
 402                                                 // invalid) and loaded CONTENT_IGNORE
 403                                                 // nodes (position valid)
 404                                                 aabb3f box = getNodeBox(p, BS);
 405                                                 cinfo.emplace_back(true, 0, p, box);
 406                                         }
 407                                 }
 408
 409                 // Do not move if world has not loaded yet, since custom node boxes
 410                 // are not available for collision detection.
 411                 // This also intentionally occurs in the case of the object being
 412                 // positioned solely on loaded CONTENT_IGNORE nodes, no matter where they
 413                 // come from.
 414                 if (!any_position_valid) {
 415                         *speed_f = v3f(0, 0, 0);
 416                         return result;
 417                 }
 418
 419         } // tt2
 420
 421         if (collideWithObjects) {
 422                 /* add object boxes to cinfo */
 423
 424                 std::vector<ActiveObject *> objects;
 425 #ifndef SERVER
 426                 ClientEnvironment *c_env = dynamic_cast<ClientEnvironment *>(env);
 427                 if (c_env != 0) {
 428                         // Calculate distance by speed, add own extent and 1.5m of
 429                         // tolerance
 430                         f32 distance = speed_f->getLength() * dtime +
 431                                        box_0.getExtent().getLength() + 1.5f * BS;
 432                         std::vector<DistanceSortedActiveObject> clientobjects;
 433                         c_env->getActiveObjects(*pos_f, distance, clientobjects);
 434
 435                         for (auto &clientobject : clientobjects) {
 436                                 // Do collide with everything but itself and the parent
 437                                 // CAO
 438                                 if (!self || (self != clientobject.obj &&
 439                                                              self != clientobject.obj->getParent())) {
 440                                         objects.push_back(
 441                                                         (ActiveObject *)clientobject.obj);
 442                                 }
 443                         }
 444                 } else
 445 #endif
 446                 {
 447                         ServerEnvironment *s_env = dynamic_cast<ServerEnvironment *>(env);
 448                         if (s_env != NULL) {
 449                                 // Calculate distance by speed, add own extent and 1.5m of
 450                                 // tolerance
 451                                 f32 distance = speed_f->getLength() * dtime +
 452                                                box_0.getExtent().getLength() + 1.5f * BS;
 453
 454                                 // search for objects which are not us, or we are not its
 455                                 // parent we directly use the callback to populate the
 456                                 // result to prevent a useless result loop here
 457                                 auto include_obj_cb = [self, &objects](
 458                                                                       ServerActiveObject *
 459                                                                                       obj) {
 460                                         if (!obj->isGone() &&
 461                                                         (!self || (self != obj && self != obj->getParent()))) {
 462                                                 objects.push_back((ActiveObject *)obj);
 463                                         }
 464                                         return false;
 465                                 };
 466
 467                                 std::vector<ServerActiveObject *> s_objects;
 468                                 s_env->getObjectsInsideRadius(s_objects, *pos_f, distance,
 469                                                 include_obj_cb);
 470                         }
 471                 }
 472
 473                 for (std::vector<ActiveObject *>::const_iterator iter = objects.begin();
 474                                 iter != objects.end(); ++iter) {
 475                         ActiveObject *object = *iter;
 476
 477                         if (object && object->collideWithObjects()) {
 478                                 aabb3f object_collisionbox;
 479                                 if (object->getCollisionBox(&object_collisionbox))
 480                                         cinfo.emplace_back(
 481                                                         object, 0, object_collisionbox);
 482                         }
 483                 }
 484 #ifndef SERVER
 485                 if (self && c_env) {
 486                         LocalPlayer *lplayer = c_env->getLocalPlayer();
 487                         if (lplayer->getParent() == nullptr) {
 488                                 aabb3f lplayer_collisionbox = lplayer->getCollisionbox();
 489                                 v3f lplayer_pos = lplayer->getPosition();
 490                                 lplayer_collisionbox.MinEdge += lplayer_pos;
 491                                 lplayer_collisionbox.MaxEdge += lplayer_pos;
 492                                 ActiveObject *obj = (ActiveObject *)lplayer->getCAO();
 493                                 cinfo.emplace_back(obj, 0, lplayer_collisionbox);
 494                         }
 495                 }
 496 #endif
 497         } // tt3
 498
 499         /*
 500                 Collision detection
 501         */
 502
 503         f32 d = 0.0f;
 504
 505         int loopcount = 0;
 506
 507         while (dtime > BS * 1e-10f) {
 508                 // Avoid infinite loop
 509                 loopcount++;
 510                 if (loopcount >= 100) {
 511                         warningstream << "collisionMoveSimple: Loop count exceeded, "
 512                                          "aborting to avoid infiniite loop"
 513                                       << std::endl;
 514                         break;
 515                 }
 516
 517                 aabb3f movingbox = box_0;
 518                 movingbox.MinEdge += *pos_f;
 519                 movingbox.MaxEdge += *pos_f;
 520
 521                 CollisionAxis nearest_collided = COLLISION_AXIS_NONE;
 522                 f32 nearest_dtime = dtime;
 523                 int nearest_boxindex = -1;
 524
 525                 /*
 526                         Go through every nodebox, find nearest collision
 527                 */
 528                 for (u32 boxindex = 0; boxindex < cinfo.size(); boxindex++) {
 529                         const NearbyCollisionInfo &box_info = cinfo[boxindex];
 530                         // Ignore if already stepped up this nodebox.
 531                         if (box_info.is_step_up)
 532                                 continue;
 533
 534                         // Find nearest collision of the two boxes (raytracing-like)
 535                         f32 dtime_tmp = nearest_dtime;
 536                         CollisionAxis collided = axisAlignedCollision(
 537                                         box_info.box, movingbox, *speed_f, &dtime_tmp);
 538
 539                         if (collided == -1 || dtime_tmp >= nearest_dtime)
 540                                 continue;
 541
 542                         nearest_dtime = dtime_tmp;
 543                         nearest_collided = collided;
 544                         nearest_boxindex = boxindex;
 545                 }
 546
 547                 if (nearest_collided == COLLISION_AXIS_NONE) {
 548                         // No collision with any collision box.
 549                         *pos_f += truncate(*speed_f * dtime, 100.0f);
 550                         dtime = 0; // Set to 0 to avoid "infinite" loop due to small FP
 551                                    // numbers
 552                 } else {
 553                         // Otherwise, a collision occurred.
 554                         NearbyCollisionInfo &nearest_info = cinfo[nearest_boxindex];
 555                         const aabb3f &cbox = nearest_info.box;
 556
 557                         // movingbox except moved to the horizontal position it would be
 558                         // after step up
 559                         aabb3f stepbox = movingbox;
 560                         stepbox.MinEdge.X += speed_f->X * dtime;
 561                         stepbox.MinEdge.Z += speed_f->Z * dtime;
 562                         stepbox.MaxEdge.X += speed_f->X * dtime;
 563                         stepbox.MaxEdge.Z += speed_f->Z * dtime;
 564                         // Check for stairs.
 565                         bool step_up = (nearest_collided !=
 566                                                        COLLISION_AXIS_Y) && // must not be
 567                                                                             // Y direction
 568                                        (movingbox.MinEdge.Y < cbox.MaxEdge.Y) &&
 569                                        (movingbox.MinEdge.Y + stepheight >
 570                                                        cbox.MaxEdge.Y) &&
 571                                        (!wouldCollideWithCeiling(cinfo, stepbox,
 572                                                        cbox.MaxEdge.Y -
 573                                                                        movingbox.MinEdge
 574                                                                                        .Y,
 575                                                        d));
 576
 577                         // Get bounce multiplier
 578                         float bounce = -(float)nearest_info.bouncy / 100.0f;
 579
 580                         // Move to the point of collision and reduce dtime by
 581                         // nearest_dtime
 582                         if (nearest_dtime < 0) {
 583                                 // Handle negative nearest_dtime
 584                                 if (!step_up) {
 585                                         if (nearest_collided == COLLISION_AXIS_X)
 586                                                 pos_f->X += speed_f->X * nearest_dtime;
 587                                         if (nearest_collided == COLLISION_AXIS_Y)
 588                                                 pos_f->Y += speed_f->Y * nearest_dtime;
 589                                         if (nearest_collided == COLLISION_AXIS_Z)
 590                                                 pos_f->Z += speed_f->Z * nearest_dtime;
 591                                 }
 592                         } else {
 593                                 *pos_f += truncate(*speed_f * nearest_dtime, 100.0f);
 594                                 dtime -= nearest_dtime;
 595                         }
 596
 597                         bool is_collision = true;
 598                         if (nearest_info.is_unloaded)
 599                                 is_collision = false;
 600
 601                         CollisionInfo info;
 602                         if (nearest_info.isObject())
 603                                 info.type = COLLISION_OBJECT;
 604                         else
 605                                 info.type = COLLISION_NODE;
 606
 607                         info.node_p = nearest_info.position;
 608                         info.object = nearest_info.obj;
 609                         info.old_speed = *speed_f;
 610                         info.plane = nearest_collided;
 611
 612                         // Set the speed component that caused the collision to zero
 613                         if (step_up) {
 614                                 // Special case: Handle stairs
 615                                 nearest_info.is_step_up = true;
 616                                 is_collision = false;
 617                         } else if (nearest_collided == COLLISION_AXIS_X) {
 618                                 if (fabs(speed_f->X) > BS * 3)
 619                                         speed_f->X *= bounce;
 620                                 else
 621                                         speed_f->X = 0;
 622                                 result.collides = true;
 623                         } else if (nearest_collided == COLLISION_AXIS_Y) {
 624                                 if (fabs(speed_f->Y) > BS * 3)
 625                                         speed_f->Y *= bounce;
 626                                 else
 627                                         speed_f->Y = 0;
 628                                 result.collides = true;
 629                         } else if (nearest_collided == COLLISION_AXIS_Z) {
 630                                 if (fabs(speed_f->Z) > BS * 3)
 631                                         speed_f->Z *= bounce;
 632                                 else
 633                                         speed_f->Z = 0;
 634                                 result.collides = true;
 635                         }
 636
 637                         info.new_speed = *speed_f;
 638                         if (info.new_speed.getDistanceFrom(info.old_speed) < 0.1f * BS)
 639                                 is_collision = false;
 640
 641                         if (is_collision) {
 642                                 info.axis = nearest_collided;
 643                                 result.collisions.push_back(info);
 644                         }
 645                 }
 646         }
 647
 648         /*
 649                 Final touches: Check if standing on ground, step up stairs.
 650         */
 651         aabb3f box = box_0;
 652         box.MinEdge += *pos_f;
 653         box.MaxEdge += *pos_f;
 654         for (const auto &box_info : cinfo) {
 655                 const aabb3f &cbox = box_info.box;
 656
 657                 /*
 658                         See if the object is touching ground.
 659
 660                         Object touches ground if object's minimum Y is near node's
 661                         maximum Y and object's X-Z-area overlaps with the node's
 662                         X-Z-area.
 663                 */
 664
 665                 if (cbox.MaxEdge.X - d > box.MinEdge.X &&
 666                                 cbox.MinEdge.X + d < box.MaxEdge.X &&
 667                                 cbox.MaxEdge.Z - d > box.MinEdge.Z &&
 668                                 cbox.MinEdge.Z + d < box.MaxEdge.Z) {
 669                         if (box_info.is_step_up) {
 670                                 pos_f->Y += cbox.MaxEdge.Y - box.MinEdge.Y;
 671                                 box = box_0;
 672                                 box.MinEdge += *pos_f;
 673                                 box.MaxEdge += *pos_f;
 674                         }
 675                         if (std::fabs(cbox.MaxEdge.Y - box.MinEdge.Y) < 0.05f) {
 676                                 result.touching_ground = true;
 677
 678                                 if (box_info.isObject())
 679                                         result.standing_on_object = true;
 680                         }
 681                 }
 682         }
 683
 684         return result;
 685 }