OpenTTD
refresh.cpp
1 /* $Id: refresh.cpp 27614 2016-07-10 12:17:00Z fonsinchen $ */
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 
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 
28 /* static */ void LinkRefresher::Run(Vehicle *v, bool allow_merge, bool is_full_loading)
29 {
30  /* If there are no orders we can't predict anything.*/
31  if (v->orders.list == NULL) return;
32 
33  /* Make sure the first order is a useful order. */
35  if (first == NULL) return;
36 
37  HopSet seen_hops;
38  LinkRefresher refresher(v, &seen_hops, allow_merge, is_full_loading);
39 
40  refresher.RefreshLinks(first, first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0);
41 }
42 
48 bool LinkRefresher::Hop::operator<(const Hop &other) const
49 {
50  if (this->from < other.from) {
51  return true;
52  } else if (this->from > other.from) {
53  return false;
54  }
55  if (this->to < other.to) {
56  return true;
57  } else if (this->to > other.to) {
58  return false;
59  }
60  return this->cargo < other.cargo;
61 }
62 
72  vehicle(vehicle), seen_hops(seen_hops), cargo(CT_INVALID), allow_merge(allow_merge),
73  is_full_loading(is_full_loading)
74 {
75  memset(this->capacities, 0, sizeof(this->capacities));
76 
77  /* Assemble list of capacities and set last loading stations to 0. */
78  for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
79  this->refit_capacities.push_back(RefitDesc(v->cargo_type, v->cargo_cap, v->refit_cap));
80  if (v->refit_cap > 0) {
81  assert(v->cargo_type < NUM_CARGO);
82  this->capacities[v->cargo_type] += v->refit_cap;
83  }
84  }
85 }
86 
93 {
94  this->cargo = refit_cargo;
95  RefitList::iterator refit_it = this->refit_capacities.begin();
96  bool any_refit = false;
97  for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
98  const Engine *e = Engine::Get(v->engine_type);
99  if (!HasBit(e->info.refit_mask, this->cargo)) {
100  ++refit_it;
101  continue;
102  }
103  any_refit = true;
104 
105  /* Back up the vehicle's cargo type */
106  CargoID temp_cid = v->cargo_type;
107  byte temp_subtype = v->cargo_subtype;
108  v->cargo_type = this->cargo;
109  v->cargo_subtype = GetBestFittingSubType(v, v, this->cargo);
110 
111  uint16 mail_capacity = 0;
112  uint amount = e->DetermineCapacity(v, &mail_capacity);
113 
114  /* Restore the original cargo type */
115  v->cargo_type = temp_cid;
116  v->cargo_subtype = temp_subtype;
117 
118  /* Skip on next refit. */
119  if (this->cargo != refit_it->cargo && refit_it->remaining > 0) {
120  this->capacities[refit_it->cargo] -= refit_it->remaining;
121  refit_it->remaining = 0;
122  } else if (amount < refit_it->remaining) {
123  this->capacities[refit_it->cargo] -= refit_it->remaining - amount;
124  refit_it->remaining = amount;
125  }
126  refit_it->capacity = amount;
127  refit_it->cargo = this->cargo;
128 
129  ++refit_it;
130 
131  /* Special case for aircraft with mail. */
132  if (v->type == VEH_AIRCRAFT) {
133  if (mail_capacity < refit_it->remaining) {
134  this->capacities[refit_it->cargo] -= refit_it->remaining - mail_capacity;
135  refit_it->remaining = mail_capacity;
136  }
137  refit_it->capacity = mail_capacity;
138  break; // aircraft have only one vehicle
139  }
140  }
141  return any_refit;
142 }
143 
148 {
149  for (RefitList::iterator it(this->refit_capacities.begin()); it != this->refit_capacities.end(); ++it) {
150  if (it->remaining == it->capacity) continue;
151  this->capacities[it->cargo] += it->capacity - it->remaining;
152  it->remaining = it->capacity;
153  }
154 }
155 
165 const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next, uint8 flags, uint num_hops)
166 {
167  /* next is good if it's either NULL (then the caller will stop the
168  * evaluation) or if it's not conditional and the caller allows it to be
169  * chosen (by setting USE_NEXT). */
170  while (next != NULL && (!HasBit(flags, USE_NEXT) || next->IsType(OT_CONDITIONAL))) {
171 
172  /* After the first step any further non-conditional order is good,
173  * regardless of previous USE_NEXT settings. The case of cur and next or
174  * their respective stations being equal is handled elsewhere. */
175  SetBit(flags, USE_NEXT);
176 
177  if (next->IsType(OT_CONDITIONAL)) {
178  const Order *skip_to = this->vehicle->orders.list->GetNextDecisionNode(
179  this->vehicle->orders.list->GetOrderAt(next->GetConditionSkipToOrder()), num_hops);
180  if (skip_to != NULL && num_hops < this->vehicle->orders.list->GetNumOrders()) {
181  /* Make copies of capacity tracking lists. There is potential
182  * for optimization here: If the vehicle never refits we don't
183  * need to copy anything. Also, if we've seen the branched link
184  * before we don't need to branch at all. */
185  LinkRefresher branch(*this);
186  branch.RefreshLinks(cur, skip_to, flags, num_hops + 1);
187  }
188  }
189 
190  /* Reassign next with the following stop. This can be a station or a
191  * depot.*/
192  next = this->vehicle->orders.list->GetNextDecisionNode(
193  this->vehicle->orders.list->GetNext(next), num_hops++);
194  }
195  return next;
196 }
197 
203 void LinkRefresher::RefreshStats(const Order *cur, const Order *next)
204 {
205  StationID next_station = next->GetDestination();
207  if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {
208  for (CargoID c = 0; c < NUM_CARGO; c++) {
209  /* Refresh the link and give it a minimum capacity. */
210 
211  uint cargo_quantity = this->capacities[c];
212  if (cargo_quantity == 0) continue;
213 
214  /* If not allowed to merge link graphs, make sure the stations are
215  * already in the same link graph. */
216  if (!this->allow_merge && st->goods[c].link_graph != Station::Get(next_station)->goods[c].link_graph) {
217  continue;
218  }
219 
220  /* A link is at least partly restricted if a vehicle can't load at its source. */
221  EdgeUpdateMode restricted_mode = (cur->GetLoadType() & OLFB_NO_LOAD) == 0 ?
223 
224  /* If the vehicle is currently full loading, increase the capacities at the station
225  * where it is loading by an estimate of what it would have transported if it wasn't
226  * loading. Don't do that if the vehicle has been waiting for longer than the entire
227  * order list is supposed to take, though. If that is the case the total duration is
228  * probably far off and we'd greatly overestimate the capacity by increasing.*/
229  if (this->is_full_loading && this->vehicle->orders.list != NULL &&
231  this->vehicle->orders.list->GetTotalDuration() >
232  (Ticks)this->vehicle->current_order_time) {
233  uint effective_capacity = cargo_quantity * this->vehicle->load_unload_ticks;
234  if (effective_capacity > (uint)this->vehicle->orders.list->GetTotalDuration()) {
235  IncreaseStats(st, c, next_station, effective_capacity /
236  this->vehicle->orders.list->GetTotalDuration(), 0,
237  EUM_INCREASE | restricted_mode);
238  } else if (RandomRange(this->vehicle->orders.list->GetTotalDuration()) < effective_capacity) {
239  IncreaseStats(st, c, next_station, 1, 0, EUM_INCREASE | restricted_mode);
240  } else {
241  IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode);
242  }
243  } else {
244  IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode);
245  }
246  }
247  }
248 }
249 
261 void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flags, uint num_hops)
262 {
263  while (next != NULL) {
264 
265  if ((next->IsType(OT_GOTO_DEPOT) || next->IsType(OT_GOTO_STATION)) && next->IsRefit()) {
266  SetBit(flags, WAS_REFIT);
267  if (!next->IsAutoRefit()) {
268  this->HandleRefit(next->GetRefitCargo());
269  } else if (!HasBit(flags, IN_AUTOREFIT)) {
270  SetBit(flags, IN_AUTOREFIT);
271  LinkRefresher backup(*this);
272  for (CargoID c = 0; c != NUM_CARGO; ++c) {
273  if (CargoSpec::Get(c)->IsValid() && this->HandleRefit(c)) {
274  this->RefreshLinks(cur, next, flags, num_hops);
275  *this = backup;
276  }
277  }
278  }
279  }
280 
281  /* Only reset the refit capacities if the "previous" next is a station,
282  * meaning that either the vehicle was refit at the previous station or
283  * it wasn't at all refit during the current hop. */
284  if (HasBit(flags, WAS_REFIT) && (next->IsType(OT_GOTO_STATION) || next->IsType(OT_IMPLICIT))) {
285  SetBit(flags, RESET_REFIT);
286  } else {
287  ClrBit(flags, RESET_REFIT);
288  }
289 
290  next = this->PredictNextOrder(cur, next, flags, num_hops);
291  if (next == NULL) break;
292  Hop hop(cur->index, next->index, this->cargo);
293  if (this->seen_hops->find(hop) != this->seen_hops->end()) {
294  break;
295  } else {
296  this->seen_hops->insert(hop);
297  }
298 
299  /* Don't use the same order again, but choose a new one in the next round. */
300  ClrBit(flags, USE_NEXT);
301 
302  /* Skip resetting and link refreshing if next order won't do anything with cargo. */
303  if (!next->IsType(OT_GOTO_STATION) && !next->IsType(OT_IMPLICIT)) continue;
304 
305  if (HasBit(flags, RESET_REFIT)) {
306  this->ResetRefit();
307  ClrBit(flags, RESET_REFIT);
308  ClrBit(flags, WAS_REFIT);
309  }
310 
311  if (cur->IsType(OT_GOTO_STATION) || cur->IsType(OT_IMPLICIT)) {
312  if (cur->CanLeaveWithCargo(HasBit(flags, HAS_CARGO))) {
313  SetBit(flags, HAS_CARGO);
314  this->RefreshStats(cur, next);
315  } else {
316  ClrBit(flags, HAS_CARGO);
317  }
318  }
319 
320  /* "cur" is only assigned here if the stop is a station so that
321  * whenever stats are to be increased two stations can be found. */
322  cur = next;
323  }
324 }
CargoID cargo
Cargo the consist is probably carrying or CT_INVALID if unknown.
Definition: refresh.h:64
Increase capacity.
Definition of link refreshing utility.
OrderID from
Last order where vehicle could interact with cargo or absolute first order.
Definition: refresh.h:62
Consist had a chance to load since the last refit and the refit capacities can be reset...
Definition: refresh.h:37
void RefreshStats(const Order *cur, const Order *next)
Refresh link stats for the given pair of orders.
Definition: refresh.cpp:203
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:246
CargoID cargo
Cargo given in last refit order.
Definition: refresh.h:89
VehicleOrderID GetConditionSkipToOrder() const
Get the order to skip to.
Definition: order_base.h:145
bool is_full_loading
If the vehicle is full loading.
Definition: refresh.h:91
static T SetBit(T &x, const uint8 y)
Set a bit in a variable.
Ticks GetTotalDuration() const
Gets the known duration of the vehicles orders, timetabled or not.
Definition: order_base.h:376
OrderList * list
Pointer to the order list for this vehicle.
Definition: vehicle_base.h:321
StationID last_loading_station
Last station the vehicle has stopped at and could possibly leave from with any cargo loaded...
Definition: vehicle_base.h:303
byte GetBestFittingSubType(Vehicle *v_from, Vehicle *v_for, CargoID dest_cargo_type)
Get the best fitting subtype when &#39;cloning&#39;/&#39;replacing&#39; v_from with v_for.
uint32 current_order_time
How many ticks have passed since this order started.
Definition: base_consist.h:23
Vehicle data structure.
Definition: vehicle_base.h:212
Tindex index
Index of this pool item.
Definition: pool_type.hpp:147
StationID last_station_visited
The last station we stopped at.
Definition: vehicle_base.h:302
void ResetRefit()
Restore capacities and refit_capacities as vehicle might have been able to load now.
Definition: refresh.cpp:147
const Order * GetNextDecisionNode(const Order *next, uint hops) const
Get the next order which will make the given vehicle stop at a station or refit at a depot or evaluat...
Definition: order_cmd.cpp:369
bool CanLeaveWithCargo(bool has_cargo) const
A vehicle can leave the current station with cargo if:
Definition: order_cmd.cpp:2283
GoodsEntry goods[NUM_CARGO]
Goods at this station.
Definition: station_base.h:472
static uint32 RandomRange(uint32 limit)
Pick a random number between 0 and limit - 1, inclusive.
Definition: random_func.hpp:83
Consist could leave the last stop where it could interact with cargo carrying cargo (i...
Definition: refresh.h:35
Order * GetOrderAt(int index) const
Get a certain order of the order chain.
Definition: order_cmd.cpp:346
bool IsAutoRefit() const
Is this order a auto-refit order.
Definition: order_base.h:117
Refresh capacity.
Vehicle * vehicle
Vehicle for which the links should be refreshed.
Definition: refresh.h:85
Aircraft vehicle type.
Definition: vehicle_type.h:27
uint capacities[NUM_CARGO]
Current added capacities per cargo ID in the consist.
Definition: refresh.h:86
LinkGraphID link_graph
Link graph this station belongs to.
Definition: station_base.h:257
bool IsRefit() const
Is this order a refit order.
Definition: order_base.h:110
bool operator<(const Hop &other) const
Comparison operator to allow hops to be used in a std::set.
Definition: refresh.cpp:48
Do not load anything.
Definition: order_type.h:72
bool IsType(OrderType type) const
Check whether this order is of the given type.
Definition: order_base.h:63
bool allow_merge
If the refresher is allowed to merge or extend link graphs.
Definition: refresh.h:90
void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage, EdgeUpdateMode mode)
Increase capacity for a link stat given by station cargo and next hop.
static void Run(Vehicle *v, bool allow_merge=true, bool is_full_loading=false)
Refresh all links the given vehicle will visit.
Definition: refresh.cpp:28
OrderID to
Next order to be processed.
Definition: refresh.h:63
uint16 load_unload_ticks
Ticks to wait before starting next cycle.
Definition: vehicle_base.h:325
Use restricted link.
HopSet * seen_hops
Hops already seen. If the same hop is seen twice we stop the algorithm. This is shared between all Re...
Definition: refresh.h:88
const Order * PredictNextOrder(const Order *cur, const Order *next, uint8 flags, uint num_hops=0)
Predict the next order the vehicle will execute and resolve conditionals by recursion and return next...
Definition: refresh.cpp:165
Currently doing an autorefit loop. Ignore the first autorefit order.
Definition: refresh.h:38
OrderLoadFlags GetLoadType() const
How must the consist be loaded?
Definition: order_base.h:129
Invalid cargo type.
Definition: cargo_type.h:70
void RefreshLinks(const Order *cur, const Order *next, uint8 flags, uint num_hops=0)
Iterate over orders starting at cur and next and refresh links associated with them.
Definition: refresh.cpp:261
A hop the refresh algorithm might evaluate.
Definition: refresh.h:61
LinkRefresher(Vehicle *v, HopSet *seen_hops, bool allow_merge, bool is_full_loading)
Constructor for link refreshing algorithm.
Definition: refresh.cpp:71
uint DetermineCapacity(const Vehicle *v, uint16 *mail_capacity=NULL) const
Determines capacity of a given vehicle from scratch.
Definition: engine.cpp:206
const Order * GetNext(const Order *curr) const
Get the order after the given one or the first one, if the given one is the last one.
Definition: order_base.h:306
Maximal number of cargo types in a game.
Definition: cargo_type.h:66
EdgeUpdateMode
Special modes for updating links.
RefitList refit_capacities
Current state of capacity remaining from previous refits versus overall capacity per vehicle in the c...
Definition: refresh.h:87
static T ClrBit(T &x, const uint8 y)
Clears a bit in a variable.
DestinationID GetDestination() const
Gets the destination of this order.
Definition: order_base.h:96
static CargoSpec * Get(size_t index)
Retrieve cargo details for the given cargo ID.
Definition: cargotype.h:118
Vehicle * Next() const
Get the next vehicle of this vehicle.
Definition: vehicle_base.h:582
bool HandleRefit(CargoID refit_cargo)
Handle refit orders by updating capacities and refit_capacities.
Definition: refresh.cpp:92
int32 Ticks
The type to store ticks in.
Definition: date_type.h:18
There was a conditional jump. Try to use the given next order when looking for a new one...
Definition: refresh.h:34
Declaration of link graph classes used for cargo distribution.
Order * GetOrder(int index) const
Returns order &#39;index&#39; of a vehicle or NULL when it doesn&#39;t exists.
Definition: vehicle_base.h:859
static bool HasBit(const T x, const uint8 y)
Checks if a bit in a value is set.
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:22
Use unrestricted link.
union Vehicle::@46 orders
The orders currently assigned to the vehicle.
Simulated cargo type and capacity for prediction of future links.
Definition: refresh.h:44
static Station * Get(size_t index)
Gets station with given index.
VehicleOrderID cur_implicit_order_index
The index to the current implicit order.
Definition: base_consist.h:30
Station data structure.
Definition: station_base.h:446
VehicleOrderID GetNumOrders() const
Get number of orders in the order list.
Definition: order_base.h:312
CargoID GetRefitCargo() const
Get the cargo to to refit to.
Definition: order_base.h:124
Consist was refit since the last stop where it could interact with cargo.
Definition: refresh.h:36
Utility to refresh links a consist will visit.
Definition: refresh.h:24
static Station * GetIfValid(size_t index)
Returns station if the index is a valid index for this station type.