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

    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, bool *path_not_found)

   107

	{

   108

		// create pathfinder instance

   109

		Tpf pf;

   110

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

   111

	}

   112

   113

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

   114

	{

   115

		// set origin and destination nodes

   124

		Yapf().SetDestination(v);

   125

   126

		// find the best path

   127

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

   128

		if (!path_found && path_not_found != NULL) {

   129

			// tell controller that the path was only 'guessed'

   130

			*path_not_found = !path_found;

   131

		}

   132

   133

		// if path not found - return INVALID_TRACKDIR

   134

		Trackdir next_trackdir = INVALID_TRACKDIR;

   135

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

   136

		if (pNode != NULL) {

   137

			// path was found or at least suggested

   138

			// walk through the path back to the origin

   139

			Node* pPrev = NULL;

   140

			while (pNode->m_parent != NULL) {

   141

				pPrev = pNode;

   142

				pNode = pNode->m_parent;

   143

			}

   144

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

   147

			next_trackdir = best_next_node.GetTrackdir();

   148

		}

   149

		return next_trackdir;

   150

	}

   151

   152

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

   153

	{

   154

		Tpf pf;

   155

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

   156

	}

   157

   158

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

   159

	{

   160

		// create pathfinder instance

   161

		// set origin and destination nodes

   163

		Yapf().SetDestination(v);

   164

   165

		// find the best path

   166

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

   167

   168

		if (!bFound) return false;

   169

   170

		// path was found

   171

		// walk through the path back to the origin

   172

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

   173

		while (pNode->m_parent != NULL) {

   174

			pNode = pNode->m_parent;

   175

		}

   176

   177

		// check if it was reversed origin

   178

		Node& best_org_node = *pNode;

   179

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

   180

		return reversed;

   181

	}

   182

};

   183

   184

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

   185

struct CYapfRail_TypesT

   186

{

   187

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

   188

   189

	typedef Tpf_                                Tpf;

   190

	typedef Ttrack_follower                     TrackFollower;

   191

	typedef Tnode_list                          NodeList;

   192

	typedef CYapfBaseT<Types>                   PfBase;

   193

	typedef TfollowT<Types>                     PfFollow;

   194

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   195

	typedef TdestinationT<Types>                PfDestination;

   196

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   197

	typedef CYapfCostRailT<Types>               PfCost;

   198

};

   199

   200

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

   201

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

   202

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

   203

   204

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

   205

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

   206

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

   207

   208

   209

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

   210

{

   211

	// default is YAPF type 2

   212

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

   213

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   214

   215

	// check if non-default YAPF type needed

   216

	if (_patches.forbid_90_deg)

   217

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

   218

	else if (_patches.yapf.disable_node_optimization)

   219

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

   220

   221

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

   222

   223

	return td_ret;

   224

}

   225

   226

bool YapfCheckReverseTrain(Vehicle* v)

   227

{

   228

	// tile where the engine is

   229

	TileIndex tile = v->tile;

   230

	// tile where we have last wagon

   231

	Vehicle* last_veh = GetLastVehicleInChain(v);

   232

	// if we are in tunnel then give up

   233

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

   234

	// get trackdirs of both ends

   235

	Trackdir td = GetVehicleTrackdir(v);

   236

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   237

   238

   239

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

   240

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   241

   242

	// check if non-default YAPF type needed

   243

	if (_patches.forbid_90_deg)

   244

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

   245

	else if (_patches.yapf.disable_node_optimization)

   246

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

   247

   248

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

   249

   250

	return reverse;

   251

}

   252

   253

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

   254

{

   255

	*depot_tile = INVALID_TILE;

   256

	*reversed = false;

   257

   258

	Vehicle* last_veh = GetLastVehicleInChain(v);

   259

   260

	TileIndex tile = v->tile;

   261

	TileIndex last_tile = last_veh->tile;

   262

   263

	// their trackdirs

   264

	Trackdir td = GetVehicleTrackdir(v);

   265

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   266

   267

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

   268

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;

   269

   270

	// check if non-default YAPF type needed

   271

	if (_patches.forbid_90_deg)

   272

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

   273

	else if (_patches.yapf.disable_node_optimization)

   274

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

   275

   276

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

   277

	return ret;

   278

}

   279

   280

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

   281

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   282

   283

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