Don't skip corners in A* pathfinding algorithm.

5 files changed, 31 insertions, 13 deletions

diff --git a/file.list b/file.list
index 3339611c..3432ab76 100644
--- a/file.list
+++ b/file.list
@@ -41,7 +41,6 @@ MODULES = src/sound/sound.cpp \
           src/resources/resource.cpp \
           src/resources/resourcemanager.cpp \
           src/configuration.cpp \
-          src/astar.cpp \
           src/base64.cpp \
           src/being.cpp \
           src/game.cpp \
diff --git a/src/Makefile.am b/src/Makefile.am
index 8f2c4ef8..9c07832f 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,7 +41,6 @@ tmw_SOURCES = sound/sound.cpp \
 	resources/image.cpp \
 	resources/resource.cpp \
 	resources/resourcemanager.cpp \
-	astar.cpp \
 	base64.cpp \
 	being.cpp \
 	configuration.cpp \
diff --git a/src/being.cpp b/src/being.cpp
index 8207d4a2..422f8d83 100644
--- a/src/being.cpp
+++ b/src/being.cpp
@@ -21,7 +21,6 @@
  *  $Id$
  */
 
-#include "astar.h"
 #include "being.h"
 #include "game.h"
 
diff --git a/src/graphic/graphic.cpp b/src/graphic/graphic.cpp
index 107c441f..d39338de 100644
--- a/src/graphic/graphic.cpp
+++ b/src/graphic/graphic.cpp
@@ -505,9 +505,10 @@ void Engine::draw()
         Tile *tile = tiledMap.getTile(debugPath->x, debugPath->y);
 
         std::stringstream cost;
-        cost << tile->Fcost;
+        cost << tile->Gcost;
         guiGraphics->_beginDraw();
-        guiGraphics->drawText(cost.str(), destRect.x - 12, destRect.y + 8);
+        guiGraphics->drawText(cost.str(), destRect.x + 4, destRect.y + 12,
+                gcn::Graphics::CENTER);
         guiGraphics->_endDraw();
 
         // Move to the next node
diff --git a/src/map.cpp b/src/map.cpp
index 1e4cb3ba..c810fab6 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -233,6 +233,15 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
         // 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 == onClosedList)
+        {
+            continue;
+        }
+
+        // Put the current tile on the closed list
         curr.tile->whichList = onClosedList;
 
         // Check the adjacent tiles
@@ -244,9 +253,8 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
                 int x = curr.x + dx;
                 int y = curr.y + dy;
 
-                // Skip if if we're checking the same tile we're leaving
-                // from, or if the new location falls outside of the map
-                // boundaries
+                // 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))
                 {
@@ -261,6 +269,21 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
                     continue;
                 }
 
+                // When taking a diagonal step, verify that we can skip the
+                // corner. We allow skipping past beings but not past non-
+                // walkable tiles.
+                if (dx != 0 && dy != 0)
+                {
+                    Tile *t1 = getTile(curr.x, curr.y + dy);
+                    Tile *t2 = getTile(curr.x + dx, curr.y);
+
+                    if ((t1->flags & TILE_WALKABLE) == 0 ||
+                            (t2->flags & TILE_WALKABLE) == 0)
+                    {
+                        continue;
+                    }
+                }
+
                 // Calculate G cost for this route, 10 for moving straight and
                 // 14 for moving diagonal
                 int Gcost = curr.tile->Gcost + ((dx == 0 || dy == 0) ? 10 : 14);
@@ -315,9 +338,8 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
 
     // If a path has been found, iterate backwards using the parent locations
     // to extract it.
-    if (foundPath) {
-        //printf("Found path from (%d, %d) to (%d, %d):\n",
-        //        startX, startY, destX, destY);
+    if (foundPath)
+    {
         PATH_NODE *path = new PATH_NODE(destX, destY);
         int pathX = destX;
         int pathY = destY;
@@ -329,8 +351,6 @@ PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY)
             pathX = tile->parentX;
             pathY = tile->parentY;
 
-            //printf("- (%d, %d)\n", pathX, pathY);
-
             // Add the new path node to the start of the path list
             PATH_NODE *pn = new PATH_NODE(pathX, pathY);
             pn->next = path;