1

/* $Id$ */

     2

     3

#include "../stdafx.h"

     4

     5

#include "yapf.hpp"

     6

     7

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

     8

template <class Types>

     9

class CYapfFollowShipT

    10

{

    11

public:

    12

	typedef typename Types::Tpf Tpf;

    13

	typedef typename Types::TrackFollower TrackFollower;

    14

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

    15

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

    16

    17

protected:

    18

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

    19

    20

public:

    21

	inline void PfFollowNode(Node& old_node)

    22

	{

    23

		TrackFollower F;

    24

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

    25

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

    26

	}

    27

    28

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

    29

    30

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

    31

	{

    32

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

    33

		if (tile == v->dest_tile) {

    34

			// convert tracks to trackdirs

    35

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

    36

			// choose any trackdir reachable from enterdir

    37

			trackdirs &= DiagdirReachesTrackdirs(enterdir);

    38

			return (Trackdir)FindFirstBit2x64(trackdirs);

    39

		}

    40

    41

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

    42

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

    43

		Trackdir trackdir = GetVehicleTrackdir(v);

    44

		assert(IsValidTrackdir(trackdir));

    45

    46

		// convert origin trackdir to TrackdirBits

    47

		TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir);

    48

		// get available trackdirs on the destination tile

    49

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

    50

    51

		// create pathfinder instance

    52

		Tpf pf;

    53

		// set origin and destination nodes

    54

		pf.SetOrigin(src_tile, trackdirs);

    55

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

    56

		// find best path

    57

		bool bFound = pf.FindPath(v);

    58

    59

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

    60

		if (bFound) {

    61

			// path was found

    62

			// walk through the path back to the origin

    63

			Node* pNode = &pf.GetBestNode();

    64

			Node* pPrevNode = NULL;

    65

			while (pNode->m_parent != NULL) {

    66

				pPrevNode = pNode;

    67

				pNode = pNode->m_parent;

    68

			}

    69

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

    70

			Node& best_next_node = *pPrevNode;

    71

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

    72

			next_trackdir = best_next_node.GetTrackdir();

    73

		}

    74

		return next_trackdir;

    75

	}

    76

};

    77

    78

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

    79

template <class Types>

    80

class CYapfCostShipT

    81

{

    82

public:

    83

	typedef typename Types::Tpf Tpf;

    84

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

    85

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

    86

    87

protected:

    88

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

    89

    90

public:

    91

	FORCEINLINE bool PfCalcCost(Node& n)

    92

	{

    93

		// base tile cost depending on distance

    94

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

    95

		// additional penalty for curves

    96

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

    97

		// apply it

    98

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

    99

		return true;

   100

	}

   101

};

   102

   103

/** Config struct of YAPF for ships.

   104

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

   105

*/

   106

template <class Tpf_, class Ttrack_follower, class Tnode_list>

   107

struct CYapfShip_TypesT

   108

{

   109

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

   110

	typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list>  Types;

   111

   112

	/** Tpf - pathfinder type */

   113

	typedef Tpf_                              Tpf;

   114

	/** track follower helper class */

   115

	typedef Ttrack_follower                   TrackFollower;

   116

	/** node list type */

   117

	typedef Tnode_list                        NodeList;

   118

	/** pathfinder components (modules) */

   119

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

   120

	typedef CYapfFollowShipT<Types>           PfFollow;      // node follower

   121

	typedef CYapfOriginTileT<Types>           PfOrigin;      // origin provider

   122

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

   123

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

   124

	typedef CYapfCostShipT<Types>             PfCost;        // cost provider

   125

};

   126

   127

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

   128

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

   129

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

   130

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

   131

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

   132

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

   133

   134

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

   135

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

   136

{

   137

	// default is YAPF type 2

   138

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

   139

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

   140

   141

	// check if non-default YAPF type needed

   142

	if (_patches.forbid_90_deg)

   143

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

   144

	else if (_patches.yapf.disable_node_optimization)

   145

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

   146

   147

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

   148

	return td_ret;

   149

}

   150

   151

/** performance measurement helper */

   152

void* NpfBeginInterval()

   153

{

   154

	CPerformanceTimer& perf = *new CPerformanceTimer;

   155

	perf.Start();

   156

	return &perf;

   157

}

   158

   159

/** performance measurement helper */

   160

int NpfEndInterval(void* vperf)

   161

{

   162

	CPerformanceTimer& perf = *(CPerformanceTimer*)vperf;

   163

	perf.Stop();

   164

	int t = perf.Get(1000000);

   165

	delete &perf;

   166

	return t;

   167

}

   168