Implemented dynamic and selective pathblocking. Monsters are blocked by player characters and other monsters, player characters only by monsters.

13 files changed, 241 insertions, 46 deletions

diff --git a/src/game-server/being.cpp b/src/game-server/being.cpp
index 9164aa43..b18914fa 100644
--- a/src/game-server/being.cpp
+++ b/src/game-server/being.cpp
@@ -65,8 +65,7 @@ int Being::damage(Object *, Damage const &damage)
        And at 200, it means vulnerable (double damage). */
     int mod1 = getModifiedAttribute(BASE_ELEM_BEGIN + damage.element);
 
-    /* Resistance to damage at 0 gives normal damage. At 100, it gives halved
-       damage. At 200, it divides damage by 3. And so on. */
+    /* Defence is an absolute value which is subtracted from the damage total. */
     int mod2 = 0;
     switch (damage.type)
     {
@@ -84,11 +83,10 @@ int Being::damage(Object *, Damage const &damage)
     if (HPloss < 0) HPloss = 0;
 
     mHitsTaken.push_back(HPloss);
-
     Attribute &HP = mAttributes[BASE_ATTR_HP];
     LOG_DEBUG("Being " << getPublicID() << " suffered "<<HPloss<<" damage. HP: "<<HP.base + HP.mod<<"/"<<HP.base);
     HP.mod -= HPloss;
-    modifiedAttribute(BASE_ATTR_HP);
+    if (HPloss != 0) modifiedAttribute(BASE_ATTR_HP);
 
     return HPloss;
 }
@@ -242,7 +240,6 @@ void Being::update()
     //only update HP when it actually changed to avoid network noise
     if (newHP != oldHP)
     {
-        LOG_INFO("HP Update - newHP:"<<newHP<<", oldHP:"<<oldHP<<", maxHP:"<<maxHP);
         applyModifier(BASE_ATTR_HP, newHP - oldHP);
     }
 
diff --git a/src/game-server/character.cpp b/src/game-server/character.cpp
index 7318f712..d4abd9f4 100644
--- a/src/game-server/character.cpp
+++ b/src/game-server/character.cpp
@@ -429,3 +429,13 @@ void Character::disconnected()
         if (l.dispatch->disconnected) l.dispatch->disconnected(&l, this);
     }
 }
+
+Character::~Character()
+{
+    if (getMap())
+    {
+        Point oldP = getPosition();
+        getMap()->getMap()->freeTile(oldP.x / 32, oldP.y / 32, getBlockType());
+    }
+}
+
diff --git a/src/game-server/character.hpp b/src/game-server/character.hpp
index b90d2b3c..62bec49d 100644
--- a/src/game-server/character.hpp
+++ b/src/game-server/character.hpp
@@ -50,6 +50,8 @@ class Character : public Being
          */
         Character(MessageIn &msg);
 
+        ~Character();
+
         /**
          * recalculates the level when necessary and calls Being::update
          */
@@ -271,6 +273,12 @@ class Character : public Being
         int getCorrectionPoints() const
         { return mCorrectionPoints; }
 
+        /**
+         * Gets the way the object is blocked by other things on the map
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x82; } // blocked by walls and monsters ( bin 1000 0010)
+
     private:
         Character(Character const &);
         Character &operator=(Character const &);
@@ -340,6 +348,13 @@ class Character : public Being
         bool mRecalculateLevel;      /**< flag raised when the character level might have increased */
         unsigned char mAccountLevel; /**< Account level of the user. */
         TransactionType mTransaction; /**< Trade/buy/sell action the character is involved in. */
