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         uint8_t 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         uint8_t type;          ///< Type of this airport, @see AirportTypes
 295         uint8_t 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()->depots.empty();
 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                 for (const auto &depot : this->GetSpec()->depots) {
 361                         if (depot.hangar_num == hangar_num) {
 362                                 return this->GetRotatedTileFromOffset(depot.ti);
 363                         }
 364                 }
 365                 NOT_REACHED();
 366         }
 367
 368         /**
 369          * Get the exit direction of the hangar at a specific tile.
 370          * @param tile The tile to query.
 371          * @pre IsHangarTile(tile).
 372          * @return The exit direction of the hangar, taking airport rotation into account.
 373          */
 374         inline Direction GetHangarExitDirection(TileIndex tile) const
 375         {
 376                 const AirportSpec *as = this->GetSpec();
 377                 const HangarTileTable *htt = GetHangarDataByTile(tile);
 378                 return ChangeDir(htt->dir, DirDifference(this->rotation, as->layouts[0].rotation));
 379         }
 380
 381         /**
 382          * Get the hangar number of the hangar at a specific tile.
 383          * @param tile The tile to query.
 384          * @pre IsHangarTile(tile).
 385          * @return The hangar number of the hangar at the given tile.
 386          */
 387         inline uint GetHangarNum(TileIndex tile) const
 388         {
 389                 const HangarTileTable *htt = GetHangarDataByTile(tile);
 390                 return htt->hangar_num;
 391         }
 392
 393         /** Get the number of hangars on this airport. */
 394         inline uint GetNumHangars() const
 395         {
 396                 uint num = 0;
 397                 uint counted = 0;
 398                 for (const auto &depot : this->GetSpec()->depots) {
 399                         if (!HasBit(counted, depot.hangar_num)) {
 400                                 num++;
 401                                 SetBit(counted, depot.hangar_num);
 402                         }
 403                 }
 404                 return num;
 405         }
 406
 407 private:
 408         /**
 409          * Retrieve hangar information of a hangar at a given tile.
 410          * @param tile %Tile containing the hangar.
 411          * @return The requested hangar information.
 412          * @pre The \a tile must be at a hangar tile at an airport.
 413          */
 414         inline const HangarTileTable *GetHangarDataByTile(TileIndex tile) const
 415         {
 416                 for (const auto &depot : this->GetSpec()->depots) {
 417                         if (this->GetRotatedTileFromOffset(depot.ti) == tile) {
 418                                 return &depot;
 419                         }
 420                 }
 421                 NOT_REACHED();
 422         }
 423 };
 424
 425 struct IndustryListEntry {
 426         uint distance;
 427         Industry *industry;
 428
 429         bool operator== (const IndustryListEntry &other) const { return this->distance == other.distance && this->industry == other.industry; };
 430 };
 431
 432 struct IndustryCompare {
 433         bool operator() (const IndustryListEntry &lhs, const IndustryListEntry &rhs) const;
 434 };
 435
 436 typedef std::set<IndustryListEntry, IndustryCompare> IndustryList;
 437
 438 /** Station data structure */
 439 struct Station final : SpecializedStation<Station, false> {
 440 public:
 441         RoadStop *GetPrimaryRoadStop(RoadStopType type) const
 442         {
 443                 return type == ROADSTOP_BUS ? bus_stops : truck_stops;
 444         }
 445
 446         RoadStop *GetPrimaryRoadStop(const struct RoadVehicle *v) const;
 447
 448         RoadStop *bus_stops;    ///< All the road stops
 449         TileArea bus_station;   ///< Tile area the bus 'station' part covers
 450         RoadStop *truck_stops;  ///< All the truck stops
 451         TileArea truck_station; ///< Tile area the truck 'station' part covers
 452
 453         Airport airport;          ///< Tile area the airport covers
 454         TileArea ship_station;    ///< Tile area the ship 'station' part covers
 455         TileArea docking_station; ///< Tile area the docking tiles cover
 456
 457         IndustryType indtype;   ///< Industry type to get the name from
 458
 459         BitmapTileArea catchment_tiles; ///< NOSAVE: Set of individual tiles covered by catchment area
 460
 461         StationHadVehicleOfType had_vehicle_of_type;
 462
 463         uint8_t time_since_load;
 464         uint8_t time_since_unload;
 465
 466         uint8_t last_vehicle_type;
 467         std::list<Vehicle *> loading_vehicles;
 468         GoodsEntry goods[NUM_CARGO];  ///< Goods at this station
 469         CargoTypes always_accepted;       ///< Bitmask of always accepted cargo types (by houses, HQs, industry tiles when industry doesn't accept cargo)
 470
 471         IndustryList industries_near; ///< Cached list of industries near the station that can accept cargo, @see DeliverGoodsToIndustry()
 472         Industry *industry;           ///< NOSAVE: Associated industry for neutral stations. (Rebuilt on load from Industry->st)
 473
 474         Station(TileIndex tile = INVALID_TILE);
 475         ~Station();
 476
 477         void AddFacility(StationFacility new_facility_bit, TileIndex facil_xy);
 478
 479         void MarkTilesDirty(bool cargo_change) const;
 480
 481         void UpdateVirtCoord() override;
 482
 483         void MoveSign(TileIndex new_xy) override;
 484
 485         void AfterStationTileSetChange(bool adding, StationType type);
 486
 487         uint GetPlatformLength(TileIndex tile, DiagDirection dir) const override;
 488         uint GetPlatformLength(TileIndex tile) const override;
 489         void RecomputeCatchment(bool no_clear_nearby_lists = false);
 490         static void RecomputeCatchmentForAll();
 491
 492         uint GetCatchmentRadius() const;
 493         Rect GetCatchmentRect() const;
 494         bool CatchmentCoversTown(TownID t) const;
 495         void AddIndustryToDeliver(Industry *ind, TileIndex tile);
 496         void RemoveIndustryToDeliver(Industry *ind);
 497         void RemoveFromAllNearbyLists();
 498
 499         inline bool TileIsInCatchment(TileIndex tile) const
 500         {
 501                 return this->catchment_tiles.HasTile(tile);
 502         }
 503
 504         inline bool TileBelongsToRailStation(TileIndex tile) const override
 505         {
 506                 return IsRailStationTile(tile) && GetStationIndex(tile) == this->index;
 507         }
 508
 509         inline bool TileBelongsToRoadStop(TileIndex tile) const
 510         {
 511                 return IsStationRoadStopTile(tile) && GetStationIndex(tile) == this->index;
 512         }
 513
 514         inline bool TileBelongsToAirport(TileIndex tile) const
 515         {
 516                 return IsAirportTile(tile) && GetStationIndex(tile) == this->index;
 517         }
 518
 519         uint32_t GetNewGRFVariable(const ResolverObject &object, uint8_t variable, uint8_t parameter, bool &available) const override;
 520
 521         void GetTileArea(TileArea *ta, StationType type) const override;
 522 };
 523
 524 /** Iterator to iterate over all tiles belonging to an airport. */
 525 class AirportTileIterator : public OrthogonalTileIterator {
 526 private:
 527         const Station *st; ///< The station the airport is a part of.
 528
 529 public:
 530         /**
 531          * Construct the iterator.
 532          * @param st Station the airport is part of.
 533          */
 534         AirportTileIterator(const Station *st) : OrthogonalTileIterator(st->airport), st(st)
 535         {
 536                 if (!st->TileBelongsToAirport(this->tile)) ++(*this);
 537         }
 538
 539         inline TileIterator& operator ++() override
 540         {
 541                 (*this).OrthogonalTileIterator::operator++();
 542                 while (this->tile != INVALID_TILE && !st->TileBelongsToAirport(this->tile)) {
 543                         (*this).OrthogonalTileIterator::operator++();
 544                 }
 545                 return *this;
 546         }
 547
 548         std::unique_ptr<TileIterator> Clone() const override
 549         {
 550                 return std::make_unique<AirportTileIterator>(*this);
 551         }
 552 };
 553
 554 void RebuildStationKdtree();
 555
 556 /**
 557  * Call a function on all stations that have any part of the requested area within their catchment.
 558  * @tparam Func The type of funcion to call
 559  * @param area The TileArea to check
 560  * @param func The function to call, must take two parameters: Station* and TileIndex and return true
 561  *             if coverage of that tile is acceptable for a given station or false if search should continue
 562  */
 563 template<typename Func>
 564 void ForAllStationsAroundTiles(const TileArea &ta, Func func)
 565 {
 566         /* There are no stations, so we will never find anything. */
 567         if (Station::GetNumItems() == 0) return;
 568
 569         /* Not using, or don't have a nearby stations list, so we need to scan. */
 570         std::set<StationID> seen_stations;
 571
 572         /* Scan an area around the building covering the maximum possible station
 573          * to find the possible nearby stations. */
 574         uint max_c = _settings_game.station.modified_catchment ? MAX_CATCHMENT : CA_UNMODIFIED;
 575         TileArea ta_ext = TileArea(ta).Expand(max_c);
 576         for (TileIndex tile : ta_ext) {
 577                 if (IsTileType(tile, MP_STATION)) seen_stations.insert(GetStationIndex(tile));
 578         }
 579
 580         for (StationID stationid : seen_stations) {
 581                 Station *st = Station::GetIfValid(stationid);
 582                 if (st == nullptr) continue; /* Waypoint */
 583
 584                 /* Check if station is attached to an industry */
 585                 if (!_settings_game.station.serve_neutral_industries && st->industry != nullptr) continue;
 586
 587                 /* Test if the tile is within the station's catchment */
 588                 for (TileIndex tile : ta) {
 589                         if (st->TileIsInCatchment(tile)) {
 590                                 if (func(st, tile)) break;
 591                         }
 592                 }
 593         }
 594 }
 595
 596 #endif /* STATION_BASE_H */