Split path finding out of the Map class

Extracted the path finding algorithm out of the Map class and introduced
a new class called PathInfo that has the path finding information that
used to be part of MetaTile.

This allows a single vector of path information to be shared between all
maps running on the server, significantly reducing the memory overhead
per map (for 200x200 maps, the memory reduction is about 1 MB per map).

Part of this change is some cleanup, like moving the 'occupation' counts
into MetaTile, inlining some methods for performance reasons, and using
STL to simplify memory management.

Mantis-issue: 106
Reviewed-by: Bertram

7 files changed, 176 insertions, 176 deletions

diff --git a/src/game-server/actor.h b/src/game-server/actor.h
index 3aac3b60..e345d579 100644
--- a/src/game-server/actor.h
+++ b/src/game-server/actor.h
@@ -127,8 +127,8 @@ class Actor : public Thing
         /**
          * Gets the way the actor blocks pathfinding for other actors.
          */
-        virtual Map::BlockType getBlockType() const
-        { return Map::BLOCKTYPE_NONE; }
+        virtual BlockType getBlockType() const
+        { return BLOCKTYPE_NONE; }
 
         /** Delay until move to next tile in miliseconds. */
         unsigned short mMoveTime;
diff --git a/src/game-server/character.h b/src/game-server/character.h
index dfbf14e4..5a826908 100644
--- a/src/game-server/character.h
+++ b/src/game-server/character.h
@@ -372,8 +372,8 @@ class Character : public Being
         /**
          * Gets the way the actor blocks pathfinding for other objects
          */
-        virtual Map::BlockType getBlockType() const
-        { return Map::BLOCKTYPE_CHARACTER; }
+        virtual BlockType getBlockType() const
+        { return BLOCKTYPE_CHARACTER; }
 
     private:
         double getAttrBase(AttributeMap::const_iterator it) const
diff --git a/src/game-server/map.cpp b/src/game-server/map.cpp
index 702bc3b4..d48546a2 100644
--- a/src/game-server/map.cpp
+++ b/src/game-server/map.cpp
@@ -1,6 +1,6 @@
 /*
  *  The Mana Server
- *  Copyright (C) 2004-2010  The Mana World Development Team
+ *  Copyright (C) 2004-2011  The Mana World Development Team
  *
  *  This file is part of The Mana Server.
  *
@@ -28,55 +28,89 @@
 
 #include "defines.h"
 
-MetaTile::MetaTile():
-    whichList(0),
-    blockmask(0)
-{ }
+/**
+ * Stores information used during path finding for each tile of a map.
+ */
+class PathInfo
+{
+    public:
+        PathInfo()
+            : whichList(0)
+        {}
+
+        int Fcost;              /**< Estimation of total path cost */
+        int Gcost;              /**< Cost from start to this location */
+        int Hcost;              /**< Estimated cost to goal */
+        unsigned whichList;     /**< No list, open list or closed list */
+        int parentX;            /**< X coordinate of parent tile */
+        int parentY;            /**< Y coordinate of parent tile */
+};
+
+/**
+ * A helper class for finding a path on a map, functor style.
+ */
+class FindPath
+{
+    public:
+        FindPath() :
+            mWidth(0),
+            mOnClosedList(1),
+            mOnOpenList(2)
+        {}
 
-Location::Location(int x, int y, MetaTile *tile):
-    x(x), y(y), tile(tile)
-{ }
+        Path operator() (int startX, int startY,
+                         int destX, int destY,
+                         unsigned char walkmask, int maxCost,
+                         const Map *map);
 
-bool Location::operator< (const Location &loc) const
-{
-   return tile->Fcost > loc.tile->Fcost;
-}
+    private:
+        PathInfo *getInfo(int x, int y)
+        { return &mPathInfos.at(x + y * mWidth); }
 
-Map::Map(int width, int height, int twidth, int theight):
-    mWidth(width), mHeight(height),
-    mTileWidth(twidth), mTileHeight(theight),
-    mOnClosedList(1), mOnOpenList(2)
+        void prepare(const Map *map);
+
+        int mWidth;
+        std::vector<PathInfo> mPathInfos;
+        unsigned mOnClosedList, mOnOpenList;
+};
+
+static FindPath findPath;
+
+
+/**
+ * A location on a tile map. Used for pathfinding, open list.
+ */
+class Location
 {
-    mMetaTiles = new MetaTile[mWidth * mHeight];
-    for (int i = 0; i < NB_BLOCKTYPES; i++)
-    {
-        mOccupation[i] = new unsigned[mWidth * mHeight];
-        memset(mOccupation[i], 0, mWidth * mHeight * sizeof(unsigned));
-    }
-}
+    public:
+        Location(int x, int y, PathInfo *info):
+            x(x), y(y), info(info)
+        {}
+
+        /**
+         * Comparison operator.
+         */
+        bool operator< (const Location &loc) const
+        { return info->Fcost > loc.info->Fcost; }
+
+        int x, y;
+        PathInfo *info;
+};
+
 
