3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
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.
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.
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.
20 #include "collision.h"
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)
30 collisionMoveResult result;
32 // If there is no speed, there are no collisions
33 if(speed_f.getLength() == 0)
37 v3s16 oldpos_i = floatToInt(oldpos_f, BS);
40 Calculate new position
42 pos_f += speed_f * dtime;
49 v3s16 pos_i = floatToInt(pos_f, BS);
52 Collision uncertainty radius
53 Make it a bit larger than the maximum distance of movement
55 f32 d = pos_max_d * 1.1;
56 // A fairly large value in here makes moving smoother
59 // This should always apply, otherwise there are glitches
60 assert(d > pos_max_d);
63 Calculate collision box
65 core::aabbox3d<f32> box = box_0;
68 core::aabbox3d<f32> oldbox = box_0;
69 oldbox.MaxEdge += oldpos_f;
70 oldbox.MinEdge += oldpos_f;
73 If the object lies on a walkable node, this is set to true.
75 result.touching_ground = false;
78 Go through every node around the object
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++)
91 // Object collides into walkable nodes
92 MapNode n = map->getNode(v3s16(x,y,z));
93 if(gamedef->getNodeDefManager()->get(n).walkable == false)
96 catch(InvalidPositionException &e)
98 // Doing nothing here will block the object from
99 // walking over map borders
102 core::aabbox3d<f32> nodebox = getNodeBox(v3s16(x,y,z), BS);
105 See if the object is touching ground.
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
111 Use 0.15*BS so that it is easier to get on a node.
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
121 result.touching_ground = true;
124 // If object doesn't intersect with node, ignore node.
125 if(box.intersectsWithBox(nodebox) == false)
129 Go through every axis
132 v3f(0,0,1), // back-front
133 v3f(0,1,0), // top-bottom
134 v3f(1,0,0), // right-left
136 for(u16 i=0; i<3; i++)
139 Calculate values along the axis
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]);
149 Check collision for the axis.
150 Collision happens when object is going through a surface.
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;
162 Check overlap of object and node in other axes
164 bool other_axes_overlap = true;
165 for(u16 j=0; j<3; j++)
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))
175 other_axes_overlap = false;
181 If this is a collision, revert the pos_f in the main
184 if(other_axes_overlap && main_axis_collides)
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;
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)
202 collisionMoveResult final_result;
204 // If there is no speed, there are no collisions
205 if(speed_f.getLength() == 0)
208 // Maximum time increment (for collision detection etc)
209 // time = distance / speed
210 f32 dtime_max_increment = pos_max_d / speed_f.getLength();
212 // Maximum time increment is 10ms or lower
213 if(dtime_max_increment > 0.01)
214 dtime_max_increment = 0.01;
216 // Don't allow overly huge dtime
220 f32 dtime_downcount = dtime;
228 if(dtime_downcount > dtime_max_increment)
230 dtime_part = dtime_max_increment;
231 dtime_downcount -= dtime_part;
235 dtime_part = dtime_downcount;
237 Setting this to 0 (no -=dtime_part) disables an infinite loop
238 when dtime_part is so small that dtime_downcount -= dtime_part
244 collisionMoveResult result = collisionMoveSimple(map, gamedef,
245 pos_max_d, box_0, dtime_part, pos_f, speed_f);
247 if(result.touching_ground)
248 final_result.touching_ground = true;
250 final_result.collides = true;
252 while(dtime_downcount > 0.001);