From aec5250a740302fbf7b64eb1250d5ad15eaee57e Mon Sep 17 00:00:00 2001
From: Bjørn Lindeijer <bjorn@lindeijer.nl>
Date: Sun, 13 Feb 2005 12:04:24 +0000
Subject: Don't skip corners in A* pathfinding algorithm.
---
file.list | 1 -
src/Makefile.am | 1 -
src/being.cpp | 1 -
src/graphic/graphic.cpp | 5 +++--
src/map.cpp | 36 ++++++++++++++++++++++++++++--------
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;
--
cgit v1.2.3-70-g09d2