diff options
author | Nicolas Chappe <74881848+nchappe@users.noreply.github.com> | 2021-07-24 11:07:10 +0200 |
---|---|---|
committer | Michael Lutz <michi@icosahedron.de> | 2021-08-17 14:57:59 +0200 |
commit | 977604ef08212cc93653eaa8187ab64ebe72e7d2 (patch) | |
tree | 5aa86c084ebee29497147fa8008855acf572977b /src/linkgraph | |
parent | 6acf204d14343e67fdc01ae8c52044d0de20bbd2 (diff) | |
download | openttd-977604ef08212cc93653eaa8187ab64ebe72e7d2.tar.xz |
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.
Diffstat (limited to 'src/linkgraph')
-rw-r--r-- | src/linkgraph/linkgraph.cpp | 36 | ||||
-rw-r--r-- | src/linkgraph/linkgraph.h | 13 | ||||
-rw-r--r-- | src/linkgraph/mcf.cpp | 15 | ||||
-rw-r--r-- | src/linkgraph/refresh.cpp | 14 |
4 files changed, 61 insertions, 17 deletions
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<uint64>(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. @@ -98,6 +99,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<BaseEdge>(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<Tannotation *>(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); } } } |