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.

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;