From 11d98f043e96b7b7d9a2f97b5a7297b641f97c26 Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Thu, 1 May 2014 14:50:52 +0000 Subject: (svn r26549) -Change: better estimation for link capacities during full load --- src/economy.cpp | 2 +- src/linkgraph/linkgraph.cpp | 68 ++++++++++++++++++------------------------ src/linkgraph/linkgraph.h | 22 ++------------ src/linkgraph/linkgraph_type.h | 22 ++++++++++++++ src/linkgraph/refresh.cpp | 41 ++++++++++++++++++++----- src/linkgraph/refresh.h | 5 ++-- src/station_cmd.cpp | 9 +++--- src/station_func.h | 3 +- 8 files changed, 98 insertions(+), 74 deletions(-) diff --git a/src/economy.cpp b/src/economy.cpp index 1c51f860c..321c738f1 100644 --- a/src/economy.cpp +++ b/src/economy.cpp @@ -1721,7 +1721,7 @@ static void LoadUnloadVehicle(Vehicle *front) * along them. Otherwise the vehicle could wait for cargo * indefinitely if it hasn't visited the other links yet, or if the * links die while it's loading. */ - if (!finished_loading) LinkRefresher::Run(front); + if (!finished_loading) LinkRefresher::Run(front, true, true); } SB(front->vehicle_flags, VF_LOADING_FINISHED, 1, finished_loading); diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp index 461b3b47e..72d3e42fc 100644 --- a/src/linkgraph/linkgraph.cpp +++ b/src/linkgraph/linkgraph.cpp @@ -197,47 +197,41 @@ NodeID LinkGraph::AddNode(const Station *st) } /** - * Fill an edge with values from a link. If usage < capacity set the usage, - * otherwise set the restricted or unrestricted update timestamp. + * Fill an edge with values from a link. Set the restricted or unrestricted + * update timestamp according to the given update mode. * @param to Destination node of the link. * @param capacity Capacity of the link. - * @param usage Usage to be added or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED. + * @param usage Usage to be added. + * @param mode Update mode to be used. */ -void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage) +void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode) { assert(this->index != to); BaseEdge &edge = this->edges[to]; BaseEdge &first = this->edges[this->index]; edge.capacity = capacity; + edge.usage = usage; edge.next_edge = first.next_edge; first.next_edge = to; - switch (usage) { - case REFRESH_UNRESTRICTED: - edge.last_unrestricted_update = _date; - break; - case REFRESH_RESTRICTED: - edge.last_restricted_update = _date; - break; - default: - edge.usage = usage; - break; - } + if (mode & EUM_UNRESTRICTED) edge.last_unrestricted_update = _date; + if (mode & EUM_RESTRICTED) edge.last_restricted_update = _date; } /** * Creates an edge if none exists yet or updates an existing edge. * @param to Target node. * @param capacity Capacity of the link. - * @param usage Usage to be added or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED. + * @param usage Usage to be added. + * @param mode Update mode to be used. */ -void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage) +void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode) { assert(capacity > 0); - assert(usage <= capacity || usage == REFRESH_RESTRICTED || usage == REFRESH_UNRESTRICTED); + assert(usage <= capacity); if (this->edges[to].capacity == 0) { - this->AddEdge(to, capacity, usage); + this->AddEdge(to, capacity, usage, mode); } else { - (*this)[to].Update(capacity, usage); + (*this)[to].Update(capacity, usage, mode); } } @@ -270,34 +264,30 @@ void LinkGraph::Node::RemoveEdge(NodeID to) } /** - * Create a new edge or update an existing one. If usage is REFRESH_UNRESTRICTED - * or REFRESH_RESTRICTED refresh the edge to have at least the given capacity - * and also update the respective update timestamp, otherwise add the capacity. + * Update an edge. If mode contains UM_REFRESH refresh the edge to have at + * least the given capacity and usage, otherwise add the capacity and usage. + * In any case set the respective update timestamp(s), according to the given + * mode. * @param from Start node of the edge. * @param to End node of the edge. * @param capacity Capacity to be added/updated. - * @param usage Usage to be added or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED. + * @param usage Usage to be added. + * @param mode Update mode to be applied. */ -void LinkGraph::Edge::Update(uint capacity, uint usage) +void LinkGraph::Edge::Update(uint capacity, uint usage, EdgeUpdateMode mode) { assert(this->edge.capacity > 0); - if (usage > capacity) { - this->edge.capacity = max(this->edge.capacity, capacity); - switch (usage) { - case REFRESH_UNRESTRICTED: - this->edge.last_unrestricted_update = _date; - break; - case REFRESH_RESTRICTED: - this->edge.last_restricted_update = _date; - break; - default: - NOT_REACHED(); - break; - } - } else { + assert(capacity >= usage); + + if (mode & EUM_INCREASE) { this->edge.capacity += capacity; this->edge.usage += usage; + } else if (mode & EUM_REFRESH) { + this->edge.capacity = max(this->edge.capacity, capacity); + this->edge.usage = max(this->edge.usage, usage); } + if (mode & EUM_UNRESTRICTED) this->edge.last_unrestricted_update = _date; + if (mode & EUM_RESTRICTED) this->edge.last_restricted_update = _date; } /** diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h index 4306ad2b3..7aaa1901d 100644 --- a/src/linkgraph/linkgraph.h +++ b/src/linkgraph/linkgraph.h @@ -40,22 +40,6 @@ extern LinkGraphPool _link_graph_pool; class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> { public: - /** - * Special modes for updating links. 'Restricted' means that vehicles with - * 'no loading' orders are serving the link. If a link is only served by - * such vehicles it's 'fully restricted'. This means the link can be used - * by cargo arriving in such vehicles, but not by cargo generated or - * transferring at the source station of the link. In order to find out - * about this condition we keep two update timestamps in each link, one for - * the restricted and one for the unrestricted part of it. If either one - * times out while the other is still valid the link becomes fully - * restricted or fully unrestricted, respectively. - */ - enum UpdateMode { - REFRESH_RESTRICTED = UINT_MAX - 1, ///< Refresh restricted link. - REFRESH_UNRESTRICTED = UINT_MAX ///< Refresh unrestricted link. - }; - /** * Node of the link graph. contains all relevant information from the associated * station. It's copied so that the link graph job can work on its own data set @@ -313,7 +297,7 @@ public: * @param edge Edge to be wrapped. */ Edge(BaseEdge &edge) : EdgeWrapper(edge) {} - void Update(uint capacity, uint usage); + void Update(uint capacity, uint usage, EdgeUpdateMode mode); void Restrict() { this->edge.last_unrestricted_update = INVALID_DATE; } void Release() { this->edge.last_restricted_update = INVALID_DATE; } }; @@ -437,8 +421,8 @@ public: this->node.demand = demand; } - void AddEdge(NodeID to, uint capacity, uint usage = 0); - void UpdateEdge(NodeID to, uint capacity, uint usage = 0); + void AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode); + void UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode); void RemoveEdge(NodeID to); }; diff --git a/src/linkgraph/linkgraph_type.h b/src/linkgraph/linkgraph_type.h index 330461841..6a3239b08 100644 --- a/src/linkgraph/linkgraph_type.h +++ b/src/linkgraph/linkgraph_type.h @@ -39,4 +39,26 @@ enum DistributionType { template <> struct EnumPropsT : MakeEnumPropsT {}; typedef TinyEnumT DistributionTypeByte; // typedefing-enumification of DistributionType +/** + * Special modes for updating links. 'Restricted' means that vehicles with + * 'no loading' orders are serving the link. If a link is only served by + * such vehicles it's 'fully restricted'. This means the link can be used + * by cargo arriving in such vehicles, but not by cargo generated or + * transferring at the source station of the link. In order to find out + * about this condition we keep two update timestamps in each link, one for + * the restricted and one for the unrestricted part of it. If either one + * times out while the other is still valid the link becomes fully + * restricted or fully unrestricted, respectively. + * Refreshing a link makes just sure a minimum capacity is kept. Increasing + * actually adds the given capacity. + */ +enum EdgeUpdateMode { + EUM_INCREASE = 1, ///< Increase capacity. + EUM_REFRESH = 1 << 1, ///< Refresh capacity. + EUM_RESTRICTED = 1 << 2, ///< Use restricted link. + EUM_UNRESTRICTED = 1 << 3, ///< Use unrestricted link. +}; + +DECLARE_ENUM_AS_BIT_SET(EdgeUpdateMode) + #endif /* LINKGRAPH_TYPE_H */ diff --git a/src/linkgraph/refresh.cpp b/src/linkgraph/refresh.cpp index 8c45cad8b..d2a3bdda1 100644 --- a/src/linkgraph/refresh.cpp +++ b/src/linkgraph/refresh.cpp @@ -23,8 +23,9 @@ * Refresh all links the given vehicle will visit. * @param v Vehicle to refresh links for. * @param allow_merge If the refresher is allowed to merge or extend link graphs. + * @param is_full_loading If the vehicle is full loading. */ -/* static */ void LinkRefresher::Run(Vehicle *v, bool allow_merge) +/* static */ void LinkRefresher::Run(Vehicle *v, bool allow_merge, bool is_full_loading) { /* If there are no orders we can't predict anything.*/ if (v->orders.list == NULL) return; @@ -34,7 +35,7 @@ if (first == NULL) return; HopSet seen_hops; - LinkRefresher refresher(v, &seen_hops, allow_merge); + LinkRefresher refresher(v, &seen_hops, allow_merge, is_full_loading); refresher.RefreshLinks(first, first, v->last_loading_station != INVALID_STATION ? 1 << HAS_CARGO : 0); } @@ -65,9 +66,11 @@ bool LinkRefresher::Hop::operator<(const Hop &other) const * @param seen_hops Set of hops already seen. This is shared between this * refresher and all its children. * @param allow_merge If the refresher is allowed to merge or extend link graphs. + * @param is_full_loading If the vehicle is full loading. */ -LinkRefresher::LinkRefresher(Vehicle *vehicle, HopSet *seen_hops, bool allow_merge) : - vehicle(vehicle), seen_hops(seen_hops), cargo(CT_INVALID), allow_merge(allow_merge) +LinkRefresher::LinkRefresher(Vehicle *vehicle, HopSet *seen_hops, bool allow_merge, bool is_full_loading) : + vehicle(vehicle), seen_hops(seen_hops), cargo(CT_INVALID), allow_merge(allow_merge), + is_full_loading(is_full_loading) { /* Assemble list of capacities and set last loading stations to 0. */ for (Vehicle *v = this->vehicle; v != NULL; v = v->Next()) { @@ -205,10 +208,32 @@ void LinkRefresher::RefreshStats(const Order *cur, const Order *next) continue; } - /* A link is at least partly restricted if a - * vehicle can't load at its source. */ - IncreaseStats(st, c, next_station, i->second, - (cur->GetLoadType() & OLFB_NO_LOAD) == 0 ? LinkGraph::REFRESH_UNRESTRICTED : LinkGraph::REFRESH_RESTRICTED); + /* A link is at least partly restricted if a vehicle can't load at its source. */ + EdgeUpdateMode restricted_mode = (cur->GetLoadType() & OLFB_NO_LOAD) == 0 ? + EUM_UNRESTRICTED : EUM_RESTRICTED; + + /* If the vehicle is currently full loading, increase the capacities at the station + * where it is loading by an estimate of what it would have transported if it wasn't + * loading. Don't do that if the vehicle has been waiting for longer than the entire + * order list is supposed to take, though. If that is the case the total duration is + * probably far off and we'd greatly overestimate the capacity by increasing.*/ + if (this->is_full_loading && this->vehicle->orders.list != NULL && + st->index == vehicle->last_station_visited && + this->vehicle->orders.list->GetTotalDuration() > + (Ticks)this->vehicle->current_order_time) { + uint effective_capacity = i->second * this->vehicle->load_unload_ticks; + if (effective_capacity > (uint)this->vehicle->orders.list->GetTotalDuration()) { + IncreaseStats(st, c, next_station, effective_capacity / + this->vehicle->orders.list->GetTotalDuration(), 0, + EUM_INCREASE | restricted_mode); + } else if (RandomRange(this->vehicle->orders.list->GetTotalDuration()) < effective_capacity) { + IncreaseStats(st, c, next_station, 1, 0, EUM_INCREASE | restricted_mode); + } else { + IncreaseStats(st, c, next_station, i->second, 0, EUM_REFRESH | restricted_mode); + } + } else { + IncreaseStats(st, c, next_station, i->second, 0, EUM_REFRESH | restricted_mode); + } } } } diff --git a/src/linkgraph/refresh.h b/src/linkgraph/refresh.h index 6f3f8f9b6..eac34266d 100644 --- a/src/linkgraph/refresh.h +++ b/src/linkgraph/refresh.h @@ -23,7 +23,7 @@ */ class LinkRefresher { public: - static void Run(Vehicle *v, bool allow_merge = true); + static void Run(Vehicle *v, bool allow_merge = true, bool is_full_loading = false); protected: /** @@ -88,8 +88,9 @@ protected: 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. bool allow_merge; ///< If the refresher is allowed to merge or extend link graphs. + bool is_full_loading; ///< If the vehicle is full loading. - LinkRefresher(Vehicle *v, HopSet *seen_hops, bool allow_merge); + LinkRefresher(Vehicle *v, HopSet *seen_hops, bool allow_merge, bool is_full_loading); void HandleRefit(const Order *next); void ResetRefit(); diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp index 56c79a1ad..8546c4be6 100644 --- a/src/station_cmd.cpp +++ b/src/station_cmd.cpp @@ -3505,9 +3505,10 @@ void DeleteStaleLinks(Station *from) * @param cargo Cargo to increase stat for. * @param next_station_id Station the consist will be travelling to next. * @param capacity Capacity to add to link stat. - * @param usage Usage to add to link stat. If UINT_MAX refresh the link instead of increasing. + * @param usage Usage to add to link stat. + * @param mode Update mode to be applied. */ -void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage) +void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage, EdgeUpdateMode mode) { GoodsEntry &ge1 = st->goods[cargo]; Station *st2 = Station::Get(next_station_id); @@ -3549,7 +3550,7 @@ void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint c } } if (lg != NULL) { - (*lg)[ge1.node].UpdateEdge(ge2.node, capacity, usage); + (*lg)[ge1.node].UpdateEdge(ge2.node, capacity, usage, mode); } } @@ -3570,7 +3571,7 @@ void IncreaseStats(Station *st, const Vehicle *front, StationID next_station_id) * As usage is not such an important figure anyway we just * ignore the additional cargo then.*/ IncreaseStats(st, v->cargo_type, next_station_id, v->refit_cap, - min(v->refit_cap, v->cargo.StoredCount())); + min(v->refit_cap, v->cargo.StoredCount()), EUM_INCREASE); } } } diff --git a/src/station_func.h b/src/station_func.h index 39b8f5bb3..f33dbd21f 100644 --- a/src/station_func.h +++ b/src/station_func.h @@ -18,6 +18,7 @@ #include "vehicle_type.h" #include "economy_func.h" #include "rail.h" +#include "linkgraph/linkgraph_type.h" void ModifyStationRatingAround(TileIndex tile, Owner owner, int amount, uint radius); @@ -49,7 +50,7 @@ void UpdateAirportsNoise(); bool SplitGroundSpriteForOverlay(const TileInfo *ti, SpriteID *ground, RailTrackOffset *overlay_offset); void IncreaseStats(Station *st, const Vehicle *v, StationID next_station_id); -void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage); +void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage, EdgeUpdateMode mode); void RerouteCargo(Station *st, CargoID c, StationID avoid, StationID avoid2); /** -- cgit v1.2.3-70-g09d2