src/station_base.h

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