-Map::~Map()
+Map::Map(int width, int height, int tileWidth, int tileHeight):
+    mWidth(width), mHeight(height),
+    mTileWidth(tileWidth), mTileHeight(tileHeight),
+    mMetaTiles(width * height)
 {
-    delete[] mMetaTiles;
-    for (int i = 0; i < NB_BLOCKTYPES; i++)
-    {
-        delete[] mOccupation[i];
-    }
 }
 
 void Map::setSize(int width, int height)
 {
-    this->mWidth = width;
-    this->mHeight = height;
+    mWidth = width;
+    mHeight = height;
 
-    delete[] mMetaTiles;
-    mMetaTiles = new MetaTile[mWidth * mHeight];
-
-    for (int i = 0; i < NB_BLOCKTYPES; i++)
-    {
-        delete[] mOccupation[i];
-        mOccupation[i] = new unsigned[mWidth * mHeight];
-    }
+    mMetaTiles.resize(width * height);
 }
 
 const std::string &Map::getProperty(const std::string &key) const
@@ -91,26 +125,24 @@ const std::string &Map::getProperty(const std::string &key) const
 
 void Map::blockTile(int x, int y, BlockType type)
 {
-    if (type == BLOCKTYPE_NONE || x < 0 || y < 0 || x >= mWidth || y >= mHeight)
-    {
+    if (type == BLOCKTYPE_NONE || !contains(x, y))
         return;
-    }
 
-    int tileNum = x + y * mWidth;
+    MetaTile &metaTile = mMetaTiles[x + y * mWidth];
 
-    if (mOccupation[type][tileNum] < UINT_MAX &&
-        (++mOccupation[type][tileNum]) > 0)
+    if (metaTile.occupation[type] < UINT_MAX &&
+        (++metaTile.occupation[type]) > 0)
     {
         switch (type)
         {
             case BLOCKTYPE_WALL:
-                mMetaTiles[tileNum].blockmask |= BLOCKMASK_WALL;
+                metaTile.blockmask |= BLOCKMASK_WALL;
                 break;
             case BLOCKTYPE_CHARACTER:
-                mMetaTiles[tileNum].blockmask |= BLOCKMASK_CHARACTER;
+                metaTile.blockmask |= BLOCKMASK_CHARACTER;
                 break;
             case BLOCKTYPE_MONSTER:
-                mMetaTiles[tileNum].blockmask |= BLOCKMASK_MONSTER;
+                metaTile.blockmask |= BLOCKMASK_MONSTER;
                 break;
             default:
                 // Nothing to do.
@@ -121,26 +153,23 @@ void Map::blockTile(int x, int y, BlockType type)
 
 void Map::freeTile(int x, int y, BlockType type)
 {
-    if (type == BLOCKTYPE_NONE || x < 0 || y < 0 || x >= mWidth || y >= mHeight)
-    {
+    if (type == BLOCKTYPE_NONE || !contains(x, y))
         return;
-    }
 
-    int tileNum = x + y * mWidth;
+    MetaTile &metaTile = mMetaTiles[x + y * mWidth];
 
-    if (mOccupation[type][tileNum] > 0 &&
-        !(--mOccupation[type][tileNum]))
+    if (metaTile.occupation[type] > 0 && !(--metaTile.occupation[type]))
     {
         switch (type)
         {
             case BLOCKTYPE_WALL:
-                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_WALL xor 0xff);
+                metaTile.blockmask &= (BLOCKMASK_WALL xor 0xff);
                 break;
             case BLOCKTYPE_CHARACTER:
-                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_CHARACTER xor 0xff);
+                metaTile.blockmask &= (BLOCKMASK_CHARACTER xor 0xff);
                 break;
             case BLOCKTYPE_MONSTER:
-                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_MONSTER xor 0xff);
+                metaTile.blockmask &= (BLOCKMASK_MONSTER xor 0xff);
                 break;
             default:
                 // nothing
@@ -153,27 +182,26 @@ bool Map::getWalk(int x, int y, char walkmask) const
 {
     // You can't walk outside of the map
     if (!contains(x, y))
-    {
         return false;
-    }
 
     // Check if the tile is walkable
     return !(mMetaTiles[x + y * mWidth].blockmask & walkmask);
 }
 
-MetaTile *Map::getMetaTile(int x, int y)
-{
-    return &mMetaTiles[x + y * mWidth];
-}
-
-bool Map::contains(int x, int y) const
+Path Map::findPath(int startX, int startY,
+                   int destX, int destY,
+                   unsigned char walkmask, int maxCost) const
 {
-    return x >= 0 && y >= 0 && x < mWidth && y < mHeight;
+    return ::findPath(startX, startY,
+                      destX, destY,
+                      walkmask, maxCost,
+                      this);
 }
 
-Path Map::findPath(int startX, int startY,
-                                   int destX, int destY,
-                                   unsigned char walkmask, int maxCost)
+Path FindPath::operator() (int startX, int startY,
+                           int destX, int destY,
+                           unsigned char walkmask, int maxCost,
+                           const Map *map)
 {
     // Basic cost for moving from one tile to another.
     static int const basicCost = 100;
@@ -181,14 +209,17 @@ Path Map::findPath(int startX, int startY,
     // Path to be built up (empty by default)
     Path path;
 
+    // Return when destination not walkable
+    if (!map->getWalk(destX, destY, walkmask))
+        return path;
+
+    prepare(map);
+
     // Declare open list, a list with open tiles sorted on F cost
     std::priority_queue<Location> openList;
 
-    // Return when destination not walkable
-    if (!getWalk(destX, destY, walkmask)) return path;
-
     // Reset starting tile's G cost to 0
-    MetaTile *startTile = getMetaTile(startX, startY);
+    PathInfo *startTile = getInfo(startX, startY);
     startTile->Gcost = 0;
 
     // Add the start point to the open list
@@ -206,11 +237,11 @@ Path 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 == mOnClosedList)
+        if (curr.info->whichList == mOnClosedList)
             continue;
 
         // Put the current tile on the closed list
-        curr.tile->whichList = mOnClosedList;
+        curr.info->whichList = mOnClosedList;
 
         // Check the adjacent tiles
         for (int dy = -1; dy <= 1; dy++)
@@ -223,29 +254,27 @@ Path 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) || !contains(x, y))
+                if ((dx == 0 && dy == 0) || !map->contains(x, y))
                     continue;
 
-                MetaTile *newTile = getMetaTile(x, y);
+                PathInfo *newTile = getInfo(x, y);
 
                 // Skip if the tile is on the closed list or is not walkable
-                if (newTile->whichList == mOnClosedList || newTile->blockmask
-                                                           & walkmask)
+                if (newTile->whichList == mOnClosedList
+                        || !map->getWalk(x, y, walkmask))
                     continue;
 
                 // When taking a diagonal step, verify that we can skip the
                 // corner.
                 if (dx != 0 && dy != 0)
                 {
-                    MetaTile *t1 = getMetaTile(curr.x, curr.y + dy);
-                    MetaTile *t2 = getMetaTile(curr.x + dx, curr.y);
-
-                    if ((t1->blockmask | t2->blockmask) & walkmask)
+                    if (!map->getWalk(curr.x, curr.y + dy, walkmask)
+                            || !map->getWalk(curr.x + dx, curr.y, walkmask))
                         continue;
                 }
 
                 // Calculate G cost for this route, ~sqrt(2) for moving diagonal
-                int Gcost = curr.tile->Gcost +
+                int Gcost = curr.info->Gcost +
                     (dx == 0 || dy == 0 ? basicCost : basicCost * 362 / 256);
 
                 /* Demote an arbitrary direction to speed pathfinding by
@@ -318,25 +347,6 @@ Path Map::findPath(int startX, int startY,
         }
     }
 
-    // Two new values to indicate whether a tile is on the open or closed list,
-    // this way we don't have to clear all the values between each pathfinding.
-    if (mOnOpenList > UINT_MAX - 2)
-    {
-        // We reset the list memebers value.
-        mOnClosedList = 1;
-        mOnOpenList = 2;
-
-        // Clean up the metaTiles
-        const int size = mWidth * mHeight;
-        for (int i = 0; i < size; ++i)
-            mMetaTiles[i].whichList = 0;
-    }
-    else
-    {
-        mOnClosedList += 2;
-        mOnOpenList += 2;
-    }
-
     // If a path has been found, iterate backwards using the parent locations
     // to extract it.
     if (foundPath)
@@ -350,7 +360,7 @@ Path Map::findPath(int startX, int startY,
             path.push_front(Point(pathX, pathY));
 
             // Find out the next parent
-            MetaTile *tile = getMetaTile(pathX, pathY);
+            PathInfo *tile = getInfo(pathX, pathY);
             pathX = tile->parentX;
             pathY = tile->parentY;
         }
@@ -358,3 +368,29 @@ Path Map::findPath(int startX, int startY,
 
     return path;
 }
+
+void FindPath::prepare(const Map *map)
+{
+    // Two new values to indicate whether a tile is on the open or closed list,
+    // this way we don't have to clear all the values between each pathfinding.
+    if (mOnOpenList < UINT_MAX - 2)
+    {
+        mOnClosedList += 2;
+        mOnOpenList += 2;
+    }
+    else
+    {
+        // Reset closed and open list IDs and clear the whichList values
+        mOnClosedList = 1;
+        mOnOpenList = 2;
+        for (unsigned i = 0, end = mPathInfos.size(); i < end; ++i)
+            mPathInfos[i].whichList = 0;
+    }
+
+    // Make sure we have enough room to cover this map with path information
+    const unsigned size = map->getWidth() * map->getHeight();
+    if (mPathInfos.size() < size)
+        mPathInfos.resize(size);
+
+    mWidth = map->getWidth();
+}
diff --git a/src/game-server/map.h b/src/game-server/map.h
index 28004870..7c58d005 100644
--- a/src/game-server/map.h
+++ b/src/game-server/map.h
@@ -1,6 +1,6 @@
 /*
  *  The Mana Server
- *  Copyright (C) 2004-2010  The Mana World Development Team
+ *  Copyright (C) 2004-2011  The Mana World Development Team
  *
  *  This file is part of The Mana Server.
  *
@@ -24,12 +24,22 @@
 #include <list>
 #include <map>
 #include <string>
+#include <vector>
 
 #include "utils/point.h"
 
 typedef std::list<Point> Path;
 typedef Path::iterator PathIterator;
 
+enum BlockType
+{
+    BLOCKTYPE_NONE = -1,
+    BLOCKTYPE_WALL,
+    BLOCKTYPE_CHARACTER,
+    BLOCKTYPE_MONSTER,
+    NB_BLOCKTYPES
+};
+
 /**
  * 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
@@ -38,39 +48,15 @@ typedef Path::iterator PathIterator;
 class MetaTile
 {
     public:
-        /**
-         * Constructor.
-         */
-        MetaTile();
-
-        // Pathfinding members
-        int Fcost;              /**< Estimation of total path cost */
-        int Gcost;              /**< Cost from start to this location */
-        int Hcost;              /**< Estimated cost to goal */
-        unsigned whichList;     /**< No list, open list or closed list */
-        int parentX;            /**< X coordinate of parent tile */
-        int parentY;            /**< Y coordinate of parent tile */
-        char blockmask;          /**< walkability bitfield */
-};
-
-/**
- * A location on a tile map. Used for pathfinding, open list.
- */
-class Location
-{
-    public:
-        /**
-         * Constructor.
-         */
-        Location(int x, int y, MetaTile *tile);
-
-        /**
-         * Comparison operator.
-         */
-        bool operator< (const Location &loc) const;
+        MetaTile()
+            : blockmask(0)
+        {
+            for (unsigned i = 0; i < NB_BLOCKTYPES; ++i)
+                occupation[i] = 0;
+        }
 
-        int x, y;
-        MetaTile *tile;
+        unsigned occupation[NB_BLOCKTYPES];
+        char blockmask;          /**< walkability bitfield */
 };
 
 /**
@@ -79,35 +65,16 @@ class Location
 class Map
 {
     public:
-        enum BlockType
-        {
-            BLOCKTYPE_NONE = -1,
-            BLOCKTYPE_WALL,
-            BLOCKTYPE_CHARACTER,
-            BLOCKTYPE_MONSTER,
-            NB_BLOCKTYPES
-        };
-
         /**
          * Constructor that takes initial map size as parameters.
          */
         Map(int width, int height,
-            int twidth, int theight);
-
-        /**
-         * Destructor.
-         */
-        ~Map();
+            int tileWidth, int tileHeight);
 
         /**
          * Sets the size of the map. This will destroy any existing map data.
          */
