diff options
| -rw-r--r-- | ChangeLog | 7 | ||||
| -rw-r--r-- | src/map.cpp | 53 | ||||
| -rw-r--r-- | src/map.h | 12 |
3 files changed, 49 insertions, 23 deletions
@@ -1,3 +1,10 @@ +2006-11-12 Bjørn Lindeijer <bjorn@lindeijer.nl> + + * src/map.cpp, src/map.h: Made pathfinding algorithm cope better with + beings blocking the road. This is done by allowing walking over other + beings, but at an additional cost so that it is preferable to walk + around them. + 2006-11-09 Eugenio Favalli <elvenprogrammer@gmail.com> * src/main.cpp, src/net/network.cpp, src/net/network.h, diff --git a/src/map.cpp b/src/map.cpp index 05dea951..897fbe22 100644 --- a/src/map.cpp +++ b/src/map.cpp @@ -282,33 +282,35 @@ Map::setWalk(int x, int y, bool walkable) bool Map::getWalk(int x, int y) { - // Check for being walkable - if (tileCollides(x, y)) { - return false; - } + return !tileCollides(x, y) && !occupied(x, y); +} - // Check for collision with a being +bool +Map::occupied(int x, int y) +{ Beings &beings = beingManager->getAll(); - for (BeingIterator i = beings.begin(); i != beings.end(); i++) { + for (BeingIterator i = beings.begin(); i != beings.end(); i++) + { // job 45 is a portal, they don't collide - if ((*i)->mX == x && (*i)->mY == y && (*i)->mJob != 45) { - return false; + if ((*i)->mX == x && (*i)->mY == y && (*i)->mJob != 45) + { + return true; } } - return true; + return false; } bool Map::tileCollides(int x, int y) { - // You can't walk outside of the map - if (x < 0 || y < 0 || x >= mWidth || y >= mHeight) { - return true; - } + return !(contains(x, y) && mMetaTiles[x + y * mWidth].walkable); +} - // Check if the tile is walkable - return !mMetaTiles[x + y * mWidth].walkable; +bool +Map::contains(int x, int y) +{ + return x >= 0 && y >= 0 && x < mWidth && y < mHeight; } void @@ -351,8 +353,9 @@ 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 empty path when destination not walkable - if (!getWalk(destX, destY)) return path; + // Return empty path when destination collides + if (tileCollides(destX, destY)) + return path; // Reset starting tile's G cost to 0 MetaTile *startTile = getMetaTile(startX, startY); @@ -391,16 +394,15 @@ Map::findPath(int startX, int startY, int destX, int destY) // 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 >= mWidth || y >= mHeight)) + if ((dx == 0 && dy == 0) || !contains(x, y)) { continue; } MetaTile *newTile = getMetaTile(x, y); - // Skip if the tile is on the closed list or is not walkable - if (newTile->whichList == mOnClosedList || !getWalk(x, y)) + // Skip if the tile is on the closed list or collides + if (newTile->whichList == mOnClosedList || tileCollides(x, y)) { continue; } @@ -420,9 +422,16 @@ Map::findPath(int startX, int startY, int destX, int destY) } // Calculate G cost for this route, 10 for moving straight and - // 14 for moving diagonal + // 14 for moving diagonal (sqrt(200) = 14.1421...) int Gcost = curr.tile->Gcost + ((dx == 0 || dy == 0) ? 10 : 14); + // It costs extra to walk through a being (needs to be enough + // to make it more attractive to walk around). + if (occupied(x, y)) + { + Gcost += 30; + } + // Skip if Gcost becomes too much // Warning: probably not entirely accurate if (Gcost > 200) @@ -129,7 +129,7 @@ class Map : public Properties MetaTile *getMetaTile(int x, int y); /** - * Set walkability flag for a tile + * Set walkability flag for a tile. */ void setWalk(int x, int y, bool walkable); @@ -199,6 +199,16 @@ class Map : public Properties Tileset* getTilesetWithGid(int gid); + /** + * Tells whether a tile is occupied by a being. + */ + bool occupied(int x, int y); + + /** + * Tells whether the given coordinates fall within the map boundaries. + */ + bool contains(int x, int y); + int mWidth, mHeight; int mTileWidth, mTileHeight; MetaTile *mMetaTiles; |