1

/* $Id$ */

     2

     3

#include "../stdafx.h"

     4

     5

#include "yapf.hpp"

     6

#include "yapf_node_rail.hpp"

     7

#include "yapf_costrail.hpp"

     8

#include "yapf_destrail.hpp"

     9

    10

int _total_pf_time_us = 0;

    11

    12

    13

    14

    15

    16

template <class Types>

    17

class CYapfFollowAnyDepotRailT

    18

{

    19

public:

    20

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

    21

	typedef typename Types::TrackFollower TrackFollower;

    22

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

    23

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

    24

    25

protected:

    26

	/// to access inherited path finder

    27

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

    28

    29

public:

    30

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

    31

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

    32

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

    33

	inline void PfFollowNode(Node& old_node)

    34

	{

    35

		TrackFollower F(Yapf().GetVehicle());

    36

		if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))

    37

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

    38

	}

    39

    40

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

    41

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

    42

    43

	static bool stFindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)

    44

	{

    45

		Tpf pf;

    46

		return pf.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed);

    47

	}

    48

    49

	FORCEINLINE bool FindNearestDepotTwoWay(Vehicle *v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)

    50

	{

    51

		// set origin and destination nodes

    52

		Yapf().SetOrigin(t1, td1, t2, td2, reverse_penalty, true);

    53

		Yapf().SetDestination(v);

    54

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

    55

    56

		// find the best path

    57

		bool bFound = Yapf().FindPath(v);

    58

		if (!bFound) return false;

    59

    60

		// some path found

    61

		// get found depot tile

    62

		Node& n = Yapf().GetBestNode();

    63

		*depot_tile = n.GetLastTile();

    64

    65

		// walk through the path back to the origin

    66

		Node* pNode = &n;

    67

		while (pNode->m_parent != NULL) {

    68

			pNode = pNode->m_parent;

    69

		}

    70

    71

		// if the origin node is our front vehicle tile/Trackdir then we didn't reverse

    72

		// but we can also look at the cost (== 0 -> not reversed, == reverse_penalty -> reversed)

    73

		*reversed = (pNode->m_cost != 0);

    74

    75

		return true;

    76

	}

    77

};

    78

    79

template <class Types>

    80

class CYapfFollowRailT

    81

{

    82

public:

    83

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

    84

	typedef typename Types::TrackFollower TrackFollower;

    85

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

    86

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

    87

    88

protected:

    89

	/// to access inherited path finder

    90

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

    91

    92

public:

    93

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

    94

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

    95

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

    96

	inline void PfFollowNode(Node& old_node)

    97

	{

    98

		TrackFollower F(Yapf().GetVehicle());

    99

		if (F.Follow(old_node.GetLastTile(), old_node.GetLastTrackdir()))

   100

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

   101

	}

   102

   103

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

   104

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

   105

   106

	static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)

   107

	{

   108

		// create pathfinder instance

   109

		Tpf pf;

   110

		return pf.ChooseRailTrack(v, tile, enterdir, trackdirs);

   111

	}

   112

   113

	FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)

   114

	{

   115

		// set origin and destination nodes

   116

		Yapf().SetOrigin(v->tile, GetVehicleTrackdir(v), INVALID_TILE, INVALID_TRACKDIR, 1, true);

   117

		Yapf().SetDestination(v);

   118

   119

		// find the best path

   120

		Yapf().FindPath(v);

   121

   122

		// if path not found - return INVALID_TRACKDIR

   123

		Trackdir next_trackdir = INVALID_TRACKDIR;

   124

		Node* pNode = &Yapf().GetBestNode();

   125

		if (pNode != NULL) {

   126

			// path was found or at least suggested

   127

			// walk through the path back to the origin

   128

			Node* pPrev = NULL;

   129

			while (pNode->m_parent != NULL) {

   130

				pPrev = pNode;

   131

				pNode = pNode->m_parent;

   132

			}

   133

			// return trackdir from the best origin node (one of start nodes)

   134

			Node& best_next_node = *pPrev;

   135

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

   136

			next_trackdir = best_next_node.GetTrackdir();

   137

		}

   138

		return next_trackdir;

   139

	}

   140

   141

	static bool stCheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)

   142

	{

   143

		Tpf pf;

   144

		return pf.CheckReverseTrain(v, t1, td1, t2, td2);

   145

	}

   146

   147

	FORCEINLINE bool CheckReverseTrain(Vehicle* v, TileIndex t1, Trackdir td1, TileIndex t2, Trackdir td2)

   148

	{

   149

		// create pathfinder instance

   150

		// set origin and destination nodes

   151

		Yapf().SetOrigin(t1, td1, t2, td2, 1, false);

   152

		Yapf().SetDestination(v);

   153

   154

		// find the best path

   155

		bool bFound = Yapf().FindPath(v);

   156

   157

		if (!bFound) return false;

   158

   159

		// path was found

   160

		// walk through the path back to the origin

   161

		Node* pNode = &Yapf().GetBestNode();

   162

		while (pNode->m_parent != NULL) {

   163

			pNode = pNode->m_parent;

   164

		}

   165

   166

		// check if it was reversed origin

   167

		Node& best_org_node = *pNode;

   168

		bool reversed = (best_org_node.m_cost != 0);

   169

		return reversed;

   170

	}

   171

};

   172

   173

template <class Tpf_, class Ttrack_follower, class Tnode_list, template <class Types> class TdestinationT, template <class Types> class TfollowT>

   174

struct CYapfRail_TypesT

   175

