add walkmaps support.

Fast detecting between two targets is they in same walkable area.

17 files changed, 393 insertions, 32 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 13b47965c..5523549ac 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -610,6 +610,10 @@ SET(SRCS
     mobileopenglgraphics.h
     mouseinput.cpp
     mouseinput.h
+    mumblemanager.cpp
+    mumblemanager.h
+    navigationmanager.cpp
+    navigationmanager.h
     normalopenglgraphics.cpp
     normalopenglgraphics.h
     notifications.h
@@ -660,8 +664,8 @@ SET(SRCS
     variabledata.h
     vector.cpp
     vector.h
-    mumblemanager.cpp
-    mumblemanager.h
+    walklayer.cpp
+    walklayer.h
     )
 
 SET(SRCS_GUICHAN
diff --git a/src/Makefile.am b/src/Makefile.am
index 453d53160..c4b5971fa 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -613,6 +613,8 @@ manaplus_SOURCES += gui/widgets/avatarlistbox.cpp \
 	      mobileopenglgraphics.h \
 	      mouseinput.cpp \
 	      mouseinput.h \
+	      navigationmanager.cpp \
+	      navigationmanager.h \
 	      normalopenglgraphics.cpp \
 	      normalopenglgraphics.h \
 	      notifications.h \
@@ -663,6 +665,8 @@ manaplus_SOURCES += gui/widgets/avatarlistbox.cpp \
 	      variabledata.h \
 	      vector.cpp \
 	      vector.h \
+	      walklayer.cpp \
+	      walklayer.h \
 	      winver.h
 
 manaplus_SOURCES += \
diff --git a/src/actorspritemanager.cpp b/src/actorspritemanager.cpp
index 90a71aaee..09dc1ff8e 100644
--- a/src/actorspritemanager.cpp
+++ b/src/actorspritemanager.cpp
@@ -636,7 +636,7 @@ bool ActorSpriteManager::pickUpNearest(const int x, const int y,
 
             if ((d < dist || !closestItem) && (!mTargetOnlyReachable
                 || player_node->isReachable(item->getTileX(),
-                item->getTileY())))
+                item->getTileY(), false)))
             {
                 if (allowAll)
                 {
diff --git a/src/client.cpp b/src/client.cpp
index 467d49f3b..dc4f118a8 100644
--- a/src/client.cpp
+++ b/src/client.cpp
@@ -1872,6 +1872,7 @@ void Client::initTempDir()
         logger->error(strprintf(_("%s doesn't exist and can't be created! "
             "Exiting."), mTempDir.c_str()));
     }
+//    ResourceManager::deleteFilesInDirectory(mTempDir);
 }
 
 void Client::initConfigDir()
diff --git a/src/gui/socialwindow.cpp b/src/gui/socialwindow.cpp
index 653140e3f..2b3ec2c3a 100644
--- a/src/gui/socialwindow.cpp
+++ b/src/gui/socialwindow.cpp
@@ -701,7 +701,7 @@ public:
 
             Avatar *const ava = new Avatar(name);
             if (player_node)
-                ava->setOnline(player_node->isReachable(x, y, 0));
+                ava->setOnline(player_node->isReachable(x, y, true));
             else
                 ava->setOnline(false);
             ava->setLevel(-1);
@@ -842,7 +842,7 @@ public:
 
         Avatar *const ava = new Avatar(name);
         if (player_node)
-            ava->setOnline(player_node->isReachable(x, y, 0));
+            ava->setOnline(player_node->isReachable(x, y, true));
         else
             ava->setOnline(false);
         ava->setLevel(-1);
diff --git a/src/localplayer.cpp b/src/localplayer.cpp
index 65f2faaba..3d2af40c6 100644
--- a/src/localplayer.cpp
+++ b/src/localplayer.cpp
@@ -25,6 +25,7 @@
 #include "actorspritemanager.h"
 #include "client.h"
 #include "configuration.h"
+#include "dropshortcut.h"
 #include "effectmanager.h"
 #include "graphics.h"
 #include "guild.h"
