diff options
Diffstat (limited to 'src/game-server')
-rw-r--r-- | src/game-server/actor.h | 4 | ||||
-rw-r--r-- | src/game-server/character.h | 4 | ||||
-rw-r--r-- | src/game-server/map.cpp | 244 | ||||
-rw-r--r-- | src/game-server/map.h | 89 | ||||
-rw-r--r-- | src/game-server/mapreader.cpp | 2 | ||||
-rw-r--r-- | src/game-server/monster.h | 4 | ||||
-rw-r--r-- | src/game-server/npc.h | 5 |
7 files changed, 176 insertions, 176 deletions
diff --git a/src/game-server/actor.h b/src/game-server/actor.h index 3aac3b60..e345d579 100644 --- a/src/game-server/actor.h +++ b/src/game-server/actor.h @@ -127,8 +127,8 @@ class Actor : public Thing /** * Gets the way the actor blocks pathfinding for other actors. */ - virtual Map::BlockType getBlockType() const - { return Map::BLOCKTYPE_NONE; } + virtual BlockType getBlockType() const + { return BLOCKTYPE_NONE; } /** Delay until move to next tile in miliseconds. */ unsigned short mMoveTime; diff --git a/src/game-server/character.h b/src/game-server/character.h index dfbf14e4..5a826908 100644 --- a/src/game-server/character.h +++ b/src/game-server/character.h @@ -372,8 +372,8 @@ class Character : public Being /** * Gets the way the actor blocks pathfinding for other objects */ - virtual Map::BlockType getBlockType() const - { return Map::BLOCKTYPE_CHARACTER; } + virtual BlockType getBlockType() const + { return BLOCKTYPE_CHARACTER; } private: double getAttrBase(AttributeMap::const_iterator it) const diff --git a/src/game-server/map.cpp b/src/game-server/map.cpp index 702bc3b4..d48546a2 100644 --- a/src/game-server/map.cpp +++ b/src/game-server/map.cpp @@ -1,6 +1,6 @@ /* * The Mana Server - * Copyright (C) 2004-2010 The Mana World Development Team + * Copyright (C) 2004-2011 The Mana World Development Team * * This file is part of The Mana Server. * @@ -28,55 +28,89 @@ #include "defines.h" -MetaTile::MetaTile(): - whichList(0), - blockmask(0) -{ } +/** + * Stores information used during path finding for each tile of a map. + */ +class PathInfo +{ + public: + PathInfo() + : whichList(0) + {} + + int Fcost; /**< Estimation of total path cost */ + int Gcost; /**< Cost from start to this location */ + int Hcost; /**< Estimated cost to goal */ + unsigned whichList; /**< No list, open list or closed list */ + int parentX; /**< X coordinate of parent tile */ + int parentY; /**< Y coordinate of parent tile */ +}; + +/** + * A helper class for finding a path on a map, functor style. + */ +class FindPath +{ + public: + FindPath() : + mWidth(0), + mOnClosedList(1), + mOnOpenList(2) + {} -Location::Location(int x, int y, MetaTile *tile): - x(x), y(y), tile(tile) -{ } + Path operator() (int startX, int startY, + int destX, int destY, + unsigned char walkmask, int maxCost, + const Map *map); -bool Location::operator< (const Location &loc) const -{ - return tile->Fcost > loc.tile->Fcost; -} + private: + PathInfo *getInfo(int x, int y) + { return &mPathInfos.at(x + y * mWidth); } -Map::Map(int width, int height, int twidth, int theight): - mWidth(width), mHeight(height), - mTileWidth(twidth), mTileHeight(theight), - mOnClosedList(1), mOnOpenList(2) + void prepare(const Map *map); + + int mWidth; + std::vector<PathInfo> mPathInfos; + unsigned mOnClosedList, mOnOpenList; +}; + +static FindPath findPath; + + +/** + * A location on a tile map. Used for pathfinding, open list. + */ +class Location { - mMetaTiles = new MetaTile[mWidth * mHeight]; - for (int i = 0; i < NB_BLOCKTYPES; i++) - { - mOccupation[i] = new unsigned[mWidth * mHeight]; - memset(mOccupation[i], 0, mWidth * mHeight * sizeof(unsigned)); - } -} + public: + Location(int x, int y, PathInfo *info): + x(x), y(y), info(info) + {} + + /** + * Comparison operator. + */ + bool operator< (const Location &loc) const + { return info->Fcost > loc.info->Fcost; } + + int x, y; + PathInfo *info; +}; + -Map::~Map() +Map::Map(int width, int height, int tileWidth, int tileHeight): + mWidth(width), mHeight(height), + mTileWidth(tileWidth), mTileHeight(tileHeight), + mMetaTiles(width * height) { - delete[] mMetaTiles; - for (int i = 0; i < NB_BLOCKTYPES; i++) - { - delete[] mOccupation[i]; - } } void Map::setSize(int width, int height) { - this->mWidth = width; - this->mHeight = height; + mWidth = width; + mHeight = height; - delete[] mMetaTiles; - mMetaTiles = new MetaTile[mWidth * mHeight]; - - for (int i = 0; i < NB_BLOCKTYPES; i++) - { - delete[] mOccupation[i]; - mOccupation[i] = new unsigned[mWidth * mHeight]; - } + mMetaTiles.resize(width * height); } const std::string &Map::getProperty(const std::string &key) const @@ -91,26 +125,24 @@ const std::string &Map::getProperty(const std::string &key) const void Map::blockTile(int x, int y, BlockType type) { - if (type == BLOCKTYPE_NONE || x < 0 || y < 0 || x >= mWidth || y >= mHeight) - { + if (type == BLOCKTYPE_NONE || !contains(x, y)) return; - } - int tileNum = x + y * mWidth; + MetaTile &metaTile = mMetaTiles[x + y * mWidth]; - if (mOccupation[type][tileNum] < UINT_MAX && - (++mOccupation[type][tileNum]) > 0) + if (metaTile.occupation[type] < UINT_MAX && + (++metaTile.occupation[type]) > 0) { switch (type) { case BLOCKTYPE_WALL: - mMetaTiles[tileNum].blockmask |= BLOCKMASK_WALL; + metaTile.blockmask |= BLOCKMASK_WALL; break; case BLOCKTYPE_CHARACTER: - mMetaTiles[tileNum].blockmask |= BLOCKMASK_CHARACTER; + metaTile.blockmask |= BLOCKMASK_CHARACTER; break; case BLOCKTYPE_MONSTER: - mMetaTiles[tileNum].blockmask |= BLOCKMASK_MONSTER; + metaTile.blockmask |= BLOCKMASK_MONSTER; break; default: // Nothing to do. @@ -121,26 +153,23 @@ void Map::blockTile(int x, int y, BlockType type) void Map::freeTile(int x, int y, BlockType type) { - if (type == BLOCKTYPE_NONE || x < 0 || y < 0 || x >= mWidth || y >= mHeight) - { + if (type == BLOCKTYPE_NONE || !contains(x, y)) return; - } - int tileNum = x + y * mWidth; + MetaTile &metaTile = mMetaTiles[x + y * mWidth]; - if (mOccupation[type][tileNum] > 0 && - !(--mOccupation[type][tileNum])) + if (metaTile.occupation[type] > 0 && !(--metaTile.occupation[type])) { switch (type) { case BLOCKTYPE_WALL: - mMetaTiles[tileNum].blockmask &= (BLOCKMASK_WALL xor 0xff); + metaTile.blockmask &= (BLOCKMASK_WALL xor 0xff); break; case BLOCKTYPE_CHARACTER: - mMetaTiles[tileNum].blockmask &= (BLOCKMASK_CHARACTER xor 0xff); + metaTile.blockmask &= (BLOCKMASK_CHARACTER xor 0xff); break; case BLOCKTYPE_MONSTER: - mMetaTiles[tileNum].blockmask &= (BLOCKMASK_MONSTER xor 0xff); + metaTile.blockmask &= (BLOCKMASK_MONSTER xor 0xff); break; default: // nothing @@ -153,27 +182,26 @@ bool Map::getWalk(int x, int y, char walkmask) const { // You can't walk outside of the map if (!contains(x, y)) - { return false; - } // Check if the tile is walkable return !(mMetaTiles[x + y * mWidth].blockmask & walkmask); } -MetaTile *Map::getMetaTile(int x, int y) -{ - return &mMetaTiles[x + y * mWidth]; -} - -bool Map::contains(int x, int y) const +Path Map::findPath(int startX, int startY, + int destX, int destY, + unsigned char walkmask, int maxCost) const { - return x >= 0 && y >= 0 && x < mWidth && y < mHeight; + return ::findPath(startX, startY, + destX, destY, + walkmask, maxCost, + this); } -Path Map::findPath(int startX, int startY, - int destX, int destY, - unsigned char walkmask, int maxCost) +Path FindPath::operator() (int startX, int startY, + int destX, int destY, + unsigned char walkmask, int maxCost, + const Map *map) { // Basic cost for moving from one tile to another. static int const basicCost = 100; @@ -181,14 +209,17 @@ Path Map::findPath(int startX, int startY, // Path to be built up (empty by default) Path path; + // Return when destination not walkable + if (!map->getWalk(destX, destY, walkmask)) + return path; + + prepare(map); + // 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, walkmask)) return path; - // Reset starting tile's G cost to 0 - MetaTile *startTile = getMetaTile(startX, startY); + PathInfo *startTile = getInfo(startX, startY); startTile->Gcost = 0; // Add the start point to the open list @@ -206,11 +237,11 @@ Path Map::findPath(int startX, int startY, // 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 == mOnClosedList) + if (curr.info->whichList == mOnClosedList) continue; // Put the current tile on the closed list - curr.tile->whichList = mOnClosedList; + curr.info->whichList = mOnClosedList; // Check the adjacent tiles for (int dy = -1; dy <= 1; dy++) @@ -223,29 +254,27 @@ Path Map::findPath(int startX, int startY, // 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) || !contains(x, y)) + if ((dx == 0 && dy == 0) || !map->contains(x, y)) continue; - MetaTile *newTile = getMetaTile(x, y); + PathInfo *newTile = getInfo(x, y); // Skip if the tile is on the closed list or is not walkable - if (newTile->whichList == mOnClosedList || newTile->blockmask - & walkmask) + if (newTile->whichList == mOnClosedList + || !map->getWalk(x, y, walkmask)) continue; // When taking a diagonal step, verify that we can skip the // corner. if (dx != 0 && dy != 0) { - MetaTile *t1 = getMetaTile(curr.x, curr.y + dy); - MetaTile *t2 = getMetaTile(curr.x + dx, curr.y); - - if ((t1->blockmask | t2->blockmask) & walkmask) + if (!map->getWalk(curr.x, curr.y + dy, walkmask) + || !map->getWalk(curr.x + dx, curr.y, walkmask)) continue; } // Calculate G cost for this route, ~sqrt(2) for moving diagonal - int Gcost = curr.tile->Gcost + + int Gcost = curr.info->Gcost + (dx == 0 || dy == 0 ? basicCost : basicCost * 362 / 256); /* Demote an arbitrary direction to speed pathfinding by @@ -318,25 +347,6 @@ Path Map::findPath(int startX, int startY, } } - // Two new values to indicate whether a tile is on the open or closed list, - // this way we don't have to clear all the values between each pathfinding. - if (mOnOpenList > UINT_MAX - 2) - { - // We reset the list memebers value. - mOnClosedList = 1; - mOnOpenList = 2; - - // Clean up the metaTiles - const int size = mWidth * mHeight; - for (int i = 0; i < size; ++i) - mMetaTiles[i].whichList = 0; - } - else - { - mOnClosedList += 2; - mOnOpenList += 2; - } - // If a path has been found, iterate backwards using the parent locations // to extract it. if (foundPath) @@ -350,7 +360,7 @@ Path Map::findPath(int startX, int startY, path.push_front(Point(pathX, pathY)); // Find out the next parent - MetaTile *tile = getMetaTile(pathX, pathY); + PathInfo *tile = getInfo(pathX, pathY); pathX = tile->parentX; pathY = tile->parentY; } @@ -358,3 +368,29 @@ Path Map::findPath(int startX, int startY, return path; } + +void FindPath::prepare(const Map *map) +{ + // Two new values to indicate whether a tile is on the open or closed list, + // this way we don't have to clear all the values between each pathfinding. + if (mOnOpenList < UINT_MAX - 2) + { + mOnClosedList += 2; + mOnOpenList += 2; + } + else + { + // Reset closed and open list IDs and clear the whichList values + mOnClosedList = 1; + mOnOpenList = 2; + for (unsigned i = 0, end = mPathInfos.size(); i < end; ++i) + mPathInfos[i].whichList = 0; + } + + // Make sure we have enough room to cover this map with path information + const unsigned size = map->getWidth() * map->getHeight(); + if (mPathInfos.size() < size) + mPathInfos.resize(size); + + mWidth = map->getWidth(); +} diff --git a/src/game-server/map.h b/src/game-server/map.h index 28004870..7c58d005 100644 --- a/src/game-server/map.h +++ b/src/game-server/map.h @@ -1,6 +1,6 @@ /* * The Mana Server - * Copyright (C) 2004-2010 The Mana World Development Team + * Copyright (C) 2004-2011 The Mana World Development Team * * This file is part of The Mana Server. * @@ -24,12 +24,22 @@ #include <list> #include <map> #include <string> +#include <vector> #include "utils/point.h" typedef std::list<Point> Path; typedef Path::iterator PathIterator; +enum BlockType +{ + BLOCKTYPE_NONE = -1, + BLOCKTYPE_WALL, + BLOCKTYPE_CHARACTER, + BLOCKTYPE_MONSTER, + NB_BLOCKTYPES +}; + /** * A meta tile stores additional information about a location on a tile map. * This is information that doesn't need to be repeated for each tile in each @@ -38,39 +48,15 @@ typedef Path::iterator PathIterator; class MetaTile { public: - /** - * Constructor. - */ - MetaTile(); - - // Pathfinding members - int Fcost; /**< Estimation of total path cost */ - int Gcost; /**< Cost from start to this location */ - int Hcost; /**< Estimated cost to goal */ - unsigned whichList; /**< No list, open list or closed list */ - int parentX; /**< X coordinate of parent tile */ - int parentY; /**< Y coordinate of parent tile */ - char blockmask; /**< walkability bitfield */ -}; - -/** - * A location on a tile map. Used for pathfinding, open list. - */ -class Location -{ - public: - /** - * Constructor. - */ - Location(int x, int y, MetaTile *tile); - - /** - * Comparison operator. - */ - bool operator< (const Location &loc) const; + MetaTile() + : blockmask(0) + { + for (unsigned i = 0; i < NB_BLOCKTYPES; ++i) + occupation[i] = 0; + } - int x, y; - MetaTile *tile; + unsigned occupation[NB_BLOCKTYPES]; + char blockmask; /**< walkability bitfield */ }; /** @@ -79,35 +65,16 @@ class Location class Map { public: - enum BlockType - { - BLOCKTYPE_NONE = -1, - BLOCKTYPE_WALL, - BLOCKTYPE_CHARACTER, - BLOCKTYPE_MONSTER, - NB_BLOCKTYPES - }; - /** * Constructor that takes initial map size as parameters. */ Map(int width, int height, - int twidth, int theight); - - /** - * Destructor. - */ - ~Map(); + int tileWidth, int tileHeight); /** * Sets the size of the map. This will destroy any existing map data. */ - void setSize(int mWidth, int height); - - /** - * Get tile reference. - */ - MetaTile *getMetaTile(int x, int y); + void setSize(int width, int height); /** * Marks a tile as occupied @@ -127,7 +94,8 @@ class Map /** * Tells if a tile location is within the map range. */ - bool contains(int x, int y) const; + bool contains(int x, int y) const + { return x >= 0 && y >= 0 && x < mWidth && y < mHeight; } /** * Returns the width of this map. @@ -168,9 +136,9 @@ class Map * Find a path from one location to the next. */ Path findPath(int startX, int startY, - int destX, int destY, - unsigned char walkmask, - int maxCost = 20); + int destX, int destY, + unsigned char walkmask, + int maxCost = 20) const; private: /** @@ -179,16 +147,13 @@ class Map static const unsigned char BLOCKMASK_WALL = 0x80; // = bin 1000 0000 static const unsigned char BLOCKMASK_CHARACTER = 0x01;// = bin 0000 0001 static const unsigned char BLOCKMASK_MONSTER = 0x02; // = bin 0000 0010 - unsigned *mOccupation[NB_BLOCKTYPES]; // map properties int mWidth, mHeight; int mTileWidth, mTileHeight; std::map<std::string, std::string> mProperties; - // Pathfinding members - MetaTile *mMetaTiles; - unsigned mOnClosedList, mOnOpenList; + std::vector<MetaTile> mMetaTiles; }; #endif diff --git a/src/game-server/mapreader.cpp b/src/game-server/mapreader.cpp index f96de174..eefca086 100644 --- a/src/game-server/mapreader.cpp +++ b/src/game-server/mapreader.cpp @@ -589,5 +589,5 @@ void MapReader::setTileWithGid(Map *map, int x, int y, int gid) } if (gid != set) - map->blockTile(x, y, Map::BLOCKTYPE_WALL); + map->blockTile(x, y, BLOCKTYPE_WALL); } diff --git a/src/game-server/monster.h b/src/game-server/monster.h index 2d826e48..14ebad35 100644 --- a/src/game-server/monster.h +++ b/src/game-server/monster.h @@ -308,8 +308,8 @@ class Monster : public Being /** * Returns the way the actor blocks pathfinding for other objects. */ - virtual Map::BlockType getBlockType() const - { return Map::BLOCKTYPE_MONSTER; } + virtual BlockType getBlockType() const + { return BLOCKTYPE_MONSTER; } private: static const int DECAY_TIME = 50; diff --git a/src/game-server/npc.h b/src/game-server/npc.h index 02b26a72..566b481c 100644 --- a/src/game-server/npc.h +++ b/src/game-server/npc.h @@ -74,12 +74,11 @@ class NPC : public Being { return 0x83; } // blocked like a monster by walls, monsters and characters ( bin 1000 0011) protected: - /** * Gets the way a monster blocks pathfinding for other objects */ - virtual Map::BlockType getBlockType() const - { return Map::BLOCKTYPE_CHARACTER; } //blocks like a player character + virtual BlockType getBlockType() const + { return BLOCKTYPE_CHARACTER; } // blocks like a player character private: Script *mScript; /**< Script describing NPC behavior. */ |