summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ChangeLog10
-rw-r--r--src/Makefile.am2
-rw-r--r--src/game-server/being.cpp60
-rw-r--r--src/game-server/collisiondetection.cpp138
-rw-r--r--src/game-server/collisiondetection.hpp27
-rw-r--r--src/game-server/main-game.cpp4
-rw-r--r--src/utils/fastsqrt.h23
-rw-r--r--src/utils/mathutils.cpp106
-rw-r--r--src/utils/mathutils.h46
9 files changed, 350 insertions, 66 deletions
diff --git a/ChangeLog b/ChangeLog
index c7044ee3..f41c6804 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2007-03-03 Rogier Polak <rogier.l.a.polak@gmail.com>
+
+ * src/utils/mathutils.h, src/utils/mathutils.cpp,
+ src/utils/fastsqrt.h, src/Makefile.am, src/game-server/main-game.cpp:
+ Moved math utility functions to the namespace utils::math, added
+ cached trigonomic functions.
+ * src/game-server/collisiondetection.hpp, src/game-server/being.cpp,
+ src/game-server/collisiondetection.cpp: Implemented an alternate
+ collision-detection function, for disks and circle-sectors.
+
2007-03-03 Philipp Sehmisch <tmw@crushnet.org>
* src/controller.cpp, src/controller.h, src/defines.h,
diff --git a/src/Makefile.am b/src/Makefile.am
index 869471ad..56897e40 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -114,6 +114,8 @@ tmwserv_game_SOURCES = \
net/netcomputer.cpp \
utils/base64.h \
utils/base64.cpp \
+ utils/mathutils.h \
+ utils/mathutils.cpp \
utils/logger.h \
utils/logger.cpp \
utils/stringfilter.h \
diff --git a/src/game-server/being.cpp b/src/game-server/being.cpp
index 6924f3b9..046423d6 100644
--- a/src/game-server/being.cpp
+++ b/src/game-server/being.cpp
@@ -21,11 +21,11 @@
*/
#include "game-server/being.hpp"
+
#include "game-server/collisiondetection.hpp"
#include "game-server/mapcomposite.hpp"
#include "utils/logger.h"
-#include <cmath>
void Being::damage(Damage damage)
{
@@ -71,54 +71,48 @@ void Being::move()
void Being::performAttack(MapComposite *map)
{
int SHORT_RANGE = 32;
- float SMALL_ANGLE = M_PI_2;
+ int SMALL_ANGLE = 15;
Point ppos = getPosition();
int dir = getDirection();
- /* TODO: calculate real attack power and damage properties based on
+ int attackAngle = 0;
+
+ switch (dir)
+ {
+ case DIRECTION_UP:
+ attackAngle = 90;
+ break;
+ case DIRECTION_DOWN:
+ attackAngle = 270;
+ break;
+ case DIRECTION_LEFT:
+ attackAngle = 180;
+ break;
+ case DIRECTION_RIGHT:
+ attackAngle = 0;
+ break;
+ default:
+ break;
+ }
+
+/* TODO: calculate real attack power and damage properties based on
character equipment and stats. */
Damage damage = 1;
for (MovingObjectIterator i(map->getAroundObjectIterator(this, SHORT_RANGE)); i; ++i)
{
MovingObject *o = *i;
- if (o == this)
- {
- continue;
- }
+ if (o == this) continue;
int type = o->getType();
- if (type != OBJECT_PLAYER && type != OBJECT_MONSTER)
- {
- continue;
- }
+ if (type != OBJECT_PLAYER && type != OBJECT_MONSTER) continue;
Point opos = o->getPosition();
- float attackAngle = 0.0f;
- // basic triangle-shaped damage zone
- switch (dir)
- {
- case DIRECTION_UP:
- attackAngle = M_PI_2;
- break;
- case DIRECTION_DOWN:
- attackAngle = - M_PI_2;
- break;
- case DIRECTION_LEFT:
- attackAngle = M_PI;
- break;
- case DIRECTION_RIGHT:
- attackAngle = 0.0f;
- break;
- default:
- break;
- }
-
- if (Collision::circleWithCirclesector(
+ if (Collision::diskWithCircleSector(
opos, o->getSize(),
- ppos, SHORT_RANGE, attackAngle, SMALL_ANGLE)
+ ppos, SHORT_RANGE, SMALL_ANGLE, attackAngle)
)
{
static_cast< Being * >(o)->damage(damage);
diff --git a/src/game-server/collisiondetection.cpp b/src/game-server/collisiondetection.cpp
index 8fdd50e5..6297e3d6 100644
--- a/src/game-server/collisiondetection.cpp
+++ b/src/game-server/collisiondetection.cpp
@@ -17,26 +17,27 @@
* with The Mana World; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
- * $Id: being.cpp 3010 2007-01-05 20:12:51Z gmelquio $
+ * $Id: $
*/
#include "collisiondetection.hpp"
-#include "point.h"
-
#include <cmath>
-#include "utils/fastsqrt.h"
+
+#include "point.h"
+#include "utils/mathutils.h"
bool
Collision::circleWithCirclesector( const Point& circlePos, int circleRadius,
- const Point& secPos, int secRadius, float secAngle, float secSize)
+ const Point& secPos, int secRadius,
+ float secAngle, float secSize)
{
float targetAngle;
//calculate distance
int distX = circlePos.x - secPos.x;
int distY = circlePos.y - secPos.y;
- float invDist = fastInvSqrt(distX * distX + distY * distY);
+ float invDist = utils::math::fastInvSqrt(distX * distX + distY * distY);
float dist = 1.0f / invDist;
//if out of range we can't hit it
@@ -75,3 +76,128 @@ Collision::circleWithCirclesector( const Point& circlePos, int circleRadius,
return (targetDiff < secSize * 0.5f);
}
+
+/**
+ * Collision of a Disk with a Circle-Sector
+ *
+ * For a detailled explanation of this function please see:
+ * http://wiki.themanaworld.org/index.php/Collision_determination
+ */
+bool
+Collision::diskWithCircleSector(const Point &diskCenter, int diskRadius,
+ const Point &sectorCenter, int sectorRadius,
+ int halfTopAngle, int placeAngle)
+{
+ //The coordinates of the diskcenter the base coordinate systems and an
+ //alternate coordinate system
+ float Px, Py, Px1, Py1,
+ distAx, distAy, distBx, distBy;
+
+ //Converting the radii to float
+ float R = (float) sectorRadius;
+ float Rp = (float) diskRadius;
+
+ //The values of the trigonomic functions (only have to be computed once)
+ float sinAlpha, cosAlpha, sinBeta, cosBeta, tan2Alpha;
+
+ //Transform to the primary coordinate system
+ Px = diskCenter.x - sectorCenter.x;
+ Py = diskCenter.y - sectorCenter.y;
+
+ //Calculating the values of the trigonomic functions
+ sinAlpha = utils::math::cachedSin(halfTopAngle);
+ cosAlpha = utils::math::cachedCos(halfTopAngle);
+ sinBeta = utils::math::cachedSin(placeAngle);
+ cosBeta = utils::math::cachedCos(placeAngle);
+
+ /**
+ * This bounding circle implementation can be used up and until a
+ * half-top-angle of +/- 85 degrees. The bounding circle becomes
+ * infinitly large at 90 degrees. Above about 60 degrees a bounding
+ * half-circle with radius R becomes more efficient.
+ * (The additional check for a region 1 collision can then be scrapped.)
+ */
+
+ // Calculating the coordinates of the disk's center in coordinate system 4
+ Px1 = Px * cosBeta + Py * sinBeta;
+ Py1 = Py * cosBeta - Px * sinBeta;
+
+ //Check for an intersection with the bounding circle
+ // (>) : touching is accepted
+ if ((cosAlpha * Px1 * Px1 + cosAlpha * Py1 * Py1 - Px1 * R)
+ > (Rp * Rp * cosAlpha + Rp * R)) return false;
+
+ //Check for a region 4 collision
+ if ((Px*Px + Py*Py) <= (Rp*Rp)) return true;
+
+ //Calculating the coordinates of the disk's center in coordinate system 1
+ Px1 = Px * (cosAlpha * cosBeta + sinAlpha * sinBeta)
+ + Py * (cosAlpha * sinBeta - sinAlpha * cosBeta);
+ Py1 = Py * (cosAlpha * cosBeta + sinAlpha * sinBeta)
+ - Px * (cosAlpha * sinBeta - sinAlpha * cosBeta);
+
+ //Check if P is in region 5 (using coordinate system 1)
+ if ((Px1 >= 0.0f) && (Px1 <= R) && (Py1 <= 0.0f))
+ {
+ //Return true on intersection, false otherwise
+ // (>=) : touching is accepted
+ return (Py1 >= -1.0f * Rp);
+ }
+
+ //Check if P is in region 3 (using coordinate system 1)
+ if ((Px1 > R) && (Py1 <= 0.0f))
+ {
+ //Calculating the vector from point A to the disk center
+ distAx = Px - R * (cosAlpha*cosBeta + sinAlpha*sinBeta);
+ distAy = Py - R * (cosAlpha*sinBeta - sinAlpha*cosBeta);
+
+ //Check for a region 3 collision
+ return ((distAx*distAx + distAy*distAy) <= Rp*Rp);
+ }
+
+ //Discard, if P is in region 4 (was previously checked)
+ if ((Px1 < 0.0f) && (Py1 <= 0.0f)) return false;
+
+ tan2Alpha = utils::math::cachedTan(2 * halfTopAngle);
+
+ //Check if P is in region 1 (using coordinate system 1)
+ if ((Px1 >= 0.0f) && (Py1 >= 0.0f) && (Py1 <= Px1 * tan2Alpha))
+ {
+ //Return true on intersection, false otherwise
+ // (<=) : touching is accepted
+ return ((Px*Px + Py*Py) <= (R*R + Rp*Rp + 2.0f*R*Rp));
+ }
+
+ //Calculating the coordinates of the disk's center in coordinate system 3
+ Px1 = Px * (cosAlpha * cosBeta - sinAlpha * sinBeta)
+ + Py * (sinAlpha * cosBeta + cosAlpha * sinBeta);
+ Py1 = Py * (cosAlpha * cosBeta - sinAlpha * sinBeta)
+ - Px * (sinAlpha * cosBeta + cosAlpha * sinBeta);
+
+ //Discard, if P is in region 4 (was previously checked)
+ if ((Px1 < 0.0f) && (Py1 >= 0.0f)) return false;
+
+ //Check if P is in region 6 (using coordinate system 3)
+ if ((Px1 >= 0.0f) && (Px1 <= R) && (Py1 >= 0.0f))
+ {
+ //Return true on intersection, false otherwise
+ // (<=) : touching is accepted
+ return (Py1 <= Rp);
+ }
+
+ //Check if P is in region 2 (using coordinate system 3)
+ if ((Px1 > R) && (Py1 <= 0.0f))
+ {
+ //Calculating the vector from point B to the disk center
+ distBx = Px - R * (cosAlpha*cosBeta - sinAlpha*sinBeta);
+ distBy = Py - R * (cosAlpha*sinBeta + sinAlpha*cosBeta);
+
+ //Check for a region 2 collision
+ return ((distBx*distBx + distBy*distBy) <= (Rp*Rp));
+ }
+
+ // The intersection with the bounding circle is in region 4,
+ // but the disk and circle sector don't intersect.
+ return false;
+}
+
diff --git a/src/game-server/collisiondetection.hpp b/src/game-server/collisiondetection.hpp
index 9f5c0fa4..88631031 100644
--- a/src/game-server/collisiondetection.hpp
+++ b/src/game-server/collisiondetection.hpp
@@ -17,18 +17,37 @@
* with The Mana World; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
- * $Id: object.hpp 3098 2007-02-01 20:12:27Z b_lindeijer $
+ * $Id: $
*/
+#ifndef _TMW_COLLISIONDETECTION_H
+#define _TMW_COLLISIONDETECTION_H
+
class Point;
/**
- * This namespace collects all collision detection functions we need
+ * This namespace collects all needed collision detection functions
*/
namespace Collision
{
bool
- circleWithCirclesector( const Point &circlePos, int circleRadius,
- const Point &secPos, int secRadius, float secAngle, float secSize);
+ circleWithCirclesector(const Point &circlePos, int circleRadius,
+ const Point &secPos, int secRadius,
+ float secAngle, float secSize);
+ /**
+ * Checks if a disk and a circle-sector collide
+ *
+ * @param halfTopAngle
+ * The half-top-angle of the circle sector in degrees (0,359).
+ * @param placeAngle
+ * The placement-angle of the circle sector in degrees (0,359).
+ */
+ bool
+ diskWithCircleSector(const Point &diskCenter, int diskRadius,
+ const Point &sectorCenter, int sectorRadius,
+ int halfTopAngle, int placeAngle);
+
};
+
+#endif
diff --git a/src/game-server/main-game.cpp b/src/game-server/main-game.cpp
index 6383a9ec..831dc9f1 100644
--- a/src/game-server/main-game.cpp
+++ b/src/game-server/main-game.cpp
@@ -44,6 +44,7 @@
#include "utils/logger.h"
#include "utils/stringfilter.h"
#include "utils/timer.h"
+#include "utils/mathutils.h"
// Scripting
#ifdef SCRIPT_SUPPORT
@@ -206,6 +207,9 @@ void initialize()
#else
LOG_WARN("No scripting language support.");
#endif
+
+ // Pre-calulate the needed trigomic function values
+ utils::math::init();
}
diff --git a/src/utils/fastsqrt.h b/src/utils/fastsqrt.h
deleted file mode 100644
index 8ba6f8ce..00000000
--- a/src/utils/fastsqrt.h
+++ /dev/null
@@ -1,23 +0,0 @@
-/* A very fast function to calculate the approximate inverse square root of a
- * floating point value and a helper function that uses it for getting the
- * normal squareroot. For an explanation of the inverse squareroot function
- * read:
- * http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf
- *
- * Unfortunately the original creator of this function seems to be unknown.
- */
-
-float fastInvSqrt(float x)
-{
- float xhalf = 0.5f*x;
- int i = *(int*)&x;
- i = 0x5f375a86- (i>>1);
- x = *(float*)&i;
- x = x*(1.5f-xhalf*x*x);
- return x;
-}
-
-float fastSqrt(float x)
-{
- return 1.0f/fastInvSqrt(x);
-}
diff --git a/src/utils/mathutils.cpp b/src/utils/mathutils.cpp
new file mode 100644
index 00000000..0a46ff2c
--- /dev/null
+++ b/src/utils/mathutils.cpp
@@ -0,0 +1,106 @@
+/*
+ * The Mana World Server
+ * Copyright 2004 The Mana World Development Team
+ *
+ * This file is part of The Mana World.
+ *
+ * The Mana World 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 any later version.
+ *
+ * The Mana World 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 The Mana World; if not, write to the Free Software Foundation, Inc.,
+ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * $Id: $
+ */
+
+#include "mathutils.h"
+
+#include <cmath>
+
+#define MATH_UTILS_MAX_ANGLE 360
+
+float sinList[MATH_UTILS_MAX_ANGLE];
+float cosList[MATH_UTILS_MAX_ANGLE];
+float tanList[MATH_UTILS_MAX_ANGLE];
+
+/**
+ * fastInvSqrt:
+ *
+ * A very fast function to calculate the approximate inverse square root of a
+ * floating point value. For an explanation of the inverse squareroot function
+ * read:
+ * http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf
+ *
+ * Unfortunately the original creator of this function seems to be unknown.
+ *
+ * TODO: - Make this function run on 64-bit architectures
+ * - Find out and fix why this function fails when compiled with the -O2
+ * optimization flag on
+ * gcc version 4.0.2 20050808 (prerelease) (Ubuntu 4.0.1-4ubuntu9).
+ */
+float utils::math::fastInvSqrt(float x)
+{
+ float xhalf = 0.5f*x;
+ int i = *(int*)&x;
+ i = 0x5f375a86- (i>>1);
+ x = *(float*)&i;
+ x = x*(1.5f-xhalf*x*x);
+ return x;
+}
+
+/**
+ * fastSqrt:
+ *
+ * A helper function that uses the fastInvSqrt for getting the
+ * normal squareroot.
+ */
+float utils::math::fastSqrt(float x)
+{
+ return 1.0f/utils::math::fastInvSqrt(x);
+}
+
+void utils::math::init()
+{
+ // Constant for calculating an angle in radians out of an angle in degrees
+ const float radianAngleRatio = acos(0.0f) / 90.0f; // pi/2 / 90[deg]
+
+ for(int i = 0; i < MATH_UTILS_MAX_ANGLE; i++)
+ {
+ sinList[i] = sin(radianAngleRatio * (float)i);
+ cosList[i] = cos(radianAngleRatio * (float)i);
+
+ if (i == 90)
+ {
+ tanList[i] = 1.0E40f; //approximately infinity
+ continue;
+ }
+ if (i == 270)
+ {
+ tanList[i] = -1.0E40f; //approximately infinity
+ continue;
+ }
+ tanList[i] = tan(radianAngleRatio * (float)i);
+ }
+}
+
+float utils::math::cachedSin(int angle)
+{
+ return sinList[angle];
+}
+
+float utils::math::cachedCos(int angle)
+{
+ return cosList[angle];
+}
+
+float utils::math::cachedTan(int angle)
+{
+ return tanList[angle];
+}
diff --git a/src/utils/mathutils.h b/src/utils/mathutils.h
new file mode 100644
index 00000000..3d90b022
--- /dev/null
+++ b/src/utils/mathutils.h
@@ -0,0 +1,46 @@
+/*
+ * The Mana World Server
+ * Copyright 2004 The Mana World Development Team
+ *
+ * This file is part of The Mana World.
+ *
+ * The Mana World 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 any later version.
+ *
+ * The Mana World 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 The Mana World; if not, write to the Free Software Foundation, Inc.,
+ * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * $Id: $
+ */
+
+#ifndef _TMWSERV_MATHUTILS_H_
+#define _TMWSERV_MATHUTILS_H_
+
+namespace utils
+{
+ namespace math
+ {
+ float fastInvSqrt(float x);
+
+ float fastSqrt(float x);
+
+ float cachedSin(int angle);
+
+ float cachedCos(int angle);
+
+ float cachedTan(int angle);
+
+ void init();
+
+ } // namespace math
+
+} // namespace utils
+
+#endif