{

   176

	typedef CYapfRail_TypesT<Tpf_, Ttrack_follower, Tnode_list, TdestinationT, TfollowT>  Types;

   177

   178

	typedef Tpf_                                Tpf;

   179

	typedef Ttrack_follower                     TrackFollower;

   180

	typedef Tnode_list                          NodeList;

   181

	typedef CYapfBaseT<Types>                   PfBase;

   182

	typedef TfollowT<Types>                     PfFollow;

   183

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   184

	typedef TdestinationT<Types>                PfDestination;

   185

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   186

	typedef CYapfCostRailT<Types>               PfCost;

   187

};

   188

   189

struct CYapfRail1         : CYapfT<CYapfRail_TypesT<CYapfRail1        , CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

   190

struct CYapfRail2         : CYapfT<CYapfRail_TypesT<CYapfRail2        , CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

   191

struct CYapfRail3         : CYapfT<CYapfRail_TypesT<CYapfRail3        , CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationTileOrStationRailT, CYapfFollowRailT> > {};

   192

   193

struct CYapfAnyDepotRail1 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail1, CFollowTrackRail    , CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

   194

struct CYapfAnyDepotRail2 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail2, CFollowTrackRail    , CRailNodeListExitDir , CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

   195

struct CYapfAnyDepotRail3 : CYapfT<CYapfRail_TypesT<CYapfAnyDepotRail3, CFollowTrackRailNo90, CRailNodeListTrackDir, CYapfDestinationAnyDepotRailT     , CYapfFollowAnyDepotRailT> > {};

   196

   197

   198

Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)

   199

{

   200

	// default is YAPF type 2

   201

	typedef Trackdir (*PfnChooseRailTrack)(Vehicle*, TileIndex, DiagDirection, TrackdirBits);

   202

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   203

   204

	// check if non-default YAPF type needed

   205

	if (_patches.forbid_90_deg)

   206

		pfnChooseRailTrack = &CYapfRail3::stChooseRailTrack; // Trackdir, forbid 90-deg

   207

	else if (_patches.yapf.disable_node_optimization)

   208

		pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack; // Trackdir, allow 90-deg

   209

   210

	Trackdir td_ret = pfnChooseRailTrack(v, tile, enterdir, trackdirs);

   211

   212

	return td_ret;

   213

}

   214

   215

bool YapfCheckReverseTrain(Vehicle* v)

   216

{

   217

	// tile where the engine is

   218

	TileIndex tile = v->tile;

   219

	// tile where we have last wagon

   220

	Vehicle* last_veh = GetLastVehicleInChain(v);

   221

	// if we are in tunnel then give up

   222

	if (v->u.rail.track == 0x40 || last_veh->u.rail.track == 0x40) return false;

   223

	// get trackdirs of both ends

   224

	Trackdir td = GetVehicleTrackdir(v);

   225

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   226

   227

   228

	typedef bool (*PfnCheckReverseTrain)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir);

   229

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   230

   231

	// check if non-default YAPF type needed

   232

	if (_patches.forbid_90_deg)

   233

		pfnCheckReverseTrain = &CYapfRail3::stCheckReverseTrain; // Trackdir, forbid 90-deg

   234

	else if (_patches.yapf.disable_node_optimization)

   235

		pfnCheckReverseTrain = &CYapfRail1::stCheckReverseTrain; // Trackdir, allow 90-deg

   236

   237

	bool reverse = pfnCheckReverseTrain(v, tile, td, last_veh->tile, td_rev);

   238

   239

	return reverse;

   240

}

   241

   242

bool YapfFindNearestRailDepotTwoWay(Vehicle *v, int max_distance, int reverse_penalty, TileIndex* depot_tile, bool* reversed)

   243

{

   244

	*depot_tile = INVALID_TILE;

   245

	*reversed = false;

   246

   247

	Vehicle* last_veh = GetLastVehicleInChain(v);

   248

   249

	bool first_in_tunnel = v->u.rail.track == 0x40;

   250

	bool last_in_tunnel = last_veh->u.rail.track == 0x40;

   251

   252

	// tile where the engine and last wagon are

   253

	TileIndex tile = first_in_tunnel ? INVALID_TILE : v->tile;

   254

	TileIndex last_tile = last_in_tunnel ? INVALID_TILE : last_veh->tile;

   255

   256

	// their trackdirs

   257

	Trackdir td = first_in_tunnel ? INVALID_TRACKDIR : GetVehicleTrackdir(v);

   258

	Trackdir td_rev = last_in_tunnel ? INVALID_TRACKDIR : ReverseTrackdir(GetVehicleTrackdir(last_veh));

   259

   260

	typedef bool (*PfnFindNearestDepotTwoWay)(Vehicle*, TileIndex, Trackdir, TileIndex, Trackdir, int, int, TileIndex*, bool*);

   261

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;

   262

   263

	// check if non-default YAPF type needed

   264

	if (_patches.forbid_90_deg)

   265

		pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail3::stFindNearestDepotTwoWay; // Trackdir, forbid 90-deg

   266

	else if (_patches.yapf.disable_node_optimization)

   267

		pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay; // Trackdir, allow 90-deg

   268

   269

	bool ret = pfnFindNearestDepotTwoWay(v, tile, td, last_tile, td_rev, max_distance, reverse_penalty, depot_tile, reversed);

   270

	return ret;

   271

}

   272

   273

/** if any track changes, this counter is incremented - that will invalidate segment cost cache */

   274

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   275

   276

void YapfNotifyTrackLayoutChange(TileIndex tile, Track track) {CSegmentCostCacheBase::NotifyTrackLayoutChange(tile, track);}