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