summaryrefslogtreecommitdiff
path: root/yapf/yapf_ship.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'yapf/yapf_ship.cpp')
-rw-r--r--yapf/yapf_ship.cpp168
1 files changed, 168 insertions, 0 deletions
diff --git a/yapf/yapf_ship.cpp b/yapf/yapf_ship.cpp
new file mode 100644
index 000000000..c19f6bbdd
--- /dev/null
+++ b/yapf/yapf_ship.cpp
@@ -0,0 +1,168 @@
+/* $Id$ */
+
+#include "../stdafx.h"
+
+#include "yapf.hpp"
+
+/** Node Follower module of YAPF for ships */
+template <class Types>
+class CYapfFollowShipT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::TrackFollower TrackFollower;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ inline void PfFollowNode(Node& old_node)
+ {
+ TrackFollower F;
+ if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td))
+ Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits);
+ }
+
+ FORCEINLINE char TransportTypeChar() const {return 'w';}
+
+ static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+ {
+ // handle special case - when next tile is destination tile
+ if (tile == v->dest_tile) {
+ // convert tracks to trackdirs
+ TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));
+ // choose any trackdir reachable from enterdir
+ trackdirs &= DiagdirReachesTrackdirs(enterdir);
+ return (Trackdir)FindFirstBit2x64(trackdirs);
+ }
+
+ // move back to the old tile/trackdir (where ship is coming from)
+ TileIndex src_tile = TILE_ADD(tile, TileOffsByDir(ReverseDiagDir(enterdir)));
+ Trackdir trackdir = GetVehicleTrackdir(v);
+ assert(IsValidTrackdir(trackdir));
+
+ // convert origin trackdir to TrackdirBits
+ TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
+ // get available trackdirs on the destination tile
+ TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK);
+
+ // create pathfinder instance
+ Tpf pf;
+ // set origin and destination nodes
+ pf.SetOrigin(src_tile, trackdirs);
+ pf.SetDestination(v->dest_tile, dest_trackdirs);
+ // find best path
+ bool bFound = pf.FindPath(v);
+
+ Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
+ if (bFound) {
+ // path was found
+ // walk through the path back to the origin
+ Node* pNode = &pf.GetBestNode();
+ Node* pPrevNode = NULL;
+ while (pNode->m_parent != NULL) {
+ pPrevNode = pNode;
+ pNode = pNode->m_parent;
+ }
+ // return trackdir from the best next node (direct child of origin)
+ Node& best_next_node = *pPrevNode;
+ assert(best_next_node.GetTile() == tile);
+ next_trackdir = best_next_node.GetTrackdir();
+ }
+ return next_trackdir;
+ }
+};
+
+/** Cost Provider module of YAPF for ships */
+template <class Types>
+class CYapfCostShipT
+{
+public:
+ typedef typename Types::Tpf Tpf;
+ typedef typename Types::NodeList::Titem Node; ///< this will be our node type
+ typedef typename Node::Key Key; ///< key to hash tables
+
+protected:
+ Tpf& Yapf() {return *static_cast<Tpf*>(this);}
+
+public:
+ FORCEINLINE bool PfCalcCost(Node& n)
+ {
+ // base tile cost depending on distance
+ int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;
+ // additional penalty for curves
+ if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3;
+ // apply it
+ n.m_cost = n.m_parent->m_cost + c;
+ return true;
+ }
+};
+
+/** Config struct of YAPF for ships.
+ Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.
+*/
+template <class Tpf_, class Ttrack_follower, class Tnode_list>
+struct CYapfShip_TypesT
+{
+ /** Types - shortcut for this struct type */
+ typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list> Types;
+
+ /** Tpf - pathfinder type */
+ typedef Tpf_ Tpf;
+ /** track follower helper class */
+ typedef Ttrack_follower TrackFollower;
+ /** node list type */
+ typedef Tnode_list NodeList;
+ /** pathfinder components (modules) */
+ typedef CYapfBaseT<Types> PfBase; // base pathfinder class
+ typedef CYapfFollowShipT<Types> PfFollow; // node follower
+ typedef CYapfOriginTileT<Types> PfOrigin; // origin provider
+ typedef CYapfDestinationTileT<Types> PfDestination; // destination/distance provider
+ typedef CYapfSegmentCostCacheNoneT<Types> PfCache; // segment cost cache provider
+ typedef CYapfCostShipT<Types> PfCost; // cost provider
+};
+
+// YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns
+struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {};
+// YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns
+struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {};
+// YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns
+struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};
+
+/** Ship controller helper - path finder invoker */
+Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+{
+ // default is YAPF type 2
+ typedef Trackdir (*PfnChooseShipTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits);
+ PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
+
+ // check if non-default YAPF type needed
+ if (_patches.forbid_90_deg)
+ pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
+ else if (_patches.yapf.disable_node_optimization)
+ pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg
+
+ Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks);
+ return td_ret;
+}
+
+/** performance measurement helper */
+void* NpfBeginInterval()
+{
+ CPerformanceTimer& perf = *new CPerformanceTimer;
+ perf.Start();
+ return &perf;
+}
+
+/** performance measurement helper */
+int NpfEndInterval(void* vperf)
+{
+ CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;
+ perf.Stop();
+ int t = perf.Get(1000000);
+ delete &perf;
+ return t;
+}
+