summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorsmatz <smatz@openttd.org>2008-02-16 16:40:47 +0000
committersmatz <smatz@openttd.org>2008-02-16 16:40:47 +0000
commit058f39fe180bcbe829afa8f3ac377aeb877a41df (patch)
tree43a2c1e1a3b14b24617b84cdf4007ca172fec406 /src
parente7173d3ba456c3f3ec0cc69161396cd7410fe248 (diff)
downloadopenttd-058f39fe180bcbe829afa8f3ac377aeb877a41df.tar.xz
(svn r12160) -Fix [FS#1744]: remove the arbitrary limit of 64 waypoints per town, so weird things won't happen anymore
Diffstat (limited to 'src')
-rw-r--r--src/saveload.cpp2
-rw-r--r--src/waypoint.cpp69
-rw-r--r--src/waypoint.h2
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