summaryrefslogtreecommitdiff
path: root/src/pathfinder/yapf/yapf_cargo.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathfinder/yapf/yapf_cargo.cpp')
-rw-r--r--src/pathfinder/yapf/yapf_cargo.cpp442
1 files changed, 442 insertions, 0 deletions
diff --git a/src/pathfinder/yapf/yapf_cargo.cpp b/src/pathfinder/yapf/yapf_cargo.cpp
new file mode 100644
index 000000000..22e995197
--- /dev/null
+++ b/src/pathfinder/yapf/yapf_cargo.cpp
@@ -0,0 +1,442 @@
+/* $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 yapf_cargo.cpp Implementation of YAPF for cargo routing. */
+
+#include "../../stdafx.h"
+#include "../../cargodest_base.h"
+#include "../../station_base.h"
+#include "../../town.h"
+#include "yapf.hpp"
+
+
+/** YAPF node key for cargo routing. */
+struct CYapfRouteLinkNodeKeyT {
+ RouteLink *m_link;
+
+ /** Initialize this node key. */
+ inline void Set(RouteLink *link)
+ {
+ this->m_link = link;
+ }
+
+ /** Calculate the hash of this cargo/route key. */
+ inline int CalcHash() const
+ {
+ return (int)(size_t)this->m_link >> 4;
+ }
+
+ inline bool operator == (const CYapfRouteLinkNodeKeyT& other) const
+ {
+ return this->m_link == other.m_link;
+ }
+
+ void Dump(DumpTarget &dmp) const
+ {
+ dmp.WriteLine("m_link = %u", this->m_link->GetDestination());
+ }
+};
+
+/** YAPF node class for cargo routing. */
+struct CYapfRouteLinkNodeT : public CYapfNodeT<CYapfRouteLinkNodeKeyT, CYapfRouteLinkNodeT> {
+ typedef CYapfNodeT<CYapfRouteLinkNodeKeyT, CYapfRouteLinkNodeT> Base;
+
+ uint m_num_transfers; ///< Number of transfers to reach this node.
+
+ /** Initialize this node. */
+ inline void Set(CYapfRouteLinkNodeT *parent, RouteLink *link)
+ {
+ Base::Set(parent, false);
+ this->m_key.Set(link);
+ this->m_num_transfers = (parent != NULL) ? parent->m_num_transfers : 0;
+ }
+
+ /** Get the route link of this node. */
+ inline RouteLink *GetRouteLink() const { return this->m_key.m_link; }
+
+ /** Get the number of transfers needed to reach this node. */
+ inline int GetNumberOfTransfers() const { return this->m_num_transfers; }
+};
+
+typedef CNodeList_HashTableT<CYapfRouteLinkNodeT, 8, 10, 2048> CRouteLinkNodeList;
+
+/** Route link follower. */
+struct CFollowRouteLinkT {
+ CargoID m_cid;
+ RouteLink *m_old_link;
+ RouteLinkList *m_new_links;
+
+ CFollowRouteLinkT(CargoID cid) : m_cid(cid) {}
+
+ /** Fill in route links reachable by this route link. */
+ inline bool Follow(RouteLink *from)
+ {
+ this->m_old_link = from;
+
+ Station *st = Station::Get(from->GetDestination());
+ m_new_links = &st->goods[this->m_cid].routes;
+ return !this->m_new_links->empty();
+ }
+};
+
+/** YAPF cost provider for route links. */
+template <class Types>
+class CYapfCostRouteLinkT {
+ typedef typename Types::Tpf Tpf; ///< The pathfinder class (derived from THIS class).
+ typedef typename Types::TrackFollower Follower; ///< The route follower.
+ typedef typename Types::NodeList::Titem Node; ///< This will be our node type.
+
+ static const int PENALTY_DIVISOR = 16; ///< Penalty factor divisor for fixed-point arithmetics.
+ static const int LOCAL_PENALTY_FACTOR = 16; ///< Penalty factor for source-local delivery.
+ static const int RF_DISTANCE_FACTOR = 2; ///< Vehicle modifier for "cheap" cargo packets.
+ static const int RF_TIME_FACTOR = 3; ///< Time modifier for "fast" cargo packets.
+
+ /** To access inherited path finder. */
+ inline Tpf& Yapf() { return *static_cast<Tpf*>(this); }
+ inline const Tpf& Yapf() const { return *static_cast<const Tpf*>(this); }
+
+ /** Check if this is a valid connection. */
+ inline bool ValidLink(Node &n, const RouteLink *link, const RouteLink *parent) const
+ {
+ /* If the parent link has an owner, and the owner is different to
+ * the new owner, discard the node. Otherwise cargo could switch
+ * companies at oil rigs, which would mess up payment. */
+ if (parent->GetOwner() != INVALID_OWNER && link->GetOwner() != parent->GetOwner()) return false;
+
+ /* Check for no loading/no unloading when transferring. */
+ if (link->GetOriginOrderId() != parent->GetDestOrderId() || (Order::Get(link->GetOriginOrderId())->GetUnloadType() & OUFB_UNLOAD) != 0) {
+ /* Can't transfer if the current order prohibits loading. */
+ if ((Order::Get(link->GetOriginOrderId())->GetLoadType() & OLFB_NO_LOAD) != 0) return false;
+
+ /* Can't transfer if the last order prohibits unloading. */
+ if (parent->GetDestOrderId() != INVALID_ORDER && (Order::Get(parent->GetDestOrderId())->GetUnloadType() & OUFB_NO_UNLOAD) != 0) return false;
+
+ /* Increase transfer counter and stop if max number of transfers is exceeded. */
+ if (++n.m_num_transfers > Yapf().PfGetSettings().route_max_transfers) return false;
+ }
+
+ return true;
+ }
+
+ /** Cost of a single route link. */
+ inline int RouteLinkCost(const RouteLink *link, const RouteLink *parent) const
+ {
+ int cost = 0;
+
+ /* Distance cost. */
+ const Station *from = Station::Get(parent->GetDestination());
+ const Station *to = Station::Get(link->GetDestination());
+ cost = DistanceManhattan(from->xy, to->xy) * this->Yapf().PfGetSettings().route_distance_factor;
+
+ /* Modulate the distance by a vehicle-type specific factor to
+ * simulate the different costs. Cost is doubled if the cargo
+ * wants to go cheap. */
+ assert_compile(lengthof(_settings_game.pf.yapf.route_mode_cost_factor) == VEH_AIRCRAFT + 1);
+ byte dfactor = this->Yapf().PfGetSettings().route_mode_cost_factor[link->GetVehicleType()];
+ if (HasBit(this->Yapf().GetFlags(), RF_WANT_CHEAP)) dfactor *= RF_DISTANCE_FACTOR;
+ cost *= dfactor;
+
+ /* Factor for the time penalties based on whether the cargo wants to go fast. */
+ uint time_factor = HasBit(this->Yapf().GetFlags(), RF_WANT_FAST) ? RF_TIME_FACTOR : 1;
+
+ /* Transfer penalty when switching vehicles or forced unloading. */
+ if (link->GetOriginOrderId() != parent->GetDestOrderId() || (Order::Get(link->GetOriginOrderId())->GetUnloadType() & OUFB_UNLOAD) != 0) {
+ cost += this->Yapf().PfGetSettings().route_transfer_cost;
+
+ /* Penalty for time since the last vehicle arrived. */
+ cost += link->GetWaitTime() * this->Yapf().PfGetSettings().route_station_last_veh_factor * time_factor / PENALTY_DIVISOR;
+
+ /* Penalty for cargo waiting on our link. */
+ cost += (from->goods[this->Yapf().GetCargoID()].cargo.CountForNextHop(link->GetOriginOrderId()) * this->Yapf().PfGetSettings().route_station_waiting_factor) / PENALTY_DIVISOR;
+ }
+
+ /* Penalty for travel time. */
+ cost += (link->GetTravelTime() * this->Yapf().PfGetSettings().route_travel_time_factor * time_factor) / PENALTY_DIVISOR;
+
+ return cost;
+ }
+
+public:
+ /** Called by YAPF to calculate the cost from the origin to the given node. */
+ inline bool PfCalcCost(Node& n, const Follower *follow)
+ {
+ int segment_cost = 0;
+
+ if (this->Yapf().PfDetectDestination(n)) {
+ Station *st = Station::Get(n.m_parent->GetRouteLink()->GetDestination());
+ /* Discard node if the station doesn't accept the cargo type. */
+ if (!HasBit(st->goods[follow->m_cid].acceptance_pickup, GoodsEntry::GES_ACCEPTANCE)) return false;
+ /* Destination node, get delivery cost. Parent has the station. */
+ segment_cost += this->Yapf().DeliveryCost(st);
+ /* If this link comes from an origin station, penalize it to encourage
+ * delivery using other stations. */
+ if (n.m_parent->GetRouteLink()->GetDestOrderId() == INVALID_ORDER) segment_cost *= LOCAL_PENALTY_FACTOR;
+ } else {
+ RouteLink *link = n.GetRouteLink();
+ RouteLink *parent = n.m_parent->GetRouteLink();
+
+ /* Check if the link is a valid connection. */
+ if (!this->ValidLink(n, link, parent)) return false;
+
+ /* Cost of the single route link. */
+ segment_cost += this->RouteLinkCost(link, parent);
+ }
+
+ /* Apply it. */
+ n.m_cost = n.m_parent->m_cost + segment_cost;
+ return n.m_cost <= this->Yapf().GetMaxCost();
+ }
+};
+
+/** YAPF origin provider for route links. */
+template <class Types>
+class CYapfOriginRouteLinkT {
+ typedef typename Types::Tpf Tpf; ///< The pathfinder class (derived from THIS class).
+ typedef typename Types::NodeList::Titem Node; ///< This will be our node type.
+
+ CargoID m_cid;
+ TileIndex m_src;
+ OrderID m_order;
+ byte m_flags;
+ SmallVector<RouteLink, 2> m_origin;
+
+ /** To access inherited path finder. */
+ inline Tpf& Yapf() { return *static_cast<Tpf*>(this); }
+
+public:
+ /** Get the current cargo type. */
+ inline CargoID GetCargoID() const
+ {
+ return this->m_cid;
+ }
+
+ /** Get the cargo routing flags. */
+ inline byte GetFlags() const
+ {
+ return this->m_flags;
+ }
+
+ /** Set origin. */
+ void SetOrigin(CargoID cid, TileIndex src, const StationList *stations, bool cargo_creation, OrderID order, byte flags)
+ {
+ this->m_cid = cid;
+ this->m_src = src;
+ this->m_order = order;
+ this->m_flags = flags;
+ /* Create fake links for the origin stations. */
+ for (const Station * const *st = stations->Begin(); st != stations->End(); st++) {
+ if (cargo_creation) {
+ /* Exclusive rights in effect? Only serve those stations. */
+ if ((*st)->town->exclusive_counter > 0 && (*st)->town->exclusivity != (*st)->owner) continue;
+ /* Selectively servicing stations, and not this one. */
+ if (_settings_game.order.selectgoods && (*st)->goods[cid].last_speed == 0) continue;
+ }
+
+ *this->m_origin.Append() = RouteLink((*st)->index, INVALID_ORDER, this->m_order);
+ }
+ }
+
+ /** Called when YAPF needs to place origin nodes into the open list. */
+ void PfSetStartupNodes()
+ {
+ for (RouteLink *link = this->m_origin.Begin(); link != this->m_origin.End(); link++) {
+ Node &n = this->Yapf().CreateNewNode();
+ n.Set(NULL, link);
+ /* Prefer stations closer to the source tile. */
+ n.m_cost = DistanceSquare(this->m_src, Station::Get(link->GetDestination())->xy) * this->Yapf().PfGetSettings().route_distance_factor;
+ this->Yapf().AddStartupNode(n);
+ }
+ }
+};
+
+/** YAPF destination provider for route links. */
+template <class Types>
+class CYapfDestinationRouteLinkT {
+ typedef typename Types::Tpf Tpf; ///< The pathfinder class (derived from THIS class).
+ typedef typename Types::NodeList::Titem Node; ///< This will be our node type.
+
+ TileArea m_dest;
+ int m_max_cost; ///< Maximum node cost.
+
+ /** To access inherited path finder. */
+ inline Tpf& Yapf() { return *static_cast<Tpf*>(this); }
+
+public:
+ /** Get the maximum allowed node cost. */
+ inline int GetMaxCost() const
+ {
+ return this->m_max_cost;
+ }
+
+ /** Set destination. */
+ void SetDestination(const TileArea &dest, uint max_cost)
+ {
+ this->m_dest = dest;
+ this->m_max_cost = max_cost;
+ }
+
+ /** Cost for delivering the cargo to the final destination tile. */
+ inline int DeliveryCost(Station *st)
+ {
+ int x = TileX(this->m_dest.tile);
+ int y = TileY(this->m_dest.tile);
+
+ /* Inside the station area? Delivery costs "nothing". */
+ if (st->rect.PtInExtendedRect(x, y)) return 0;
+
+ int dist_x = x < st->rect.left ? x - st->rect.left : x - st->rect.right;
+ int dist_y = y < st->rect.top ? y - st->rect.top : y - st->rect.bottom;
+
+ return (dist_x * dist_x + dist_y * dist_y) * this->Yapf().PfGetSettings().route_distance_factor;
+ }
+
+ /** Called by YAPF to detect if the station reaches the destination. */
+ inline bool PfDetectDestination(StationID st_id) const
+ {
+ const Station *st = Station::Get(st_id);
+ return st->rect.AreaInExtendedRect(this->m_dest, st->GetCatchmentRadius());
+ }
+
+ /** Called by YAPF to detect if the node reaches the destination. */
+ inline bool PfDetectDestination(const Node& n) const
+ {
+ return n.GetRouteLink() == NULL;
+ }
+
+ /** Called by YAPF to calculate the estimated cost to the destination. */
+ inline bool PfCalcEstimate(Node& n)
+ {
+ if (this->PfDetectDestination(n)) {
+ n.m_estimate = n.m_cost;
+ return true;
+ }
+
+ /* Estimate based on Manhattan distance to destination. */
+ Station *from = Station::Get(n.GetRouteLink()->GetDestination());
+ int d = DistanceManhattan(from->xy, this->m_dest.tile) * this->Yapf().PfGetSettings().route_distance_factor;
+
+ n.m_estimate = n.m_cost + d;
+ assert(n.m_estimate >= n.m_parent->m_estimate);
+ return true;
+ }
+};
+
+/** Main route finding class. */
+template <class Types>
+class CYapfFollowRouteLinkT {
+ typedef typename Types::Tpf Tpf; ///< The pathfinder class (derived from THIS class).
+ typedef typename Types::TrackFollower Follower; ///< The route follower.
+ typedef typename Types::NodeList::Titem Node; ///< This will be our node type.
+
+ /** To access inherited path finder. */
+ inline Tpf& Yapf() { return *static_cast<Tpf*>(this); }
+
+public:
+ /** Called by YAPF to move from the given node to the next nodes. */
+ inline void PfFollowNode(Node& old_node)
+ {
+ Follower f(this->Yapf().GetCargoID());
+
+ if (this->Yapf().PfDetectDestination(old_node.GetRouteLink()->GetDestination()) && (old_node.GetRouteLink()->GetDestOrderId() == INVALID_ORDER || (Order::Get(old_node.GetRouteLink()->GetDestOrderId())->GetUnloadType() & OUFB_NO_UNLOAD) == 0)) {
+ /* Possible destination? Add sentinel node for final delivery. */
+ Node &n = this->Yapf().CreateNewNode();
+ n.Set(&old_node, NULL);
+ this->Yapf().AddNewNode(n, f);
+ }
+
+ if (f.Follow(old_node.GetRouteLink())) {
+ for (RouteLinkList::iterator link = f.m_new_links->begin(); link != f.m_new_links->end(); ++link) {
+ /* Add new node. */
+ Node &n = this->Yapf().CreateNewNode();
+ n.Set(&old_node, *link);
+ this->Yapf().AddNewNode(n, f);
+ }
+ }
+ }
+
+ /** Return debug report character to identify the transportation type. */
+ inline char TransportTypeChar() const
+ {
+ return 'c';
+ }
+
+ /** Find the best cargo routing from a station to a destination. */
+ static RouteLink *ChooseRouteLink(CargoID cid, const StationList *stations, TileIndex src, const TileArea &dest, StationID *start_station, StationID *next_unload, byte flags, bool *found, OrderID order, int max_cost)
+ {
+ /* Initialize pathfinder instance. */
+ Tpf pf;
+ pf.SetOrigin(cid, src, stations, start_station != NULL, order, flags);
+ pf.SetDestination(dest, max_cost);
+
+ *next_unload = INVALID_STATION;
+
+ /* Do it. Exit if we didn't find a path. */
+ bool res = pf.FindPath(NULL);
+ if (found != NULL) *found = res;
+ if (!res) return NULL;
+
+ /* Walk back to find the start node. */
+ Node *node = pf.GetBestNode();
+ while (node->m_parent->m_parent != NULL) {
+ /* Transfer? Then save transfer station as next unload station. */
+ if (node->GetRouteLink() == NULL || (node->GetRouteLink()->GetOriginOrderId() != node->m_parent->GetRouteLink()->GetDestOrderId())) {
+ *next_unload = node->m_parent->GetRouteLink()->GetDestination();
+ }
+
+ node = node->m_parent;
+ }
+
+ /* Save result. */
+ if (start_station != NULL) {
+ *start_station = node->m_parent->GetRouteLink()->GetDestination();
+ /* Path starts and ends at the same station, do local delivery. */
+ if (*start_station == pf.GetBestNode()->m_parent->GetRouteLink()->GetDestination()) return NULL;
+ }
+ return node->GetRouteLink();
+ }
+};
+
+/** Config struct for route link finding. */
+template <class Tpf_>
+struct CYapfRouteLink_TypesT {
+ typedef CYapfRouteLink_TypesT<Tpf_> Types;
+
+ typedef Tpf_ Tpf; ///< Pathfinder type
+ typedef CFollowRouteLinkT TrackFollower; ///< Node follower
+ typedef CRouteLinkNodeList NodeList; ///< Node list type
+ typedef Vehicle VehicleType; ///< Dummy type
+
+ typedef CYapfBaseT<Types> PfBase; ///< Base pathfinder class
+ typedef CYapfFollowRouteLinkT<Types> PfFollow; ///< Node follower
+ typedef CYapfOriginRouteLinkT<Types> PfOrigin; ///< Origin provider
+ typedef CYapfDestinationRouteLinkT<Types> PfDestination; ///< Destination/distance provider
+ typedef CYapfSegmentCostCacheNoneT<Types> PfCache; ///< Cost cache provider
+ typedef CYapfCostRouteLinkT<Types> PfCost; ///< Cost provider
+};
+
+struct CYapfRouteLink : CYapfT<CYapfRouteLink_TypesT<CYapfRouteLink> > {};
+
+
+/**
+ * Find the best cargo routing from a station to a destination.
+ * @param cid Cargo type to route.
+ * @param stations Set of possible originating stations.
+ * @param dest Destination tile area.
+ * @param[out] start_station Station the best route link originates from.
+ * @param[out] next_unload Next station the cargo should be unloaded from the vehicle.
+ * @param flags Routing flags of the cargo.
+ * @param[out] found True if a link was found.
+ * @param order Order the vehicle arrived at the origin station.
+ * @param max_cost Maxmimum allowed node cost.
+ * @return The best RouteLink to the target or NULL if either no link found or one of the origin stations is the best destination.
+ */
+RouteLink *YapfChooseRouteLink(CargoID cid, const StationList *stations, TileIndex src, const TileArea &dest, StationID *start_station, StationID *next_unload, byte flags, bool *found, OrderID order, int max_cost)
+{
+ return CYapfRouteLink::ChooseRouteLink(cid, stations, src, dest, start_station, next_unload, flags, found, order, max_cost);
+}
generated by cgit v1.2.3-54-g00ecf (git 2.44.0) at 2024-05-14 20:23:18 +0000