diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/saveload.cpp | 2 | ||||
| -rw-r--r-- | src/waypoint.cpp | 69 | ||||
| -rw-r--r-- | src/waypoint.h | 2 |
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 |