summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBjørn Lindeijer <bjorn@lindeijer.nl>2005-02-13 12:04:24 +0000
committerBjørn Lindeijer <bjorn@lindeijer.nl>2005-02-13 12:04:24 +0000
commitaec5250a740302fbf7b64eb1250d5ad15eaee57e (patch)
tree2c9de3e9fb8afe90b2cf85a7d032aae3966b61f6
parentba5dc49d30d6ba465b01dbf3abc933250edcb6c6 (diff)
downloadmana-client-aec5250a740302fbf7b64eb1250d5ad15eaee57e.tar.gz
mana-client-aec5250a740302fbf7b64eb1250d5ad15eaee57e.tar.bz2
mana-client-aec5250a740302fbf7b64eb1250d5ad15eaee57e.tar.xz
mana-client-aec5250a740302fbf7b64eb1250d5ad15eaee57e.zip
Don't skip corners in A* pathfinding algorithm.
-rw-r--r--file.list1
-rw-r--r--src/Makefile.am1
-rw-r--r--src/being.cpp1
-rw-r--r--src/graphic/graphic.cpp5
-rw-r--r--src/map.cpp36
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;