src/linkgraph/refresh.cpp

   1 /* $Id$ */
   2
   3 /*
   4 * This file is part of OpenTTD.
   5 * 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.
   6 * 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.
   7 * 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/>.
   8 */
   9
  10 /** @file refresh.h Definition of link refreshing utility. */
  11
  12 #include "../stdafx.h"
  13 #include "../core/bitmath_func.hpp"
  14 #include "../station_func.h"
  15 #include "../engine_base.h"
  16 #include "../vehicle_func.h"
  17 #include "refresh.h"
  18 #include "linkgraph.h"
  19
  20 #include "../safeguards.h"
  21
  22 /**
  23 * Refresh all links the given vehicle will visit.
  24 * @param v Vehicle to refresh links for.
  25 * @param allow_merge If the refresher is allowed to merge or extend link graphs.
  26 * @param is_full_loading If the vehicle is full loading.
  27 * @param cargo_mask Mask of cargoes to refresh
  28 */
  29 /* static */ void LinkRefresher::Run(Vehicle *v, bool allow_merge, bool is_full_loading, uint32 cargo_mask)
  30 {
  31         /* If there are no orders we can't predict anything.*/
  32         if (!v->HasOrdersList()) return;
  33
  34         uint32 have_cargo_mask = v->GetLastLoadingStationValidCargoMask();
  35
  36         /* Scan orders for cargo-specific load/unload, and run LinkRefresher separately for each set of cargoes where they differ. */
  37         while (cargo_mask != 0) {
  38                 uint32 iter_cargo_mask = cargo_mask;
  39                 for (const Order *o = v->GetFirstOrder(); o != NULL; o = o->next) {
  40                         if (o->IsType(OT_GOTO_STATION) || o->IsType(OT_IMPLICIT)) {
  41                                 if (o->GetUnloadType() == OUFB_CARGO_TYPE_UNLOAD) {
  42                                         CargoMaskValueFilter<uint>(iter_cargo_mask, [&](CargoID cargo) -> uint {
  43                                                 return o->GetCargoUnloadType(cargo) & (OUFB_TRANSFER | OUFB_UNLOAD | OUFB_NO_UNLOAD);
  44                                         });
  45                                 }
  46                                 if (o->GetLoadType() == OLFB_CARGO_TYPE_LOAD) {
  47                                         CargoMaskValueFilter<uint>(iter_cargo_mask, [&](CargoID cargo) -> uint {
  48                                                 return o->GetCargoLoadType(cargo) & (OLFB_NO_LOAD);
  49                                         });
  50                                 }
  51                         }
  52                 }
  53
  54                 /* Make sure the first order is a useful order. */
  55                 const Order *first = v->GetNextDecisionNode(v->GetOrder(v->cur_implicit_order_index), 0, iter_cargo_mask);
  56                 if (first != NULL) {
  57                         HopSet seen_hops;
  58                         LinkRefresher refresher(v, &seen_hops, allow_merge, is_full_loading, iter_cargo_mask);
  59
  60                         refresher.RefreshLinks(first, first, (iter_cargo_mask & have_cargo_mask) ? 1 << HAS_CARGO : 0);
  61                 }
  62
  63                 cargo_mask &= ~iter_cargo_mask;
  64         }
  65 }
  66
  67 /**
  68 * Comparison operator to allow hops to be used in a std::set.
  69 * @param other Other hop to be compared with.
  70 * @return If this hop is "smaller" than the other (defined by from, to and cargo in this order).
  71 */
  72 bool LinkRefresher::Hop::operator<(const Hop &other) const
  73 {
  74         if (this->from < other.from) {
  75                 return true;
  76         }
  77         else if (this->from > other.from) {
  78                 return false;
  79         }
  80         if (this->to < other.to) {
  81                 return true;
  82         }
  83         else if (this->to > other.to) {
  84                 return false;
  85         }
  86         return this->cargo < other.cargo;
  87 }
  88
  89 /**
  90 * Constructor for link refreshing algorithm.
  91 * @param vehicle Vehicle to refresh links for.
  92 * @param seen_hops Set of hops already seen. This is shared between this
  93 *                  refresher and all its children.
  94 * @param allow_merge If the refresher is allowed to merge or extend link graphs.
  95 * @param is_full_loading If the vehicle is full loading.
  96 */
  97 LinkRefresher::LinkRefresher(Vehicle *vehicle, HopSet *seen_hops, bool allow_merge, bool is_full_loading, uint32 cargo_mask) :
  98         vehicle(vehicle), seen_hops(seen_hops), cargo(CT_INVALID), allow_merge(allow_merge),
  99         is_full_loading(is_full_loading), cargo_mask(cargo_mask)
 100 {
 101         memset(this->capacities, 0, sizeof(this->capacities));
 102
 103         /* Assemble list of capacities and set last loading stations to 0. */
 104         for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
 105                 this->refit_capacities.push_back(RefitDesc(v->cargo_type, v->cargo_cap, v->refit_cap));
 106                 if (v->refit_cap > 0) {
 107                         assert(v->cargo_type < NUM_CARGO);
 108                         this->capacities[v->cargo_type] += v->refit_cap;
 109                 }
 110         }
 111 }
 112
 113 /**
 114 * Handle refit orders by updating capacities and refit_capacities.
 115 * @param refit_cargo Cargo to refit to.
 116 * @return True if any vehicle was refit; false if none was.
 117 */
 118 bool LinkRefresher::HandleRefit(CargoID refit_cargo)
 119 {
 120         this->cargo = refit_cargo;
 121         RefitList::iterator refit_it = this->refit_capacities.begin();
 122         bool any_refit = false;
 123         for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
 124                 const Engine *e = Engine::Get(v->engine_type);
 125                 if (!HasBit(e->info.refit_mask, this->cargo)) {
 126                         ++refit_it;
 127                         continue;
 128                 }
 129                 any_refit = true;
 130
 131                 /* Back up the vehicle's cargo type */
 132                 CargoID temp_cid = v->cargo_type;
 133                 byte temp_subtype = v->cargo_subtype;
 134                 v->cargo_type = this->cargo;
 135                 v->cargo_subtype = GetBestFittingSubType(v, v, this->cargo);
 136
 137                 uint16 mail_capacity = 0;
 138                 uint amount = e->DetermineCapacity(v, &mail_capacity);
 139
 140                 /* Restore the original cargo type */
 141                 v->cargo_type = temp_cid;
 142                 v->cargo_subtype = temp_subtype;
 143
 144                 /* Skip on next refit. */
 145                 if (this->cargo != refit_it->cargo && refit_it->remaining > 0) {
 146                         this->capacities[refit_it->cargo] -= refit_it->remaining;
 147                         refit_it->remaining = 0;
 148                 }
 149                 else if (amount < refit_it->remaining) {
 150                         this->capacities[refit_it->cargo] -= refit_it->remaining - amount;
 151                         refit_it->remaining = amount;
 152                 }
 153                 refit_it->capacity = amount;
 154                 refit_it->cargo = this->cargo;
 155
 156                 ++refit_it;
 157
 158                 /* Special case for aircraft with mail. */
 159                 if (v->type == VEH_AIRCRAFT) {
 160                         if (mail_capacity < refit_it->remaining) {
 161                                 this->capacities[refit_it->cargo] -= refit_it->remaining - mail_capacity;
 162                                 refit_it->remaining = mail_capacity;
 163                         }
 164                         refit_it->capacity = mail_capacity;
 165                         break; // aircraft have only one vehicle
 166                 }
 167         }
 168         return any_refit;
 169 }
 170
 171 /**
 172 * Restore capacities and refit_capacities as vehicle might have been able to load now.
 173 */
 174 void LinkRefresher::ResetRefit()
 175 {
 176         for (RefitList::iterator it(this->refit_capacities.begin()); it != this->refit_capacities.end(); ++it) {
 177                 if (it->remaining == it->capacity) continue;
 178                 this->capacities[it->cargo] += it->capacity - it->remaining;
 179                 it->remaining = it->capacity;
 180         }
 181 }
 182
 183 /**
 184 * Predict the next order the vehicle will execute and resolve conditionals by
 185 * recursion and return next non-conditional order in list.
 186 * @param cur Current order being evaluated.
 187 * @param next Next order to be evaluated.
 188 * @param flags RefreshFlags to give hints about the previous link and state carried over from that.
 189 * @param num_hops Number of hops already taken by recursive calls to this method.
 190 * @return new next Order.
 191 */
 192 const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next, uint8 flags, uint num_hops)
 193 {
 194         /* next is good if it's either NULL (then the caller will stop the
 195         * evaluation) or if it's not conditional and the caller allows it to be
 196         * chosen (by setting USE_NEXT). */
 197         while (next != NULL && (!HasBit(flags, USE_NEXT) || next->IsType(OT_CONDITIONAL))) {
 198
 199                 /* After the first step any further non-conditional order is good,
 200                 * regardless of previous USE_NEXT settings. The case of cur and next or
 201                 * their respective stations being equal is handled elsewhere. */
 202                 SetBit(flags, USE_NEXT);
 203
 204                 if (next->IsType(OT_CONDITIONAL)) {
 205                         uint32 this_cargo_mask = this->cargo_mask;
 206                         const Order *skip_to = this->vehicle->GetNextDecisionNode(
 207                                 this->vehicle->GetOrderAt(next->GetConditionSkipToOrder()), num_hops, this_cargo_mask);
 208                         assert(this_cargo_mask == this->cargo_mask);
 209                         if (skip_to != NULL && num_hops < this->vehicle->GetNumOrders()) {
 210                                 /* Make copies of capacity tracking lists. There is potential
 211                                 * for optimization here: If the vehicle never refits we don't
 212                                 * need to copy anything. Also, if we've seen the branched link
 213                                 * before we don't need to branch at all. */
 214                                 LinkRefresher branch(*this);
 215                                 branch.RefreshLinks(cur, skip_to, flags, num_hops + 1);
 216                         }
 217                 }
 218
 219                 /* Reassign next with the following stop. This can be a station or a
 220                 * depot.*/
 221                 uint32 this_cargo_mask = this->cargo_mask;
 222                 next = this->vehicle->GetNextDecisionNode(
 223                         this->vehicle->GetNextOrder(next), num_hops++, this_cargo_mask);
 224                 assert(this_cargo_mask == this->cargo_mask);
 225         }
 226         return next;
 227 }
 228
 229 /**
 230 * Refresh link stats for the given pair of orders.
 231 * @param cur Last stop where the consist could interact with cargo.
 232 * @param next Next order to be processed.
 233 */
 234 void LinkRefresher::RefreshStats(const Order *cur, const Order *next)
 235 {
 236         StationID next_station = next->GetDestination();
 237         Station *st = Station::GetIfValid(cur->GetDestination());
 238         if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {
 239                 for (CargoID c = 0; c < NUM_CARGO; c++) {
 240                         /* Refresh the link and give it a minimum capacity. */
 241
 242                         if (!HasBit(this->cargo_mask, c)) continue;
 243
 244                         uint cargo_quantity = this->capacities[c];
 245                         if (cargo_quantity == 0) continue;
 246
 247                         /* If not allowed to merge link graphs, make sure the stations are
 248                         * already in the same link graph. */
 249                         if (!this->allow_merge && st->goods[c].link_graph != Station::Get(next_station)->goods[c].link_graph) {
 250                                 continue;
 251                         }
 252
 253                         /* A link is at least partly restricted if a vehicle can't load at its source. */
 254                         EdgeUpdateMode restricted_mode = (cur->GetCargoLoadType(c) & OLFB_NO_LOAD) == 0 ?
 255                                 EUM_UNRESTRICTED : EUM_RESTRICTED;
 256
 257                         /* If the vehicle is currently full loading, increase the capacities at the station
 258                         * where it is loading by an estimate of what it would have transported if it wasn't
 259                         * loading. Don't do that if the vehicle has been waiting for longer than the entire
 260                         * order list is supposed to take, though. If that is the case the total duration is
 261                         * probably far off and we'd greatly overestimate the capacity by increasing.*/
 262                         if (this->is_full_loading && this->vehicle->HasOrdersList() &&
 263                                 st->index == vehicle->last_station_visited &&
 264                                 this->vehicle->GetTotalOrderListDuration() >
 265                                 (Ticks)this->vehicle->current_order_time) {
 266                                 uint effective_capacity = cargo_quantity * this->vehicle->load_unload_ticks;
 267                                 if (effective_capacity > (uint)this->vehicle->GetTotalOrderListDuration()) {
 268                                         IncreaseStats(st, c, next_station, effective_capacity /
 269                                                 this->vehicle->GetTotalOrderListDuration(), 0,
 270                                                 EUM_INCREASE | restricted_mode);
 271                                 }
 272                                 else if (RandomRange(this->vehicle->GetTotalOrderListDuration()) < effective_capacity) {
 273                                         IncreaseStats(st, c, next_station, 1, 0, EUM_INCREASE | restricted_mode);
 274                                 }
 275                                 else {
 276                                         IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode);
 277                                 }
 278                         }
 279                         else {
 280                                 IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode);
 281                         }
 282                 }
 283         }
 284 }
 285
 286 /**
 287 * Iterate over orders starting at \a cur and \a next and refresh links
 288 * associated with them. \a cur and \a next can be equal. If they're not they
 289 * must be "neigbours" in their order list, which means \a next must be directly
 290 * reachable from \a cur without passing any further OT_GOTO_STATION or
 291 * OT_IMPLICIT orders in between.
 292 * @param cur Current order being evaluated.
 293 * @param next Next order to be checked.
 294 * @param flags RefreshFlags to give hints about the previous link and state carried over from that.
 295 * @param num_hops Number of hops already taken by recursive calls to this method.
 296 */
 297 void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flags, uint num_hops)
 298 {
 299         while (next != NULL) {
 300
 301                 if ((next->IsType(OT_GOTO_DEPOT) || next->IsType(OT_GOTO_STATION)) && next->IsRefit()) {
 302                         SetBit(flags, WAS_REFIT);
 303                         if (!next->IsAutoRefit()) {
 304                                 this->HandleRefit(next->GetRefitCargo());
 305                         }
 306                         else if (!HasBit(flags, IN_AUTOREFIT)) {
 307                                 SetBit(flags, IN_AUTOREFIT);
 308                                 LinkRefresher backup(*this);
 309                                 for (CargoID c = 0; c != NUM_CARGO; ++c) {
 310                                         if (CargoSpec::Get(c)->IsValid() && this->HandleRefit(c)) {
 311                                                 this->RefreshLinks(cur, next, flags, num_hops);
 312                                                 *this = backup;
 313                                         }
 314                                 }
 315                         }
 316                 }
 317
 318                 /* Only reset the refit capacities if the "previous" next is a station,
 319                 * meaning that either the vehicle was refit at the previous station or
 320                 * it wasn't at all refit during the current hop. */
 321                 if (HasBit(flags, WAS_REFIT) && (next->IsType(OT_GOTO_STATION) || next->IsType(OT_IMPLICIT))) {
 322                         SetBit(flags, RESET_REFIT);
 323                 }
 324                 else {
 325                         ClrBit(flags, RESET_REFIT);
 326                 }
 327
 328                 next = this->PredictNextOrder(cur, next, flags, num_hops);
 329                 if (next == NULL) break;
 330                 Hop hop(cur->index, next->index, this->cargo);
 331                 if (this->seen_hops->find(hop) != this->seen_hops->end()) {
 332                         break;
 333                 }
 334                 else {
 335                         this->seen_hops->insert(hop);
 336                 }
 337
 338                 /* Don't use the same order again, but choose a new one in the next round. */
 339                 ClrBit(flags, USE_NEXT);
 340
 341                 /* Skip resetting and link refreshing if next order won't do anything with cargo. */
 342                 if (!next->IsType(OT_GOTO_STATION) && !next->IsType(OT_IMPLICIT)) continue;
 343
 344                 if (HasBit(flags, RESET_REFIT)) {
 345                         this->ResetRefit();
 346                         ClrBit(flags, RESET_REFIT);
 347                         ClrBit(flags, WAS_REFIT);
 348                 }
 349
 350                 if (cur->IsType(OT_GOTO_STATION) || cur->IsType(OT_IMPLICIT)) {
 351                         if (cur->CanLeaveWithCargo(HasBit(flags, HAS_CARGO), FindFirstBit(this->cargo_mask))) {
 352                                 SetBit(flags, HAS_CARGO);
 353                                 this->RefreshStats(cur, next);
 354                         }
 355                         else {
 356                                 ClrBit(flags, HAS_CARGO);
 357                         }
 358                 }
 359
 360                 /* "cur" is only assigned here if the stop is a station so that
 361                 * whenever stats are to be increased two stations can be found. */
 362                 cur = next;
 363         }
 364 }