+
+    protected:
+        /**
+         * Gets the way the object blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_CHARACTER; }
 };
 
 #endif // _TMWSERV_CHARACTER_HPP_
diff --git a/src/game-server/map.cpp b/src/game-server/map.cpp
index 3699b6da..8ad9242a 100644
--- a/src/game-server/map.cpp
+++ b/src/game-server/map.cpp
@@ -27,7 +27,8 @@
 #include "game-server/map.hpp"
 
 MetaTile::MetaTile():
-    whichList(0)
+    whichList(0),
+    blockmask(0)
 {
 }
 
@@ -44,62 +45,131 @@ bool Location::operator< (const Location &loc) const
 
 
 Map::Map():
-    width(0), height(0),
+    mWidth(0), mHeight(0),
     tileWidth(32), tileHeight(32),
     onClosedList(1), onOpenList(2)
 {
-    metaTiles = new MetaTile[width * height];
+    mMetaTiles = new MetaTile[mWidth * mHeight];
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        mOccupation[i] = new int[mWidth * mHeight];
+        memset(mOccupation[i], 0, mWidth * mHeight * sizeof(int));
+    }
 }
 
 Map::Map(int width, int height):
-    width(width), height(height),
+    mWidth(width), mHeight(height),
     tileWidth(32), tileHeight(32),
     onClosedList(1), onOpenList(2)
 {
-    metaTiles = new MetaTile[width * height];
+    mMetaTiles = new MetaTile[mWidth * mHeight];
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        mOccupation[i] = new int[mWidth * mHeight];
+        memset(mOccupation[i], 0, mWidth * mHeight * sizeof(int));
+    }
 }
 
 Map::~Map()
 {
-    delete[] metaTiles;
+    delete[] mMetaTiles;
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        delete[] mOccupation[i];
+    }
 }
 
 void
 Map::setSize(int width, int height)
 {
-    this->width = width;
-    this->height = height;
-    delete[] metaTiles;
-    metaTiles = new MetaTile[width * height];
+    this->mWidth = width;
+    this->mHeight = height;
+
+    delete[] mMetaTiles;
+    mMetaTiles = new MetaTile[mWidth * mHeight];
+
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        delete[] mOccupation[i];
+        mOccupation[i] = new int[mWidth * mHeight];
+    }
+}
+
+void Map::blockTile(int x, int y, BlockType type)
+{
+    if (type == BLOCKTYPE_NONE) return;
+    int tileNum = x + y * mWidth;
+    assert (tileNum <= mWidth * mHeight);
+
+    if (++mOccupation[type][tileNum])
+    {
+        switch (type)
+        {
+            case BLOCKTYPE_WALL:
+                mMetaTiles[tileNum].blockmask |= BLOCKMASK_WALL;
+                break;
+            case BLOCKTYPE_CHARACTER:
+                mMetaTiles[tileNum].blockmask |= BLOCKMASK_CHARACTER;
+                break;
+            case BLOCKTYPE_MONSTER:
+                mMetaTiles[tileNum].blockmask |= BLOCKMASK_MONSTER;
+                break;
+            default:
+                // shut up!
+                break;
+        }
+    }
 }
 
-void Map::setWalk(int x, int y, bool walkable)
+void Map::freeTile(int x, int y, BlockType type)
 {
-    metaTiles[x + y * width].walkable = walkable;
+    if (type == BLOCKTYPE_NONE) return;
+
+    int tileNum = x + y * mWidth;
+    assert (tileNum <= mWidth * mHeight);
+
+    if (!(--mOccupation[type][tileNum]))
+    {
+        switch (type)
+        {
+            case BLOCKTYPE_WALL:
+                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_WALL xor 0xff);
+                break;
+            case BLOCKTYPE_CHARACTER:
+                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_CHARACTER xor 0xff);
+                break;
+            case BLOCKTYPE_MONSTER:
+                mMetaTiles[tileNum].blockmask &= (BLOCKMASK_MONSTER xor 0xff);
+                break;
+            default:
+                // shut up!
+                break;
+        }
+    }
 }
 
-bool Map::getWalk(int x, int y) const
+bool Map::getWalk(int x, int y, char walkmask) const
 {
     // You can't walk outside of the map
-    if (x < 0 || y < 0 || x >= width || y >= height)
+    if (x < 0 || y < 0 || x >= mWidth || y >= mHeight)
     {
         return false;
     }
 
     // Check if the tile is walkable
-    return metaTiles[x + y * width].walkable;
+    return !(mMetaTiles[x + y * mWidth].blockmask & walkmask);
 }
 
 MetaTile*
 Map::getMetaTile(int x, int y)
 {
-    return &metaTiles[x + y * width];
+    return &mMetaTiles[x + y * mWidth];
 }
 
 static int const basicCost = 100;
 
 std::list<PATH_NODE>
-Map::findPath(int startX, int startY, int destX, int destY, int maxCost)
+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;
@@ -108,7 +178,7 @@ Map::findPath(int startX, int startY, int destX, int destY, int maxCost)
     std::priority_queue<Location> openList;
 
     // Return when destination not walkable
-    if (!getWalk(destX, destY)) return path;
+    if (!getWalk(destX, destY, walkmask)) return path;
 
     // Reset starting tile's G cost to 0
     MetaTile *startTile = getMetaTile(startX, startY);
@@ -149,7 +219,7 @@ Map::findPath(int startX, int startY, int destX, int destY, int maxCost)
                 // 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 >= width || y >= height))
+                        (x < 0 || y < 0 || x >= mWidth || y >= mHeight))
                 {
                     continue;
                 }
@@ -157,20 +227,19 @@ Map::findPath(int startX, int startY, int destX, int destY, int maxCost)
                 MetaTile *newTile = getMetaTile(x, y);
 
                 // Skip if the tile is on the closed list or is not walkable
-                if (newTile->whichList == onClosedList || !newTile->walkable)
+                if (newTile->whichList == onClosedList || newTile->blockmask & walkmask)
                 {
                     continue;
                 }
 
                 // When taking a diagonal step, verify that we can skip the
-                // corner. We allow skipping past beings but not past non-
-                // walkable tiles.
+                // corner.
                 if (dx != 0 && dy != 0)
                 {
                     MetaTile *t1 = getMetaTile(curr.x, curr.y + dy);
                     MetaTile *t2 = getMetaTile(curr.x + dx, curr.y);
 
-                    if (!(t1->walkable && t2->walkable))
+                    if (t1->blockmask & walkmask && !(t2->blockmask & walkmask)) // I hope I didn't fuck this line up
                     {
                         continue;
                     }
diff --git a/src/game-server/map.hpp b/src/game-server/map.hpp
index e056c862..a5acca2a 100644
--- a/src/game-server/map.hpp
+++ b/src/game-server/map.hpp
@@ -57,7 +57,7 @@ class MetaTile
         int whichList;          /**< No list, open list or closed list */
         int parentX;            /**< X coordinate of parent tile */
         int parentY;            /**< Y coordinate of parent tile */
