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 "mapblock.h"
  22 #include "map.h"
  23 #include "nodedef.h"
  24 #include "gamedef.h"
  25 #include "log.h"
  26 #include <vector>
  27 #include "util/timetaker.h"
  28 #include "main.h" // g_profiler
  29 #include "profiler.h"
  30
  31 // Helper function:
  32 // Checks for collision of a moving aabbox with a static aabbox
  33 // Returns -1 if no collision, 0 if X collision, 1 if Y collision, 2 if Z collision
  34 // The time after which the collision occurs is stored in dtime.
  35 int axisAlignedCollision(
  36                 const aabb3f &staticbox, const aabb3f &movingbox,
  37                 const v3f &speed, f32 d, f32 &dtime)
  38 {
  39         //TimeTaker tt("axisAlignedCollision");
  40
  41         f32 xsize = (staticbox.MaxEdge.X - staticbox.MinEdge.X);
  42         f32 ysize = (staticbox.MaxEdge.Y - staticbox.MinEdge.Y);
  43         f32 zsize = (staticbox.MaxEdge.Z - staticbox.MinEdge.Z);
  44
  45         aabb3f relbox(
  46                         movingbox.MinEdge.X - staticbox.MinEdge.X,
  47                         movingbox.MinEdge.Y - staticbox.MinEdge.Y,
  48                         movingbox.MinEdge.Z - staticbox.MinEdge.Z,
  49                         movingbox.MaxEdge.X - staticbox.MinEdge.X,
  50                         movingbox.MaxEdge.Y - staticbox.MinEdge.Y,
  51                         movingbox.MaxEdge.Z - staticbox.MinEdge.Z
  52         );
  53
  54         if(speed.X > 0) // Check for collision with X- plane
  55         {
  56                 if(relbox.MaxEdge.X <= d)
  57                 {
  58                         dtime = - relbox.MaxEdge.X / speed.X;
  59                         if((relbox.MinEdge.Y + speed.Y * dtime < ysize) &&
  60                                         (relbox.MaxEdge.Y + speed.Y * dtime > 0) &&
  61                                         (relbox.MinEdge.Z + speed.Z * dtime < zsize) &&
  62                                         (relbox.MaxEdge.Z + speed.Z * dtime > 0))
  63                                 return 0;
  64                 }
  65                 else if(relbox.MinEdge.X > xsize)
  66                 {
  67                         return -1;
  68                 }
  69         }
  70         else if(speed.X < 0) // Check for collision with X+ plane
  71         {
  72                 if(relbox.MinEdge.X >= xsize - d)
  73                 {
  74                         dtime = (xsize - relbox.MinEdge.X) / speed.X;
  75                         if((relbox.MinEdge.Y + speed.Y * dtime < ysize) &&
  76                                         (relbox.MaxEdge.Y + speed.Y * dtime > 0) &&
  77                                         (relbox.MinEdge.Z + speed.Z * dtime < zsize) &&
  78                                         (relbox.MaxEdge.Z + speed.Z * dtime > 0))
  79                                 return 0;
  80                 }
  81                 else if(relbox.MaxEdge.X < 0)
  82                 {
  83                         return -1;
  84                 }
  85         }
  86
  87         // NO else if here
  88
  89         if(speed.Y > 0) // Check for collision with Y- plane
  90         {
  91                 if(relbox.MaxEdge.Y <= d)
  92                 {
  93                         dtime = - relbox.MaxEdge.Y / speed.Y;
  94                         if((relbox.MinEdge.X + speed.X * dtime < xsize) &&
  95                                         (relbox.MaxEdge.X + speed.X * dtime > 0) &&
  96                                         (relbox.MinEdge.Z + speed.Z * dtime < zsize) &&
  97                                         (relbox.MaxEdge.Z + speed.Z * dtime > 0))
  98                                 return 1;
  99                 }
 100                 else if(relbox.MinEdge.Y > ysize)
 101                 {
 102                         return -1;
 103                 }
 104         }
 105         else if(speed.Y < 0) // Check for collision with Y+ plane
 106         {
 107                 if(relbox.MinEdge.Y >= ysize - d)
 108                 {
 109                         dtime = (ysize - relbox.MinEdge.Y) / speed.Y;
 110                         if((relbox.MinEdge.X + speed.X * dtime < xsize) &&
 111                                         (relbox.MaxEdge.X + speed.X * dtime > 0) &&
 112                                         (relbox.MinEdge.Z + speed.Z * dtime < zsize) &&
 113                                         (relbox.MaxEdge.Z + speed.Z * dtime > 0))
 114                                 return 1;
 115                 }
 116                 else if(relbox.MaxEdge.Y < 0)
 117                 {
 118                         return -1;
 119                 }
 120         }
 121
 122         // NO else if here
 123
 124         if(speed.Z > 0) // Check for collision with Z- plane
 125         {
 126                 if(relbox.MaxEdge.Z <= d)
 127                 {
 128                         dtime = - relbox.MaxEdge.Z / speed.Z;
 129                         if((relbox.MinEdge.X + speed.X * dtime < xsize) &&
 130                                         (relbox.MaxEdge.X + speed.X * dtime > 0) &&
 131                                         (relbox.MinEdge.Y + speed.Y * dtime < ysize) &&
 132                                         (relbox.MaxEdge.Y + speed.Y * dtime > 0))
 133                                 return 2;
 134                 }
 135                 //else if(relbox.MinEdge.Z > zsize)
 136                 //{
 137                 //      return -1;
 138                 //}
 139         }
 140         else if(speed.Z < 0) // Check for collision with Z+ plane
 141         {
 142                 if(relbox.MinEdge.Z >= zsize - d)
 143                 {
 144                         dtime = (zsize - relbox.MinEdge.Z) / speed.Z;
 145                         if((relbox.MinEdge.X + speed.X * dtime < xsize) &&
 146                                         (relbox.MaxEdge.X + speed.X * dtime > 0) &&
 147                                         (relbox.MinEdge.Y + speed.Y * dtime < ysize) &&
 148                                         (relbox.MaxEdge.Y + speed.Y * dtime > 0))
 149                                 return 2;
 150                 }
 151                 //else if(relbox.MaxEdge.Z < 0)
 152                 //{
 153                 //      return -1;
 154                 //}
 155         }
 156
 157         return -1;
 158 }
 159
 160 // Helper function:
 161 // Checks if moving the movingbox up by the given distance would hit a ceiling.
 162 bool wouldCollideWithCeiling(
 163                 const std::vector<aabb3f> &staticboxes,
 164                 const aabb3f &movingbox,
 165                 f32 y_increase, f32 d)
 166 {
 167         //TimeTaker tt("wouldCollideWithCeiling");
 168
 169         assert(y_increase >= 0);
 170
 171         for(std::vector<aabb3f>::const_iterator
 172                         i = staticboxes.begin();
 173                         i != staticboxes.end(); i++)
 174         {
 175                 const aabb3f& staticbox = *i;
 176                 if((movingbox.MaxEdge.Y - d <= staticbox.MinEdge.Y) &&
 177                                 (movingbox.MaxEdge.Y + y_increase > staticbox.MinEdge.Y) &&
 178                                 (movingbox.MinEdge.X < staticbox.MaxEdge.X) &&
 179                                 (movingbox.MaxEdge.X > staticbox.MinEdge.X) &&
 180                                 (movingbox.MinEdge.Z < staticbox.MaxEdge.Z) &&
 181                                 (movingbox.MaxEdge.Z > staticbox.MinEdge.Z))
 182                         return true;
 183         }
 184
 185         return false;
 186 }
 187
 188
 189 collisionMoveResult collisionMoveSimple(Map *map, IGameDef *gamedef,
 190                 f32 pos_max_d, const aabb3f &box_0,
 191                 f32 stepheight, f32 dtime,
 192                 v3f &pos_f, v3f &speed_f, v3f &accel_f)
 193 {
 194         //TimeTaker tt("collisionMoveSimple");
 195     ScopeProfiler sp(g_profiler, "collisionMoveSimple avg", SPT_AVG);
 196
 197         collisionMoveResult result;
 198
 199         /*
 200                 Calculate new velocity
 201         */
 202         if( dtime > 0.5 ) {
 203                 infostream<<"collisionMoveSimple: WARNING: maximum step interval exceeded, lost movement details!"<<std::endl;
 204                 dtime = 0.5;
 205         }
 206         speed_f += accel_f * dtime;
 207
 208     // If there is no speed, there are no collisions
 209         if(speed_f.getLength() == 0)
 210                 return result;
 211
 212         /*
 213                 Collect node boxes in movement range
 214         */
 215         std::vector<aabb3f> cboxes;
 216         std::vector<bool> is_unloaded;
 217         std::vector<bool> is_step_up;
 218         std::vector<int> bouncy_values;
 219         std::vector<v3s16> node_positions;
 220         {
 221         //TimeTaker tt2("collisionMoveSimple collect boxes");
 222     ScopeProfiler sp(g_profiler, "collisionMoveSimple collect boxes avg", SPT_AVG);
 223
 224         v3s16 oldpos_i = floatToInt(pos_f, BS);
 225         v3s16 newpos_i = floatToInt(pos_f + speed_f * dtime, BS);
 226         s16 min_x = MYMIN(oldpos_i.X, newpos_i.X) + (box_0.MinEdge.X / BS) - 1;
 227         s16 min_y = MYMIN(oldpos_i.Y, newpos_i.Y) + (box_0.MinEdge.Y / BS) - 1;
 228         s16 min_z = MYMIN(oldpos_i.Z, newpos_i.Z) + (box_0.MinEdge.Z / BS) - 1;
 229         s16 max_x = MYMAX(oldpos_i.X, newpos_i.X) + (box_0.MaxEdge.X / BS) + 1;
 230         s16 max_y = MYMAX(oldpos_i.Y, newpos_i.Y) + (box_0.MaxEdge.Y / BS) + 1;
 231         s16 max_z = MYMAX(oldpos_i.Z, newpos_i.Z) + (box_0.MaxEdge.Z / BS) + 1;
 232
 233         for(s16 x = min_x; x <= max_x; x++)
 234         for(s16 y = min_y; y <= max_y; y++)
 235         for(s16 z = min_z; z <= max_z; z++)
 236         {
 237                 v3s16 p(x,y,z);
 238                 try{
 239                         // Object collides into walkable nodes
 240                         MapNode n = map->getNode(p);
 241                         const ContentFeatures &f = gamedef->getNodeDefManager()->get(n);
 242                         if(f.walkable == false)
 243                                 continue;
 244                         int n_bouncy_value = itemgroup_get(f.groups, "bouncy");
 245
 246                         std::vector<aabb3f> nodeboxes = n.getNodeBoxes(gamedef->ndef());
 247                         for(std::vector<aabb3f>::iterator
 248                                         i = nodeboxes.begin();
 249                                         i != nodeboxes.end(); i++)
 250                         {
 251                                 aabb3f box = *i;
 252                                 box.MinEdge += v3f(x, y, z)*BS;
 253                                 box.MaxEdge += v3f(x, y, z)*BS;
 254                                 cboxes.push_back(box);
 255                                 is_unloaded.push_back(false);
 256                                 is_step_up.push_back(false);
 257                                 bouncy_values.push_back(n_bouncy_value);
 258                                 node_positions.push_back(p);
 259                         }
 260                 }
 261                 catch(InvalidPositionException &e)
 262                 {
 263                         // Collide with unloaded nodes
 264                         aabb3f box = getNodeBox(p, BS);
 265                         cboxes.push_back(box);
 266                         is_unloaded.push_back(true);
 267                         is_step_up.push_back(false);
 268                         bouncy_values.push_back(0);
 269                         node_positions.push_back(p);
 270                 }
 271         }
 272         } // tt2
 273
 274         assert(cboxes.size() == is_unloaded.size());
 275         assert(cboxes.size() == is_step_up.size());
 276         assert(cboxes.size() == bouncy_values.size());
 277         assert(cboxes.size() == node_positions.size());
 278
 279         /*
 280                 Collision detection
 281         */
 282
 283         /*
 284                 Collision uncertainty radius
 285                 Make it a bit larger than the maximum distance of movement
 286         */
 287         f32 d = pos_max_d * 1.1;
 288         // A fairly large value in here makes moving smoother
 289         //f32 d = 0.15*BS;
 290
 291         // This should always apply, otherwise there are glitches
 292         assert(d > pos_max_d);
 293
 294         int loopcount = 0;
 295
 296         while(dtime > BS*1e-10)
 297         {
 298                 //TimeTaker tt3("collisionMoveSimple dtime loop");
 299         ScopeProfiler sp(g_profiler, "collisionMoveSimple dtime loop avg", SPT_AVG);
 300
 301                 // Avoid infinite loop
 302                 loopcount++;
 303                 if(loopcount >= 100)
 304                 {
 305                         infostream<<"collisionMoveSimple: WARNING: Loop count exceeded, aborting to avoid infiniite loop"<<std::endl;
 306                         dtime = 0;
 307                         break;
 308                 }
 309
 310                 aabb3f movingbox = box_0;
 311                 movingbox.MinEdge += pos_f;
 312                 movingbox.MaxEdge += pos_f;
 313
 314                 int nearest_collided = -1;
 315                 f32 nearest_dtime = dtime;
 316                 u32 nearest_boxindex = -1;
 317
 318                 /*
 319                         Go through every nodebox, find nearest collision
 320                 */
 321                 for(u32 boxindex = 0; boxindex < cboxes.size(); boxindex++)
 322                 {
 323                         // Ignore if already stepped up this nodebox.
 324                         if(is_step_up[boxindex])
 325                                 continue;
 326
 327                         // Find nearest collision of the two boxes (raytracing-like)
 328                         f32 dtime_tmp;
 329                         int collided = axisAlignedCollision(
 330                                         cboxes[boxindex], movingbox, speed_f, d, dtime_tmp);
 331
 332                         if(collided == -1 || dtime_tmp >= nearest_dtime)
 333                                 continue;
 334
 335                         nearest_dtime = dtime_tmp;
 336                         nearest_collided = collided;
 337                         nearest_boxindex = boxindex;
 338                 }
 339
 340                 if(nearest_collided == -1)
 341                 {
 342                         // No collision with any collision box.
 343                         pos_f += speed_f * dtime;
 344                         dtime = 0;  // Set to 0 to avoid "infinite" loop due to small FP numbers
 345                 }
 346                 else
 347                 {
 348                         // Otherwise, a collision occurred.
 349
 350                         const aabb3f& cbox = cboxes[nearest_boxindex];
 351
 352                         // Check for stairs.
 353                         bool step_up = (nearest_collided != 1) && // must not be Y direction
 354                                         (movingbox.MinEdge.Y < cbox.MaxEdge.Y) &&
 355                                         (movingbox.MinEdge.Y + stepheight > cbox.MaxEdge.Y) &&
 356                                         (!wouldCollideWithCeiling(cboxes, movingbox,
 357                                                         cbox.MaxEdge.Y - movingbox.MinEdge.Y,
 358                                                         d));
 359
 360                         // Get bounce multiplier
 361                         bool bouncy = (bouncy_values[nearest_boxindex] >= 1);
 362                         float bounce = -(float)bouncy_values[nearest_boxindex] / 100.0;
 363
 364                         // Move to the point of collision and reduce dtime by nearest_dtime
 365                         if(nearest_dtime < 0)
 366                         {
 367                                 // Handle negative nearest_dtime (can be caused by the d allowance)
 368                                 if(!step_up)
 369                                 {
 370                                         if(nearest_collided == 0)
 371                                                 pos_f.X += speed_f.X * nearest_dtime;
 372                                         if(nearest_collided == 1)
 373                                                 pos_f.Y += speed_f.Y * nearest_dtime;
 374                                         if(nearest_collided == 2)
 375                                                 pos_f.Z += speed_f.Z * nearest_dtime;
 376                                 }
 377                         }
 378                         else
 379                         {
 380                                 pos_f += speed_f * nearest_dtime;
 381                                 dtime -= nearest_dtime;
 382                         }
 383
 384                         bool is_collision = true;
 385                         if(is_unloaded[nearest_boxindex])
 386                                 is_collision = false;
 387
 388                         CollisionInfo info;
 389                         info.type = COLLISION_NODE;
 390                         info.node_p = node_positions[nearest_boxindex];
 391                         info.bouncy = bouncy;
 392                         info.old_speed = speed_f;
 393
 394                         // Set the speed component that caused the collision to zero
 395                         if(step_up)
 396                         {
 397                                 // Special case: Handle stairs
 398                                 is_step_up[nearest_boxindex] = true;
 399                                 is_collision = false;
 400                         }
 401                         else if(nearest_collided == 0) // X
 402                         {
 403                                 if(fabs(speed_f.X) > BS*3)
 404                                         speed_f.X *= bounce;
 405                                 else
 406                                         speed_f.X = 0;
 407                                 result.collides = true;
 408                                 result.collides_xz = true;
 409                         }
 410                         else if(nearest_collided == 1) // Y
 411                         {
 412                                 if(fabs(speed_f.Y) > BS*3)
 413                                         speed_f.Y *= bounce;
 414                                 else
 415                                         speed_f.Y = 0;
 416                                 result.collides = true;
 417                         }
 418                         else if(nearest_collided == 2) // Z
 419                         {
 420                                 if(fabs(speed_f.Z) > BS*3)
 421                                         speed_f.Z *= bounce;
 422                                 else
 423                                         speed_f.Z = 0;
 424                                 result.collides = true;
 425                                 result.collides_xz = true;
 426                         }
 427
 428                         info.new_speed = speed_f;
 429                         if(info.new_speed.getDistanceFrom(info.old_speed) < 0.1*BS)
 430                                 is_collision = false;
 431
 432                         if(is_collision){
 433                                 result.collisions.push_back(info);
 434                         }
 435                 }
 436         }
 437
 438         /*
 439                 Final touches: Check if standing on ground, step up stairs.
 440         */
 441         aabb3f box = box_0;
 442         box.MinEdge += pos_f;
 443         box.MaxEdge += pos_f;
 444         for(u32 boxindex = 0; boxindex < cboxes.size(); boxindex++)
 445         {
 446                 const aabb3f& cbox = cboxes[boxindex];
 447
 448                 /*
 449                         See if the object is touching ground.
 450
 451                         Object touches ground if object's minimum Y is near node's
 452                         maximum Y and object's X-Z-area overlaps with the node's
 453                         X-Z-area.
 454
 455                         Use 0.15*BS so that it is easier to get on a node.
 456                 */
 457                 if(
 458                                 cbox.MaxEdge.X-d > box.MinEdge.X &&
 459                                 cbox.MinEdge.X+d < box.MaxEdge.X &&
 460                                 cbox.MaxEdge.Z-d > box.MinEdge.Z &&
 461                                 cbox.MinEdge.Z+d < box.MaxEdge.Z
 462                 ){
 463                         if(is_step_up[boxindex])
 464                         {
 465                                 pos_f.Y += (cbox.MaxEdge.Y - box.MinEdge.Y);
 466                                 box = box_0;
 467                                 box.MinEdge += pos_f;
 468                                 box.MaxEdge += pos_f;
 469                         }
 470                         if(fabs(cbox.MaxEdge.Y-box.MinEdge.Y) < 0.15*BS)
 471                         {
 472                                 result.touching_ground = true;
 473                                 if(is_unloaded[boxindex])
 474                                         result.standing_on_unloaded = true;
 475                         }
 476                 }
 477         }
 478
 479         return result;
 480 }
 481
 482 #if 0
 483 // This doesn't seem to work and isn't used
 484 collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef,
 485                 f32 pos_max_d, const aabb3f &box_0,
 486                 f32 stepheight, f32 dtime,
 487                 v3f &pos_f, v3f &speed_f, v3f &accel_f)
 488 {
 489         //TimeTaker tt("collisionMovePrecise");
 490     ScopeProfiler sp(g_profiler, "collisionMovePrecise avg", SPT_AVG);
 491
 492         collisionMoveResult final_result;
 493
 494         // If there is no speed, there are no collisions
 495         if(speed_f.getLength() == 0)
 496                 return final_result;
 497
 498         // Don't allow overly huge dtime
 499         if(dtime > 2.0)
 500                 dtime = 2.0;
 501
 502         f32 dtime_downcount = dtime;
 503
 504         u32 loopcount = 0;
 505         do
 506         {
 507                 loopcount++;
 508
 509                 // Maximum time increment (for collision detection etc)
 510                 // time = distance / speed
 511                 f32 dtime_max_increment = 1.0;
 512                 if(speed_f.getLength() != 0)
 513                         dtime_max_increment = pos_max_d / speed_f.getLength();
 514
 515                 // Maximum time increment is 10ms or lower
 516                 if(dtime_max_increment > 0.01)
 517                         dtime_max_increment = 0.01;
 518
 519                 f32 dtime_part;
 520                 if(dtime_downcount > dtime_max_increment)
 521                 {
 522                         dtime_part = dtime_max_increment;
 523                         dtime_downcount -= dtime_part;
 524                 }
 525                 else
 526                 {
 527                         dtime_part = dtime_downcount;
 528                         /*
 529                                 Setting this to 0 (no -=dtime_part) disables an infinite loop
 530                                 when dtime_part is so small that dtime_downcount -= dtime_part
 531                                 does nothing
 532                         */
 533                         dtime_downcount = 0;
 534                 }
 535
 536                 collisionMoveResult result = collisionMoveSimple(map, gamedef,
 537                                 pos_max_d, box_0, stepheight, dtime_part,
 538                                 pos_f, speed_f, accel_f);
 539
 540                 if(result.touching_ground)
 541                         final_result.touching_ground = true;
 542                 if(result.collides)
 543                         final_result.collides = true;
 544                 if(result.collides_xz)
 545                         final_result.collides_xz = true;
 546                 if(result.standing_on_unloaded)
 547                         final_result.standing_on_unloaded = true;
 548         }
 549         while(dtime_downcount > 0.001);
 550
 551         return final_result;
 552 }
 553 #endif