add walkmaps support.

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

1 files changed, 161 insertions, 0 deletions

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;
+            }
+        }
+    }
+}