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