Implemented an alternate collision-detection function, added namespace utils::math.

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