src/collision.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 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         speed_f += accel_f * dtime;
 203
 204     // If there is no speed, there are no collisions
 205         if(speed_f.getLength() == 0)
 206                 return result;
 207
 208         /*
 209                 Collect node boxes in movement range
 210         */
 211         std::vector<aabb3f> cboxes;
 212         std::vector<bool> is_unloaded;
 213         std::vector<bool> is_step_up;
 214         std::vector<int> bouncy_values;
 215         std::vector<v3s16> node_positions;
 216         {
 217         //TimeTaker tt2("collisionMoveSimple collect boxes");
 218     ScopeProfiler sp(g_profiler, "collisionMoveSimple collect boxes avg", SPT_AVG);
 219
 220         v3s16 oldpos_i = floatToInt(pos_f, BS);
 221         v3s16 newpos_i = floatToInt(pos_f + speed_f * dtime, BS);
 222         s16 min_x = MYMIN(oldpos_i.X, newpos_i.X) + (box_0.MinEdge.X / BS) - 1;
 223         s16 min_y = MYMIN(oldpos_i.Y, newpos_i.Y) + (box_0.MinEdge.Y / BS) - 1;
 224         s16 min_z = MYMIN(oldpos_i.Z, newpos_i.Z) + (box_0.MinEdge.Z / BS) - 1;
 225         s16 max_x = MYMAX(oldpos_i.X, newpos_i.X) + (box_0.MaxEdge.X / BS) + 1;
 226         s16 max_y = MYMAX(oldpos_i.Y, newpos_i.Y) + (box_0.MaxEdge.Y / BS) + 1;
 227         s16 max_z = MYMAX(oldpos_i.Z, newpos_i.Z) + (box_0.MaxEdge.Z / BS) + 1;
 228
 229         for(s16 x = min_x; x <= max_x; x++)
 230         for(s16 y = min_y; y <= max_y; y++)
 231         for(s16 z = min_z; z <= max_z; z++)
 232         {
 233                 v3s16 p(x,y,z);
 234                 try{
 235                         // Object collides into walkable nodes
 236                         MapNode n = map->getNode(p);
 237                         const ContentFeatures &f = gamedef->getNodeDefManager()->get(n);
 238                         if(f.walkable == false)
 239                                 continue;
 240                         int n_bouncy_value = itemgroup_get(f.groups, "bouncy");
 241
 242                         std::vector<aabb3f> nodeboxes = n.getNodeBoxes(gamedef->ndef());
 243                         for(std::vector<aabb3f>::iterator
 244                                         i = nodeboxes.begin();
 245                                         i != nodeboxes.end(); i++)
 246                         {
 247                                 aabb3f box = *i;
 248                                 box.MinEdge += v3f(x, y, z)*BS;
 249                                 box.MaxEdge += v3f(x, y, z)*BS;
 250                                 cboxes.push_back(box);
 251                                 is_unloaded.push_back(false);
 252                                 is_step_up.push_back(false);
 253                                 bouncy_values.push_back(n_bouncy_value);
 254                                 node_positions.push_back(p);
 255                         }
 256                 }
 257                 catch(InvalidPositionException &e)
 258                 {
 259                         // Collide with unloaded nodes
 260                         aabb3f box = getNodeBox(p, BS);
 261                         cboxes.push_back(box);
 262                         is_unloaded.push_back(true);
 263                         is_step_up.push_back(false);
 264                         bouncy_values.push_back(0);
 265                         node_positions.push_back(p);
 266                 }
 267         }
 268         } // tt2
 269
 270         assert(cboxes.size() == is_unloaded.size());
 271         assert(cboxes.size() == is_step_up.size());
 272         assert(cboxes.size() == bouncy_values.size());
 273         assert(cboxes.size() == node_positions.size());
 274
 275         /*
 276                 Collision detection
 277         */
 278
 279         /*
 280                 Collision uncertainty radius
 281                 Make it a bit larger than the maximum distance of movement
 282         */
 283         f32 d = pos_max_d * 1.1;
 284         // A fairly large value in here makes moving smoother
 285         //f32 d = 0.15*BS;
 286
 287         // This should always apply, otherwise there are glitches
 288         assert(d > pos_max_d);
 289
 290         int loopcount = 0;
 291
 292         while(dtime > BS*1e-10)
 293         {
 294                 //TimeTaker tt3("collisionMoveSimple dtime loop");
 295         ScopeProfiler sp(g_profiler, "collisionMoveSimple dtime loop avg", SPT_AVG);
 296
 297                 // Avoid infinite loop
 298                 loopcount++;
 299                 if(loopcount >= 100)
 300                 {
 301                         infostream<<"collisionMoveSimple: WARNING: Loop count exceeded, aborting to avoid infiniite loop"<<std::endl;
 302                         dtime = 0;
 303                         break;
 304                 }
 305
 306                 aabb3f movingbox = box_0;
 307                 movingbox.MinEdge += pos_f;
 308                 movingbox.MaxEdge += pos_f;
 309
 310                 int nearest_collided = -1;
 311                 f32 nearest_dtime = dtime;
 312                 u32 nearest_boxindex = -1;
 313
 314                 /*
 315                         Go through every nodebox, find nearest collision
 316                 */
 317                 for(u32 boxindex = 0; boxindex < cboxes.size(); boxindex++)
 318                 {
 319                         // Ignore if already stepped up this nodebox.
 320                         if(is_step_up[boxindex])
 321                                 continue;
 322
 323                         // Find nearest collision of the two boxes (raytracing-like)
 324                         f32 dtime_tmp;
 325                         int collided = axisAlignedCollision(
 326                                         cboxes[boxindex], movingbox, speed_f, d, dtime_tmp);
 327
 328                         if(collided == -1 || dtime_tmp >= nearest_dtime)
 329                                 continue;
 330
 331                         nearest_dtime = dtime_tmp;
 332                         nearest_collided = collided;
 333                         nearest_boxindex = boxindex;
 334                 }
 335
 336                 if(nearest_collided == -1)
 337                 {
 338                         // No collision with any collision box.
 339                         pos_f += speed_f * dtime;
 340                         dtime = 0;  // Set to 0 to avoid "infinite" loop due to small FP numbers
 341                 }
 342                 else
 343                 {
 344                         // Otherwise, a collision occurred.
 345
 346                         const aabb3f& cbox = cboxes[nearest_boxindex];
 347
 348                         // Check for stairs.
 349                         bool step_up = (nearest_collided != 1) && // must not be Y direction
 350                                         (movingbox.MinEdge.Y < cbox.MaxEdge.Y) &&
 351                                         (movingbox.MinEdge.Y + stepheight > cbox.MaxEdge.Y) &&
 352                                         (!wouldCollideWithCeiling(cboxes, movingbox,
 353                                                         cbox.MaxEdge.Y - movingbox.MinEdge.Y,
 354                                                         d));
 355
 356                         // Get bounce multiplier
 357                         bool bouncy = (bouncy_values[nearest_boxindex] >= 1);
 358                         float bounce = -(float)bouncy_values[nearest_boxindex] / 100.0;
 359
 360                         // Move to the point of collision and reduce dtime by nearest_dtime
 361                         if(nearest_dtime < 0)
 362                         {
 363                                 // Handle negative nearest_dtime (can be caused by the d allowance)
 364                                 if(!step_up)
 365                                 {
 366                                         if(nearest_collided == 0)
 367                                                 pos_f.X += speed_f.X * nearest_dtime;
 368                                         if(nearest_collided == 1)
 369                                                 pos_f.Y += speed_f.Y * nearest_dtime;
 370                                         if(nearest_collided == 2)
 371                                                 pos_f.Z += speed_f.Z * nearest_dtime;
 372                                 }
 373                         }
 374                         else
 375                         {
 376                                 pos_f += speed_f * nearest_dtime;
 377                                 dtime -= nearest_dtime;
 378                         }
 379
 380                         bool is_collision = true;
 381                         if(is_unloaded[nearest_boxindex])
 382                                 is_collision = false;
 383
 384                         CollisionInfo info;
 385                         info.type = COLLISION_NODE;
 386                         info.node_p = node_positions[nearest_boxindex];
 387                         info.bouncy = bouncy;
 388                         info.old_speed = speed_f;
 389
 390                         // Set the speed component that caused the collision to zero
 391                         if(step_up)
 392                         {
 393                                 // Special case: Handle stairs
 394                                 is_step_up[nearest_boxindex] = true;
 395                                 is_collision = false;
 396                         }
 397                         else if(nearest_collided == 0) // X
 398                         {
 399                                 if(fabs(speed_f.X) > BS*3)
 400                                         speed_f.X *= bounce;
 401                                 else
 402                                         speed_f.X = 0;
 403                                 result.collides = true;
 404                                 result.collides_xz = true;
 405                         }
 406                         else if(nearest_collided == 1) // Y
 407                         {
 408                                 if(fabs(speed_f.Y) > BS*3)
 409                                         speed_f.Y *= bounce;
 410                                 else
 411                                         speed_f.Y = 0;
 412                                 result.collides = true;
 413                         }
 414                         else if(nearest_collided == 2) // Z
 415                         {
 416                                 if(fabs(speed_f.Z) > BS*3)
 417                                         speed_f.Z *= bounce;
 418                                 else
 419                                         speed_f.Z = 0;
 420                                 result.collides = true;
 421                                 result.collides_xz = true;
 422                         }
 423
 424                         info.new_speed = speed_f;
 425                         if(info.new_speed.getDistanceFrom(info.old_speed) < 0.1*BS)
 426                                 is_collision = false;
 427
 428                         if(is_collision){
 429                                 result.collisions.push_back(info);
 430                         }
 431                 }
 432         }
 433
 434         /*
 435                 Final touches: Check if standing on ground, step up stairs.
 436         */
 437         aabb3f box = box_0;
 438         box.MinEdge += pos_f;
 439         box.MaxEdge += pos_f;
 440         for(u32 boxindex = 0; boxindex < cboxes.size(); boxindex++)
 441         {
 442                 const aabb3f& cbox = cboxes[boxindex];
 443
 444                 /*
 445                         See if the object is touching ground.
 446
 447                         Object touches ground if object's minimum Y is near node's
 448                         maximum Y and object's X-Z-area overlaps with the node's
 449                         X-Z-area.
 450
 451                         Use 0.15*BS so that it is easier to get on a node.
 452                 */
 453                 if(
 454                                 cbox.MaxEdge.X-d > box.MinEdge.X &&
 455                                 cbox.MinEdge.X+d < box.MaxEdge.X &&
 456                                 cbox.MaxEdge.Z-d > box.MinEdge.Z &&
 457                                 cbox.MinEdge.Z+d < box.MaxEdge.Z
 458                 ){
 459                         if(is_step_up[boxindex])
 460                         {
 461                                 pos_f.Y += (cbox.MaxEdge.Y - box.MinEdge.Y);
 462                                 box = box_0;
 463                                 box.MinEdge += pos_f;
 464                                 box.MaxEdge += pos_f;
 465                         }
 466                         if(fabs(cbox.MaxEdge.Y-box.MinEdge.Y) < 0.15*BS)
 467                         {
 468                                 result.touching_ground = true;
 469                                 if(is_unloaded[boxindex])
 470                                         result.standing_on_unloaded = true;
 471                         }
 472                 }
 473         }
 474
 475         return result;
 476 }
 477
 478 #if 0
 479 // This doesn't seem to work and isn't used
 480 collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef,
 481                 f32 pos_max_d, const aabb3f &box_0,
 482                 f32 stepheight, f32 dtime,
 483                 v3f &pos_f, v3f &speed_f, v3f &accel_f)
 484 {
 485         //TimeTaker tt("collisionMovePrecise");
 486     ScopeProfiler sp(g_profiler, "collisionMovePrecise avg", SPT_AVG);
 487
 488         collisionMoveResult final_result;
 489
 490         // If there is no speed, there are no collisions
 491         if(speed_f.getLength() == 0)
 492                 return final_result;
 493
 494         // Don't allow overly huge dtime
 495         if(dtime > 2.0)
 496                 dtime = 2.0;
 497
 498         f32 dtime_downcount = dtime;
 499
 500         u32 loopcount = 0;
 501         do
 502         {
 503                 loopcount++;
 504
 505                 // Maximum time increment (for collision detection etc)
 506                 // time = distance / speed
 507                 f32 dtime_max_increment = 1.0;
 508                 if(speed_f.getLength() != 0)
 509                         dtime_max_increment = pos_max_d / speed_f.getLength();
 510
 511                 // Maximum time increment is 10ms or lower
 512                 if(dtime_max_increment > 0.01)
 513                         dtime_max_increment = 0.01;
 514
 515                 f32 dtime_part;
 516                 if(dtime_downcount > dtime_max_increment)
 517                 {
 518                         dtime_part = dtime_max_increment;
 519                         dtime_downcount -= dtime_part;
 520                 }
 521                 else
 522                 {
 523                         dtime_part = dtime_downcount;
 524                         /*
 525                                 Setting this to 0 (no -=dtime_part) disables an infinite loop
 526                                 when dtime_part is so small that dtime_downcount -= dtime_part
 527                                 does nothing
 528                         */
 529                         dtime_downcount = 0;
 530                 }
 531
 532                 collisionMoveResult result = collisionMoveSimple(map, gamedef,
 533                                 pos_max_d, box_0, stepheight, dtime_part,
 534                                 pos_f, speed_f, accel_f);
 535
 536                 if(result.touching_ground)
 537                         final_result.touching_ground = true;
 538                 if(result.collides)
 539                         final_result.collides = true;
 540                 if(result.collides_xz)
 541                         final_result.collides_xz = true;
 542                 if(result.standing_on_unloaded)
 543                         final_result.standing_on_unloaded = true;
 544         }
 545         while(dtime_downcount > 0.001);
 546
 547         return final_result;
 548 }
 549 #endif