From 0c6bf93ee13f0b3344079ebf4e60c5ec8323f0bd Mon Sep 17 00:00:00 2001
From: Yohann Ferreira <yohann_dot_ferreira_at_orange_dot_efer>
Date: Thu, 10 Mar 2011 18:28:49 +0100
Subject: 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.
---
 src/map.cpp | 27 ++++++++++++++++++++++-----
 src/map.h   |  6 +++---
 2 files changed, 25 insertions(+), 8 deletions(-)

diff --git a/src/map.cpp b/src/map.cpp
index 467d12331..855570eb8 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -47,6 +47,7 @@
 #include "utils/stringutils.h"
 
 #include <queue>
+#include <limits.h>
 
 #include <sys/stat.h>
 
@@ -385,8 +386,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));
     }
     mSpecialLayer = new SpecialLayer(width, height);
     mTempLayer = new SpecialLayer(width, height, true);
@@ -770,7 +771,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)
         {
@@ -983,6 +985,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)
@@ -1142,8 +1145,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 79ab8e8fa..5cc25cf01 100644
--- a/src/map.h
+++ b/src/map.h
@@ -69,7 +69,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 */
@@ -463,7 +463,7 @@ class Map : public Properties, public ConfigListener
         /**
          * Blockmasks for different entities
          */
-        int *mOccupation[NB_BLOCKTYPES];
+        unsigned *mOccupation[NB_BLOCKTYPES];
 
         int mWidth, mHeight;
         int mTileWidth, mTileHeight;
@@ -478,7 +478,7 @@ class Map : public Properties, public ConfigListener
         int mDebugFlags;
 
         // Pathfinding members
-        int mOnClosedList, mOnOpenList;
+        unsigned mOnClosedList, mOnOpenList;
 
         // Overlay data
         std::list<AmbientLayer*> mBackgrounds;
-- 
cgit v1.2.3-60-g2f50