-        bool walkable;          /**< Can beings normally walk on this tile */
+        char blockmask;          /**< walkability bitfield */
 };
 
 /**
@@ -86,6 +86,15 @@ class Location
 class Map
 {
     public:
+        enum BlockType
+        {
+            BLOCKTYPE_NONE = -1,
+            BLOCKTYPE_WALL,
+            BLOCKTYPE_CHARACTER,
+            BLOCKTYPE_MONSTER,
+            NB_BLOCKTYPES
+        };
+
         /**
          * Constructor.
          */
@@ -105,7 +114,7 @@ class Map
          * Sets the size of the map. This will destroy any existing map data.
          */
         void
-        setSize(int width, int height);
+        setSize(int mWidth, int height);
 
         /**
          * Get tile reference.
@@ -114,26 +123,31 @@ class Map
         getMetaTile(int x, int y);
 
         /**
-         * Sets walkability for a tile.
+         * Marks a tile as occupied
+         */
+        void blockTile(int x, int y, BlockType type);
+
+        /**
+         * Marks a tile as unoccupied
          */
-        void setWalk(int x, int y, bool walkable);
+        void freeTile(int x, int y, BlockType type);
 
         /**
-         * Gets walkability for a tile.
+         * Gets walkability for a tile with a blocking bitmask
          */
-        bool getWalk(int x, int y) const;
+        bool getWalk(int x, int y, char walkmask) const;
 
         /**
          * Returns the width of this map.
          */
         int getWidth() const
-        { return width; }
+        { return mWidth; }
 
         /**
          * Returns the height of this map.
          */
         int getHeight() const
-        { return height; }
+        { return mHeight; }
 
         /**
          * Returns the tile width of this map.
@@ -151,15 +165,25 @@ class Map
          * Find a path from one location to the next.
          */
         std::list<PATH_NODE> findPath(int startX, int startY,
-                                      int destX, int destY, int maxCost = 20);
+                                      int destX, int destY,
+                                      unsigned char walkmask,
+                                      int maxCost = 20);
 
     private:
-        int width, height;
+        /**
+         * Blockmasks for different entities
+         */
+        static const unsigned char BLOCKMASK_WALL = 128;   // = bin 1000 0000
+        static const unsigned char BLOCKMASK_CHARACTER = 1;// = bin 0000 0001
+        static const unsigned char BLOCKMASK_MONSTER = 2;  // = bin 0000 0010
+        int *mOccupation[NB_BLOCKTYPES];
+        int mWidth, mHeight;
         int tileWidth, tileHeight;
-        MetaTile *metaTiles;
+        MetaTile *mMetaTiles;
 
         // Pathfinding members
         int onClosedList, onOpenList;
+
 };
 
 #endif
diff --git a/src/game-server/mapreader.cpp b/src/game-server/mapreader.cpp
index 48f142c4..f8dd24d9 100644
--- a/src/game-server/mapreader.cpp
+++ b/src/game-server/mapreader.cpp
@@ -521,5 +521,9 @@ static void setTileWithGid(Map *map, int x, int y, int gid)
         set = *i;
     }
 
-    map->setWalk(x, y, gid == set);
+    if (gid!=set)
+    {
+        map->blockTile(x, y, Map::BLOCKTYPE_WALL);
+    }
+
 }
diff --git a/src/game-server/monster.cpp b/src/game-server/monster.cpp
index 46225e9a..d782eae0 100644
--- a/src/game-server/monster.cpp
+++ b/src/game-server/monster.cpp
@@ -101,6 +101,13 @@ Monster::~Monster()
     {
         i->first->removeListener(&mTargetListener);
     }
+
+    // free map position
+    if (getMap())
+    {
+        Point oldP = getPosition();
+        getMap()->getMap()->freeTile(oldP.x / 32, oldP.y / 32, getBlockType());
+    }
 }
 
 void Monster::perform()
@@ -293,6 +300,7 @@ int Monster::calculatePositionPriority(Point position, int targetPriority)
     std::list<PATH_NODE> path;
     path = getMap()->getMap()->findPath(thisPos.x / 32, thisPos.y / 32,
                                         position.x / 32, position.y / 32,
+                                        getWalkMask(),
                                         range);
 
     if (path.empty() || path.size() >= range)
diff --git a/src/game-server/monster.hpp b/src/game-server/monster.hpp
index a1d3c5a5..0a614081 100644
--- a/src/game-server/monster.hpp
+++ b/src/game-server/monster.hpp
@@ -224,6 +224,12 @@ class Monster : public Being
          */
         void forgetTarget(Thing *being);
 
+        /**
+         * Gets the way the object is blocked by other things on the map
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x83; } // blocked walls, other monsters and players ( bin 1000 0011)
+
     private:
         int calculatePositionPriority(Point position, int targetPriority);
 
@@ -242,6 +248,12 @@ class Monster : public Being
         std::list<AttackPosition> mAttackPositions; /**< set positions relative to target from which the monster can attack */
 
         friend struct MonsterTargetEventDispatch;
+    protected:
+        /**
+         * Gets the way the object blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_MONSTER; }
 };
 
 #endif // _TMWSERV_MONSTER_H_
diff --git a/src/game-server/movingobject.cpp b/src/game-server/movingobject.cpp
index a24e1070..f7db2d93 100644
--- a/src/game-server/movingobject.cpp
+++ b/src/game-server/movingobject.cpp
@@ -24,6 +24,35 @@
 #include "game-server/mapcomposite.hpp"
 #include "game-server/movingobject.hpp"
 
+
+void MovingObject::setPosition(const Point &p)
+{
+    //update blockmap
+    if (getMap())
+    {
+        Point oldP = getPosition();
+        if ((oldP.x / 32 != p.x / 32 || oldP.y / 32 != p.y / 32))
+        {
+            getMap()->getMap()->freeTile(oldP.x / 32, oldP.y / 32, getBlockType());
+            getMap()->getMap()->blockTile(p.x / 32, p.y / 32, getBlockType());
+        }
+    }
+
+    Object::setPosition(p);
+}
+
+void MovingObject::setMap(MapComposite *map)
+{
+    Point p = getPosition();
+    MapComposite *oldMap = getMap();
+    if (oldMap)
+    {
+        oldMap->getMap()->freeTile(p.x / 32, p.y / 32, getBlockType());
+    }
+    map->getMap()->blockTile(p.x / 32, p.y / 32, getBlockType());
+    Object::setMap(map);
+}
+
 void MovingObject::setDestination(Point const &dst)
 {
     mDst = dst;
@@ -63,7 +92,7 @@ void MovingObject::move()
     for (std::list<PATH_NODE>::iterator pathIterator = mPath.begin();
             pathIterator != mPath.end(); pathIterator++)
     {
-        if (!map->getWalk(pathIterator->x, pathIterator->y))
+        if (!map->getWalk(pathIterator->x, pathIterator->y, getWalkMask()))
         {
             mPath.clear();
             break;
@@ -74,7 +103,7 @@ void MovingObject::move()
     {
         // No path exists: the walkability of cached path has changed, the
         // destination has changed, or a path was never set.
-        mPath = map->findPath(tileSX, tileSY, tileDX, tileDY);
+        mPath = map->findPath(tileSX, tileSY, tileDX, tileDY, getWalkMask());
     }
 
     if (mPath.empty())
diff --git a/src/game-server/movingobject.hpp b/src/game-server/movingobject.hpp
index abad313a..a81212bb 100644
--- a/src/game-server/movingobject.hpp
+++ b/src/game-server/movingobject.hpp
@@ -45,6 +45,14 @@ class MovingObject : public Object
             mDirection(0)
         {}
 
+        virtual ~MovingObject() {};
+
+        /**
+         * Updates the walkmap of the map the object is on before
+         * calling Object::setPosition
+         */
+        virtual void setPosition(const Point &p);
+
         /**
          * Gets the destination coordinates of the object.
          */
