79 * Set the default name for a waypoint |
75 * Set the default name for a waypoint |
80 * @param wp Waypoint to work on |
76 * @param wp Waypoint to work on |
81 */ |
77 */ |
82 static void MakeDefaultWaypointName(Waypoint* wp) |
78 static void MakeDefaultWaypointName(Waypoint* wp) |
83 { |
79 { |
84 Waypoint *local_wp; |
80 uint32 used = 0; // bitmap of used waypoint numbers, sliding window with 'next' as base |
85 bool used_waypoint[MAX_WAYPOINTS_PER_TOWN]; |
81 uint32 next = 0; // first waypoint number in the bitmap |
86 int i; |
82 WaypointID idx = 0; // index where we will stop |
87 |
83 |
88 wp->town_index = ClosestTownFromTile(wp->xy, (uint)-1)->index; |
84 wp->town_index = ClosestTownFromTile(wp->xy, (uint)-1)->index; |
89 |
85 |
90 memset(used_waypoint, 0, sizeof(used_waypoint)); |
86 /* Find first unused waypoint number belonging to this town. This can never fail, |
91 |
87 * as long as there can be at most 65535 waypoints in total. |
92 /* Find an unused waypoint number belonging to this town */ |
88 * |
93 FOR_ALL_WAYPOINTS(local_wp) { |
89 * This does 'n * m' search, but with 32bit 'used' bitmap, it needs at most 'n * (1 + ceil(m / 32))' |
94 if (wp == local_wp) continue; |
90 * steps (n - number of waypoints in pool, m - number of waypoints near this town). |
95 |
91 * Usually, it needs only 'n' steps. |
96 if (local_wp->xy && local_wp->name == NULL && local_wp->town_index == wp->town_index) |
92 * |
97 used_waypoint[local_wp->town_cn] = true; |
93 * If it wasn't using 'used' and 'idx', it would just search for increasing 'next', |
98 } |
94 * but this way it is faster */ |
99 |
95 |
100 /* Find an empty spot */ |
96 WaypointID cid = 0; // current index, goes to GetWaypointPoolSize()-1, then wraps to 0 |
101 for (i = 0; used_waypoint[i] && i < MAX_WAYPOINTS_PER_TOWN; i++) {} |
97 do { |
102 |
98 Waypoint *lwp = GetWaypoint(cid); |
103 wp->name = NULL; |
99 |
104 wp->town_cn = i; |
100 /* check only valid waypoints... */ |
|
101 if (lwp->IsValid() && wp != lwp) { |
|
102 /* only waypoints with 'generic' name within the same city */ |
|
103 if (lwp->name == NULL && lwp->town_index == wp->town_index) { |
|
104 /* if lwp->town_cn < next, uint will overflow to '+inf' */ |
|
105 uint i = (uint)lwp->town_cn - next; |
|
106 |
|
107 if (i < 32) { |
|
108 SetBit(used, i); // update bitmap |
|
109 if (i == 0) { |
|
110 /* shift bitmap while the lowest bit is '1'; |
|
111 * increase the base of the bitmap too */ |
|
112 do { |
|
113 used >>= 1; |
|
114 next++; |
|
115 } while (HasBit(used, 0)); |
|
116 /* when we are at 'idx' again at end of the loop and |
|
117 * 'next' hasn't changed, then no waypoint had town_cn == next, |
|
118 * so we can safely use it */ |
|
119 idx = cid; |
|
120 } |
|
121 } |
|
122 } |
|
123 } |
|
124 |
|
125 cid++; |
|
126 if (cid == GetWaypointPoolSize()) cid = 0; // wrap to zero... |
|
127 } while (cid != idx); |
|
128 |
|
129 wp->town_cn = (uint16)next; // set index... |
|
130 wp->name = NULL; // ... and use generic name |
105 } |
131 } |
106 |
132 |
107 /** |
133 /** |
108 * Find a deleted waypoint close to a tile. |
134 * Find a deleted waypoint close to a tile. |
109 * @param tile to search from |
135 * @param tile to search from |
239 } |
265 } |
240 |
266 |
241 wp->deleted = 0; |
267 wp->deleted = 0; |
242 wp->build_date = _date; |
268 wp->build_date = _date; |
243 |
269 |
244 if (wp->town_index == 0) MakeDefaultWaypointName(wp); |
270 if (wp->town_index == INVALID_TOWN) MakeDefaultWaypointName(wp); |
245 |
271 |
246 UpdateWaypointSign(wp); |
272 UpdateWaypointSign(wp); |
247 RedrawWaypointSign(wp); |
273 RedrawWaypointSign(wp); |
248 YapfNotifyTrackLayoutChange(tile, AxisToTrack(axis)); |
274 YapfNotifyTrackLayoutChange(tile, AxisToTrack(axis)); |
249 wp_auto_delete.Detach(); |
275 wp_auto_delete.Detach(); |
453 |
479 |
454 static const SaveLoad _waypoint_desc[] = { |
480 static const SaveLoad _waypoint_desc[] = { |
455 SLE_CONDVAR(Waypoint, xy, SLE_FILE_U16 | SLE_VAR_U32, 0, 5), |
481 SLE_CONDVAR(Waypoint, xy, SLE_FILE_U16 | SLE_VAR_U32, 0, 5), |
456 SLE_CONDVAR(Waypoint, xy, SLE_UINT32, 6, SL_MAX_VERSION), |
482 SLE_CONDVAR(Waypoint, xy, SLE_UINT32, 6, SL_MAX_VERSION), |
457 SLE_CONDVAR(Waypoint, town_index, SLE_UINT16, 12, SL_MAX_VERSION), |
483 SLE_CONDVAR(Waypoint, town_index, SLE_UINT16, 12, SL_MAX_VERSION), |
458 SLE_CONDVAR(Waypoint, town_cn, SLE_UINT8, 12, SL_MAX_VERSION), |
484 SLE_CONDVAR(Waypoint, town_cn, SLE_FILE_U8 | SLE_VAR_U16, 12, 88), |
|
485 SLE_CONDVAR(Waypoint, town_cn, SLE_UINT16, 89, SL_MAX_VERSION), |
459 SLE_CONDVAR(Waypoint, string, SLE_STRINGID, 0, 83), |
486 SLE_CONDVAR(Waypoint, string, SLE_STRINGID, 0, 83), |
460 SLE_CONDSTR(Waypoint, name, SLE_STR, 0, 84, SL_MAX_VERSION), |
487 SLE_CONDSTR(Waypoint, name, SLE_STR, 0, 84, SL_MAX_VERSION), |
461 SLE_VAR(Waypoint, deleted, SLE_UINT8), |
488 SLE_VAR(Waypoint, deleted, SLE_UINT8), |
462 |
489 |
463 SLE_CONDVAR(Waypoint, build_date, SLE_FILE_U16 | SLE_VAR_I32, 3, 30), |
490 SLE_CONDVAR(Waypoint, build_date, SLE_FILE_U16 | SLE_VAR_I32, 3, 30), |