@@ -38,7 +39,7 @@
 #include "simpleanimation.h"
 #include "soundmanager.h"
 #include "statuseffect.h"
-#include "dropshortcut.h"
+#include "walklayer.h"
 
 #include "gui/chatwindow.h"
 #include "gui/gui.h"
@@ -2930,28 +2931,6 @@ void LocalPlayer::crazyMoveA()
         mCrazyMoveState = 0;
 }
 
-bool LocalPlayer::isReachable(const int x, const int y,
-                              const int maxCost) const
-{
-    if (!mMap)
-        return false;
-
-    if (x - 1 <= mX && x + 1 >= mX
-        && y - 1 <= mY && y + 1 >= mY )
-    {
-        return true;
-    }
-
-    const Vector &playerPos = getPosition();
-
-    const Path debugPath = mMap->findPath(
-        static_cast<int>(playerPos.x - 16) / 32,
-        static_cast<int>(playerPos.y - 32) / 32,
-        x, y, getWalkMask(), maxCost);
-
-    return !debugPath.empty();
-}
-
 bool LocalPlayer::isReachable(Being *const being,
                               const int maxCost)
 {
@@ -2998,6 +2977,19 @@ bool LocalPlayer::isReachable(Being *const being,
     }
 }
 
+bool LocalPlayer::isReachable(const int x, const int y,
+                              const int allowCollision) const
+{
+    const WalkLayer *const walk = mMap->getWalkLayer();
+    if (!walk)
+        return false;
+    int num = walk->getDataAt(x, y);
+    if (allowCollision && num < 0)
+        num = -num;
+
+    return walk->getDataAt(mX, mY) == num;
+}
+
 bool LocalPlayer::pickUpItems(int pickUpType)
 {
     if (!actorSpriteManager)
diff --git a/src/localplayer.h b/src/localplayer.h
index dcb95a119..7dfa6025f 100644
--- a/src/localplayer.h
+++ b/src/localplayer.h
@@ -300,12 +300,12 @@ class LocalPlayer final : public Being,
 
         void debugMsg(const std::string &str) const;
 
-        bool isReachable(const int x, const int y,
-                         const int maxCost = 0) const A_WARN_UNUSED;
-
         bool isReachable(Being *const being,
                          const int maxCost = 0) A_WARN_UNUSED;
 
+        bool isReachable(const int x, const int y,
+                         const int allowCollision) const A_WARN_UNUSED;
+
         void setHome();
 
         void pingRequest();
diff --git a/src/map.cpp b/src/map.cpp
index db2a46ef8..8ce96bdc5 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -30,6 +30,7 @@
 #include "particle.h"
 #include "simpleanimation.h"
 #include "tileset.h"
+#include "walklayer.h"
 
 #include "resources/ambientlayer.h"
 #include "resources/image.h"
@@ -126,6 +127,7 @@ Map::Map(const int width, const int height,
     mTileWidth(tileWidth), mTileHeight(tileHeight),
     mMaxTileHeight(height),
     mMetaTiles(new MetaTile[mWidth * mHeight]),
+    mWalkLayer(nullptr),
     mHasWarps(false),
     mDebugFlags(MAP_NORMAL),
     mOnClosedList(1), mOnOpenList(2),
@@ -187,6 +189,11 @@ Map::~Map()
     for (int i = 0; i < NB_BLOCKTYPES; i++)
         delete [] mOccupation[i];
 
+    if (mWalkLayer)
+    {
+        mWalkLayer->decRef();
+        mWalkLayer = nullptr;
+    }
     mFringeLayer = nullptr;
     delete_all(mLayers);
     delete_all(mTilesets);
diff --git a/src/map.h b/src/map.h
index 3f922471d..2c5e0ff9c 100644
--- a/src/map.h
+++ b/src/map.h
@@ -41,6 +41,7 @@ class Tileset;
 class SpecialLayer;
 class MapItem;
 class ObjectsLayer;
+class WalkLayer;
 
 typedef std::vector<Tileset*> Tilesets;
 typedef std::vector<MapLayer*> Layers;
@@ -404,6 +405,15 @@ class Map final : public Properties, public ConfigListener
         void setAtlas(Resource *const atlas)
         { mAtlas = atlas; }
 
+        const MetaTile *getMetaTiles() const
+        { return mMetaTiles; }
+
+        WalkLayer *getWalkLayer()
+        { return mWalkLayer; }
+
+        void setWalkLayer(WalkLayer *l)
+        { mWalkLayer = l; }
+
     protected:
         friend class Actor;
         friend class Minimap;
@@ -451,6 +461,7 @@ class Map final : public Properties, public ConfigListener
         int mTileWidth, mTileHeight;
         int mMaxTileHeight;
         MetaTile *mMetaTiles;
+        WalkLayer *mWalkLayer;
         Layers mLayers;
         Tilesets mTilesets;
         Actors mActors;
diff --git a/src/navigationmanager.cpp b/src/navigationmanager.cpp
new file mode 100644
index 000000000..38dd0f718
--- /dev/null
+++ b/src/navigationmanager.cpp
@@ -0,0 +1,161 @@
+/*
+ *  The ManaPlus Client
+ *  Copyright (C) 2013  The ManaPlus Developers
+ *
+ *  This file is part of The ManaPlus Client.
+ *
+ *  This program 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.
+ *
+ *  This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "navigationmanager.h"
+
+#include "map.h"
+#include "walklayer.h"
+
+#include "resources/resource.h"
+
+static const int walkMask = (Map::BLOCKMASK_WALL | Map::BLOCKMASK_AIR
+    | Map::BLOCKMASK_WATER);
+
+namespace {
+    struct Cell
+    {
+        Cell(const int x0, const int y0) :
+            x(x0),
+            y(y0)
+        {
+        }
+
+        int x;
+        int y;
+    };
+}
+
+NavigationManager::NavigationManager()
+{
+}
+
+NavigationManager::~NavigationManager()
+{
+}
+
+Resource *NavigationManager::loadWalkLayer(Map *const map)
+{
+    if (!map)
+        return nullptr;
+
+    const int width = map->getWidth();
+    const int height = map->getHeight();
+    if (width < 2 || height < 2)
+        return nullptr;
+    WalkLayer *const walkLayer = new WalkLayer(width, height);
+
+    const MetaTile *const tiles = map->getMetaTiles();
+    int *data = walkLayer->getData();
+
+    int x = 0;
+    int y = 0;
+    int num = 1;
+    while(findWalkableTile(x, y, width, height,tiles, data))
+    {
+        fillNum(x, y, width, height, num, tiles, data);
+        num ++;
+    }
+
+    return walkLayer;
+}
+
+bool NavigationManager::findWalkableTile(int &x1, int &y1,
+                                         const int width, const int height,
+                                         const MetaTile *const tiles,
+                                         const int *const data)
+{
+    for (int y = 0; y < height; y ++)
+    {
+        const int y2 = y * width;
+        for (int x = 0; x < width; x ++)
+        {
+            const int ptr = x + y2;
+            if (!(tiles[ptr].blockmask & walkMask) && !data[ptr])
+            {
+                x1 = x;
+                y1 = y;
+                return true;
+            }
+        }
+    }
+    return false;
+}
+
+void NavigationManager::fillNum(int x, int y,
+                                const int width, const int height,
+                                const int num, const MetaTile *const tiles,
+                                int *const data)
+{
+    std::vector<Cell> cells;
+    cells.push_back(Cell(x, y));
+    while (!cells.empty())
+    {
+        const Cell cell = cells.back();
+        cells.pop_back();
+        int ptr;
+        x = cell.x;
+        y = cell.y;
+        data[x + width * y] = num;
+        if (x > 0)
+        {
+            ptr = (x - 1) + width * y;
+            if (!data[ptr])
+            {
+                if (!(tiles[ptr].blockmask & walkMask))
+                    cells.push_back(Cell(x - 1, y));
+                else
+                    data[ptr] = -num;
+            }
+        }
+        if (x < width - 1)
+        {
+            ptr = (x + 1) + width * y;
+            if (!data[ptr])
+            {
+                if (!(tiles[ptr].blockmask & walkMask))
+                    cells.push_back(Cell(x + 1, y));
+                else
+                    data[ptr] = -num;
+            }
+        }
+        if (y > 0)
+        {
+            ptr = x + width * (y - 1);
+            if (!data[ptr])
+            {
+                if (!(tiles[ptr].blockmask & walkMask))
+                    cells.push_back(Cell(x, y - 1));
+                else
+                    data[ptr] = -num;
+            }
+        }
+        if (y < height - 1)
+        {
+            ptr = x + width * (y + 1);
+            if (!data[ptr])
+            {
+                if (!(tiles[ptr].blockmask & walkMask))
+                    cells.push_back(Cell(x, y + 1));
+                else
+                    data[ptr] = -num;
+            }
+        }
+    }
+}
diff --git a/src/navigationmanager.h b/src/navigationmanager.h
new file mode 100644
index 000000000..c08f4acd5
--- /dev/null
+++ b/src/navigationmanager.h
@@ -0,0 +1,53 @@
+/*
+ *  The ManaPlus Client
+ *  Copyright (C) 2013  The ManaPlus Developers
+ *
+ *  This file is part of The ManaPlus Client.
+ *
+ *  This program 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.
+ *
+ *  This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NAVIGATIONMANAGER_H
+#define NAVIGATIONMANAGER_H
+
+#include "localconsts.h"
+
+class MetaTile;
+class Map;
+class Resource;
+
+class NavigationManager final
+{
+    public:
+        NavigationManager();
+
+        A_DELETE_COPY(NavigationManager)
+
+        ~NavigationManager();
+
+        static Resource *loadWalkLayer(Map *const map);
+
+    private:
+        static bool findWalkableTile(int &x1, int &y1,
+                                     const int width, const int height,
+                                     const MetaTile *const tiles,
+                                     const int *const data);
+
+        static void fillNum(int x, int y,
+                            const int width, const int height,
+                            const int num, const MetaTile *const tiles,
+                            int *const data);
+};
+
+#endif
diff --git a/src/resources/mapreader.cpp b/src/resources/mapreader.cpp
index 6a149c6fd..464680620 100644
--- a/src/resources/mapreader.cpp
+++ b/src/resources/mapreader.cpp
@@ -279,13 +279,15 @@ Map *MapReader::readMap(XmlNodePtr node, const std::string &path)
 
     const std::string fileName = path.substr(path.rfind("/") + 1);
     map->setProperty("shortName", fileName);
+    ResourceManager *const resman = ResourceManager::getInstance();
+
 #ifdef USE_OPENGL
     if (graphicsManager.getUseAtlases())
     {
         const MapDB::MapInfo *const info = MapDB::getMapAtlas(fileName);
         if (info)
         {
-            map->setAtlas(ResourceManager::getInstance()->getAtlas(
+            map->setAtlas(resman->getAtlas(
                 info->atlas, *info->files));
         }
     }
@@ -393,6 +395,7 @@ Map *MapReader::readMap(XmlNodePtr node, const std::string &path)
     map->clearIndexedTilesets();
     map->setActorsFix(0, atoi(map->getProperty("actorsfix").c_str()));
     map->reduce();
+    map->setWalkLayer(resman->getWalkLayer(fileName, map));
     return map;
 }
 
diff --git a/src/resources/mapreader.h b/src/resources/mapreader.h
index 26e47a74c..63805ac60 100644
--- a/src/resources/mapreader.h
+++ b/src/resources/mapreader.h
@@ -29,6 +29,7 @@
 
 class Map;
 class Properties;
+class Resource;
 class Tileset;
 
 /**
diff --git a/src/resources/resourcemanager.cpp b/src/resources/resourcemanager.cpp
index 9a4d1c3f1..43092e28d 100644
--- a/src/resources/resourcemanager.cpp
+++ b/src/resources/resourcemanager.cpp
@@ -26,6 +26,9 @@
 #include "client.h"
 #include "configuration.h"
 #include "logger.h"
+#include "map.h"
+#include "navigationmanager.h"
+#include "walklayer.h"
 
 #include "resources/atlasmanager.h"
 #include "resources/dye.h"
@@ -740,6 +743,31 @@ Resource *ResourceManager::getAtlas(const std::string &name,
 }
 #endif
 
+struct WalkLayerLoader
+{
+    const std::string name;
+    Map *map;
+
+    static Resource *load(const void *const v)
+    {
+        if (!v)
+            return nullptr;
+
+        const WalkLayerLoader *const rl = static_cast<const
+            WalkLayerLoader *const>(v);
+        Resource *const resource = NavigationManager::loadWalkLayer(rl->map);
+        return resource;
+    }
+};
+
+WalkLayer *ResourceManager::getWalkLayer(const std::string &name,
+                                        Map *const map)
+{
+    WalkLayerLoader rl = {name, map};
+    return static_cast<WalkLayer*>(get("map_" + name,
+        WalkLayerLoader::load, &rl));
+}
+
 struct SpriteDefLoader
 {
     std::string path;
diff --git a/src/resources/resourcemanager.h b/src/resources/resourcemanager.h
index 0248aeda2..72efe8693 100644
--- a/src/resources/resourcemanager.h
+++ b/src/resources/resourcemanager.h
@@ -37,10 +37,12 @@
 class AnimationDelayLoad;
 class Image;
 class ImageSet;
+class Map;
 class SDLMusic;
 class Resource;
 class SoundEffect;
 class SpriteDef;
+class WalkLayer;
 
 struct SDL_Surface;
 struct SDL_RWops;
@@ -222,6 +224,8 @@ class ResourceManager final
                            const StringVect &files) A_WARN_UNUSED;
 #endif
 
+        WalkLayer *getWalkLayer(const std::string &name, Map *const map);
+
         /**
          * Creates a sprite definition based on a given path and the supplied
          * variant.
diff --git a/src/walklayer.cpp b/src/walklayer.cpp
new file mode 100644
index 000000000..6a18ba205
--- /dev/null
+++ b/src/walklayer.cpp
@@ -0,0 +1,44 @@
+/*
+ *  The ManaPlus Client
+ *  Copyright (C) 2013  The ManaPlus Developers
+ *
+ *  This file is part of The ManaPlus Client.
+ *
+ *  This program 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.
+ *
+ *  This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "walklayer.h"
+
+#include "debug.h"
+
+WalkLayer::WalkLayer(const int width, const int height) :
+    mWidth(width),
+    mHeight(height)
+{
+    const int sz = width * height;
+    mTiles = new int[sz];
+    std::fill_n(mTiles, sz, 0);
+}
+
+WalkLayer::~WalkLayer()
+{
+    delete [] mTiles;
+}
+
+int WalkLayer::getDataAt(const int x, const int y) const
+{
+    if (x < 0 || x >= mWidth || y < 0 || y >= mHeight)
+        return 0;
+    return mTiles[x + y * mWidth];
+}
diff --git a/src/walklayer.h b/src/walklayer.h
new file mode 100644
index 000000000..104920471
--- /dev/null
+++ b/src/walklayer.h
@@ -0,0 +1,48 @@
+/*
+ *  The ManaPlus Client
+ *  Copyright (C) 2013  The ManaPlus Developers
+ *
+ *  This file is part of The ManaPlus Client.
+ *
+ *  This program 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.
+ *
+ *  This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef WALKLAYER_H
+#define WALKLAYER_H
+
+#include "resources/resource.h"
+
+#include "localconsts.h"
+
+class WalkLayer final : public Resource
+{
+    public:
+        WalkLayer(const int width, const int height);
+
+        A_DELETE_COPY(WalkLayer)
+
+        ~WalkLayer();
+
+        int *getData()
+        { return mTiles; }
+
+        int getDataAt(const int x, const int y) const;
+
+    private:
+        int mWidth;
+        int mHeight;
+        int *mTiles;
+};
+
+#endif