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
  26 collisionMoveResult collisionMoveSimple(Map *map, IGameDef *gamedef,
  27                 f32 pos_max_d, const core::aabbox3d<f32> &box_0,
  28                 f32 dtime, v3f &pos_f, v3f &speed_f)
  29 {
  30         collisionMoveResult result;
  31
  32         // If there is no speed, there are no collisions
  33         if(speed_f.getLength() == 0)
  34                 return result;
  35
  36         v3f oldpos_f = pos_f;
  37         v3s16 oldpos_i = floatToInt(oldpos_f, BS);
  38
  39         /*
  40                 Calculate new position
  41         */
  42         pos_f += speed_f * dtime;
  43
  44         /*
  45                 Collision detection
  46         */
  47
  48         // position in nodes
  49         v3s16 pos_i = floatToInt(pos_f, BS);
  50
  51         /*
  52                 Collision uncertainty radius
  53                 Make it a bit larger than the maximum distance of movement
  54         */
  55         f32 d = pos_max_d * 1.1;
  56         // A fairly large value in here makes moving smoother
  57         //f32 d = 0.15*BS;
  58
  59         // This should always apply, otherwise there are glitches
  60         assert(d > pos_max_d);
  61
  62         /*
  63                 Calculate collision box
  64         */
  65         core::aabbox3d<f32> box = box_0;
  66         box.MaxEdge += pos_f;
  67         box.MinEdge += pos_f;
  68         core::aabbox3d<f32> oldbox = box_0;
  69         oldbox.MaxEdge += oldpos_f;
  70         oldbox.MinEdge += oldpos_f;
  71
  72         /*
  73                 If the object lies on a walkable node, this is set to true.
  74         */
  75         result.touching_ground = false;
  76
  77         /*
  78                 Go through every node around the object
  79         */
  80         s16 min_x = (box_0.MinEdge.X / BS) - 2;
  81         s16 min_y = (box_0.MinEdge.Y / BS) - 2;
  82         s16 min_z = (box_0.MinEdge.Z / BS) - 2;
  83         s16 max_x = (box_0.MaxEdge.X / BS) + 1;
  84         s16 max_y = (box_0.MaxEdge.Y / BS) + 1;
  85         s16 max_z = (box_0.MaxEdge.Z / BS) + 1;
  86         for(s16 y = oldpos_i.Y + min_y; y <= oldpos_i.Y + max_y; y++)
  87         for(s16 z = oldpos_i.Z + min_z; z <= oldpos_i.Z + max_z; z++)
  88         for(s16 x = oldpos_i.X + min_x; x <= oldpos_i.X + max_x; x++)
  89         {
  90                 try{
  91                         // Object collides into walkable nodes
  92                         MapNode n = map->getNode(v3s16(x,y,z));
  93                         if(gamedef->getNodeDefManager()->get(n).walkable == false)
  94                                 continue;
  95                 }
  96                 catch(InvalidPositionException &e)
  97                 {
  98                         // Doing nothing here will block the object from
  99                         // walking over map borders
 100                 }
 101
 102                 core::aabbox3d<f32> nodebox = getNodeBox(v3s16(x,y,z), BS);
 103
 104                 /*
 105                         See if the object is touching ground.
 106
 107                         Object touches ground if object's minimum Y is near node's
 108                         maximum Y and object's X-Z-area overlaps with the node's
 109                         X-Z-area.
 110
 111                         Use 0.15*BS so that it is easier to get on a node.
 112                 */
 113                 if(
 114                                 //fabs(nodebox.MaxEdge.Y-box.MinEdge.Y) < d
 115                                 fabs(nodebox.MaxEdge.Y-box.MinEdge.Y) < 0.15*BS
 116                                 && nodebox.MaxEdge.X-d > box.MinEdge.X
 117                                 && nodebox.MinEdge.X+d < box.MaxEdge.X
 118                                 && nodebox.MaxEdge.Z-d > box.MinEdge.Z
 119                                 && nodebox.MinEdge.Z+d < box.MaxEdge.Z
 120                 ){
 121                         result.touching_ground = true;
 122                 }
 123
 124                 // If object doesn't intersect with node, ignore node.
 125                 if(box.intersectsWithBox(nodebox) == false)
 126                         continue;
 127
 128                 /*
 129                         Go through every axis
 130                 */
 131                 v3f dirs[3] = {
 132                         v3f(0,0,1), // back-front
 133                         v3f(0,1,0), // top-bottom
 134                         v3f(1,0,0), // right-left
 135                 };
 136                 for(u16 i=0; i<3; i++)
 137                 {
 138                         /*
 139                                 Calculate values along the axis
 140                         */
 141                         f32 nodemax = nodebox.MaxEdge.dotProduct(dirs[i]);
 142                         f32 nodemin = nodebox.MinEdge.dotProduct(dirs[i]);
 143                         f32 objectmax = box.MaxEdge.dotProduct(dirs[i]);
 144                         f32 objectmin = box.MinEdge.dotProduct(dirs[i]);
 145                         f32 objectmax_old = oldbox.MaxEdge.dotProduct(dirs[i]);
 146                         f32 objectmin_old = oldbox.MinEdge.dotProduct(dirs[i]);
 147
 148                         /*
 149                                 Check collision for the axis.
 150                                 Collision happens when object is going through a surface.
 151                         */
 152                         bool negative_axis_collides =
 153                                 (nodemax > objectmin && nodemax <= objectmin_old + d
 154                                         && speed_f.dotProduct(dirs[i]) < 0);
 155                         bool positive_axis_collides =
 156                                 (nodemin < objectmax && nodemin >= objectmax_old - d
 157                                         && speed_f.dotProduct(dirs[i]) > 0);
 158                         bool main_axis_collides =
 159                                         negative_axis_collides || positive_axis_collides;
 160
 161                         /*
 162                                 Check overlap of object and node in other axes
 163                         */
 164                         bool other_axes_overlap = true;
 165                         for(u16 j=0; j<3; j++)
 166                         {
 167                                 if(j == i)
 168                                         continue;
 169                                 f32 nodemax = nodebox.MaxEdge.dotProduct(dirs[j]);
 170                                 f32 nodemin = nodebox.MinEdge.dotProduct(dirs[j]);
 171                                 f32 objectmax = box.MaxEdge.dotProduct(dirs[j]);
 172                                 f32 objectmin = box.MinEdge.dotProduct(dirs[j]);
 173                                 if(!(nodemax - d > objectmin && nodemin + d < objectmax))
 174                                 {
 175                                         other_axes_overlap = false;
 176                                         break;
 177                                 }
 178                         }
 179
 180                         /*
 181                                 If this is a collision, revert the pos_f in the main
 182                                 direction.
 183                         */
 184                         if(other_axes_overlap && main_axis_collides)
 185                         {
 186                                 speed_f -= speed_f.dotProduct(dirs[i]) * dirs[i];
 187                                 pos_f -= pos_f.dotProduct(dirs[i]) * dirs[i];
 188                                 pos_f += oldpos_f.dotProduct(dirs[i]) * dirs[i];
 189                                 result.collides = true;
 190                         }
 191
 192                 }
 193         } // xyz
 194
 195         return result;
 196 }
 197
 198 collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef,
 199                 f32 pos_max_d, const core::aabbox3d<f32> &box_0,
 200                 f32 dtime, v3f &pos_f, v3f &speed_f)
 201 {
 202         collisionMoveResult final_result;
 203
 204         // If there is no speed, there are no collisions
 205         if(speed_f.getLength() == 0)
 206                 return final_result;
 207
 208         // Maximum time increment (for collision detection etc)
 209         // time = distance / speed
 210         f32 dtime_max_increment = pos_max_d / speed_f.getLength();
 211
 212         // Maximum time increment is 10ms or lower
 213         if(dtime_max_increment > 0.01)
 214                 dtime_max_increment = 0.01;
 215
 216         // Don't allow overly huge dtime
 217         if(dtime > 2.0)
 218                 dtime = 2.0;
 219
 220         f32 dtime_downcount = dtime;
 221
 222         u32 loopcount = 0;
 223         do
 224         {
 225                 loopcount++;
 226
 227                 f32 dtime_part;
 228                 if(dtime_downcount > dtime_max_increment)
 229                 {
 230                         dtime_part = dtime_max_increment;
 231                         dtime_downcount -= dtime_part;
 232                 }
 233                 else
 234                 {
 235                         dtime_part = dtime_downcount;
 236                         /*
 237                                 Setting this to 0 (no -=dtime_part) disables an infinite loop
 238                                 when dtime_part is so small that dtime_downcount -= dtime_part
 239                                 does nothing
 240                         */
 241                         dtime_downcount = 0;
 242                 }
 243
 244                 collisionMoveResult result = collisionMoveSimple(map, gamedef,
 245                                 pos_max_d, box_0, dtime_part, pos_f, speed_f);
 246
 247                 if(result.touching_ground)
 248                         final_result.touching_ground = true;
 249                 if(result.collides)
 250                         final_result.collides = true;
 251         }
 252         while(dtime_downcount > 0.001);
 253
 254
 255         return final_result;
 256 }
 257
 258