Synchronized pathfinding algorithmns with those used by the server to avoid asynchronisation.

13 files changed, 286 insertions, 87 deletions

diff --git a/ChangeLog b/ChangeLog
index f7760321..2eec14f3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2008-03-13  Philipp Sehmisch  <tmw@crushnet.org>
+
+	* src/being.cpp, src/being.h, src/gui/viewport.cpp,
+	src/localplayer.cpp, src/map.cpp, src/map.h, src/monster.cpp,
+	src/monster.h, src/net/beinghandler.cpp, src/net/playerhandler.cpp.
+	src/player.cpp, src/player.h: Unified route finding algorithmns
+	with those used by the server to minimize asynchronisation.
+	* src/map.cpp, src/gui/viewport.cpp: Improved path debugging tool
+	by displaying a raster and showing blocked tiles when it is
+	activated (alt+F).
+
 2008-03-12  David Athay  <ko2fan@gmail.com>
 
 	* src/gui/guildwindow.cpp, src/gui/guildwindow.h,
diff --git a/src/being.cpp b/src/being.cpp
index a55158c6..55530080 100644
--- a/src/being.cpp
+++ b/src/being.cpp
@@ -47,12 +47,12 @@ int Being::instances = 0;
 ImageSet *Being::emotionSet = NULL;
 
 Being::Being(int id, int job, Map *map):
-    mJob(job),
     mX(0), mY(0),
-    mAction(STAND),
-    mWalkTime(0),
     mEmotion(0), mEmotionTime(0),
     mAttackSpeed(350),
+    mWalkTime(0),
+    mAction(STAND),
+    mJob(job),
     mId(id),
     mWalkSpeed(150),
     mSpeedModifier(1024),
@@ -100,6 +100,14 @@ Being::~Being()
     }
 }
 
