diff options
Diffstat (limited to 'src/linkgraph')
| -rw-r--r-- | src/linkgraph/refresh.cpp | 249 | ||||
| -rw-r--r-- | src/linkgraph/refresh.h | 68 |
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 |