From 1575448b1a71dd029a8d135d2aff9096483a9953 Mon Sep 17 00:00:00 2001 From: Kahrl Date: Mon, 19 Mar 2012 04:25:09 +0100 Subject: Custom boxy nodes (stairs, slabs) and collision changes --- src/collision.cpp | 526 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 387 insertions(+), 139 deletions(-) (limited to 'src/collision.cpp') diff --git a/src/collision.cpp b/src/collision.cpp index f8db42d26..09a7df7c2 100644 --- a/src/collision.cpp +++ b/src/collision.cpp @@ -22,32 +22,249 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "map.h" #include "nodedef.h" #include "gamedef.h" +#include "log.h" +#include +#include "util/timetaker.h" +#include "main.h" // g_profiler +#include "profiler.h" + +// Helper function: +// Checks for collision of a moving aabbox with a static aabbox +// Returns -1 if no collision, 0 if X collision, 1 if Y collision, 2 if Z collision +// The time after which the collision occurs is stored in dtime. +int axisAlignedCollision( + const aabb3f &staticbox, const aabb3f &movingbox, + const v3f &speed, f32 d, f32 &dtime) +{ + //TimeTaker tt("axisAlignedCollision"); + + f32 xsize = (staticbox.MaxEdge.X - staticbox.MinEdge.X); + f32 ysize = (staticbox.MaxEdge.Y - staticbox.MinEdge.Y); + f32 zsize = (staticbox.MaxEdge.Z - staticbox.MinEdge.Z); + + aabb3f relbox( + movingbox.MinEdge.X - staticbox.MinEdge.X, + movingbox.MinEdge.Y - staticbox.MinEdge.Y, + movingbox.MinEdge.Z - staticbox.MinEdge.Z, + movingbox.MaxEdge.X - staticbox.MinEdge.X, + movingbox.MaxEdge.Y - staticbox.MinEdge.Y, + movingbox.MaxEdge.Z - staticbox.MinEdge.Z + ); + + if(speed.X > 0) // Check for collision with X- plane + { + if(relbox.MaxEdge.X <= d) + { + dtime = - relbox.MaxEdge.X / speed.X; + if((relbox.MinEdge.Y + speed.Y * dtime < ysize) && + (relbox.MaxEdge.Y + speed.Y * dtime > 0) && + (relbox.MinEdge.Z + speed.Z * dtime < zsize) && + (relbox.MaxEdge.Z + speed.Z * dtime > 0)) + return 0; + } + else if(relbox.MinEdge.X > xsize) + { + return -1; + } + } + else if(speed.X < 0) // Check for collision with X+ plane + { + if(relbox.MinEdge.X >= xsize - d) + { + dtime = (xsize - relbox.MinEdge.X) / speed.X; + if((relbox.MinEdge.Y + speed.Y * dtime < ysize) && + (relbox.MaxEdge.Y + speed.Y * dtime > 0) && + (relbox.MinEdge.Z + speed.Z * dtime < zsize) && + (relbox.MaxEdge.Z + speed.Z * dtime > 0)) + return 0; + } + else if(relbox.MaxEdge.X < 0) + { + return -1; + } + } + + // NO else if here + + if(speed.Y > 0) // Check for collision with Y- plane + { + if(relbox.MaxEdge.Y <= d) + { + dtime = - relbox.MaxEdge.Y / speed.Y; + if((relbox.MinEdge.X + speed.X * dtime < xsize) && + (relbox.MaxEdge.X + speed.X * dtime > 0) && + (relbox.MinEdge.Z + speed.Z * dtime < zsize) && + (relbox.MaxEdge.Z + speed.Z * dtime > 0)) + return 1; + } + else if(relbox.MinEdge.Y > ysize) + { + return -1; + } + } + else if(speed.Y < 0) // Check for collision with Y+ plane + { + if(relbox.MinEdge.Y >= ysize - d) + { + dtime = (ysize - relbox.MinEdge.Y) / speed.Y; + if((relbox.MinEdge.X + speed.X * dtime < xsize) && + (relbox.MaxEdge.X + speed.X * dtime > 0) && + (relbox.MinEdge.Z + speed.Z * dtime < zsize) && + (relbox.MaxEdge.Z + speed.Z * dtime > 0)) + return 1; + } + else if(relbox.MaxEdge.Y < 0) + { + return -1; + } + } + + // NO else if here + + if(speed.Z > 0) // Check for collision with Z- plane + { + if(relbox.MaxEdge.Z <= d) + { + dtime = - relbox.MaxEdge.Z / speed.Z; + if((relbox.MinEdge.X + speed.X * dtime < xsize) && + (relbox.MaxEdge.X + speed.X * dtime > 0) && + (relbox.MinEdge.Y + speed.Y * dtime < ysize) && + (relbox.MaxEdge.Y + speed.Y * dtime > 0)) + return 2; + } + //else if(relbox.MinEdge.Z > zsize) + //{ + // return -1; + //} + } + else if(speed.Z < 0) // Check for collision with Z+ plane + { + if(relbox.MinEdge.Z >= zsize - d) + { + dtime = (zsize - relbox.MinEdge.Z) / speed.Z; + if((relbox.MinEdge.X + speed.X * dtime < xsize) && + (relbox.MaxEdge.X + speed.X * dtime > 0) && + (relbox.MinEdge.Y + speed.Y * dtime < ysize) && + (relbox.MaxEdge.Y + speed.Y * dtime > 0)) + return 2; + } + //else if(relbox.MaxEdge.Z < 0) + //{ + // return -1; + //} + } + + return -1; +} + +// Helper function: +// Checks if moving the movingbox up by the given distance would hit a ceiling. +bool wouldCollideWithCeiling( + const std::vector &staticboxes, + const aabb3f &movingbox, + f32 y_increase, f32 d) +{ + //TimeTaker tt("wouldCollideWithCeiling"); + + assert(y_increase >= 0); + + for(std::vector::const_iterator + i = staticboxes.begin(); + i != staticboxes.end(); i++) + { + const aabb3f& staticbox = *i; + if((movingbox.MaxEdge.Y - d <= staticbox.MinEdge.Y) && + (movingbox.MaxEdge.Y + y_increase > staticbox.MinEdge.Y) && + (movingbox.MinEdge.X < staticbox.MaxEdge.X) && + (movingbox.MaxEdge.X > staticbox.MinEdge.X) && + (movingbox.MinEdge.Z < staticbox.MaxEdge.Z) && + (movingbox.MaxEdge.Z > staticbox.MinEdge.Z)) + return true; + } + + return false; +} + collisionMoveResult collisionMoveSimple(Map *map, IGameDef *gamedef, - f32 pos_max_d, const core::aabbox3d &box_0, - f32 dtime, v3f &pos_f, v3f &speed_f) + f32 pos_max_d, const aabb3f &box_0, + f32 stepheight, f32 dtime, + v3f &pos_f, v3f &speed_f, v3f &accel_f) { + //TimeTaker tt("collisionMoveSimple"); + ScopeProfiler sp(g_profiler, "collisionMoveSimple avg", SPT_AVG); + collisionMoveResult result; - // If there is no speed, there are no collisions + /* + Calculate new velocity + */ + speed_f += accel_f * dtime; + + // If there is no speed, there are no collisions if(speed_f.getLength() == 0) return result; - v3f oldpos_f = pos_f; - v3s16 oldpos_i = floatToInt(oldpos_f, BS); - /* - Calculate new position + Collect node boxes in movement range */ - pos_f += speed_f * dtime; + std::vector cboxes; + std::vector is_unloaded; + std::vector is_step_up; + { + //TimeTaker tt2("collisionMoveSimple collect boxes"); + ScopeProfiler sp(g_profiler, "collisionMoveSimple collect boxes avg", SPT_AVG); + + v3s16 oldpos_i = floatToInt(pos_f, BS); + v3s16 newpos_i = floatToInt(pos_f + speed_f * dtime, BS); + s16 min_x = MYMIN(oldpos_i.X, newpos_i.X) + (box_0.MinEdge.X / BS) - 1; + s16 min_y = MYMIN(oldpos_i.Y, newpos_i.Y) + (box_0.MinEdge.Y / BS) - 1; + s16 min_z = MYMIN(oldpos_i.Z, newpos_i.Z) + (box_0.MinEdge.Z / BS) - 1; + s16 max_x = MYMAX(oldpos_i.X, newpos_i.X) + (box_0.MaxEdge.X / BS) + 1; + s16 max_y = MYMAX(oldpos_i.Y, newpos_i.Y) + (box_0.MaxEdge.Y / BS) + 1; + s16 max_z = MYMAX(oldpos_i.Z, newpos_i.Z) + (box_0.MaxEdge.Z / BS) + 1; + + for(s16 x = min_x; x <= max_x; x++) + for(s16 y = min_y; y <= max_y; y++) + for(s16 z = min_z; z <= max_z; z++) + { + try{ + // Object collides into walkable nodes + MapNode n = map->getNode(v3s16(x,y,z)); + if(gamedef->getNodeDefManager()->get(n).walkable == false) + continue; + + std::vector nodeboxes = n.getNodeBoxes(gamedef->ndef()); + for(std::vector::iterator + i = nodeboxes.begin(); + i != nodeboxes.end(); i++) + { + aabb3f box = *i; + box.MinEdge += v3f(x, y, z)*BS; + box.MaxEdge += v3f(x, y, z)*BS; + cboxes.push_back(box); + is_unloaded.push_back(false); + is_step_up.push_back(false); + } + } + catch(InvalidPositionException &e) + { + // Collide with unloaded nodes + aabb3f box = getNodeBox(v3s16(x,y,z), BS); + cboxes.push_back(box); + is_unloaded.push_back(true); + is_step_up.push_back(false); + } + } + } // tt2 + + assert(cboxes.size() == is_unloaded.size()); + assert(cboxes.size() == is_step_up.size()); /* Collision detection */ - - // position in nodes - v3s16 pos_i = floatToInt(pos_f, BS); - + /* Collision uncertainty radius Make it a bit larger than the maximum distance of movement @@ -58,49 +275,129 @@ collisionMoveResult collisionMoveSimple(Map *map, IGameDef *gamedef, // This should always apply, otherwise there are glitches assert(d > pos_max_d); - - /* - Calculate collision box - */ - core::aabbox3d box = box_0; - box.MaxEdge += pos_f; - box.MinEdge += pos_f; - core::aabbox3d oldbox = box_0; - oldbox.MaxEdge += oldpos_f; - oldbox.MinEdge += oldpos_f; - /* - If the object lies on a walkable node, this is set to true. - */ - result.touching_ground = false; - - /* - Go through every node around the object - */ - s16 min_x = (box_0.MinEdge.X / BS) - 2; - s16 min_y = (box_0.MinEdge.Y / BS) - 2; - s16 min_z = (box_0.MinEdge.Z / BS) - 2; - s16 max_x = (box_0.MaxEdge.X / BS) + 1; - s16 max_y = (box_0.MaxEdge.Y / BS) + 1; - s16 max_z = (box_0.MaxEdge.Z / BS) + 1; - for(s16 y = oldpos_i.Y + min_y; y <= oldpos_i.Y + max_y; y++) - for(s16 z = oldpos_i.Z + min_z; z <= oldpos_i.Z + max_z; z++) - for(s16 x = oldpos_i.X + min_x; x <= oldpos_i.X + max_x; x++) + int loopcount = 0; + + while(dtime > BS*1e-10) { - try{ - // Object collides into walkable nodes - MapNode n = map->getNode(v3s16(x,y,z)); - if(gamedef->getNodeDefManager()->get(n).walkable == false) + //TimeTaker tt3("collisionMoveSimple dtime loop"); + ScopeProfiler sp(g_profiler, "collisionMoveSimple dtime loop avg", SPT_AVG); + + // Avoid infinite loop + loopcount++; + if(loopcount >= 100) + { + infostream<<"collisionMoveSimple: WARNING: Loop count exceeded, aborting to avoid infiniite loop"<= nearest_dtime) continue; + + nearest_dtime = dtime_tmp; + nearest_collided = collided; + nearest_boxindex = boxindex; } - catch(InvalidPositionException &e) + + if(nearest_collided == -1) { - // Doing nothing here will block the object from - // walking over map borders + // No collision with any collision box. + pos_f += speed_f * dtime; + dtime = 0; // Set to 0 to avoid "infinite" loop due to small FP numbers } + else + { + // Otherwise, a collision occurred. + + const aabb3f& cbox = cboxes[nearest_boxindex]; + + // Check for stairs. + bool step_up = (nearest_collided != 1) && // must not be Y direction + (movingbox.MinEdge.Y < cbox.MaxEdge.Y) && + (movingbox.MinEdge.Y + stepheight > cbox.MaxEdge.Y) && + (!wouldCollideWithCeiling(cboxes, movingbox, + cbox.MaxEdge.Y - movingbox.MinEdge.Y, + d)); + + // Move to the point of collision and reduce dtime by nearest_dtime + if(nearest_dtime < 0) + { + // Handle negative nearest_dtime (can be caused by the d allowance) + if(!step_up) + { + if(nearest_collided == 0) + pos_f.X += speed_f.X * nearest_dtime; + if(nearest_collided == 1) + pos_f.Y += speed_f.Y * nearest_dtime; + if(nearest_collided == 2) + pos_f.Z += speed_f.Z * nearest_dtime; + } + } + else + { + pos_f += speed_f * nearest_dtime; + dtime -= nearest_dtime; + } + + // Set the speed component that caused the collision to zero + if(step_up) + { + // Special case: Handle stairs + is_step_up[nearest_boxindex] = true; + } + else if(nearest_collided == 0) // X + { + speed_f.X = 0; + result.collides = true; + result.collides_xz = true; + } + else if(nearest_collided == 1) // Y + { + speed_f.Y = 0; + result.collides = true; + } + else if(nearest_collided == 2) // Z + { + speed_f.Z = 0; + result.collides = true; + result.collides_xz = true; + } + } + } + + /* + Final touches: Check if standing on ground, step up stairs. + */ + aabb3f box = box_0; + box.MinEdge += pos_f; + box.MaxEdge += pos_f; + for(u32 boxindex = 0; boxindex < cboxes.size(); boxindex++) + { + const aabb3f& cbox = cboxes[boxindex]; - core::aabbox3d nodebox = getNodeBox(v3s16(x,y,z), BS); - /* See if the object is touching ground. @@ -111,112 +408,50 @@ collisionMoveResult collisionMoveSimple(Map *map, IGameDef *gamedef, Use 0.15*BS so that it is easier to get on a node. */ if( - //fabs(nodebox.MaxEdge.Y-box.MinEdge.Y) < d - fabs(nodebox.MaxEdge.Y-box.MinEdge.Y) < 0.15*BS - && nodebox.MaxEdge.X-d > box.MinEdge.X - && nodebox.MinEdge.X+d < box.MaxEdge.X - && nodebox.MaxEdge.Z-d > box.MinEdge.Z - && nodebox.MinEdge.Z+d < box.MaxEdge.Z + cbox.MaxEdge.X-d > box.MinEdge.X && + cbox.MinEdge.X+d < box.MaxEdge.X && + cbox.MaxEdge.Z-d > box.MinEdge.Z && + cbox.MinEdge.Z+d < box.MaxEdge.Z ){ - result.touching_ground = true; - } - - // If object doesn't intersect with node, ignore node. - if(box.intersectsWithBox(nodebox) == false) - continue; - - /* - Go through every axis - */ - v3f dirs[3] = { - v3f(0,0,1), // back-front - v3f(0,1,0), // top-bottom - v3f(1,0,0), // right-left - }; - for(u16 i=0; i<3; i++) - { - /* - Calculate values along the axis - */ - f32 nodemax = nodebox.MaxEdge.dotProduct(dirs[i]); - f32 nodemin = nodebox.MinEdge.dotProduct(dirs[i]); - f32 objectmax = box.MaxEdge.dotProduct(dirs[i]); - f32 objectmin = box.MinEdge.dotProduct(dirs[i]); - f32 objectmax_old = oldbox.MaxEdge.dotProduct(dirs[i]); - f32 objectmin_old = oldbox.MinEdge.dotProduct(dirs[i]); - - /* - Check collision for the axis. - Collision happens when object is going through a surface. - */ - bool negative_axis_collides = - (nodemax > objectmin && nodemax <= objectmin_old + d - && speed_f.dotProduct(dirs[i]) < 0); - bool positive_axis_collides = - (nodemin < objectmax && nodemin >= objectmax_old - d - && speed_f.dotProduct(dirs[i]) > 0); - bool main_axis_collides = - negative_axis_collides || positive_axis_collides; - - /* - Check overlap of object and node in other axes - */ - bool other_axes_overlap = true; - for(u16 j=0; j<3; j++) + if(is_step_up[boxindex]) { - if(j == i) - continue; - f32 nodemax = nodebox.MaxEdge.dotProduct(dirs[j]); - f32 nodemin = nodebox.MinEdge.dotProduct(dirs[j]); - f32 objectmax = box.MaxEdge.dotProduct(dirs[j]); - f32 objectmin = box.MinEdge.dotProduct(dirs[j]); - if(!(nodemax - d > objectmin && nodemin + d < objectmax)) - { - other_axes_overlap = false; - break; - } + pos_f.Y += (cbox.MaxEdge.Y - box.MinEdge.Y); + box = box_0; + box.MinEdge += pos_f; + box.MaxEdge += pos_f; } - - /* - If this is a collision, revert the pos_f in the main - direction. - */ - if(other_axes_overlap && main_axis_collides) + if(fabs(cbox.MaxEdge.Y-box.MinEdge.Y) < 0.15*BS) { - speed_f -= speed_f.dotProduct(dirs[i]) * dirs[i]; - pos_f -= pos_f.dotProduct(dirs[i]) * dirs[i]; - pos_f += oldpos_f.dotProduct(dirs[i]) * dirs[i]; - result.collides = true; + result.touching_ground = true; + if(is_unloaded[boxindex]) + result.standing_on_unloaded = true; } - } - } // xyz - + } + return result; } +#if 0 +// This doesn't seem to work and isn't used collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef, - f32 pos_max_d, const core::aabbox3d &box_0, - f32 dtime, v3f &pos_f, v3f &speed_f) + f32 pos_max_d, const aabb3f &box_0, + f32 stepheight, f32 dtime, + v3f &pos_f, v3f &speed_f, v3f &accel_f) { - collisionMoveResult final_result; + //TimeTaker tt("collisionMovePrecise"); + ScopeProfiler sp(g_profiler, "collisionMovePrecise avg", SPT_AVG); + collisionMoveResult final_result; + // If there is no speed, there are no collisions if(speed_f.getLength() == 0) return final_result; - // Maximum time increment (for collision detection etc) - // time = distance / speed - f32 dtime_max_increment = pos_max_d / speed_f.getLength(); - - // Maximum time increment is 10ms or lower - if(dtime_max_increment > 0.01) - dtime_max_increment = 0.01; - // Don't allow overly huge dtime if(dtime > 2.0) dtime = 2.0; - + f32 dtime_downcount = dtime; u32 loopcount = 0; @@ -224,6 +459,16 @@ collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef, { loopcount++; + // Maximum time increment (for collision detection etc) + // time = distance / speed + f32 dtime_max_increment = 1.0; + if(speed_f.getLength() != 0) + dtime_max_increment = pos_max_d / speed_f.getLength(); + + // Maximum time increment is 10ms or lower + if(dtime_max_increment > 0.01) + dtime_max_increment = 0.01; + f32 dtime_part; if(dtime_downcount > dtime_max_increment) { @@ -242,17 +487,20 @@ collisionMoveResult collisionMovePrecise(Map *map, IGameDef *gamedef, } collisionMoveResult result = collisionMoveSimple(map, gamedef, - pos_max_d, box_0, dtime_part, pos_f, speed_f); + pos_max_d, box_0, stepheight, dtime_part, + pos_f, speed_f, accel_f); if(result.touching_ground) final_result.touching_ground = true; if(result.collides) final_result.collides = true; + if(result.collides_xz) + final_result.collides_xz = true; + if(result.standing_on_unloaded) + final_result.standing_on_unloaded = true; } while(dtime_downcount > 0.001); - return final_result; } - - +#endif -- cgit v1.2.3