summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorYohann Ferreira <yohann_dot_ferreira_at_orange_dot_efer>2011-03-10 18:28:49 +0100
committerYohann Ferreira <yohann_dot_ferreira_at_orange_dot_efer>2011-03-10 18:28:49 +0100
commita7d52dd2d59049e9bf097694c8e708bc1ad6fec2 (patch)
tree899176e3be491d111cec198673a52134816f92b5
parent369c88d1b24e17afa4dee418e01eae187d3a4169 (diff)
downloadmana-client-a7d52dd2d59049e9bf097694c8e708bc1ad6fec2.tar.gz
mana-client-a7d52dd2d59049e9bf097694c8e708bc1ad6fec2.tar.bz2
mana-client-a7d52dd2d59049e9bf097694c8e708bc1ad6fec2.tar.xz
mana-client-a7d52dd2d59049e9bf097694c8e708bc1ad6fec2.zip
Wrap the open and closed list members in path finding.
This prevent some weird things happening in path finding when playing for a very long time. Reviewed-by: Thorbjorn.
-rw-r--r--src/map.cpp31
-rw-r--r--src/map.h6
2 files changed, 25 insertions, 12 deletions
diff --git a/src/map.cpp b/src/map.cpp
index 09782699..de6cf12a 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -39,6 +39,7 @@
#include "utils/stringutils.h"
#include <queue>
+#include <limits.h>
/**
* A location on a tile map. Used for pathfinding, open list.
@@ -228,8 +229,8 @@ Map::Map(int width, int height, int tileWidth, int tileHeight):
mMetaTiles = new MetaTile[size];
for (int i = 0; i < NB_BLOCKTYPES; i++)
{
- mOccupation[i] = new int[size];
- memset(mOccupation[i], 0, size * sizeof(int));
+ mOccupation[i] = new unsigned[size];
+ memset(mOccupation[i], 0, size * sizeof(unsigned));
}
}
@@ -559,7 +560,8 @@ void Map::blockTile(int x, int y, BlockType type)
const int tileNum = x + y * mWidth;
- if ((++mOccupation[type][tileNum]) > 0)
+ if (mOccupation[type][tileNum] < UINT_MAX &&
+ (++mOccupation[type][tileNum]) > 0)
{
switch (type)
{
@@ -760,6 +762,7 @@ Path Map::findPixelPath(int startPixelX, int startPixelY, int endPixelX,
Path Map::findPath(int startX, int startY, int destX, int destY,
unsigned char walkmask, int maxCost)
{
+ // The basic walking cost of a tile.
static int const basicCost = 100;
// Path to be built up (empty by default)
@@ -791,9 +794,7 @@ Path Map::findPath(int startX, int startY, int destX, int destY,
// 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)
- {
continue;
- }
// Put the current tile on the closed list
curr.tile->whichList = mOnClosedList;
@@ -810,9 +811,7 @@ Path 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) || !contains(x, y))
- {
continue;
- }
MetaTile *newTile = getMetaTile(x, y);
@@ -923,8 +922,22 @@ Path Map::findPath(int startX, int startY, int destX, int destY,
// 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.
- mOnClosedList += 2;
- mOnOpenList += 2;
+ 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.
diff --git a/src/map.h b/src/map.h
index 160cb7f7..22ca68c4 100644
--- a/src/map.h
+++ b/src/map.h
@@ -56,7 +56,7 @@ struct MetaTile
int Fcost; /**< Estimation of total path cost */
int Gcost; /**< Cost from start to this location */
int Hcost; /**< Estimated cost to goal */
- int whichList; /**< No list, open list or closed list */
+ unsigned whichList; /**< No list, open list or closed list */
int parentX; /**< X coordinate of parent tile */
int parentY; /**< Y coordinate of parent tile */
unsigned char blockmask; /**< Blocking properties of this tile */
@@ -363,7 +363,7 @@ class Map : public Properties
/**
* Blockmasks for different entities
*/
- int *mOccupation[NB_BLOCKTYPES];
+ unsigned *mOccupation[NB_BLOCKTYPES];
int mWidth, mHeight;
int mTileWidth, mTileHeight;
@@ -377,7 +377,7 @@ class Map : public Properties
int mDebugFlags;
// Pathfinding members
- int mOnClosedList, mOnOpenList;
+ unsigned mOnClosedList, mOnOpenList;
// Overlay data
std::list<AmbientLayer*> mBackgrounds;