(svn r18364) -Codechange: move the pathfinders and their related files into a separate directory

1 files changed, 203 insertions, 0 deletions

diff --git a/src/pathfinder/yapf/yapf_ship.cpp b/src/pathfinder/yapf/yapf_ship.cpp
new file mode 100644
index 000000000..3ae152bd6
--- /dev/null
+++ b/src/pathfinder/yapf/yapf_ship.cpp
@@ -0,0 +1,203 @@
+/* $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_ship.cpp Implementation of YAPF for ships. */
+
+#include "../../stdafx.h"
+
+#include "yapf.hpp"
+
+/** Node Follower module of YAPF for ships */
+template <class Types>
+class CYapfFollowShipT
+{
+public:
+	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)
+	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:
+	/** to access inherited path finder */
+	FORCEINLINE Tpf& Yapf()
+	{
+		return *static_cast<Tpf*>(this);
+	}
+
+public:
+	/** Called by YAPF to move from the given node to the next tile. For each
+	 *  reachable trackdir on the new tile creates new node, initializes it
+	 *  and adds it to the open list by calling Yapf().AddNewNode(n) */
+	inline void PfFollowNode(Node& old_node)
+	{
+		TrackFollower F(Yapf().GetVehicle());
+		if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) {
+			Yapf().AddMultipleNodes(&old_node, F);
+		}
+	}
+
+	/** return debug report character to identify the transportation type */
+	FORCEINLINE char TransportTypeChar() const
+	{
+		return 'w';
+	}
+
+	static Trackdir ChooseShipTrack(const 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, TileOffsByDiagDir(ReverseDiagDir(enterdir)));
+		Trackdir trackdir = v->GetVehicleTrackdir();
+		assert(IsValidTrackdir(trackdir));
+
+		/* convert origin trackdir to TrackdirBits */
+		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);
+		/* get available trackdirs on the destination tile */
+		TrackdirBits dest_trackdirs = TrackStatusToTrackdirBits(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER, 0));
+
+		/* 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 */
+		pf.FindPath(v);
+
+		Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"
+
+		Node *pNode = pf.GetBestNode();
+		if (pNode != NULL) {
+			/* walk through the path back to the origin */
+			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;              ///< the pathfinder class (derived from THIS class)
+	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:
+	/** to access inherited path finder */
+	Tpf& Yapf()
+	{
+		return *static_cast<Tpf*>(this);
+	}
+
+public:
+	/** Called by YAPF to calculate the cost from the origin to the given node.
+	 *  Calculates only the cost of given node, adds it to the parent node cost
+	 *  and stores the result into Node::m_cost member */
+	FORCEINLINE bool PfCalcCost(Node& n, const TrackFollower *tf)
+	{
+		/* base tile cost depending on distance */
+		int c = IsDiagonalTrackdir(n.GetTrackdir()) ? YAPF_TILE_LENGTH : YAPF_TILE_CORNER_LENGTH;
+		/* additional penalty for curves */
+		if (n.m_parent != NULL && n.GetTrackdir() != NextTrackdir(n.m_parent->GetTrackdir())) {
+			/* new trackdir does not match the next one when going straight */
+			c += YAPF_TILE_LENGTH;
+		}
+
+		c += YAPF_TILE_LENGTH * tf->m_tiles_skipped;
+
+		/* 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(const Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+{
+	/* default is YAPF type 2 */
+	typedef Trackdir (*PfnChooseShipTrack)(const Vehicle*, TileIndex, DiagDirection, TrackBits);
+	PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg
+
+	/* check if non-default YAPF type needed */
+	if (_settings_game.pf.forbid_90_deg) {
+		pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg
+	} else if (_settings_game.pf.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;
+}