// $Id$
-//
+//
// SuperTux
-// Copyright (C) 2004 Tobias Glaesser <tobi.web@gmx.de>
+// Copyright (C) 2006 Matthias Braun <matze@braunis.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
-//
+//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
-
-#include "defines.h"
-#include "collision.h"
-#include "bitmask.h"
-#include "scene.h"
-#include "world.h"
-#include "level.h"
-#include "tile.h"
-
-bool rectcollision(const base_type& one, const base_type& two)
+#include <config.h>
+
+#include "collision.hpp"
+
+#include <algorithm>
+#include <iostream>
+#include <stdio.h>
+#include <float.h>
+#include <math.h>
+#include "math/vector.hpp"
+#include "math/aatriangle.hpp"
+#include "math/rect.hpp"
+#include "collision_hit.hpp"
+#include "log.hpp"
+
+namespace collision
{
- return (one.x >= two.x - one.width + 1 &&
- one.x <= two.x + two.width - 1 &&
- one.y >= two.y - one.height + 1 &&
- one.y <= two.y + two.height - 1);
-}
-
-bool rectcollision_offset(const base_type& one, const base_type& two, float off_x, float off_y)
-{
- return (one.x >= two.x - one.width + off_x + 1 &&
- one.x <= two.x + two.width + off_x - 1 &&
- one.y >= two.y - one.height + off_y + 1 &&
- one.y <= two.y + two.height + off_y - 1);
-}
-bool collision_object_map(const base_type& pbase)
+bool intersects(const Rect& r1, const Rect& r2)
{
- int v = (int)pbase.height / 16;
- int h = (int)pbase.width / 16;
+ if(r1.p2.x < r2.p1.x || r1.p1.x > r2.p2.x)
+ return false;
+ if(r1.p2.y < r2.p1.y || r1.p1.y > r2.p2.y)
+ return false;
- if(issolid(pbase.x + 1, pbase.y + 1) ||
- issolid(pbase.x + pbase.width -1, pbase.y + 1) ||
- issolid(pbase.x +1, pbase.y + pbase.height -1) ||
- issolid(pbase.x + pbase.width -1, pbase.y + pbase.height - 1))
- return true;
-
- for(int i = 1; i < h; ++i)
- {
- if(issolid(pbase.x + i*16,pbase.y + 1))
- return true;
- }
-
- for(int i = 1; i < h; ++i)
- {
- if( issolid(pbase.x + i*16,pbase.y + pbase.height - 1))
- return true;
- }
-
- for(int i = 1; i < v; ++i)
- {
- if( issolid(pbase.x + 1, pbase.y + i*16))
- return true;
- }
- for(int i = 1; i < v; ++i)
- {
- if( issolid(pbase.x + pbase.width - 1, pbase.y + i*16))
- return true;
- }
-
- return false;
+ return true;
}
-void* collision_func(const base_type& base, tiletestfunction function)
-{
- for(float x = base.x; x < base.x + base.width; x += 32) {
- for(float y = base.y; y < base.y + base.height; y += 32) {
- Tile* tile = gettile(x, y);
- void* result = function(tile);
- if(result != 0)
- return result;
- }
- }
+//---------------------------------------------------------------------------
- return 0;
-}
-
-static void* test_goal_tile_function(Tile* tile)
-{
- if(tile && tile->goal)
- return tile;
- return 0;
-}
+namespace {
+ inline void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
+ {
+ n = Vector(p2.y-p1.y, p1.x-p2.x);
+ c = -(p2 * n);
+ float nval = n.norm();
+ n /= nval;
+ c /= nval;
+ }
-Tile* collision_goal(const base_type& base)
-{
- return (Tile*) collision_func(base, test_goal_tile_function);
+ static const float DELTA = .0001f;
}
-void collision_swept_object_map(base_type* old, base_type* current)
+bool rectangle_aatriangle(Constraints* constraints, const Rect& rect,
+ const AATriangle& triangle, const Vector& addl_ground_movement)
{
- int steps; /* Used to speed up the collision tests, by stepping every 16pixels in the path. */
- int h;
- float lpath; /* Holds the longest path, which is either in X or Y direction. */
- float xd,yd; /* Hold the smallest steps in X and Y directions. */
- float temp, xt, yt; /* Temporary variable. */
-
- lpath = 0;
- xd = 0;
- yd = 0;
+ if(!intersects(rect, (const Rect&) triangle))
+ return false;
+
+ Vector normal;
+ float c;
+ Vector p1;
+ Rect area;
+ switch(triangle.dir & AATriangle::DEFORM_MASK) {
+ case 0:
+ area.p1 = triangle.p1;
+ area.p2 = triangle.p2;
+ break;
+ case AATriangle::DEFORM1:
+ area.p1 = Vector(triangle.p1.x, triangle.p1.y + triangle.get_height()/2);
+ area.p2 = triangle.p2;
+ break;
+ case AATriangle::DEFORM2:
+ area.p1 = triangle.p1;
+ area.p2 = Vector(triangle.p2.x, triangle.p1.y + triangle.get_height()/2);
+ break;
+ case AATriangle::DEFORM3:
+ area.p1 = triangle.p1;
+ area.p2 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p2.y);
+ break;
+ case AATriangle::DEFORM4:
+ area.p1 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p1.y);
+ area.p2 = triangle.p2;
+ break;
+ default:
+ assert(false);
+ }
- if(old->x == current->x && old->y == current->y)
- {
- return;
- }
- else if(old->x == current->x && old->y != current->y)
- {
- lpath = current->y - old->y;
- if(lpath < 0)
- {
- yd = -1;
- lpath = -lpath;
- }
- else
- {
- yd = 1;
- }
+ switch(triangle.dir & AATriangle::DIRECTION_MASK) {
+ case AATriangle::SOUTHWEST:
+ p1 = Vector(rect.p1.x, rect.p2.y);
+ makePlane(area.p1, area.p2, normal, c);
+ break;
+ case AATriangle::NORTHEAST:
+ p1 = Vector(rect.p2.x, rect.p1.y);
+ makePlane(area.p2, area.p1, normal, c);
+ break;
+ case AATriangle::SOUTHEAST:
+ p1 = rect.p2;
+ makePlane(Vector(area.p1.x, area.p2.y),
+ Vector(area.p2.x, area.p1.y), normal, c);
+ break;
+ case AATriangle::NORTHWEST:
+ p1 = rect.p1;
+ makePlane(Vector(area.p2.x, area.p1.y),
+ Vector(area.p1.x, area.p2.y), normal, c);
+ break;
+ default:
+ assert(false);
+ }
- h = 1;
- xd = 0;
+ float n_p1 = -(normal * p1);
+ float depth = n_p1 - c;
+ if(depth < 0)
+ return false;
+
+#if 0
+ std::cout << "R: " << rect << " Tri: " << triangle << "\n";
+ std::cout << "Norm: " << normal << " Depth: " << depth << "\n";
+#endif
+
+ Vector outvec = normal * (depth + 0.2f);
+
+ const float RDELTA = 3;
+ if(p1.x < area.p1.x - RDELTA || p1.x > area.p2.x + RDELTA
+ || p1.y < area.p1.y - RDELTA || p1.y > area.p2.y + RDELTA) {
+ set_rectangle_rectangle_constraints(constraints, rect, area);
+ constraints->hit.left = false;
+ constraints->hit.right = false;
+ } else {
+ if(outvec.x < 0) {
+ constraints->right = rect.get_right() + outvec.x;
+ } else {
+ constraints->left = rect.get_left() + outvec.x;
}
- else if(old->x != current->x && old->y == current->y)
- {
- lpath = current->x - old->x;
- if(lpath < 0)
- {
- xd = -1;
- lpath = -lpath;
- }
- else
- {
- xd = 1;
- }
- h = 2;
- yd = 0;
- }
- else
- {
- lpath = current->x - old->x;
- if(lpath < 0)
- lpath = -lpath;
- if(current->y - old->y > lpath || old->y - current->y > lpath)
- lpath = current->y - old->y;
- if(lpath < 0)
- lpath = -lpath;
- h = 3;
- xd = (current->x - old->x) / lpath;
- yd = (current->y - old->y) / lpath;
- }
-
- steps = (int)(lpath / (float)16);
-
- old->x += xd;
- old->y += yd;
-
- for(float i = 0; i <= lpath; old->x += xd, old->y += yd, ++i)
- {
- if(steps > 0)
- {
- old->y += yd*16.;
- old->x += xd*16.;
- steps--;
- }
-
- if(collision_object_map(*old))
- {
- switch(h)
- {
- case 1:
- current->y = old->y - yd;
- while(collision_object_map(*current))
- current->y -= yd;
- break;
- case 2:
- current->x = old->x - xd;
- while(collision_object_map(*current))
- current->x -= xd;
- break;
- case 3:
- xt = current->x;
- yt = current->y;
- current->x = old->x - xd;
- current->y = old->y - yd;
- while(collision_object_map(*current))
- {
- current->x -= xd;
- current->y -= yd;
- }
-
- temp = current->x;
- current->x = xt;
- if(!collision_object_map(*current))
- break;
- current->x = temp;
- temp = current->y;
- current->y = yt;
-
- if(!collision_object_map(*current))
- {
- break;
- }
- else
- {
- current->y = temp;
- while(!collision_object_map(*current))
- current->y += yd;
- current->y -= yd;
- break;
- }
- break;
- default:
- break;
- }
- break;
- }
+ if(outvec.y < 0) {
+ constraints->bottom = rect.get_bottom() + outvec.y;
+ constraints->hit.bottom = true;
+ constraints->ground_movement += addl_ground_movement;
+ } else {
+ constraints->top = rect.get_top() + outvec.y;
+ constraints->hit.top = true;
}
+ constraints->hit.slope_normal = normal;
+ }
- *old = *current;
-}
-
-
-Tile* gettile(float x, float y)
-{
- return TileManager::instance()->get(World::current()->get_level()->gettileid(x, y));
-}
-
-bool issolid(float x, float y)
-{
- Tile* tile = gettile(x,y);
- return tile && tile->solid;
-}
-
-bool isbrick(float x, float y)
-{
- Tile* tile = gettile(x,y);
- return tile && tile->brick;
-}
-
-bool isice(float x, float y)
-{
- Tile* tile = gettile(x,y);
- return tile && tile->ice;
+ return true;
}
-bool isfullbox(float x, float y)
+void set_rectangle_rectangle_constraints(Constraints* constraints,
+ const Rect& r1, const Rect& r2, const Vector& addl_ground_movement)
{
- Tile* tile = gettile(x,y);
- return tile && tile->fullbox;
+ float itop = r1.get_bottom() - r2.get_top();
+ float ibottom = r2.get_bottom() - r1.get_top();
+ float ileft = r1.get_right() - r2.get_left();
+ float iright = r2.get_right() - r1.get_left();
+
+ float vert_penetration = std::min(itop, ibottom);
+ float horiz_penetration = std::min(ileft, iright);
+ if(vert_penetration < horiz_penetration) {
+ if(itop < ibottom) {
+ constraints->bottom = std::min(constraints->bottom, r2.get_top());
+ constraints->hit.bottom = true;
+ constraints->ground_movement += addl_ground_movement;
+ } else {
+ constraints->top = std::max(constraints->top, r2.get_bottom());
+ constraints->hit.top = true;
+ }
+ } else {
+ if(ileft < iright) {
+ constraints->right = std::min(constraints->right, r2.get_left());
+ constraints->hit.right = true;
+ } else {
+ constraints->left = std::max(constraints->left, r2.get_right());
+ constraints->hit.left = true;
+ }
+ }
}
-bool isdistro(float x, float y)
-{
- Tile* tile = gettile(x,y);
- return tile && tile->distro;
}
-
-/* EOF */
-
-