1

/* $Id$ */

     2

     3

/** @file yapf_ship.cpp */

     4

     5

#include "../stdafx.h"

     6

     7

#include "yapf.hpp"

     8

     9

/** Node Follower module of YAPF for ships */

    10

template <class Types>

    11

class CYapfFollowShipT

    12

{

    13

public:

    14

	typedef typename Types::Tpf Tpf;                     ///< the pathfinder class (derived from THIS class)

    15

	typedef typename Types::TrackFollower TrackFollower;

    16

	typedef typename Types::NodeList::Titem Node;        ///< this will be our node type

    17

	typedef typename Node::Key Key;                      ///< key to hash tables

    18

    19

protected:

    20

	/// to access inherited path finder

    21

	FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);}

    22

    23

public:

    24

	/** Called by YAPF to move from the given node to the next tile. For each

    25

	 *  reachable trackdir on the new tile creates new node, initializes it

    26

	 *  and adds it to the open list by calling Yapf().AddNewNode(n) */

    27

	inline void PfFollowNode(Node& old_node)

    28

	{

    29

		TrackFollower F;

    30

		if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td))

    31

			Yapf().AddMultipleNodes(&old_node, F);

    32

	}

    33

    34

	/// return debug report character to identify the transportation type

    35

	FORCEINLINE char TransportTypeChar() const {return 'w';}

    36

    37

	static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)

    38

	{

    39

		// handle special case - when next tile is destination tile

    40

		if (tile == v->dest_tile) {

    41

			// convert tracks to trackdirs

    42

			TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8));

    43

			// choose any trackdir reachable from enterdir

    44

			trackdirs &= DiagdirReachesTrackdirs(enterdir);

    45

			return (Trackdir)FindFirstBit2x64(trackdirs);

    46

		}

    47

    48

		// move back to the old tile/trackdir (where ship is coming from)

    49

		TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir)));

    50

		Trackdir trackdir = GetVehicleTrackdir(v);

    51

		assert(IsValidTrackdir(trackdir));

    52

    53

		// convert origin trackdir to TrackdirBits

    54

		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);

    55

		// get available trackdirs on the destination tile

    56

		TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK);

    57

    58

		// create pathfinder instance

    59

		Tpf pf;

    60

		// set origin and destination nodes

    61

		pf.SetOrigin(src_tile, trackdirs);

    62

		pf.SetDestination(v->dest_tile, dest_trackdirs);

    63

		// find best path

    64

		bool bFound = pf.FindPath(v);

    65

    66

		Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found"

    67

		if (bFound) {

    68

			// path was found

    69

			// walk through the path back to the origin

    70

			Node* pNode = &pf.GetBestNode();

    71

			Node* pPrevNode = NULL;

    72

			while (pNode->m_parent != NULL) {

    73

				pPrevNode = pNode;

    74

				pNode = pNode->m_parent;

    75

			}

    76

			// return trackdir from the best next node (direct child of origin)

    77

			Node& best_next_node = *pPrevNode;

    78

			assert(best_next_node.GetTile() == tile);

    79

			next_trackdir = best_next_node.GetTrackdir();

    80

		}

    81

		return next_trackdir;

    82

	}

    83

};

    84

    85

/** Cost Provider module of YAPF for ships */

    86

template <class Types>

    87

class CYapfCostShipT

    88

{

    89

public:

    90

	typedef typename Types::Tpf Tpf;              ///< the pathfinder class (derived from THIS class)

    91

	typedef typename Types::TrackFollower TrackFollower;

    92

	typedef typename Types::NodeList::Titem Node; ///< this will be our node type

    93

	typedef typename Node::Key Key;               ///< key to hash tables

    94

    95

protected:

    96

	/// to access inherited path finder

    97

	Tpf& Yapf() {return *static_cast<Tpf*>(this);}

    98

    99

public:

   100

	/** Called by YAPF to calculate the cost from the origin to the given node.

   101

	 *  Calculates only the cost of given node, adds it to the parent node cost

   102

	 *  and stores the result into Node::m_cost member */

   103

	FORCEINLINE bool PfCalcCost(Node& n, const TrackFollower &tf)

   104

	{

   105

		// base tile cost depending on distance

   106

		int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7;

   107

		// additional penalty for curves

   108

		if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3;

   109

		// apply it

   110

		n.m_cost = n.m_parent->m_cost + c;

   111

		return true;

   112

	}

   113

};

   114

   115

/** Config struct of YAPF for ships.

   116

 *  Defines all 6 base YAPF modules as classes providing services for CYapfBaseT.

   117

 */

   118

template <class Tpf_, class Ttrack_follower, class Tnode_list>

   119

struct CYapfShip_TypesT

   120

{

   121

	/** Types - shortcut for this struct type */

   122

	typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;

   123

   124

	/** Tpf - pathfinder type */

   125

	typedef Tpf_                              Tpf;

   126

	/** track follower helper class */

   127

	typedef Ttrack_follower                   TrackFollower;

   128

	/** node list type */

   129

	typedef Tnode_list                        NodeList;

   130

	/** pathfinder components (modules) */

   131

	typedef CYapfBaseT<Types>                 PfBase;        // base pathfinder class

   132

	typedef CYapfFollowShipT<Types>           PfFollow;      // node follower

   133

	typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider

   134

	typedef CYapfDestinationTileT<Types>      PfDestination; // destination/distance provider

   135

	typedef CYapfSegmentCostCacheNoneT<Types> PfCache;       // segment cost cache provider

   136

	typedef CYapfCostShipT<Types>             PfCost;        // cost provider

   137

};

   138

   139

// YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns

   140

struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater    , CShipNodeListTrackDir> > {};

   141

// YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns

   142

struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater    , CShipNodeListExitDir > > {};

   143

// YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns

   144

struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {};

   145

   146

/** Ship controller helper - path finder invoker */

   147

Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)

   148

{

   149

	// default is YAPF type 2

   150

	typedef Trackdir (*PfnChooseShipTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits);

   151

	PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg

   152

   153

	// check if non-default YAPF type needed

   154

	if (_patches.forbid_90_deg)

   155

		pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg

   156

	else if (_patches.yapf.disable_node_optimization)

   157

		pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg

   158

   159

	Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks);

   160

	return td_ret;

   161

}

   162

   163

/** performance measurement helper */

   164

void* NpfBeginInterval()

   165

{

   166

	CPerformanceTimer& perf = *new CPerformanceTimer;

   167

	perf.Start();

   168

	return &perf;

   169

}

   170

   171

/** performance measurement helper */

   172

int NpfEndInterval(void* vperf)

   173

{

   174

	CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;

   175

	perf.Stop();

   176

	int t = perf.Get(1000000);

   177

	delete &perf;

   178

	return t;

   179

}