From 977604ef08212cc93653eaa8187ab64ebe72e7d2 Mon Sep 17 00:00:00 2001 From: Nicolas Chappe <74881848+nchappe@users.noreply.github.com> Date: Sat, 24 Jul 2021 11:07:10 +0200 Subject: Feature: [Linkgraph] Prioritize faster routes for passengers, mail and express cargo Passengers usually prefer fast paths to short paths. Average travel times of links are updated in real-time for use in Dijkstra's algorithm, and newer travel times weigh more, just like capacities. --- src/linkgraph/linkgraph.cpp | 36 +++++++++++++++++++++++++++++------- src/linkgraph/linkgraph.h | 13 ++++++++++--- src/linkgraph/mcf.cpp | 15 ++++++++++++--- src/linkgraph/refresh.cpp | 14 ++++++++++---- src/saveload/linkgraph_sl.cpp | 1 + src/saveload/saveload.h | 1 + src/station_cmd.cpp | 8 ++++---- src/station_func.h | 4 ++-- src/vehicle.cpp | 3 ++- 9 files changed, 71 insertions(+), 24 deletions(-) (limited to 'src') diff --git a/src/linkgraph/linkgraph.cpp b/src/linkgraph/linkgraph.cpp index 93af907fc..4c300b0d5 100644 --- a/src/linkgraph/linkgraph.cpp +++ b/src/linkgraph/linkgraph.cpp @@ -39,6 +39,7 @@ inline void LinkGraph::BaseEdge::Init() { this->capacity = 0; this->usage = 0; + this->travel_time_sum = 0; this->last_unrestricted_update = INVALID_DATE; this->last_restricted_update = INVALID_DATE; this->next_edge = INVALID_NODE; @@ -73,6 +74,7 @@ void LinkGraph::Compress() if (edge.capacity > 0) { edge.capacity = std::max(1U, edge.capacity / 2); edge.usage /= 2; + edge.travel_time_sum = std::max(1ULL, edge.travel_time_sum / 2); } } } @@ -100,9 +102,11 @@ void LinkGraph::Merge(LinkGraph *other) backward = other->edges[node2][node1]; forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age); forward.usage = LinkGraph::Scale(forward.usage, age, other_age); + forward.travel_time_sum = LinkGraph::Scale(forward.travel_time_sum, age, other_age); if (forward.next_edge != INVALID_NODE) forward.next_edge += first; backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age); backward.usage = LinkGraph::Scale(backward.usage, age, other_age); + backward.travel_time_sum = LinkGraph::Scale(backward.travel_time_sum, age, other_age); if (backward.next_edge != INVALID_NODE) backward.next_edge += first; } BaseEdge &new_start = this->edges[new_node][new_node]; @@ -188,13 +192,14 @@ NodeID LinkGraph::AddNode(const Station *st) * @param usage Usage to be added. * @param mode Update mode to be used. */ -void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode) +void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode) { assert(this->index != to); BaseEdge &edge = this->edges[to]; BaseEdge &first = this->edges[this->index]; edge.capacity = capacity; edge.usage = usage; + edge.travel_time_sum = travel_time * capacity; edge.next_edge = first.next_edge; first.next_edge = to; if (mode & EUM_UNRESTRICTED) edge.last_unrestricted_update = _date; @@ -208,14 +213,14 @@ void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMo * @param usage Usage to be added. * @param mode Update mode to be used. */ -void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode) +void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode) { assert(capacity > 0); assert(usage <= capacity); if (this->edges[to].capacity == 0) { - this->AddEdge(to, capacity, usage, mode); + this->AddEdge(to, capacity, usage, travel_time, mode); } else { - (*this)[to].Update(capacity, usage, mode); + (*this)[to].Update(capacity, usage, travel_time, mode); } } @@ -231,6 +236,7 @@ void LinkGraph::Node::RemoveEdge(NodeID to) edge.last_unrestricted_update = INVALID_DATE; edge.last_restricted_update = INVALID_DATE; edge.usage = 0; + edge.travel_time_sum = 0; NodeID prev = this->index; NodeID next = this->edges[this->index].next_edge; @@ -249,23 +255,39 @@ void LinkGraph::Node::RemoveEdge(NodeID to) /** * 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. + * least the given capacity and usage, otherwise add the capacity, usage and travel time. * In any case set the respective update timestamp(s), according to the given * mode. * @param capacity Capacity to be added/updated. * @param usage Usage to be added. + * @param travel_time Travel time to be added, in ticks. * @param mode Update mode to be applied. */ -void LinkGraph::Edge::Update(uint capacity, uint usage, EdgeUpdateMode mode) +void LinkGraph::Edge::Update(uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode) { assert(this->edge.capacity > 0); assert(capacity >= usage); if (mode & EUM_INCREASE) { + if (this->edge.travel_time_sum == 0) { + this->edge.travel_time_sum = (this->edge.capacity + capacity) * travel_time; + } else if (travel_time == 0) { + this->edge.travel_time_sum += this->edge.travel_time_sum / this->edge.capacity * capacity; + } else { + this->edge.travel_time_sum += travel_time * capacity; + } this->edge.capacity += capacity; this->edge.usage += usage; } else if (mode & EUM_REFRESH) { - this->edge.capacity = std::max(this->edge.capacity, capacity); + /* If travel time is not provided, we scale the stored time based on + * the capacity increase. */ + if (capacity > this->edge.capacity && travel_time == 0) { + this->edge.travel_time_sum = this->edge.travel_time_sum / this->edge.capacity * capacity; + this->edge.capacity = capacity; + } else { + this->edge.capacity = std::max(this->edge.capacity, capacity); + this->edge.travel_time_sum = std::max(this->edge.travel_time_sum, travel_time * capacity); + } this->edge.usage = std::max(this->edge.usage, usage); } if (mode & EUM_UNRESTRICTED) this->edge.last_unrestricted_update = _date; diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h index a11b67a52..3a2c37977 100644 --- a/src/linkgraph/linkgraph.h +++ b/src/linkgraph/linkgraph.h @@ -62,6 +62,7 @@ public: struct BaseEdge { uint capacity; ///< Capacity of the link. uint usage; ///< Usage of the link. + uint64 travel_time_sum; ///< Sum of the travel times of the link, in ticks. Date last_unrestricted_update; ///< When the unrestricted part of the link was last updated. Date last_restricted_update; ///< When the restricted part of the link was last updated. NodeID next_edge; ///< Destination of next valid edge starting at the same source node. @@ -97,6 +98,12 @@ public: */ uint Usage() const { return this->edge.usage; } + /** + * Get edge's average travel time. + * @return Travel time, in ticks. + */ + uint32 TravelTime() const { return this->edge.travel_time_sum / this->edge.capacity; } + /** * Get the date of the last update to the edge's unrestricted capacity. * @return Last update. @@ -296,7 +303,7 @@ public: * @param edge Edge to be wrapped. */ Edge(BaseEdge &edge) : EdgeWrapper(edge) {} - void Update(uint capacity, uint usage, EdgeUpdateMode mode); + void Update(uint capacity, uint usage, uint32 time, EdgeUpdateMode mode); void Restrict() { this->edge.last_unrestricted_update = INVALID_DATE; } void Release() { this->edge.last_restricted_update = INVALID_DATE; } }; @@ -429,8 +436,8 @@ public: this->node.demand = demand; } - void AddEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode); - void UpdateEdge(NodeID to, uint capacity, uint usage, EdgeUpdateMode mode); + void AddEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode); + void UpdateEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode); void RemoveEdge(NodeID to); }; diff --git a/src/linkgraph/mcf.cpp b/src/linkgraph/mcf.cpp index f24a8e028..8cd73cb91 100644 --- a/src/linkgraph/mcf.cpp +++ b/src/linkgraph/mcf.cpp @@ -284,12 +284,21 @@ void MultiCommodityFlow::Dijkstra(NodeID source_node, PathVector &paths) capacity /= 100; if (capacity == 0) capacity = 1; } - /* punish in-between stops a little */ + /* Prioritize the fastest route for passengers, mail and express cargo, + * and the shortest route for other classes of cargo. + * In-between stops are punished with a 1 tile or 1 day penalty. */ + bool express = IsCargoInClass(this->job.Cargo(), CC_PASSENGERS) || + IsCargoInClass(this->job.Cargo(), CC_MAIL) || + IsCargoInClass(this->job.Cargo(), CC_EXPRESS); uint distance = DistanceMaxPlusManhattan(this->job[from].XY(), this->job[to].XY()) + 1; + /* Compute a default travel time from the distance and an average speed of 1 tile/day. */ + uint time = (edge.TravelTime() != 0) ? edge.TravelTime() + DAY_TICKS : distance * DAY_TICKS; + uint distance_anno = express ? time : distance; + Tannotation *dest = static_cast(paths[to]); - if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance)) { + if (dest->IsBetter(source, capacity, capacity - edge.Flow(), distance_anno)) { annos.erase(dest); - dest->Fork(source, capacity, capacity - edge.Flow(), distance); + dest->Fork(source, capacity, capacity - edge.Flow(), distance_anno); dest->UpdateAnnotation(); annos.insert(dest); } diff --git a/src/linkgraph/refresh.cpp b/src/linkgraph/refresh.cpp index 430e29072..78fdd1643 100644 --- a/src/linkgraph/refresh.cpp +++ b/src/linkgraph/refresh.cpp @@ -218,6 +218,12 @@ void LinkRefresher::RefreshStats(const Order *cur, const Order *next) /* 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; + Station *st_to = Station::GetIfValid(next_station); + /* This estimates the travel time of the link as the time needed + * to travel between the stations at half the max speed of the consist. + * The result is in tiles/tick (= 2048 km-ish/h). */ + uint32 time_estimate = (st_to != nullptr) ? + DistanceManhattan(st->xy, st_to->xy) * 4096U / this->vehicle->GetDisplayMaxSpeed() : 0; /* 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 @@ -231,15 +237,15 @@ void LinkRefresher::RefreshStats(const Order *cur, const Order *next) uint effective_capacity = cargo_quantity * 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, + this->vehicle->orders.list->GetTotalDuration(), 0, 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); + IncreaseStats(st, c, next_station, 1, 0, 0, EUM_INCREASE | restricted_mode); } else { - IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode); + IncreaseStats(st, c, next_station, cargo_quantity, 0, time_estimate, EUM_REFRESH | restricted_mode); } } else { - IncreaseStats(st, c, next_station, cargo_quantity, 0, EUM_REFRESH | restricted_mode); + IncreaseStats(st, c, next_station, cargo_quantity, 0, time_estimate, EUM_REFRESH | restricted_mode); } } } diff --git a/src/saveload/linkgraph_sl.cpp b/src/saveload/linkgraph_sl.cpp index ae21de4c7..9ff7e130a 100644 --- a/src/saveload/linkgraph_sl.cpp +++ b/src/saveload/linkgraph_sl.cpp @@ -33,6 +33,7 @@ public: inline static const SaveLoad description[] = { SLE_VAR(Edge, capacity, SLE_UINT32), SLE_VAR(Edge, usage, SLE_UINT32), + SLE_CONDVAR(Edge, travel_time_sum, SLE_UINT64, SLV_LINKGRAPH_TRAVEL_TIME, SL_MAX_VERSION), SLE_VAR(Edge, last_unrestricted_update, SLE_INT32), SLE_CONDVAR(Edge, last_restricted_update, SLE_INT32, SLV_187, SL_MAX_VERSION), SLE_VAR(Edge, next_edge, SLE_UINT16), diff --git a/src/saveload/saveload.h b/src/saveload/saveload.h index 3047cbfd8..ad8b368c8 100644 --- a/src/saveload/saveload.h +++ b/src/saveload/saveload.h @@ -337,6 +337,7 @@ enum SaveLoadVersion : uint16 { SLV_TABLE_CHUNKS, ///< 295 PR#9322 Introduction of CH_TABLE and CH_SPARSE_TABLE. SLV_SCRIPT_INT64, ///< 296 PR#9415 SQInteger is 64bit but was saved as 32bit. + SLV_LINKGRAPH_TRAVEL_TIME, ///< 297 PR#9457 Store travel time in the linkgraph. SL_MAX_VERSION, ///< Highest possible saveload version }; diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp index 6a5cabc8d..05e837287 100644 --- a/src/station_cmd.cpp +++ b/src/station_cmd.cpp @@ -3737,7 +3737,7 @@ void DeleteStaleLinks(Station *from) * @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, EdgeUpdateMode mode) +void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode) { GoodsEntry &ge1 = st->goods[cargo]; Station *st2 = Station::Get(next_station_id); @@ -3779,7 +3779,7 @@ void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint c } } if (lg != nullptr) { - (*lg)[ge1.node].UpdateEdge(ge2.node, capacity, usage, mode); + (*lg)[ge1.node].UpdateEdge(ge2.node, capacity, usage, time, mode); } } @@ -3789,7 +3789,7 @@ void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint c * @param front First vehicle in the consist. * @param next_station_id Station the consist will be travelling to next. */ -void IncreaseStats(Station *st, const Vehicle *front, StationID next_station_id) +void IncreaseStats(Station *st, const Vehicle *front, StationID next_station_id, uint32 time) { for (const Vehicle *v = front; v != nullptr; v = v->Next()) { if (v->refit_cap > 0) { @@ -3800,7 +3800,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, - std::min(v->refit_cap, v->cargo.StoredCount()), EUM_INCREASE); + std::min(v->refit_cap, v->cargo.StoredCount()), time, EUM_INCREASE); } } } diff --git a/src/station_func.h b/src/station_func.h index dc8942841..65b9ac5e6 100644 --- a/src/station_func.h +++ b/src/station_func.h @@ -52,8 +52,8 @@ 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, EdgeUpdateMode mode); +void IncreaseStats(Station *st, const Vehicle *v, StationID next_station_id, uint32 time); +void IncreaseStats(Station *st, CargoID cargo, StationID next_station_id, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode); void RerouteCargo(Station *st, CargoID c, StationID avoid, StationID avoid2); /** diff --git a/src/vehicle.cpp b/src/vehicle.cpp index 955f9bde0..6df16caf6 100644 --- a/src/vehicle.cpp +++ b/src/vehicle.cpp @@ -2100,6 +2100,7 @@ void Vehicle::BeginLoading() { assert(IsTileType(this->tile, MP_STATION) || this->type == VEH_SHIP); + uint32 travel_time = this->current_order_time; if (this->current_order.IsType(OT_GOTO_STATION) && this->current_order.GetDestination() == this->last_station_visited) { this->DeleteUnreachedImplicitOrders(); @@ -2206,7 +2207,7 @@ void Vehicle::BeginLoading() this->last_loading_station != this->last_station_visited && ((this->current_order.GetLoadType() & OLFB_NO_LOAD) == 0 || (this->current_order.GetUnloadType() & OUFB_NO_UNLOAD) == 0)) { - IncreaseStats(Station::Get(this->last_loading_station), this, this->last_station_visited); + IncreaseStats(Station::Get(this->last_loading_station), this, this->last_station_visited, travel_time); } PrepareUnload(this); -- cgit v1.2.3-70-g09d2