From a9f6a1eeb77b78a00bd6e597b1fd352a2a5fe7ea Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Tue, 22 Oct 2013 18:46:20 +0000 Subject: (svn r25905) -Codechange: A more robust way of detecting loops during order prediction. --- src/linkgraph/refresh.cpp | 76 ++++++++++++++++++++++++++++------------------- src/linkgraph/refresh.h | 27 +++++++++++++++-- 2 files changed, 70 insertions(+), 33 deletions(-) (limited to 'src/linkgraph') diff --git a/src/linkgraph/refresh.cpp b/src/linkgraph/refresh.cpp index 2d22a30cd..f8d98fe16 100644 --- a/src/linkgraph/refresh.cpp +++ b/src/linkgraph/refresh.cpp @@ -26,28 +26,48 @@ /* If there are no orders we can't predict anything.*/ if (v->orders.list == NULL) return; - LinkRefresher refresher(v); + /* Make sure the first order is a useful order. */ + const Order *first = v->orders.list->GetNextDecisionNode(v->GetOrder(v->cur_implicit_order_index), 0); + if (first == NULL) return; + + HopSet seen_hops; + LinkRefresher refresher(v, &seen_hops); - if (refresher.first == NULL) return; - refresher.RefreshLinks(refresher.first, refresher.first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0); + refresher.RefreshLinks(first, first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0); +} + +/** + * Comparison operator to allow hops to be used in a std::set. + * @param other Other hop to be compared with. + * @return If this hop is "smaller" than the other (defined by from, to and cargo in this order). + */ +bool LinkRefresher::Hop::operator<(const Hop &other) const +{ + if (this->from < other.from) { + return true; + } else if (this->from > other.from) { + return false; + } + if (this->to < other.to) { + return true; + } else if (this->to > other.to) { + return false; + } + return this->cargo < other.cargo; } /** * Constructor for link refreshing algorithm. * @param vehicle Vehicle to refresh links for. */ -LinkRefresher::LinkRefresher(Vehicle *vehicle) : vehicle(vehicle), hops(0) +LinkRefresher::LinkRefresher(Vehicle *vehicle, HopSet *seen_hops) : + vehicle(vehicle), seen_hops(seen_hops), cargo(CT_INVALID) { /* 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); } /** @@ -56,11 +76,11 @@ LinkRefresher::LinkRefresher(Vehicle *vehicle) : vehicle(vehicle), hops(0) */ void LinkRefresher::HandleRefit(const Order *next) { - CargoID new_cid = next->GetRefitCargo(); + this->cargo = 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)) { + if (!HasBit(e->info.refit_mask, this->cargo)) { ++refit_it; continue; } @@ -68,8 +88,8 @@ void LinkRefresher::HandleRefit(const Order *next) /* 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); + v->cargo_type = this->cargo; + v->cargo_subtype = GetBestFittingSubType(v, v, this->cargo); uint16 mail_capacity = 0; uint amount = e->DetermineCapacity(v, &mail_capacity); @@ -79,7 +99,7 @@ void LinkRefresher::HandleRefit(const Order *next) v->cargo_subtype = temp_subtype; /* Skip on next refit. */ - if (new_cid != refit_it->cargo && refit_it->remaining > 0) { + if (this->cargo != 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) { @@ -87,7 +107,7 @@ void LinkRefresher::HandleRefit(const Order *next) refit_it->remaining = amount; } refit_it->capacity = amount; - refit_it->cargo = new_cid; + refit_it->cargo = this->cargo; ++refit_it; @@ -125,6 +145,7 @@ void LinkRefresher::ResetRefit() */ const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next, uint8 flags) { + int num_hops = 0; // Count hops to catch infinite loops without station or implicit orders. do { if (HasBit(flags, USE_NEXT)) { /* First incrementation has to be skipped if a "real" next hop, @@ -134,25 +155,21 @@ const Order *LinkRefresher::PredictNextOrder(const Order *cur, const Order *next 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); + this->vehicle->orders.list->GetOrderAt(next->GetConditionSkipToOrder()), num_hops++); } /* 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. */ + * depot.*/ next = this->vehicle->orders.list->GetNextDecisionNode( - this->vehicle->orders.list->GetNext(next), ++this->hops / 2); + this->vehicle->orders.list->GetNext(next), num_hops++); 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)); @@ -216,6 +233,12 @@ void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flag next = this->PredictNextOrder(cur, next, flags); if (next == NULL) break; + Hop hop(cur->index, next->index, this->cargo); + if (this->seen_hops->find(hop) != this->seen_hops->end()) { + break; + } else { + this->seen_hops->insert(hop); + } /* 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; @@ -236,14 +259,7 @@ void LinkRefresher::RefreshLinks(const Order *cur, const Order *next, uint8 flag } /* "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. */ + * whenever stats are to be increased two stations can be found. */ 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 index 8b59cd4ef..1551d33fa 100644 --- a/src/linkgraph/refresh.h +++ b/src/linkgraph/refresh.h @@ -16,6 +16,7 @@ #include "../vehicle_base.h" #include #include +#include /** * Utility to refresh links a consist will visit. @@ -47,15 +48,35 @@ protected: cargo(cargo), capacity(capacity), remaining(remaining) {} }; + /** + * A hop the refresh algorithm might evaluate. If the same hop is seen again + * the evaluation is stopped. This of course is a fairly simple heuristic. + * Sequences of refit orders can produce vehicles with all kinds of + * different cargoes and remembering only one can lead to early termination + * of the algorithm. However, as the order language is Turing complete, we + * are facing the halting problem here. At some point we have to draw the + * line. + */ + struct Hop { + OrderID from; ///< Last order where vehicle could interact with cargo or absolute first order. + OrderID to; ///< Next order to be processed. + CargoID cargo; ///< Cargo the consist is probably carrying or CT_INVALID if unknown. + Hop() {NOT_REACHED();} + Hop(OrderID from, OrderID to, CargoID cargo) : from(from), to(to), cargo(cargo) {} + bool operator<(const Hop &other) const; + }; + typedef std::list RefitList; typedef std::map CapacitiesMap; + typedef std::set HopSet; 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); + HopSet *seen_hops; ///< Hops already seen. If the same hop is seen twice we stop the algorithm. This is shared between all Refreshers of the same run. + CargoID cargo; ///< Cargo given in last refit order. + + LinkRefresher(Vehicle *v, HopSet *seen_hops); void HandleRefit(const Order *next); void ResetRefit(); -- cgit v1.2.3-54-g00ecf