summaryrefslogtreecommitdiff
path: root/src/linkgraph
diff options
context:
space:
mode:
Diffstat (limited to 'src/linkgraph')
-rw-r--r--src/linkgraph/refresh.cpp249
-rw-r--r--src/linkgraph/refresh.h68
2 files changed, 317 insertions, 0 deletions
diff --git a/src/linkgraph/refresh.cpp b/src/linkgraph/refresh.cpp
new file mode 100644
index 000000000..2d22a30cd
--- /dev/null
+++ b/src/linkgraph/refresh.cpp
@@ -0,0 +1,249 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * 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.
+ * 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.
+ * 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/>.
+ */
+
+/** @file refresh.h Definition of link refreshing utility. */
+
+#include "../stdafx.h"
+#include "../core/bitmath_func.hpp"
+#include "../station_func.h"
+#include "../engine_base.h"
+#include "../vehicle_func.h"
+#include "refresh.h"
+#include "linkgraph.h"
+
+/**
+ * Refresh all links the given vehicle will visit.
+ * @param v Vehicle to refresh links for.
+ */
+/* static */ void LinkRefresher::Run(Vehicle *v)
+{
+ /* If there are no orders we can't predict anything.*/
+ if (v->orders.list == NULL) return;
+
+ LinkRefresher refresher(v);
+
+ if (refresher.first == NULL) return;
+ refresher.RefreshLinks(refresher.first, refresher.first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0);
+}
+
+/**
+ * Constructor for link refreshing algorithm.
+ * @param vehicle Vehicle to refresh links for.
+ */
+LinkRefresher::LinkRefresher(Vehicle *vehicle) : vehicle(vehicle), hops(0)
+{
+ /* Assemble list of capacities and set last loading stations to 0. */
+ for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
+ this->refit_capacities.push_back(RefitDesc(v->cargo_type, v->cargo_cap, v->refit_cap));
+ if (v->refit_cap > 0) this->capacities[v->cargo_type] += v->refit_cap;
+ }
+
+ this->first = this->vehicle->GetOrder(this->vehicle->cur_implicit_order_index);
+
+ /* Make sure the first order is a useful order. */
+ this->first = this->vehicle->orders.list->GetNextDecisionNode(this->first, 0);
+}
+
+/**
+ * Handle refit orders by updating capacities and refit_capacities.
+ * @param next Order to be processed.
+ */
+void LinkRefresher::HandleRefit(const Order *next)
+{
+ CargoID new_cid = next->GetRefitCargo();
+ RefitList::iterator refit_it = this->refit_capacities.begin();
+ for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) {
+ const Engine *e = Engine::Get(v->engine_type);
+ if (!HasBit(e->info.refit_mask, new_cid)) {
+ ++refit_it;
+ continue;
+ }
+
+ /* Back up the vehicle's cargo type */
+ CargoID temp_cid = v->cargo_type;
+ byte temp_subtype = v->cargo_subtype;
+ v->cargo_type = new_cid;
+ v->cargo_subtype = GetBestFittingSubType(v, v, new_cid);
+
+ uint16 mail_capacity = 0;
+ uint amount = e->DetermineCapacity(v, &mail_capacity);
+
+ /* Restore the original cargo type */
+ v->cargo_type = temp_cid;
+ v->cargo_subtype = temp_subtype;
+
+ /* Skip on next refit. */
+ if (new_cid != refit_it->cargo && refit_it->remaining > 0) {
+ this->capacities[refit_it->cargo] -= refit_it->remaining;
+ refit_it->remaining = 0;
+ } else if (amount < refit_it->remaining) {
+ this->capacities[refit_it->cargo] -= refit_it->remaining - amount;
+ refit_it->remaining = amount;
+ }
+ refit_it->capacity = amount;
+ refit_it->cargo = new_cid;
+
+ ++refit_it;
+
+ /* Special case for aircraft with mail. */
+ if (v->type == VEH_AIRCRAFT) {
+ if (mail_capacity < refit_it->remaining) {
+ this->capacities[refit_it->cargo] -= refit_it->remaining - mail_capacity;
+ refit_it->remaining = mail_capacity;
+ }
+ refit_it->capacity = mail_capacity;
+ break; // aircraft have only one vehicle
+ }
+ }
+}
+
+/**
+ * Restore capacities and refit_capacities as vehicle might have been able to load now.
+ */
+void LinkRefresher::ResetRefit()
+{
+ for (RefitList::iterator it(this->refit_capacities.begin()); it != this->refit_capacities.end(); ++it) {
+ if (it->remaining == it->capacity) continue;
+ this->capacities[it->cargo] += it->capacity - it->remaining;
+ it->remaining = it->capacity;
+ }
+}
+
+/**
+ * Predict the next order the vehicle will execute and resolve conditionals by
+ * recursion and return next non-conditional order in list.
+ * @param cur Current order being evaluated.
+ * @param next Next order to be evaluated.
+ * @param flags RefreshFlags to give hints about the previous link and state carried over from that.
+ * @return new next Order.
+ */
+const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next, uint8 flags)
+{
+ do {
+ if (HasBit(flags, USE_NEXT)) {
+ /* First incrementation has to be skipped if a "real" next hop,
+ * different from cur, was given. */
+ ClrBit(flags, USE_NEXT);
+ } else {
+ const Order *skip_to = NULL;
+ if (next->IsType(OT_CONDITIONAL)) {
+ skip_to = this->vehicle->orders.list->GetNextDecisionNode(
+ this->vehicle->orders.list->GetOrderAt(next->GetConditionSkipToOrder()),
+ this->hops / 2);
+ }
+
+ /* Reassign next with the following stop. This can be a station or a
+ * depot. Allow the order list to be walked twice so that we can
+ * reassign "first" below without afterwards terminating early here. */
+ next = this->vehicle->orders.list->GetNextDecisionNode(
+ this->vehicle->orders.list->GetNext(next), ++this->hops / 2);
+
+ if (skip_to != NULL) {
+ /* Make copies of capacity tracking lists. There is potential
+ * for optimization here. If the vehicle never refits we don't
+ * need to copy anything. Also, if we've seen the branched link
+ * before we don't need to branch at all. */
+ ++this->hops;
+ LinkRefresher branch(*this);
+ branch.RefreshLinks(cur, skip_to, flags | (cur != skip_to ? 1 << USE_NEXT : 0));
+ this->hops = branch.hops;
+ }
+ }
+ } while (next != NULL && next->IsType(OT_CONDITIONAL));
+ return next;
+}
+
+/**
+ * Refresh link stats for the given pair of orders.
+ * @param cur Last stop where the consist could interact with cargo.
+ * @param next Next order to be processed.
+ */
+void LinkRefresher::RefreshStats(const Order *cur, const Order *next)
+{
+ StationID next_station = next->GetDestination();
+ Station *st = Station::GetIfValid(cur->GetDestination());
+ if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {
+ for (CapacitiesMap::const_iterator i = this->capacities.begin(); i != this->capacities.end(); ++i) {
+ /* Refresh the link and give it a minimum capacity. */
+ if (i->second == 0) continue;
+ /* A link is at least partly restricted if a
+ * vehicle can't load at its source. */
+ IncreaseStats(st, i->first, next_station, i->second,
+ (cur->GetLoadType() & OLFB_NO_LOAD) == 0 ? LinkGraph::REFRESH_UNRESTRICTED : LinkGraph::REFRESH_RESTRICTED);
+ }
+ }
+}
+
+/**
+ * Iterate over orders starting at \a cur and \a next and refresh links
+ * associated with them. \a cur and \a next can be equal. If they're not they
+ * must be "neigbours" in their order list, which means \a next must be directly
+ * reachable from \a cur without passing any further OT_GOTO_STATION or
+ * OT_IMPLICIT orders in between.
+ * @param cur Current order being evaluated.
+ * @param next Next order to be checked.
+ * @param flags RefreshFlags to give hints about the previous link and state carried over from that.
+ */
+void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flags)
+{
+ while (next != NULL) {
+
+ /* If the refit cargo is CT_AUTO_REFIT, we're optimistic and assume the
+ * cargo will stay the same. The point of this method is to avoid
+ * deadlocks due to vehicles waiting for cargo that isn't being routed,
+ * yet. That situation will not occur if the vehicle is actually
+ * carrying a different cargo in the end. */
+ if ((next->IsType(OT_GOTO_DEPOT) || next->IsType(OT_GOTO_STATION)) &&
+ next->IsRefit() && !next->IsAutoRefit()) {
+ SetBit(flags, WAS_REFIT);
+ this->HandleRefit(next);
+ }
+
+ /* Only reset the refit capacities if the "previous" next is a station,
+ * meaning that either the vehicle was refit at the previous station or
+ * it wasn't at all refit during the current hop. */
+ if (HasBit(flags, WAS_REFIT) && (next->IsType(OT_GOTO_STATION) || next->IsType(OT_IMPLICIT))) {
+ SetBit(flags, RESET_REFIT);
+ } else {
+ ClrBit(flags, RESET_REFIT);
+ }
+
+ next = this->PredictNextOrder(cur, next, flags);
+ if (next == NULL) break;
+
+ /* Skip resetting and link refreshing if next order won't do anything with cargo. */
+ if (!next->IsType(OT_GOTO_STATION) && !next->IsType(OT_IMPLICIT)) continue;
+
+ if (HasBit(flags, RESET_REFIT)) {
+ this->ResetRefit();
+ ClrBit(flags, RESET_REFIT);
+ ClrBit(flags, WAS_REFIT);
+ }
+
+ if (cur->IsType(OT_GOTO_STATION) || cur->IsType(OT_IMPLICIT)) {
+ if (cur->CanLeaveWithCargo(HasBit(flags, HAS_CARGO))) {
+ SetBit(flags, HAS_CARGO);
+ this->RefreshStats(cur, next);
+ } else {
+ ClrBit(flags, HAS_CARGO);
+ }
+ }
+
+ /* "cur" is only assigned here if the stop is a station so that
+ * whenever stats are to be increased two stations can be found.
+ * However, "first" can be a depot stop. If that is the case
+ * reassign it to make sure we end up with a station for the last
+ * link. */
+ cur = next;
+ if (cur == this->first) break;
+ if (!this->first->IsType(OT_GOTO_STATION) && !this->first->IsType(OT_IMPLICIT)) {
+ this->first = cur;
+ }
+ }
+}
diff --git a/src/linkgraph/refresh.h b/src/linkgraph/refresh.h
new file mode 100644
index 000000000..8b59cd4ef
--- /dev/null
+++ b/src/linkgraph/refresh.h
@@ -0,0 +1,68 @@
+/* $Id$ */
+
+/*
+ * This file is part of OpenTTD.
+ * 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.
+ * 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.
+ * 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/>.
+ */
+
+/** @file refresh.h Declaration of link refreshing utility. */
+
+#ifndef REFRESH_H
+#define REFRESH_H
+
+#include "../cargo_type.h"
+#include "../vehicle_base.h"
+#include <list>
+#include <map>
+
+/**
+ * Utility to refresh links a consist will visit.
+ */
+class LinkRefresher {
+public:
+ static void Run(Vehicle *v);
+
+protected:
+ /**
+ * Various flags about properties of the last examined link that might have
+ * an influence on the next one.
+ */
+ enum RefreshFlags {
+ USE_NEXT, ///< There has been a previous link. Try to use the given next order.
+ HAS_CARGO, ///< Consist could leave the last stop where it could interact with cargo carrying cargo (i.e. not an "unload all" + "no loading" order).
+ WAS_REFIT, ///< Consist was refit since the last stop where it could interact with cargo.
+ RESET_REFIT ///< Consist had a chance to load since the last refit and the refit capacities can be reset.
+ };
+
+ /**
+ * Simulated cargo type and capacity for prediction of future links.
+ */
+ struct RefitDesc {
+ CargoID cargo; ///< Cargo type the vehicle will be carrying.
+ uint16 capacity; ///< Capacity the vehicle will have.
+ uint16 remaining; ///< Capacity remaining from before the previous refit.
+ RefitDesc(CargoID cargo, uint16 capacity, uint16 remaining) :
+ cargo(cargo), capacity(capacity), remaining(remaining) {}
+ };
+
+ typedef std::list<RefitDesc> RefitList;
+ typedef std::map<CargoID, uint> CapacitiesMap;
+
+ Vehicle *vehicle; ///< Vehicle for which the links should be refreshed.
+ const Order *first; ///< Order to be checked first. If this is encountered again the refreshing is considered finished.
+ CapacitiesMap capacities; ///< Current added capacities per cargo ID in the consist.
+ RefitList refit_capacities; ///< Current state of capacity remaining from previous refits versus overall capacity per vehicle in the consist.
+ uint hops; ///< Number of hops already used up. If more than two times the number of orders in the list have been checked refreshing is stopped.
+ LinkRefresher(Vehicle *v);
+
+ void HandleRefit(const Order *next);
+ void ResetRefit();
+ void RefreshStats(const Order *cur, const Order *next);
+ const Order *PredictNextOrder(const Order *cur, const Order *next, uint8 flags);
+
+ void RefreshLinks(const Order *cur, const Order *next, uint8 flags);
+};
+
+#endif // REFRESH_H