-        void setSize(int mWidth, int height);
-
-        /**
-         * Get tile reference.
-         */
-        MetaTile *getMetaTile(int x, int y);
+        void setSize(int width, int height);
 
         /**
          * Marks a tile as occupied
@@ -127,7 +94,8 @@ class Map
         /**
          * Tells if a tile location is within the map range.
          */
-        bool contains(int x, int y) const;
+        bool contains(int x, int y) const
+        { return x >= 0 && y >= 0 && x < mWidth && y < mHeight; }
 
         /**
          * Returns the width of this map.
@@ -168,9 +136,9 @@ class Map
          * Find a path from one location to the next.
          */
         Path findPath(int startX, int startY,
-                                      int destX, int destY,
-                                      unsigned char walkmask,
-                                      int maxCost = 20);
+                      int destX, int destY,
+                      unsigned char walkmask,
+                      int maxCost = 20) const;
 
     private:
         /**
@@ -179,16 +147,13 @@ class Map
         static const unsigned char BLOCKMASK_WALL = 0x80;     // = bin 1000 0000
         static const unsigned char BLOCKMASK_CHARACTER = 0x01;// = bin 0000 0001
         static const unsigned char BLOCKMASK_MONSTER = 0x02;  // = bin 0000 0010
-        unsigned *mOccupation[NB_BLOCKTYPES];
 
         // map properties
         int mWidth, mHeight;
         int mTileWidth, mTileHeight;
         std::map<std::string, std::string> mProperties;
 
-        // Pathfinding members
-        MetaTile *mMetaTiles;
-        unsigned mOnClosedList, mOnOpenList;
+        std::vector<MetaTile> mMetaTiles;
 };
 
 #endif
diff --git a/src/game-server/mapreader.cpp b/src/game-server/mapreader.cpp
index f96de174..eefca086 100644
--- a/src/game-server/mapreader.cpp
+++ b/src/game-server/mapreader.cpp
@@ -589,5 +589,5 @@ void MapReader::setTileWithGid(Map *map, int x, int y, int gid)
     }
 
     if (gid != set)
-        map->blockTile(x, y, Map::BLOCKTYPE_WALL);
+        map->blockTile(x, y, BLOCKTYPE_WALL);
 }
diff --git a/src/game-server/monster.h b/src/game-server/monster.h
index 2d826e48..14ebad35 100644
--- a/src/game-server/monster.h
+++ b/src/game-server/monster.h
@@ -308,8 +308,8 @@ class Monster : public Being
         /**
          * Returns the way the actor blocks pathfinding for other objects.
          */
-        virtual Map::BlockType getBlockType() const
-        { return Map::BLOCKTYPE_MONSTER; }
+        virtual BlockType getBlockType() const
+        { return BLOCKTYPE_MONSTER; }
 
     private:
         static const int DECAY_TIME = 50;
diff --git a/src/game-server/npc.h b/src/game-server/npc.h
index 02b26a72..566b481c 100644
--- a/src/game-server/npc.h
+++ b/src/game-server/npc.h
@@ -74,12 +74,11 @@ class NPC : public Being
         { return 0x83; } // blocked like a monster by walls, monsters and characters ( bin 1000 0011)
 
     protected:
-
         /**
          * Gets the way a monster blocks pathfinding for other objects
          */
-        virtual Map::BlockType getBlockType() const
-        { return Map::BLOCKTYPE_CHARACTER; } //blocks like a player character
+        virtual BlockType getBlockType() const
+        { return BLOCKTYPE_CHARACTER; } // blocks like a player character
 
     private:
         Script *mScript;    /**< Script describing NPC behavior. */