diff options
author | Bjørn Lindeijer <bjorn@lindeijer.nl> | 2005-02-09 18:57:27 +0000 |
---|---|---|
committer | Bjørn Lindeijer <bjorn@lindeijer.nl> | 2005-02-09 18:57:27 +0000 |
commit | 6e114371296d849132e538817a16877866fa84f3 (patch) | |
tree | bd4fa48fb15a2c9a6705f68c1733275cec5ef26c /src | |
parent | 579969a548e37bb631d3f79a5d420e577e022630 (diff) | |
download | mana-client-6e114371296d849132e538817a16877866fa84f3.tar.gz mana-client-6e114371296d849132e538817a16877866fa84f3.tar.bz2 mana-client-6e114371296d849132e538817a16877866fa84f3.tar.xz mana-client-6e114371296d849132e538817a16877866fa84f3.zip |
More of a start on pathfinding, but still just a start.
Diffstat (limited to 'src')
-rw-r--r-- | src/map.cpp | 37 | ||||
-rw-r--r-- | src/map.h | 32 |
2 files changed, 68 insertions, 1 deletions
diff --git a/src/map.cpp b/src/map.cpp index a9437f9f..d7ccb4d1 100644 --- a/src/map.cpp +++ b/src/map.cpp @@ -25,6 +25,7 @@ #include "map.h" #include "log.h" #include "being.h" +#include <queue> #include <stdio.h> #ifdef WIN32 @@ -78,9 +79,19 @@ Tile::Tile(): { } +Location::Location(int x, int y, Tile *tile): + x(x), y(y), tile(tile) +{ +} + +bool Location::operator< (const Location &loc) const +{ + return tile->Fcost < loc.tile->Fcost; +} Map::Map(): - width(0), height(0) + width(0), height(0), + onClosedList(1), onOpenList(2) { tiles = new Tile[width * height]; } @@ -193,9 +204,33 @@ int Map::getHeight() PATH_NODE *Map::findPath(int startX, int startY, int destX, int destY) { + // Declare open list, a list with open tiles sorted on F cost + std::priority_queue<Location> openList; + // Return when destination not walkable if (!getWalk(destX, destY)) return NULL; + // Reset starting square's G cost to 0 + Tile *startTile = &tiles[startX + startY * width]; + startTile->Gcost = 0; + + // Add the start point to the open list + openList.push(Location(startX, startY, startTile)); + + // Keep trying new open tiles until no more tiles to try or target found + while (!openList.empty()) { + // Take the location with the lowest F cost from the open list, and + // add it to the closed list. + Location curr = openList.top(); + openList.pop(); + curr.tile->whichList = onClosedList; + } + + // Two new values to indicate wether a tile is on the open or closed list, + // this way we don't have to clear all the values between each pathfinding. + onClosedList += 2; + onOpenList += 2; + // No path found return NULL; } @@ -30,9 +30,15 @@ #define TILE_WALKABLE 1 #define TILE_ANIMATED 2 +/** + * A tile on a tile map. + */ class Tile { public: + /** + * Constructor. + */ Tile(); // Tile data @@ -45,6 +51,29 @@ class Tile int parentX, parentY; }; +/** + * A location on a tile map. Used for pathfinding, open list. + */ +class Location +{ + public: + /** + * Constructor. + */ + Location(int x, int y, Tile *tile); + + /** + * Comparison operator. + */ + bool operator< (const Location &loc) const; + + int x, y; + Tile *tile; +}; + +/** + * A tile map. + */ class Map { public: @@ -106,6 +135,9 @@ class Map private: int width, height; Tile *tiles; + + // Pathfinding members + int onClosedList, onOpenList; }; extern Map tiledMap; |