+void Being::setPositionInPixels(int x, int y)
+{
+    mMap->freeTile(mX / 32, mY / 32, getBlockType());
+    mX = x;
+    mY = y;
+    mMap->blockTile(x / 32, y / 32, getBlockType());
+}
+
 void Being::adjustCourse(Uint16 srcX, Uint16 srcY, Uint16 dstX, Uint16 dstY)
 {
     if (!mMap || (mX == dstX && mY == dstY))
@@ -130,7 +138,7 @@ void Being::adjustCourse(Uint16 srcX, Uint16 srcY, Uint16 dstX, Uint16 dstY)
     }
     else
     {
-        p1 = mMap->findPath(srcX / 32, srcY / 32, dstX / 32, dstY / 32);
+        p1 = mMap->findPath(srcX / 32, srcY / 32, dstX / 32, dstY / 32, getWalkMask());
         if (p1.empty())
         {
             // No path, but don't teleport since it could be user input.
@@ -190,7 +198,7 @@ void Being::adjustCourse(Uint16 srcX, Uint16 srcY, Uint16 dstX, Uint16 dstY)
     for (Path::iterator i = p1.begin(), i_end = p1.end(); i != i_end; ++i)
     {
         // Look if it is worth passing by tile i.
-        Path p2 = mMap->findPath(mX / 32, mY / 32, i->x / 32, i->y / 32);
+        Path p2 = mMap->findPath(mX / 32, mY / 32, i->x / 32, i->y / 32, getWalkMask());
         if (!p2.empty())
         {
             int l1 = mMap->getMetaTile(i->x / 32, i->y / 32)->Gcost;
@@ -343,9 +351,11 @@ Being::handleAttack()
 void
 Being::setMap(Map *map)
 {
+
     // Remove sprite from potential previous map
     if (mMap)
     {
+        mMap->freeTile(mX / 32, mY / 32, getBlockType());
         mMap->removeSprite(mSpriteIterator);
     }
 
@@ -355,6 +365,7 @@ Being::setMap(Map *map)
     if (mMap)
     {
         mSpriteIterator = mMap->addSprite(this);
+        mMap->blockTile(mX / 32, mY / 32, getBlockType());
     }
 
     // Clear particle effect list because child particles became invalid
@@ -488,8 +499,7 @@ Being::nextStep()
 
     setDirection(dir);
 
-    mX = node.x;
-    mY = node.y;
+    setPositionInPixels(node.x, node.y);
     setAction(WALK);
     mWalkTime += mStepTime / 10;
     mStepTime = mWalkSpeed * (int)std::sqrt((double)mStepX * mStepX + (double)mStepY * mStepY) *
diff --git a/src/being.h b/src/being.h
index 0b56994e..f4cdc743 100644
--- a/src/being.h
+++ b/src/being.h
@@ -112,14 +112,13 @@ class Being : public Sprite
         enum { DOWN = 1, LEFT = 2, UP = 4, RIGHT = 8 };
 
         std::string mName;      /**< Name of character */
-        Uint16 mJob;            /**< Job (player job, npc, monster, ) */
-        Uint16 mX, mY;          /**< Pixel coordinates (tile center) */
-        Action mAction;         /**< Action the being is performing */
-        Uint16 mWalkTime;
+        Uint16 mX, mY;          /**< Pixel coordinates of tile center */
         Uint8 mEmotion;         /**< Currently showing emotion */
         Uint8 mEmotionTime;     /**< Time until emotion disappears */
-
         Uint16 mAttackSpeed;          /**< Attack speed */
+        Uint16 mWalkTime;
+        Action mAction;                 /**< Action the being is performing */
+        Uint16 mJob;                    /**< Job (player job, npc, monster, ) */
 
         /**
          * Constructor.
@@ -265,6 +264,13 @@ class Being : public Sprite
         setAction(Action action, int attackType = 0);
 
         /**
+         * Gets the current action.
+         */
+        bool isAlive() { return mAction != DEAD; }
+
+        int getWalkTime() { return mWalkTime; }
+
+        /**
          * Returns the direction the being is facing.
          */
         SpriteDirection getSpriteDirection() const
@@ -298,6 +304,17 @@ class Being : public Sprite
         getPixelY() const { return mPy; }
 
         /**
+         * sets the position in pixels using pixel coordinates
+         */
+        void setPositionInPixels(int x, int y);
+
+        /**
+         * sets the position in pixels using tile coordinates
+         */
+        void setPositionInTiles(int x, int y)
+        { setPositionInPixels(x * 32 + 16, y * 32 + 16); }
+
+        /**
          * Get the current X pixel offset.
          */
         int
@@ -332,12 +349,24 @@ class Being : public Sprite
          */
         void controlParticle(Particle *particle);
 
+        /**
+         * Gets the way the object is blocked by other objects
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x00; } //can walk through everything
+
     protected:
         /**
          * Sets the new path for this being.
          */
         void setPath(const Path &path, int mod = 1024);
 
+        /**
+         * Gets the way the object blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_NONE; }
+
         Uint16 mId;                     /**< Unique being id */
         Uint16 mWalkSpeed;              /**< Walking speed */
         Uint16 mSpeedModifier;          /**< Modifier to keep course on sync (1024 = normal speed) */
diff --git a/src/gui/viewport.cpp b/src/gui/viewport.cpp
index 57c64cd6..d6c49fb2 100644
--- a/src/gui/viewport.cpp
+++ b/src/gui/viewport.cpp
@@ -221,6 +221,10 @@ Viewport::draw(gcn::Graphics *gcnGraphics)
         drawTargetCursor(graphics);
         mMap->draw(graphics, mCameraX, mCameraY, 1);
         mMap->draw(graphics, mCameraX, mCameraY, 2);
+        if (mShowDebugPath)
+        {
+            mMap->drawCollision(graphics, mCameraX, mCameraY);
+        }
         mMap->drawOverlay(graphics, mViewX, mViewY,
                 (int) config.getValue("OverlayDetail", 2));
         drawTargetName(graphics);
@@ -335,7 +339,7 @@ Viewport::drawDebugPath(Graphics *graphics)
 
     Path debugPath = mMap->findPath(
             player_node->mX / 32, player_node->mY / 32,
-            mouseTileX, mouseTileY);
+            mouseTileX, mouseTileY, 0xFF);
 
     graphics->setColor(gcn::Color(255, 0, 0));
     for (PathIterator i = debugPath.begin(); i != debugPath.end(); i++)
@@ -399,7 +403,7 @@ Viewport::mousePressed(gcn::MouseEvent &event)
                 player_node->pickUp(item);
         }
         // Just walk around
-        else if (mMap->getWalk(tilex, tiley))
+        else if (mMap->getWalk(tilex, tiley, player_node->getWalkMask()))
         {
             // XXX XXX XXX REALLY UGLY!
             Uint8 *keys = SDL_GetKeyState(NULL);
diff --git a/src/localplayer.cpp b/src/localplayer.cpp
index 1614b7e7..aa3bb6ba 100644
--- a/src/localplayer.cpp
+++ b/src/localplayer.cpp
@@ -233,17 +233,17 @@ void LocalPlayer::walk(unsigned char dir)
         dx += 32;
 
     // Prevent skipping corners over colliding tiles
-    if (dx && mMap->tileCollides((mX + dx) / 32, mY / 32))
+    if (dx && !mMap->getWalk((mX + dx) / 32, mY / 32, getWalkMask()))
         dx = 16 - mX % 32;
-    if (dy && mMap->tileCollides(mX / 32, (mY + dy) / 32))
+    if (dy && !mMap->getWalk(mX / 32, (mY + dy) / 32, getWalkMask()))
         dy = 16 - mY % 32;
 
     // Choose a straight direction when diagonal target is blocked
-    if (dx && dy && !mMap->getWalk((mX + dx) / 32, (mY + dy) / 32))
+    if (dx && dy && !mMap->getWalk((mX + dx) / 32, (mY + dy) / 32, getWalkMask()))
         dx = 16 - mX % 32;
 
     // Walk to where the player can actually go
-    if ((dx || dy) && mMap->getWalk((mX + dx) / 32, (mY + dy) / 32))
+    if ((dx || dy) && mMap->getWalk((mX + dx) / 32, (mY + dy) / 32, getWalkMask()))
     {
         setDestination(mX + dx, mY + dy);
     }
@@ -259,9 +259,9 @@ void LocalPlayer::setDestination(Uint16 x, Uint16 y)
 {
     // Fix coordinates so that the player does not seem to dig into walls.
     int tx = x / 32, ty = y / 32, fx = x % 32, fy = y % 32;
-    if (fx != 16 && mMap->tileCollides(tx + fx / 16 * 2 - 1, ty)) fx = 16;
-    if (fy != 16 && mMap->tileCollides(tx, ty + fy / 16 * 2 - 1)) fy = 16;
-    if (fx != 16 && fy != 16 && mMap->tileCollides(tx + fx / 16 * 2 - 1, ty + fy / 16 * 2 - 1)) fx = 16;
+    if (fx != 16 && !mMap->getWalk(tx + fx / 16 * 2 - 1, ty, getWalkMask())) fx = 16;
+    if (fy != 16 && !mMap->getWalk(tx, ty + fy / 16 * 2 - 1, getWalkMask())) fy = 16;
+    if (fx != 16 && fy != 16 && !mMap->getWalk(tx + fx / 16 * 2 - 1, ty + fy / 16 * 2 - 1, getWalkMask())) fx = 16;
     x = tx * 32 + fx;
     y = ty * 32 + fy;
 
diff --git a/src/map.cpp b/src/map.cpp
index c2b0b9a1..afa2bcc5 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -72,6 +72,11 @@ Map::Map(int width, int height, int tileWidth, int tileHeight):
     int size = mWidth * mHeight;
 
     mMetaTiles = new MetaTile[size];
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        mOccupation[i] = new int[size];
+        memset(mOccupation[i], 0, size * sizeof(int));
+    }
     mTiles = new Image*[size * 3];
     std::fill_n(mTiles, size * 3, (Image*)0);
 }
@@ -81,6 +86,10 @@ Map::~Map()
     // clean up map data
     delete[] mMetaTiles;
     delete[] mTiles;
+    for (int i=0; i < NB_BLOCKTYPES; i++)
+    {
+        delete[] mOccupation[i];
+    }
     // clean up tilesets
     for_each(mTilesets.begin(), mTilesets.end(), make_dtor(mTilesets));
     mTilesets.clear();
@@ -186,6 +195,59 @@ void Map::draw(Graphics *graphics, int scrollX, int scrollY, int layer)
     }
 }
 
+void Map::drawCollision(Graphics *graphics, int scrollX, int scrollY)
+{
+    int endPixelY = graphics->getHeight() + scrollY + mTileHeight - 1;
+    int startX = scrollX / mTileWidth;
+    int startY = scrollY / mTileHeight;
+    int endX = (graphics->getWidth() + scrollX + mTileWidth - 1) / mTileWidth;
+    int endY = endPixelY / mTileHeight;
+
+    if (startX < 0) startX = 0;
+    if (startY < 0) startY = 0;
+    if (endX > mWidth) endX = mWidth;
+    if (endY > mHeight) endY = mHeight;
+
+    for (int y = startY; y < endY; y++)
+    {
+        for (int x = startX; x < endX; x++)
+        {
+            graphics->setColor(gcn::Color(0, 0, 0, 64));
+                graphics->drawRectangle(gcn::Rectangle(
+                    x * mTileWidth - scrollX,
+                    y * mTileWidth - scrollY,
+                    33, 33));
+
+            if (!getWalk(x, y, BLOCKMASK_WALL))
+            {
+                graphics->setColor(gcn::Color(0, 0, 200, 64));
+                graphics->fillRectangle(gcn::Rectangle(
+                    x * mTileWidth - scrollX,
+                    y * mTileWidth - scrollY,
+                    32, 32));
+            }
+
+            if (!getWalk(x, y, BLOCKMASK_MONSTER))
+            {
+                graphics->setColor(gcn::Color(200, 0, 0, 64));
+                graphics->fillRectangle(gcn::Rectangle(
+                    x * mTileWidth - scrollX,
+                    y * mTileWidth - scrollY,
+                    32, 32));
+            }
+
+            if (!getWalk(x, y, BLOCKMASK_CHARACTER))
+            {
+                graphics->setColor(gcn::Color(0, 200, 0, 64));
+                graphics->fillRectangle(gcn::Rectangle(
+                    x * mTileWidth - scrollX,
+                    y * mTileWidth - scrollY,
+                    32, 32));
+            }
+        }
+    }
+}
+
 void Map::drawOverlay(Graphics *graphics,
                       float scrollX, float scrollY, int detail)
 {
@@ -231,7 +293,10 @@ void Map::setTileWithGid(int x, int y, int layer, int gid)
     if (layer == 3)
     {
         Tileset *set = getTilesetWithGid(gid);
-        setWalk(x, y, (!set || (gid - set->getFirstGid() == 0)));
+        if (set && (gid - set->getFirstGid() != 0))
+        {
+            blockTile(x, y, BLOCKTYPE_WALL);
+        }
     }
     else if (layer < 3)
     {
@@ -271,34 +336,69 @@ Image* Map::getTileWithGid(int gid) const
     return NULL;
 }
 
-void Map::setWalk(int x, int y, bool walkable)
+void Map::blockTile(int x, int y, BlockType type)
 {
-    mMetaTiles[x + y * mWidth].walkable = walkable;
-}
+    if (type == BLOCKTYPE_NONE) return;
+    int tileNum = x + y * mWidth;
+    assert (tileNum <= mWidth * mHeight);
 
-bool Map::getWalk(int x, int y) const
-{
-    return !tileCollides(x, y) && !occupied(x, y);
+    if ((++mOccupation[type][tileNum]) > 0)
+    {
+        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;
+        }
+    }
 }
 
-bool Map::occupied(int x, int y) const
+void Map::freeTile(int x, int y, BlockType type)
 {
-    Beings &beings = beingManager->getAll();
-    for (BeingIterator i = beings.begin(); i != beings.end(); i++)
+    if (type == BLOCKTYPE_NONE) return;
+
+    int tileNum = x + y * mWidth;
+    assert (tileNum <= mWidth * mHeight);
+
+    if ((--mOccupation[type][tileNum]) <= 0)
     {
-        // job 45 is a portal, they don't collide
-        if ((*i)->mX / 32 == x && (*i)->mY / 32 == y && (*i)->mJob != 45)
+        switch (type)
         {
-            return true;
+            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;
         }
     }
-
-    return false;
 }
 
-bool Map::tileCollides(int x, int y) const
+bool Map::getWalk(int x, int y, char walkmask) const
 {
-    return !(contains(x, y) && mMetaTiles[x + y * mWidth].walkable);
+    // You can't walk outside of the map
+    if (x < 0 || y < 0 || x >= mWidth || y >= mHeight)
+    {
+        return false;
+    }
+
+    // Check if the tile is walkable
+    return !(mMetaTiles[x + y * mWidth].blockmask & walkmask);
 }
 
 bool Map::contains(int x, int y) const
@@ -334,17 +434,16 @@ void Map::removeSprite(SpriteIterator iterator)
 
 static int const basicCost = 100;
 
-Path Map::findPath(int startX, int startY, int destX, int destY)
+Path Map::findPath(int startX, int startY, int destX, int destY, unsigned char walkmask, int maxCost)
 {
     // Path to be built up (empty by default)
-    Path path;
+    std::list<PATH_NODE> path;
 
     // Declare open list, a list with open tiles sorted on F cost
     std::priority_queue<Location> openList;
 
-    // Return empty path when destination collides
-    if (tileCollides(destX, destY))
-        return path;
+    // 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);
@@ -358,19 +457,20 @@ Path Map::findPath(int startX, int startY, int destX, int destY)
     // Keep trying new open tiles until no more tiles to try or target found
     while (!openList.empty() && !foundPath)
     {
-        // Take the location with the lowest F cost from the open list.
+        // Take the location with the lowest F cost from the open list, and
+        // add it to the closed list.
         Location curr = openList.top();
         openList.pop();
 
         // 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.tile->whichList == onClosedList)
         {
             continue;
         }
 
         // Put the current tile on the closed list
-        curr.tile->whichList = mOnClosedList;
+        curr.tile->whichList = onClosedList;
 
         // Check the adjacent tiles
         for (int dy = -1; dy <= 1; dy++)
@@ -383,28 +483,28 @@ Path Map::findPath(int startX, int startY, int destX, int destY)
 
                 // 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) ||
+                        (x < 0 || y < 0 || x >= mWidth || y >= mHeight))
                 {
                     continue;
                 }
 
                 MetaTile *newTile = getMetaTile(x, y);
 
-                // Skip if the tile is on the closed list or collides
-                if (newTile->whichList == mOnClosedList || tileCollides(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. 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;
                     }
@@ -428,21 +528,14 @@ Path Map::findPath(int startX, int startY, int destX, int destY)
                     ++Gcost;
                 }
 
-                // It costs extra to walk through a being (needs to be enough
-                // to make it more attractive to walk around).
-                if (occupied(x, y))
-                {
-                    Gcost += 30;
-                }
-
                 // Skip if Gcost becomes too much
                 // Warning: probably not entirely accurate
-                if (Gcost > 20 * basicCost)
+                if (Gcost > maxCost * basicCost)
                 {
                     continue;
                 }
 
-                if (newTile->whichList != mOnOpenList)
+                if (newTile->whichList != onOpenList)
                 {
                     // Found a new tile (not on open nor on closed list)
 
@@ -464,7 +557,7 @@ Path Map::findPath(int startX, int startY, int destX, int destY)
 
                     if (x != destX || y != destY) {
                         // Add this tile to the open list
-                        newTile->whichList = mOnOpenList;
+                        newTile->whichList = onOpenList;
                         openList.push(Location(x, y, newTile));
                     }
                     else {
@@ -493,8 +586,8 @@ Path Map::findPath(int startX, int startY, int destX, int destY)
 
     // 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.
-    mOnClosedList += 2;
-    mOnOpenList += 2;
+    onClosedList += 2;
+    onOpenList += 2;
 
     // If a path has been found, iterate backwards using the parent locations
     // to extract it.
diff --git a/src/map.h b/src/map.h
index d8cc2189..71bbf843 100644
--- a/src/map.h
+++ b/src/map.h
@@ -54,7 +54,7 @@ struct MetaTile
     /**
      * Constructor.
      */
-    MetaTile():whichList(0) {};
+    MetaTile():whichList(0), blockmask(0) {};
 
     // Pathfinding members
     int Fcost;              /**< Estimation of total path cost */
@@ -63,7 +63,7 @@ struct 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 walk on this tile */
+    unsigned char blockmask;          /**< Can beings walk on this tile */
 };
 
 /**
@@ -72,6 +72,15 @@ struct MetaTile
 class Map : public Properties
 {
     public:
+        enum BlockType
+        {
+            BLOCKTYPE_NONE = -1,
+            BLOCKTYPE_WALL,
+            BLOCKTYPE_CHARACTER,
+            BLOCKTYPE_MONSTER,
+            NB_BLOCKTYPES
+        };
+
         /**
          * Constructor, taking map and tile size as parameters.
          */
@@ -94,6 +103,11 @@ class Map : public Properties
         void draw(Graphics *graphics, int scrollX, int scrollY, int layer);
 
         /**
+         * Visualizes collision layer for debugging
+         */
+        void drawCollision(Graphics *graphics, int scrollX, int scrollY);
+
+        /**
          * Draws the overlay graphic to the given graphics output.
          */
         void
@@ -129,19 +143,19 @@ class Map : public Properties
         MetaTile *getMetaTile(int x, int y) const;
 
         /**
-         * Set walkability flag for a tile.
+         * Marks a tile as occupied
          */
-        void setWalk(int x, int y, bool walkable);
+        void blockTile(int x, int y, BlockType type);
 
         /**
-         * Tell if a tile is walkable or not, includes checking beings.
+         * Marks a tile as unoccupied
          */
-        bool getWalk(int x, int y) const;
+        void freeTile(int x, int y, BlockType type);
 
         /**
-         * Tell if a tile collides, not including a check on beings.
+         * Gets walkability for a tile with a blocking bitmask
          */
-        bool tileCollides(int x, int y) const;
+        bool getWalk(int x, int y, char walkmask) const;
 
         /**
          * Returns the width of this map.
@@ -171,7 +185,7 @@ class Map : public Properties
          * Find a path from one location to the next.
          */
         std::list<PATH_NODE>
-        findPath(int startX, int startY, int destX, int destY);
+        findPath(int startX, int startY, int destX, int destY, unsigned char walkmask, int maxCost = 20);
 
         /**
          * Adds a sprite to the map.
@@ -209,14 +223,20 @@ class Map : public Properties
         Tileset* getTilesetWithGid(int gid) const;
 
         /**
-         * Tells whether a tile is occupied by a being.
+         * Tells whether the given coordinates fall within the map boundaries.
          */
-        bool occupied(int x, int y) const;
+        bool contains(int x, int y) const;
 
         /**
-         * Tells whether the given coordinates fall within the map boundaries.
+         * Blockmasks for different entities
          */
-        bool contains(int x, int y) const;
+        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];
+
+        // Pathfinding members
+        int onClosedList, onOpenList;
 
         int mWidth, mHeight;
         int mTileWidth, mTileHeight;
diff --git a/src/monster.cpp b/src/monster.cpp
index 5fbcfaea..abc7946f 100644
--- a/src/monster.cpp
+++ b/src/monster.cpp
@@ -44,6 +44,11 @@ Monster::Monster(Uint16 id, Uint16 job, Map *map):
         AnimatedSprite::load("graphics/sprites/" + filename);
 }
 
+Monster::~Monster()
+{
+    if (mMap) mMap->freeTile(mX / 32, mY / 32, getBlockType());
+}
+
 Being::Type
 Monster::getType() const
 {
diff --git a/src/monster.h b/src/monster.h
index 585f6f09..ecf7ad51 100644
--- a/src/monster.h
+++ b/src/monster.h
@@ -33,6 +33,8 @@ class Monster : public Being
     public:
         Monster(Uint16 id, Uint16 job, Map *map);
 
+        virtual ~Monster();
+
         virtual void setAction(Action action, int attackType);
 
         virtual Type getType() const;
@@ -58,6 +60,19 @@ class Monster : public Being
          */
         const MonsterInfo&
         getInfo() const;
+
+        /**
+         * Gets the way the monster is blocked for other objects
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x83; } // blocked walls, other monsters and players ( bin 1000 0011)
+
+    protected:
+        /**
+         * Gets the way the monster blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_MONSTER; }
 };
 
 #endif
diff --git a/src/net/beinghandler.cpp b/src/net/beinghandler.cpp
index 05795cb1..f31ee48b 100644
--- a/src/net/beinghandler.cpp
+++ b/src/net/beinghandler.cpp
@@ -496,8 +496,7 @@ BeingHandler::handleBeingEnterMessage(MessageIn &msg)
             return;
     }
 
-    being->mX = px;
-    being->mY = py;
+    being->setPositionInPixels(px, py);
     being->setDestination(px, py);
     being->setAction(action);
 }
@@ -544,11 +543,10 @@ void BeingHandler::handleBeingsMoveMessage(MessageIn &msg)
         {
             being->setWalkSpeed(speed * 10);
         }
-        if (abs(being->mX - sx) + abs(being->mY - sy) > 4 * 32)
+        if (abs(being->getPixelX() - sx) + abs(being->getPixelY() - sy) > 4 * 32)
         {
             // Too large a desynchronization.
-            being->mX = sx;
-            being->mY = sy;
+            being->setPositionInPixels(sx, sy);
             being->setDestination(dx, dy);
         }
         else if (!(flags & MOVING_POSITION))
@@ -582,8 +580,6 @@ void BeingHandler::handleBeingAttackMessage(MessageIn &msg)
         case DIRECTION_RIGHT: being->setDirection(Being::RIGHT); break;
     }
 
-    logger->log("Attacktype: %d", attackType);
-
     being->setAction(Being::ATTACK, attackType);
 }
 
diff --git a/src/net/playerhandler.cpp b/src/net/playerhandler.cpp
index 3c06d2f5..b908eae5 100644
--- a/src/net/playerhandler.cpp
+++ b/src/net/playerhandler.cpp
@@ -301,6 +301,5 @@ PlayerHandler::handleMapChangeMessage(MessageIn &msg)
     current_npc = 0;
 
     player_node->setAction(Being::STAND);
-    player_node->mX = x;
-    player_node->mY = y;
+    player_node->setPositionInPixels(x, y);
 }
diff --git a/src/player.cpp b/src/player.cpp
index 2f1fc648..c218ad01 100644
--- a/src/player.cpp
+++ b/src/player.cpp
@@ -44,6 +44,11 @@ Player::Player(int id, int job, Map *map):
 {
 }
 
+Player::~Player()
+{
+    if (mMap) mMap->freeTile(mX / 32, mY / 32, getBlockType());
+}
+
 Being::Type
 Player::getType() const
 {
diff --git a/src/player.h b/src/player.h
index aff75221..76d6b460 100644
--- a/src/player.h
+++ b/src/player.h
@@ -49,6 +49,8 @@ class Player : public Being
          */
         Player(int id, int job, Map *map);
 
+        virtual ~Player();
+
         virtual Type
         getType() const;
 
@@ -113,10 +115,20 @@ class Player : public Being
          */
         short getNumberOfGuilds();
 
+        /**
+         * Gets the way the character is blocked by other objects
+         */
+        virtual unsigned char getWalkMask() const
+        { return 0x82; } // blocked by walls and monsters ( bin 1000 0010)
+
     protected:
         // Character guild information
         std::map<int, Guild*> mGuilds;
-
+        /**
+         * Gets the way the monster blocks pathfinding for other objects
+         */
+        virtual Map::BlockType getBlockType() const
+        { return Map::BLOCKTYPE_CHARACTER; }
     private:
         Gender mGender;
         Uint8 mHairStyle;