+// $Id$
+//
+// SuperTux
+// Copyright (C) 2005 Matthias Braun <matze@braunis.de>
//
-// C Implementation: collision
-//
-// Description:
-//
-//
-// Author: Tobias Glaesser <tobi.web@gmx.de>, (C) 2004
-//
-// Copyright: See COPYING file that comes with this distribution
-//
+// This program is free software; you can redistribute it and/or
+// modify it under the terms of the GNU General Public License
+// as published by the Free Software Foundation; either version 2
+// of the License, or (at your option) any later version.
//
+// This program is distributed in the hope that it will be useful,
+// 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 <config.h>
-#include "defines.h"
#include "collision.h"
-#include "bitmask.h"
-#include "scene.h"
-
-int rectcollision(base_type* one, base_type* two)
-{
-
- if (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)
- {
- return YES;
- }
- else
- {
- return NO;
- }
-}
-
-int rectcollision_offset(base_type* one, base_type* two, float off_x, float off_y)
-{
- if (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)
- {
- return YES;
- }
- else
- {
- return NO;
- }
-}
-int collision_object_map(base_type* pbase)
+#include <algorithm>
+#include <iostream>
+#include <stdio.h>
+#include <float.h>
+#include <math.h>
+#include "math/vector.h"
+#include "math/aatriangle.h"
+#include "math/rect.h"
+#include "collision_hit.h"
+
+static const float DELTA = .0001;
+
+bool
+Collision::rectangle_rectangle(CollisionHit& hit, const Rect& r1,
+ const Vector& movement, const Rect& r2)
{
- int v,h,i;
-
- v = (int)pbase->height / 16;
- h = (int)pbase->width / 16;
-
- 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 YES;
-
- for(i = 1; i < h; ++i)
- {
- if(issolid(pbase->x + i*16,pbase->y + 1))
- return YES;
- }
-
- for(i = 1; i < h; ++i)
- {
- if( issolid(pbase->x + i*16,pbase->y + pbase->height - 1))
- return YES;
- }
-
- for(i = 1; i < v; ++i)
- {
- if( issolid(pbase->x + 1, pbase->y + i*16))
- return YES;
- }
- for(i = 1; i < v; ++i)
- {
- if( issolid(pbase->x + pbase->width - 1, pbase->y + i*16))
- return YES;
- }
-
- return NO;
+ 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(movement.x > DELTA) {
+ hit.depth = r1.p2.x - r2.p1.x;
+ hit.time = hit.depth / movement.x;
+ hit.normal.x = -1;
+ hit.normal.y = 0;
+ } else if(movement.x < -DELTA) {
+ hit.depth = r2.p2.x - r1.p1.x;
+ hit.time = hit.depth / -movement.x;
+ hit.normal.x = 1;
+ hit.normal.y = 0;
+ } else {
+ if(movement.y > -DELTA && movement.y < DELTA) {
+ hit.time = 0;
+ hit.depth = 0;
+ hit.normal.x = 1;
+ hit.normal.y = 0;
+ return true;
+ }
+ hit.time = FLT_MAX;
+ }
+
+ if(movement.y > DELTA) {
+ float ydepth = r1.p2.y - r2.p1.y;
+ float yt = ydepth / movement.y;
+ if(yt < hit.time) {
+ hit.depth = ydepth;
+ hit.time = yt;
+ hit.normal.x = 0;
+ hit.normal.y = -1;
+ }
+ } else if(movement.y < -DELTA) {
+ float ydepth = r2.p2.y - r1.p1.y;
+ float yt = ydepth / -movement.y;
+ if(yt < hit.time) {
+ hit.depth = ydepth;
+ hit.time = yt;
+ hit.normal.x = 0;
+ hit.normal.y = 1;
+ }
+ }
+
+ return true;
}
+//---------------------------------------------------------------------------
-int collision_swept_object_map(base_type* old, base_type* current)
+static void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
{
- int steps; /* Used to speed up the collision tests, by stepping every 16pixels in the path. */
- int h;
- float i;
- 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(old->x == current->x && old->y == current->y)
- {
- return 0;
- }
- 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;
- }
-
- h = 1;
- xd = 0;
-
- }
- 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(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;
- }
- }
-
- *old = *current;
-return 0;
+ n = Vector(p2.y-p1.y, p1.x-p2.x);
+ c = -(p2 * n);
+ float nval = n.norm();
+ n /= nval;
+ c /= nval;
}
-void collision_handler()
+bool
+Collision::rectangle_aatriangle(CollisionHit& hit, const Rect& rect,
+ const Vector& movement, const AATriangle& triangle)
{
- int i,j;
-
- /* CO_BULLET & CO_BADGUY check */
- for(i = 0; i < num_bullets; ++i)
- {
- if(bullets[i].base.alive)
- {
- for(j = 0; j < num_bad_guys; ++j)
- {
- if(bad_guys[j].dying == NO && bad_guys[j].base.alive)
- {
- if(rectcollision(&bullets[i].base,&bad_guys[j].base) == YES)
- {
- /* We have detected a collision and now call the collision functions of the collided objects. */
- bullet_collision(&bullets[i], CO_BADGUY);
- badguy_collision(&bad_guys[j], &bullets[i], CO_BULLET);
- }
- }
- }
- }
- }
-
- /* CO_BADGUY & CO_BADGUY check */
- for(i = 0; i < num_bad_guys; ++i)
- {
- if(bad_guys[i].base.alive && bad_guys[i].dying == NO)
- {
- for(j = i+1; j < num_bad_guys; ++j)
- {
- if(j != i && bad_guys[j].base.alive && bad_guys[j].dying == NO)
- {
- if(rectcollision(&bad_guys[i].base,&bad_guys[j].base) == YES)
- {
- /* We have detected a collision and now call the collision functions of the collided objects. */
- badguy_collision(&bad_guys[j], &bad_guys[i], CO_BADGUY);
- badguy_collision(&bad_guys[i], &bad_guys[j], CO_BADGUY);
- }
- }
- }
- }
- }
-
-
-
- /* CO_BADGUY & CO_PLAYER check */
- for(i = 0; i < num_bad_guys; ++i)
- {
- if(bad_guys[i].base.alive)
- {
- if(bad_guys[i].dying == NO && rectcollision_offset(&bad_guys[i].base,&tux.base,0,0) == YES )
- {
- /* We have detected a collision and now call the collision functions of the collided objects. */
- if (tux.previous_base.y < tux.base.y &&
- tux.previous_base.y + tux.previous_base.height < bad_guys[i].base.y + bad_guys[i].base.height/2 &&
- bad_guys[i].kind != BAD_MONEY && bad_guys[i].mode != HELD)
- {
- badguy_collision(&bad_guys[i], &tux, CO_PLAYER);
- }
- else
- {
- player_collision(&tux, &bad_guys[i], CO_BADGUY);
- }
- }
- }
- }
-
- /* CO_UPGRADE & CO_PLAYER check */
- for(i = 0; i < num_upgrades; ++i)
- {
- if(upgrades[i].base.alive)
- {
- if(rectcollision(&upgrades[i].base,&tux.base) == YES)
- {
- /* We have detected a collision and now call the collision functions of the collided objects. */
- upgrade_collision(&upgrades[i], &tux, CO_PLAYER);
- }
-
- }
- }
-
+ if(!rectangle_rectangle(hit, rect, movement, (const Rect&) triangle))
+ return false;
+
+ Vector normal;
+ float c;
+ Vector p1;
+ Vector tp1, tp2;
+ switch(triangle.dir & AATriangle::DEFORM_MASK) {
+ case 0:
+ tp1 = triangle.p1;
+ tp2 = triangle.p2;
+ break;
+ case AATriangle::DEFORM1:
+ tp1 = Vector(triangle.p1.x, triangle.p1.y + triangle.get_height()/2);
+ tp2 = triangle.p2;
+ break;
+ case AATriangle::DEFORM2:
+ tp1 = triangle.p1;
+ tp2 = Vector(triangle.p2.x, triangle.p1.y + triangle.get_height()/2);
+ break;
+ case AATriangle::DEFORM3:
+ tp1 = triangle.p1;
+ tp2 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p2.y);
+ break;
+ case AATriangle::DEFORM4:
+ tp1 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p1.y);
+ tp2 = triangle.p2;
+ break;
+ default:
+ assert(false);
+ }
+
+ switch(triangle.dir & AATriangle::DIRECTION_MASK) {
+ case AATriangle::SOUTHWEST:
+ p1 = Vector(rect.p1.x, rect.p2.y);
+ makePlane(tp1, tp2, normal, c);
+ break;
+ case AATriangle::NORTHEAST:
+ p1 = Vector(rect.p2.x, rect.p1.y);
+ makePlane(tp2, tp1, normal, c);
+ break;
+ case AATriangle::SOUTHEAST:
+ p1 = rect.p2;
+ makePlane(Vector(tp1.x, tp2.y),
+ Vector(tp2.x, tp1.y), normal, c);
+ break;
+ case AATriangle::NORTHWEST:
+ p1 = rect.p1;
+ makePlane(Vector(tp2.x, tp1.y),
+ Vector(tp1.x, tp2.y), normal, c);
+ break;
+ default:
+ assert(false);
+ }
+
+ float n_p1 = -(normal * p1);
+ float depth = n_p1 - c;
+ if(depth < 0)
+ return false;
+ float time = depth / -(normal * movement);
+ if(time < hit.time) {
+ hit.depth = depth;
+ hit.time = time;
+ hit.normal = normal;
+ }
+
+ return true;
}
-