Mostly synced the client and server code for path finding.

5 files changed, 50 insertions, 43 deletions

diff --git a/src/game-server/being.cpp b/src/game-server/being.cpp
index 7b934a61..634d566a 100644
--- a/src/game-server/being.cpp
+++ b/src/game-server/being.cpp
@@ -126,7 +126,7 @@ void Being::setDestination(const Point &dst)
     mPath.clear();
 }
 
-std::list<PATH_NODE> Being::findPath()
+Path Being::findPath()
 {
     mOld = getPosition();
     int startX = mOld.x / 32, startY = mOld.y / 32;
@@ -165,7 +165,7 @@ void Being::move()
      * class has been used, because that seems to be the most logical
      * place extra functionality will be added.
      */
-    for (std::list<PATH_NODE>::iterator pathIterator = mPath.begin();
+    for (PathIterator pathIterator = mPath.begin();
             pathIterator != mPath.end(); pathIterator++)
     {
         if (!map->getWalk(pathIterator->x, pathIterator->y, getWalkMask()))
@@ -190,11 +190,11 @@ void Being::move()
         return;
     }
 
-    PATH_NODE prev(tileSX, tileSY);
+    Position prev(tileSX, tileSY);
     Point pos;
     do
     {
-        PATH_NODE next = mPath.front();
+        Position next = mPath.front();
         mPath.pop_front();
         // 362 / 256 is square root of 2, used for walking diagonally
         mActionTime += (prev.x != next.x && prev.y != next.y)
diff --git a/src/game-server/being.hpp b/src/game-server/being.hpp
index 782ddfa3..c25e24e2 100644
--- a/src/game-server/being.hpp
+++ b/src/game-server/being.hpp
@@ -241,7 +241,7 @@ class Being : public Actor
         /**
          * Returns the path to the being's current destination.
          */
-        virtual std::list<PATH_NODE> findPath();
+        virtual Path findPath();
 
         /**
          * Sets an attribute.
@@ -342,7 +342,7 @@ class Being : public Actor
         Being(const Being &rhs);
         Being &operator=(const Being &rhs);
 
-        std::list<PATH_NODE> mPath;
+        Path mPath;
         unsigned short mSpeed;      /**< Speed. */
         unsigned char mDirection;   /**< Facing direction. */
 
diff --git a/src/game-server/map.cpp b/src/game-server/map.cpp
index 3f5f818d..b63c37e2 100644
--- a/src/game-server/map.cpp
+++ b/src/game-server/map.cpp
@@ -26,17 +26,18 @@
 
 #include "game-server/map.hpp"
 
+// Basic cost for moving from one tile to another.
+// Used in findPath() function when computing the A* path algorithm.
+static int const basicCost = 100;
+
 MetaTile::MetaTile():
     whichList(0),
     blockmask(0)
-{
-}
-
+{ }
 
 Location::Location(int x, int y, MetaTile *tile):
     x(x), y(y), tile(tile)
-{
-}
+{ }
 
 bool Location::operator< (const Location &loc) const
 {
@@ -151,7 +152,7 @@ void Map::freeTile(int x, int y, BlockType type)
 bool Map::getWalk(int x, int y, char walkmask) const
 {
     // You can't walk outside of the map
-    if (x < 0 || y < 0 || x >= mWidth || y >= mHeight)
+    if (!contains(x, y))
     {
         return false;
     }
@@ -165,15 +166,17 @@ MetaTile *Map::getMetaTile(int x, int y)
     return &mMetaTiles[x + y * mWidth];
 }
 
-static int const basicCost = 100;
-
+bool Map::contains(int x, int y) const
+{
+    return x >= 0 && y >= 0 && x < mWidth && y < mHeight;
+}
 
-std::list<PATH_NODE> Map::findSimplePath(int startX, int startY,
+Path Map::findSimplePath(int startX, int startY,
                                          int destX, int destY,
                                          unsigned char walkmask)
 {
     // Path to be built up (empty by default)
-    std::list<PATH_NODE> path;
+    Path path;
     int positionX = startX, positionY = startY;
     int directionX, directionY;
     // Checks our path up to 1 tiles, if a blocking tile is found
@@ -198,7 +201,7 @@ std::list<PATH_NODE> Map::findSimplePath(int startX, int startY,
 
         if (getWalk(positionX, positionY, walkmask))
         {
-            path.push_back(PATH_NODE(positionX, positionY));
+            path.push_back(Position(positionX, positionY));
 
             if ((positionX == destX) && (positionY == destY))
             {
@@ -212,12 +215,12 @@ std::list<PATH_NODE> Map::findSimplePath(int startX, int startY,
     }
 }
 
-std::list<PATH_NODE> Map::findPath(int startX, int startY,
+Path Map::findPath(int startX, int startY,
                                    int destX, int destY,
                                    unsigned char walkmask, int maxCost)
 {
     // Path to be built up (empty by default)
-    std::list<PATH_NODE> path;
+    Path path;
 
     // Declare open list, a list with open tiles sorted on F cost
     std::priority_queue<Location> openList;
@@ -245,9 +248,7 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
         // If the tile is already on the closed list, this means it has already
         // been processed with a shorter path to the start point (lower G cost)
         if (curr.tile->whichList == onClosedList)
-        {
             continue;
-        }
 
         // Put the current tile on the closed list
         curr.tile->whichList = onClosedList;
@@ -263,19 +264,14 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
 
                 // Skip if if we're checking the same tile we're leaving from,
                 // or if the new location falls outside of the map boundaries
-                if ((dx == 0 && dy == 0) ||
-                        (x < 0 || y < 0 || x >= mWidth || y >= mHeight))
-                {
+                if ((dx == 0 && dy == 0) || !contains(x, y))
                     continue;
-                }
 
                 MetaTile *newTile = getMetaTile(x, y);
 
                 // Skip if the tile is on the closed list or is not walkable
                 if (newTile->whichList == onClosedList || newTile->blockmask & walkmask)
-                {
                     continue;
-                }
 
                 // When taking a diagonal step, verify that we can skip the
                 // corner.
@@ -284,10 +280,8 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
                     MetaTile *t1 = getMetaTile(curr.x, curr.y + dy);
                     MetaTile *t2 = getMetaTile(curr.x + dx, curr.y);
 
-                    if (t1->blockmask & walkmask && !(t2->blockmask & walkmask)) // I hope I didn't fuck this line up
-                    {
+                    if ((t1->blockmask | t2->blockmask) & walkmask)
                         continue;
-                    }
                 }
 
                 // Calculate G cost for this route, ~sqrt(2) for moving diagonal
@@ -311,9 +305,7 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
                 // Skip if Gcost becomes too much
                 // Warning: probably not entirely accurate
                 if (Gcost > maxCost * basicCost)
-                {
                     continue;
-                }
 
                 if (newTile->whichList != onOpenList)
                 {
@@ -340,7 +332,8 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
                         newTile->whichList = onOpenList;
                         openList.push(Location(x, y, newTile));
                     }
-                    else {
+                    else
+                    {
                         // Target location was found
                         foundPath = true;
                     }
@@ -350,7 +343,7 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
                     // Found a shorter route.
                     // Update Gcost and Fcost of the new tile
                     newTile->Gcost = Gcost;
-                    newTile->Fcost = newTile->Gcost + newTile->Hcost;
+                    newTile->Fcost = Gcost + newTile->Hcost;
 
                     // Set the current tile as the parent of the new tile
                     newTile->parentX = curr.x;
@@ -379,7 +372,7 @@ std::list<PATH_NODE> Map::findPath(int startX, int startY,
         while (pathX != startX || pathY != startY)
         {
             // Add the new path node to the start of the path list
-            path.push_front(PATH_NODE(pathX, pathY));
+            path.push_front(Position(pathX, pathY));
 
             // Find out the next parent
             MetaTile *tile = getMetaTile(pathX, pathY);
diff --git a/src/game-server/map.hpp b/src/game-server/map.hpp
index 90d8ff33..4de34f08 100644
--- a/src/game-server/map.hpp
+++ b/src/game-server/map.hpp
@@ -29,14 +29,23 @@
 const unsigned int DEFAULT_TILE_WIDTH = 32;
 const unsigned int DEFAULT_TILE_HEIGHT = 32;
 
-struct PATH_NODE {
-    PATH_NODE(unsigned short u, unsigned short v)
-        : x(u), y(v)
-    {}
+/**
+ * A position along a being's path.
+ * Used to compute each Path Nodes of the path.
+ */
+struct Position
+{
+    Position(int x, int y):
+        x(x), y(y)
+    { }
 
-    unsigned short x, y;
+    int x;
+    int y;
 };
 
+typedef std::list<Position> Path;
+typedef Path::iterator PathIterator;
+
 /**
  * A meta tile stores additional information about a location on a tile map.
  * This is information that doesn't need to be repeated for each tile in each
@@ -131,6 +140,11 @@ class Map
         bool getWalk(int x, int y, char walkmask = BLOCKMASK_WALL) const;
 
         /**
+         * Tells if a tile location is within the map range.
+         */
+        bool contains(int x, int y) const;
+
+        /**
          * Returns the width of this map.
          */
         int getWidth() const
@@ -168,7 +182,7 @@ class Map
         /**
          * Find a path from one location to the next.
          */
-        std::list<PATH_NODE> findPath(int startX, int startY,
+        Path findPath(int startX, int startY,
                                       int destX, int destY,
                                       unsigned char walkmask,
                                       int maxCost = 20);
@@ -176,7 +190,7 @@ class Map
         /**
          * Finds a simple path from location to the next.
          */
-        std::list<PATH_NODE> findSimplePath(int startX, int startY,
+        Path findSimplePath(int startX, int startY,
                                             int destX, int destY,
                                             unsigned char walkmask);
 
diff --git a/src/game-server/monster.cpp b/src/game-server/monster.cpp
index af2bc7aa..4d13ac0e 100644
--- a/src/game-server/monster.cpp
+++ b/src/game-server/monster.cpp
@@ -349,7 +349,7 @@ int Monster::calculatePositionPriority(Point position, int targetPriority)
         return targetPriority *= range;
     }
 
-    std::list<PATH_NODE> path;
+    Path path;
     path = getMap()->getMap()->findPath(thisPos.x / 32, thisPos.y / 32,
                                         position.x / 32, position.y / 32,
                                         getWalkMask(),