@@ -128,6 +136,17 @@ class MovingObject : public Object
         void setPublicID(int id)
         { mPublicID = id; }
 
+        /**
+         * Gets the way the object blocks pathfinding for other objects
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x00; } //can walk through everything
+
+        /**
+         * Sets the map this thing is located on.
+         */
+        virtual void setMap(MapComposite *map);
+
     private:
         /** Object ID sent to clients (unique with respect to the map). */
         unsigned short mPublicID;
@@ -141,6 +160,12 @@ class MovingObject : public Object
         unsigned short mActionTime; /**< Delay until next action. */
         unsigned char mDirection;   /**< Facing direction. */
         unsigned char mSize;        /**< Radius of bounding circle. */
+
+        /**
+         * Gets the way the object blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_NONE; }
 };
 
 #endif // _TMWSERV_MOVINGOBJECT_H_
diff --git a/src/game-server/object.hpp b/src/game-server/object.hpp
index ed0af356..f50dff4d 100644
--- a/src/game-server/object.hpp
+++ b/src/game-server/object.hpp
@@ -59,7 +59,7 @@ class Object : public Thing
          *
          * @param p the coordinates.
          */
-        void setPosition(const Point &p)
+        virtual void setPosition(const Point &p)
         { mPos = p; }
 
         /**
diff --git a/src/game-server/spawnarea.cpp b/src/game-server/spawnarea.cpp
index abc16575..3054a0ac 100644
--- a/src/game-server/spawnarea.cpp
+++ b/src/game-server/spawnarea.cpp
@@ -79,15 +79,16 @@ SpawnArea::update()
                 height = realMap->getHeight() * 32;
             }
 
+            Being *being = new Monster(mSpecy);
+
             do
             {
                 position = Point(x + rand() % width, y + rand() % height);
                 c--;
-            } while (!realMap->getWalk(position.x / 32, position.y / 32) && c);
+            } while (!realMap->getWalk(position.x / 32, position.y / 32, being->getWalkMask()) && c);
 
             if (c)
             {
-                Being *being = new Monster(mSpecy);
                 being->addListener(&mSpawnedListener);
 
                 being->setMap(map);
@@ -103,6 +104,7 @@ SpawnArea::update()
                          << mSpecy->getType() << " on map " << map->getName()
                          << " (" << x << ',' << y << ','
                          << width << ',' << height << ')');
+                delete being;
             }
         }
     }
diff --git a/src/game-server/thing.hpp b/src/game-server/thing.hpp
index 2f160d37..3c6b82dc 100644
--- a/src/game-server/thing.hpp
+++ b/src/game-server/thing.hpp
@@ -106,7 +106,7 @@ class Thing
         /**
          * Sets the map this thing is located on.
          */
-        void setMap(MapComposite *map)
+        virtual void setMap(MapComposite *map)
         { mMap = map; }
 
         /**