1 /*
2 * This file is part of OpenTTD.
3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6 */
7
8 /** @file station_base.h Base classes/functions for stations. */
9
10 #ifndef STATION_BASE_H
11 #define STATION_BASE_H
12
13 #include "core/random_func.hpp"
14 #include "base_station_base.h"
15 #include "newgrf_airport.h"
16 #include "cargopacket.h"
17 #include "industry_type.h"
18 #include "linkgraph/linkgraph_type.h"
19 #include "newgrf_storage.h"
20 #include "bitmap_type.h"
21 #include <map>
22 #include <set>
23
24 static const byte INITIAL_STATION_RATING = 175;
25
26 /**
27 * Flow statistics telling how much flow should be sent along a link. This is
28 * done by creating "flow shares" and using std::map's upper_bound() method to
29 * look them up with a random number. A flow share is the difference between a
30 * key in a map and the previous key. So one key in the map doesn't actually
31 * mean anything by itself.
32 */
33 class FlowStat {
34 public:
35 typedef std::map<uint32, StationID> SharesMap;
36
37 static const SharesMap empty_sharesmap;
38
39 /**
40 * Invalid constructor. This can't be called as a FlowStat must not be
41 * empty. However, the constructor must be defined and reachable for
42 * FlowStat to be used in a std::map.
43 */
FlowStat()44 inline FlowStat() {NOT_REACHED();}
45
46 /**
47 * Create a FlowStat with an initial entry.
48 * @param st Station the initial entry refers to.
49 * @param flow Amount of flow for the initial entry.
50 * @param restricted If the flow to be added is restricted.
51 */
52 inline FlowStat(StationID st, uint flow, bool restricted = false)
53 {
54 assert(flow > 0);
55 this->shares[flow] = st;
56 this->unrestricted = restricted ? 0 : flow;
57 }
58
59 /**
60 * Add some flow to the end of the shares map. Only do that if you know
61 * that the station isn't in the map yet. Anything else may lead to
62 * inconsistencies.
63 * @param st Remote station.
64 * @param flow Amount of flow to be added.
65 * @param restricted If the flow to be added is restricted.
66 */
67 inline void AppendShare(StationID st, uint flow, bool restricted = false)
68 {
69 assert(flow > 0);
70 this->shares[(--this->shares.end())->first + flow] = st;
71 if (!restricted) this->unrestricted += flow;
72 }
73
74 uint GetShare(StationID st) const;
75
76 void ChangeShare(StationID st, int flow);
77
78 void RestrictShare(StationID st);
79
80 void ReleaseShare(StationID st);
81
82 void ScaleToMonthly(uint runtime);
83
84 /**
85 * Get the actual shares as a const pointer so that they can be iterated
86 * over.
87 * @return Actual shares.
88 */
GetShares()89 inline const SharesMap *GetShares() const { return &this->shares; }
90
91 /**
92 * Return total amount of unrestricted shares.
93 * @return Amount of unrestricted shares.
94 */
GetUnrestricted()95 inline uint GetUnrestricted() const { return this->unrestricted; }
96
97 /**
98 * Swap the shares maps, and thus the content of this FlowStat with the
99 * other one.
100 * @param other FlowStat to swap with.
101 */
SwapShares(FlowStat & other)102 inline void SwapShares(FlowStat &other)
103 {
104 this->shares.swap(other.shares);
105 Swap(this->unrestricted, other.unrestricted);
106 }
107
108 /**
109 * Get a station a package can be routed to. This done by drawing a
110 * random number between 0 and sum_shares and then looking that up in
111 * the map with lower_bound. So each share gets selected with a
112 * probability dependent on its flow. Do include restricted flows here.
113 * @param is_restricted Output if a restricted flow was chosen.
114 * @return A station ID from the shares map.
115 */
GetViaWithRestricted(bool & is_restricted)116 inline StationID GetViaWithRestricted(bool &is_restricted) const
117 {
118 assert(!this->shares.empty());
119 uint rand = RandomRange((--this->shares.end())->first);
120 is_restricted = rand >= this->unrestricted;
121 return this->shares.upper_bound(rand)->second;
122 }
123
124 /**
125 * Get a station a package can be routed to. This done by drawing a
126 * random number between 0 and sum_shares and then looking that up in
127 * the map with lower_bound. So each share gets selected with a
128 * probability dependent on its flow. Don't include restricted flows.
129 * @return A station ID from the shares map.
130 */
GetVia()131 inline StationID GetVia() const
132 {
133 assert(!this->shares.empty());
134 return this->unrestricted > 0 ?
135 this->shares.upper_bound(RandomRange(this->unrestricted))->second :
136 INVALID_STATION;
137 }
138
139 StationID GetVia(StationID excluded, StationID excluded2 = INVALID_STATION) const;
140
141 void Invalidate();
142
143 private:
144 SharesMap shares; ///< Shares of flow to be sent via specified station (or consumed locally).
145 uint unrestricted; ///< Limit for unrestricted shares.
146 };
147
148 /** Flow descriptions by origin stations. */
149 class FlowStatMap : public std::map<StationID, FlowStat> {
150 public:
151 uint GetFlow() const;
152 uint GetFlowVia(StationID via) const;
153 uint GetFlowFrom(StationID from) const;
154 uint GetFlowFromVia(StationID from, StationID via) const;
155
156 void AddFlow(StationID origin, StationID via, uint amount);
157 void PassOnFlow(StationID origin, StationID via, uint amount);
158 StationIDStack DeleteFlows(StationID via);
159 void RestrictFlows(StationID via);
160 void ReleaseFlows(StationID via);
161 void FinalizeLocalConsumption(StationID self);
162 };
163
164 /**
165 * Stores station stats for a single cargo.
166 */
167 struct GoodsEntry {
168 /** Status of this cargo for the station. */
169 enum GoodsEntryStatus {
170 /**
171 * Set when the station accepts the cargo currently for final deliveries.
172 * It is updated every STATION_ACCEPTANCE_TICKS ticks by checking surrounding tiles for acceptance >= 8/8.
173 */
174 GES_ACCEPTANCE,
175
176 /**
177 * This indicates whether a cargo has a rating at the station.
178 * Set when cargo was ever waiting at the station.
179 * It is set when cargo supplied by surrounding tiles is moved to the station, or when
180 * arriving vehicles unload/transfer cargo without it being a final delivery.
181 *
182 * This flag is cleared after 255 * STATION_RATING_TICKS of not having seen a pickup.
183 */
184 GES_RATING,
185
186 /**
187 * Set when a vehicle ever delivered cargo to the station for final delivery.
188 * This flag is never cleared.
189 */
190 GES_EVER_ACCEPTED,
191
192 /**
193 * Set when cargo was delivered for final delivery last month.
194 * This flag is set to the value of GES_CURRENT_MONTH at the start of each month.
195 */
196 GES_LAST_MONTH,
197
198 /**
199 * Set when cargo was delivered for final delivery this month.
200 * This flag is reset on the beginning of every month.
201 */
202 GES_CURRENT_MONTH,
203
204 /**
205 * Set when cargo was delivered for final delivery during the current STATION_ACCEPTANCE_TICKS interval.
206 * This flag is reset every STATION_ACCEPTANCE_TICKS ticks.
207 */
208 GES_ACCEPTED_BIGTICK,
209 };
210
GoodsEntryGoodsEntry211 GoodsEntry() :
212 status(0),
213 time_since_pickup(255),
214 rating(INITIAL_STATION_RATING),
215 last_speed(0),
216 last_age(255),
217 amount_fract(0),
218 link_graph(INVALID_LINK_GRAPH),
219 node(INVALID_NODE),
220 max_waiting_cargo(0)
221 {}
222
223 byte status; ///< Status of this cargo, see #GoodsEntryStatus.
224
225 /**
226 * Number of rating-intervals (up to 255) since the last vehicle tried to load this cargo.
227 * The unit used is STATION_RATING_TICKS.
228 * This does not imply there was any cargo to load.
229 */
230 byte time_since_pickup;
231
232 byte rating; ///< %Station rating for this cargo.
233
234 /**
235 * Maximum speed (up to 255) of the last vehicle that tried to load this cargo.
236 * This does not imply there was any cargo to load.
237 * The unit used is a special vehicle-specific speed unit for station ratings.
238 * - Trains: km-ish/h
239 * - RV: km-ish/h
240 * - Ships: 0.5 * km-ish/h
241 * - Aircraft: 8 * mph
242 */
243 byte last_speed;
244
245 /**
246 * Age in years (up to 255) of the last vehicle that tried to load this cargo.
247 * This does not imply there was any cargo to load.
248 */
249 byte last_age;
250
251 byte amount_fract; ///< Fractional part of the amount in the cargo list
252 StationCargoList cargo; ///< The cargo packets of cargo waiting in this station
253
254 LinkGraphID link_graph; ///< Link graph this station belongs to.
255 NodeID node; ///< ID of node in link graph referring to this goods entry.
256 FlowStatMap flows; ///< Planned flows through this station.
257 uint max_waiting_cargo; ///< Max cargo from this station waiting at any station.
258
259 /**
260 * Reports whether a vehicle has ever tried to load the cargo at this station.
261 * This does not imply that there was cargo available for loading. Refer to GES_RATING for that.
262 * @return true if vehicle tried to load.
263 */
HasVehicleEverTriedLoadingGoodsEntry264 bool HasVehicleEverTriedLoading() const { return this->last_speed != 0; }
265
266 /**
267 * Does this cargo have a rating at this station?
268 * @return true if the cargo has a rating, i.e. cargo has been moved to the station.
269 */
HasRatingGoodsEntry270 inline bool HasRating() const
271 {
272 return HasBit(this->status, GES_RATING);
273 }
274
275 /**
276 * Get the best next hop for a cargo packet from station source.
277 * @param source Source of the packet.
278 * @return The chosen next hop or INVALID_STATION if none was found.
279 */
GetViaGoodsEntry280 inline StationID GetVia(StationID source) const
281 {
282 FlowStatMap::const_iterator flow_it(this->flows.find(source));
283 return flow_it != this->flows.end() ? flow_it->second.GetVia() : INVALID_STATION;
284 }
285
286 /**
287 * Get the best next hop for a cargo packet from station source, optionally
288 * excluding one or two stations.
289 * @param source Source of the packet.
290 * @param excluded If this station would be chosen choose the second best one instead.
291 * @param excluded2 Second station to be excluded, if != INVALID_STATION.
292 * @return The chosen next hop or INVALID_STATION if none was found.
293 */
294 inline StationID GetVia(StationID source, StationID excluded, StationID excluded2 = INVALID_STATION) const
295 {
296 FlowStatMap::const_iterator flow_it(this->flows.find(source));
297 return flow_it != this->flows.end() ? flow_it->second.GetVia(excluded, excluded2) : INVALID_STATION;
298 }
299 };
300
301 /** All airport-related information. Only valid if tile != INVALID_TILE. */
302 struct Airport : public TileArea {
AirportAirport303 Airport() : TileArea(INVALID_TILE, 0, 0) {}
304
305 uint64 flags; ///< stores which blocks on the airport are taken. was 16 bit earlier on, then 32
306 byte type; ///< Type of this airport, @see AirportTypes
307 byte layout; ///< Airport layout number.
308 Direction rotation; ///< How this airport is rotated.
309
310 PersistentStorage *psa; ///< Persistent storage for NewGRF airports.
311
312 /**
313 * Get the AirportSpec that from the airport type of this airport. If there
314 * is no airport (\c tile == INVALID_TILE) then return the dummy AirportSpec.
315 * @return The AirportSpec for this airport.
316 */
GetSpecAirport317 const AirportSpec *GetSpec() const
318 {
319 if (this->tile == INVALID_TILE) return &AirportSpec::dummy;
320 return AirportSpec::Get(this->type);
321 }
322
323 /**
324 * Get the finite-state machine for this airport or the finite-state machine
325 * for the dummy airport in case this isn't an airport.
326 * @pre this->type < NEW_AIRPORT_OFFSET.
327 * @return The state machine for this airport.
328 */
GetFTAAirport329 const AirportFTAClass *GetFTA() const
330 {
331 return this->GetSpec()->fsm;
332 }
333
334 /** Check if this airport has at least one hangar. */
HasHangarAirport335 inline bool HasHangar() const
336 {
337 return this->GetSpec()->nof_depots > 0;
338 }
339
340 /**
341 * Add the tileoffset to the base tile of this airport but rotate it first.
342 * The base tile is the northernmost tile of this airport. This function
343 * helps to make sure that getting the tile of a hangar works even for
344 * rotated airport layouts without requiring a rotated array of hangar tiles.
345 * @param tidc The tilediff to add to the airport tile.
346 * @return The tile of this airport plus the rotated offset.
347 */
GetRotatedTileFromOffsetAirport348 inline TileIndex GetRotatedTileFromOffset(TileIndexDiffC tidc) const
349 {
350 const AirportSpec *as = this->GetSpec();
351 switch (this->rotation) {
352 case DIR_N: return this->tile + ToTileIndexDiff(tidc);
353
354 case DIR_E: return this->tile + TileDiffXY(tidc.y, as->size_x - 1 - tidc.x);
355
356 case DIR_S: return this->tile + TileDiffXY(as->size_x - 1 - tidc.x, as->size_y - 1 - tidc.y);
357
358 case DIR_W: return this->tile + TileDiffXY(as->size_y - 1 - tidc.y, tidc.x);
359
360 default: NOT_REACHED();
361 }
362 }
363
364 /**
365 * Get the first tile of the given hangar.
366 * @param hangar_num The hangar to get the location of.
367 * @pre hangar_num < GetNumHangars().
368 * @return A tile with the given hangar.
369 */
GetHangarTileAirport370 inline TileIndex GetHangarTile(uint hangar_num) const
371 {
372 const AirportSpec *as = this->GetSpec();
373 for (uint i = 0; i < as->nof_depots; i++) {
374 if (as->depot_table[i].hangar_num == hangar_num) {
375 return this->GetRotatedTileFromOffset(as->depot_table[i].ti);
376 }
377 }
378 NOT_REACHED();
379 }
380
381 /**
382 * Get the exit direction of the hangar at a specific tile.
383 * @param tile The tile to query.
384 * @pre IsHangarTile(tile).
385 * @return The exit direction of the hangar, taking airport rotation into account.
386 */
GetHangarExitDirectionAirport387 inline Direction GetHangarExitDirection(TileIndex tile) const
388 {
389 const AirportSpec *as = this->GetSpec();
390 const HangarTileTable *htt = GetHangarDataByTile(tile);
391 return ChangeDir(htt->dir, DirDifference(this->rotation, as->rotation[0]));
392 }
393
394 /**
395 * Get the hangar number of the hangar at a specific tile.
396 * @param tile The tile to query.
397 * @pre IsHangarTile(tile).
398 * @return The hangar number of the hangar at the given tile.
399 */
GetHangarNumAirport400 inline uint GetHangarNum(TileIndex tile) const
401 {
402 const HangarTileTable *htt = GetHangarDataByTile(tile);
403 return htt->hangar_num;
404 }
405
406 /** Get the number of hangars on this airport. */
GetNumHangarsAirport407 inline uint GetNumHangars() const
408 {
409 uint num = 0;
410 uint counted = 0;
411 const AirportSpec *as = this->GetSpec();
412 for (uint i = 0; i < as->nof_depots; i++) {
413 if (!HasBit(counted, as->depot_table[i].hangar_num)) {
414 num++;
415 SetBit(counted, as->depot_table[i].hangar_num);
416 }
417 }
418 return num;
419 }
420
421 private:
422 /**
423 * Retrieve hangar information of a hangar at a given tile.
424 * @param tile %Tile containing the hangar.
425 * @return The requested hangar information.
426 * @pre The \a tile must be at a hangar tile at an airport.
427 */
GetHangarDataByTileAirport428 inline const HangarTileTable *GetHangarDataByTile(TileIndex tile) const
429 {
430 const AirportSpec *as = this->GetSpec();
431 for (uint i = 0; i < as->nof_depots; i++) {
432 if (this->GetRotatedTileFromOffset(as->depot_table[i].ti) == tile) {
433 return as->depot_table + i;
434 }
435 }
436 NOT_REACHED();
437 }
438 };
439
440 struct IndustryCompare {
441 bool operator() (const Industry *lhs, const Industry *rhs) const;
442 };
443
444 typedef std::set<Industry *, IndustryCompare> IndustryList;
445
446 /** Station data structure */
447 struct Station FINAL : SpecializedStation<Station, false> {
448 public:
GetPrimaryRoadStopFINAL449 RoadStop *GetPrimaryRoadStop(RoadStopType type) const
450 {
451 return type == ROADSTOP_BUS ? bus_stops : truck_stops;
452 }
453
454 RoadStop *GetPrimaryRoadStop(const struct RoadVehicle *v) const;
455
456 RoadStop *bus_stops; ///< All the road stops
457 TileArea bus_station; ///< Tile area the bus 'station' part covers
458 RoadStop *truck_stops; ///< All the truck stops
459 TileArea truck_station; ///< Tile area the truck 'station' part covers
460
461 Airport airport; ///< Tile area the airport covers
462 TileArea ship_station; ///< Tile area the ship 'station' part covers
463 TileArea docking_station; ///< Tile area the docking tiles cover
464
465 IndustryType indtype; ///< Industry type to get the name from
466
467 BitmapTileArea catchment_tiles; ///< NOSAVE: Set of individual tiles covered by catchment area
468
469 StationHadVehicleOfType had_vehicle_of_type;
470
471 byte time_since_load;
472 byte time_since_unload;
473
474 byte last_vehicle_type;
475 std::list<Vehicle *> loading_vehicles;
476 GoodsEntry goods[NUM_CARGO]; ///< Goods at this station
477 CargoTypes always_accepted; ///< Bitmask of always accepted cargo types (by houses, HQs, industry tiles when industry doesn't accept cargo)
478
479 IndustryList industries_near; ///< Cached list of industries near the station that can accept cargo, @see DeliverGoodsToIndustry()
480 Industry *industry; ///< NOSAVE: Associated industry for neutral stations. (Rebuilt on load from Industry->st)
481
482 Station(TileIndex tile = INVALID_TILE);
483 ~Station();
484
485 void AddFacility(StationFacility new_facility_bit, TileIndex facil_xy);
486
487 void MarkTilesDirty(bool cargo_change) const;
488
489 void UpdateVirtCoord() override;
490
491 void MoveSign(TileIndex new_xy) override;
492
493 void AfterStationTileSetChange(bool adding, StationType type);
494
495 uint GetPlatformLength(TileIndex tile, DiagDirection dir) const override;
496 uint GetPlatformLength(TileIndex tile) const override;
497 void RecomputeCatchment();
498 static void RecomputeCatchmentForAll();
499
500 uint GetCatchmentRadius() const;
501 Rect GetCatchmentRect() const;
502 bool CatchmentCoversTown(TownID t) const;
503 void AddIndustryToDeliver(Industry *ind);
504 void RemoveFromAllNearbyLists();
505
TileIsInCatchmentFINAL506 inline bool TileIsInCatchment(TileIndex tile) const
507 {
508 return this->catchment_tiles.HasTile(tile);
509 }
510
TileBelongsToRailStationFINAL511 inline bool TileBelongsToRailStation(TileIndex tile) const override
512 {
513 return IsRailStationTile(tile) && GetStationIndex(tile) == this->index;
514 }
515
TileBelongsToAirportFINAL516 inline bool TileBelongsToAirport(TileIndex tile) const
517 {
518 return IsAirportTile(tile) && GetStationIndex(tile) == this->index;
519 }
520
521 uint32 GetNewGRFVariable(const ResolverObject &object, byte variable, byte parameter, bool *available) const override;
522
523 void GetTileArea(TileArea *ta, StationType type) const override;
524 };
525
526 /** Iterator to iterate over all tiles belonging to an airport. */
527 class AirportTileIterator : public OrthogonalTileIterator {
528 private:
529 const Station *st; ///< The station the airport is a part of.
530
531 public:
532 /**
533 * Construct the iterator.
534 * @param st Station the airport is part of.
535 */
AirportTileIterator(const Station * st)536 AirportTileIterator(const Station *st) : OrthogonalTileIterator(st->airport), st(st)
537 {
538 if (!st->TileBelongsToAirport(this->tile)) ++(*this);
539 }
540
541 inline TileIterator& operator ++()
542 {
543 (*this).OrthogonalTileIterator::operator++();
544 while (this->tile != INVALID_TILE && !st->TileBelongsToAirport(this->tile)) {
545 (*this).OrthogonalTileIterator::operator++();
546 }
547 return *this;
548 }
549
Clone()550 virtual TileIterator *Clone() const
551 {
552 return new AirportTileIterator(*this);
553 }
554 };
555
556 void RebuildStationKdtree();
557
558 /**
559 * Call a function on all stations that have any part of the requested area within their catchment.
560 * @tparam Func The type of funcion to call
561 * @param area The TileArea to check
562 * @param func The function to call, must take two parameters: Station* and TileIndex and return true
563 * if coverage of that tile is acceptable for a given station or false if search should continue
564 */
565 template<typename Func>
ForAllStationsAroundTiles(const TileArea & ta,Func func)566 void ForAllStationsAroundTiles(const TileArea &ta, Func func)
567 {
568 /* There are no stations, so we will never find anything. */
569 if (Station::GetNumItems() == 0) return;
570
571 /* Not using, or don't have a nearby stations list, so we need to scan. */
572 std::set<StationID> seen_stations;
573
574 /* Scan an area around the building covering the maximum possible station
575 * to find the possible nearby stations. */
576 uint max_c = _settings_game.station.modified_catchment ? MAX_CATCHMENT : CA_UNMODIFIED;
577 TileArea ta_ext = TileArea(ta).Expand(max_c);
578 for (TileIndex tile : ta_ext) {
579 if (IsTileType(tile, MP_STATION)) seen_stations.insert(GetStationIndex(tile));
580 }
581
582 for (StationID stationid : seen_stations) {
583 Station *st = Station::GetIfValid(stationid);
584 if (st == nullptr) continue; /* Waypoint */
585
586 /* Check if station is attached to an industry */
587 if (!_settings_game.station.serve_neutral_industries && st->industry != nullptr) continue;
588
589 /* Test if the tile is within the station's catchment */
590 for (TileIndex tile : ta) {
591 if (st->TileIsInCatchment(tile)) {
592 if (func(st, tile)) break;
593 }
594 }
595 }
596 }
597
598 #endif /* STATION_BASE_H */
599