(svn r12160) -Fix [FS#1744]: remove the arbitrary limit of 64 waypoints per town, so weird things won't happen anymore

3 files changed, 50 insertions, 23 deletions

diff --git a/src/saveload.cpp b/src/saveload.cpp
index 57e7c1a4b..2e8378c9c 100644
--- a/src/saveload.cpp
+++ b/src/saveload.cpp
@@ -34,7 +34,7 @@
 
 #include "table/strings.h"
 
-extern const uint16 SAVEGAME_VERSION = 88;
+extern const uint16 SAVEGAME_VERSION = 89;
 uint16 _sl_version;       ///< the major savegame version identifier
 byte   _sl_minor_version; ///< the minor savegame version, DO NOT USE!
 
diff --git a/src/waypoint.cpp b/src/waypoint.cpp
index 125a5202e..08af0f310 100644
--- a/src/waypoint.cpp
+++ b/src/waypoint.cpp
@@ -34,10 +34,6 @@
 
 #include "table/strings.h"
 
-enum {
-	MAX_WAYPOINTS_PER_TOWN = 64,
-};
-
 DEFINE_OLD_POOL_GENERIC(Waypoint, Waypoint)
 
 
@@ -81,27 +77,57 @@ void UpdateAllWaypointSigns()
  */
 static void MakeDefaultWaypointName(Waypoint* wp)
 {
-	Waypoint *local_wp;
-	bool used_waypoint[MAX_WAYPOINTS_PER_TOWN];
-	int i;
+	uint32 used = 0; // bitmap of used waypoint numbers, sliding window with 'next' as base
+	uint32 next = 0; // first waypoint number in the bitmap
+	WaypointID idx = 0; // index where we will stop
 
 	wp->town_index = ClosestTownFromTile(wp->xy, (uint)-1)->index;
 
-	memset(used_waypoint, 0, sizeof(used_waypoint));
-
-	/* Find an unused waypoint number belonging to this town */
-	FOR_ALL_WAYPOINTS(local_wp) {
-		if (wp == local_wp) continue;
-
-		if (local_wp->xy && local_wp->name == NULL && local_wp->town_index == wp->town_index)
-			used_waypoint[local_wp->town_cn] = true;
-	}
+	/* Find first unused waypoint number belonging to this town. This can never fail,
+	 * as long as there can be at most 65535 waypoints in total.
+	 *
+	 * This does 'n * m' search, but with 32bit 'used' bitmap, it needs at most 'n * (1 + ceil(m / 32))'
+	 * steps (n - number of waypoints in pool, m - number of waypoints near this town).
+	 * Usually, it needs only 'n' steps.
+	 *
+	 * If it wasn't using 'used' and 'idx', it would just search for increasing 'next',
+	 * but this way it is faster */
+
+	WaypointID cid = 0; // current index, goes to GetWaypointPoolSize()-1, then wraps to 0
+	do {
+		Waypoint *lwp = GetWaypoint(cid);
+
+		/* check only valid waypoints... */
+ 		if (lwp->IsValid() && wp != lwp) {
+			/* only waypoints with 'generic' name within the same city */
+			if (lwp->name == NULL && lwp->town_index == wp->town_index) {
+				/* if lwp->town_cn < next, uint will overflow to '+inf' */
+				uint i = (uint)lwp->town_cn - next;
+
+				if (i < 32) {
+					SetBit(used, i); // update bitmap
+					if (i == 0) {
+						/* shift bitmap while the lowest bit is '1';
+						 * increase the base of the bitmap too */
+						do {
+							used >>= 1;
+							next++;
+						} while (HasBit(used, 0));
+						/* when we are at 'idx' again at end of the loop and
+						 * 'next' hasn't changed, then no waypoint had town_cn == next,
+						 * so we can safely use it */
+						idx = cid;
+					}
+				}
+			}
+		}
 
-	/* Find an empty spot */
-	for (i = 0; used_waypoint[i] && i < MAX_WAYPOINTS_PER_TOWN; i++) {}
+		cid++;
+		if (cid == GetWaypointPoolSize()) cid = 0; // wrap to zero...
+	} while (cid != idx);
 
-	wp->name = NULL;
-	wp->town_cn = i;
+	wp->town_cn = (uint16)next; // set index...
+	wp->name = NULL; // ... and use generic name
 }
 
 /**
@@ -455,7 +481,8 @@ static const SaveLoad _waypoint_desc[] = {
 	SLE_CONDVAR(Waypoint, xy,         SLE_FILE_U16 | SLE_VAR_U32,  0, 5),
 	SLE_CONDVAR(Waypoint, xy,         SLE_UINT32,                  6, SL_MAX_VERSION),
 	SLE_CONDVAR(Waypoint, town_index, SLE_UINT16,                 12, SL_MAX_VERSION),
-	SLE_CONDVAR(Waypoint, town_cn,    SLE_UINT8,                  12, SL_MAX_VERSION),
+	SLE_CONDVAR(Waypoint, town_cn,    SLE_FILE_U8 | SLE_VAR_U16,  12, 88),
+	SLE_CONDVAR(Waypoint, town_cn,    SLE_UINT16,                 89, SL_MAX_VERSION),
 	SLE_CONDVAR(Waypoint, string,     SLE_STRINGID,                0, 83),
 	SLE_CONDSTR(Waypoint, name,       SLE_STR, 0,                 84, SL_MAX_VERSION),
 	    SLE_VAR(Waypoint, deleted,    SLE_UINT8),
diff --git a/src/waypoint.h b/src/waypoint.h
index 9737d5942..c995dca0d 100644
--- a/src/waypoint.h
+++ b/src/waypoint.h
@@ -16,7 +16,7 @@ struct Waypoint : PoolItem<Waypoint, WaypointID, &_Waypoint_pool> {
 	TileIndex xy;      ///< Tile of waypoint
 
 	TownID town_index; ///< Town associated with the waypoint
-	byte town_cn;      ///< The Nth waypoint for this town (consecutive number)
+	uint16 town_cn;    ///< The Nth waypoint for this town (consecutive number)
 	StringID string;   ///< C000-C03F have special meaning in old games
 	char *name;        ///< Custom name. If not set, town + town_cn is used for naming