1

/* $Id$ */

     2

     3

/** @file yapf_rail.cpp */

     4

     5

#include "../stdafx.h"

     6

     7

#include "yapf.hpp"

     8

#include "yapf_node_rail.hpp"

     9

#include "yapf_costrail.hpp"

    10

#include "yapf_destrail.hpp"

    11

    12

int _total_pf_time_us = 0;

    13

    14

    15

    16

    17

    18

template <class Types>

    19

class CYapfFollowAnyDepotRailT

    20

{

    21

public:

    22

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

    23

	typedef typename Types::TrackFollower TrackFollower;

    24

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

    25

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

    26

    27

protected:

    28

	/// to access inherited path finder

    29

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

    30

    31

public:

    32

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

    33

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

    34

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

    35

	inline void PfFollowNode(Node& old_node)

    36

	{

    37

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

    38

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

    39

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

    40

	}

    41

    42

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

    43

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

    44

    45

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

    46

	{

    47

		Tpf pf;

    48

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

    49

	}

    50

    51

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

    52

	{

    53

		// set origin and destination nodes

    54

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

    55

		Yapf().SetDestination(v);

    56

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

    57

    58

		// find the best path

    59

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

    60

		if (!bFound) return false;

    61

    62

		// some path found

    63

		// get found depot tile

    66

    67

		// walk through the path back to the origin

    69

		while (pNode->m_parent != NULL) {

    70

			pNode = pNode->m_parent;

    71

		}

    72

    73

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

    74

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

    75

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

    76

    77

		return true;

    78

	}

    79

};

    80

    81

template <class Types>

    82

class CYapfFollowRailT

    83

{

    84

public:

    85

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

    86

	typedef typename Types::TrackFollower TrackFollower;

    87

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

    88

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

    89

    90

protected:

    91

	/// to access inherited path finder

    92

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

    93

    94

public:

    95

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

    96

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

    97

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

    98

	inline void PfFollowNode(Node& old_node)

    99

	{

   100

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

   101

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

   102

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

   103

	}

   104

   105

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

   106

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

   107

   108

	static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

   109

	{

   110

		// create pathfinder instance

   111

		Tpf pf;

   112

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

   113

	}

   114

   115

	FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

   116

	{

   117

		// set origin and destination nodes

   118

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

   119

		Yapf().SetDestination(v);

   120

   121

		// find the best path

   122

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

   123

		if (path_not_found != NULL) {

   124

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

   125

			// treat the path as found if stopped on the first two way signal(s)

   126

			*path_not_found = !(path_found || Yapf().m_stopped_on_first_two_way_signal);

   127

		}

   128

   129

		// if path not found - return INVALID_TRACKDIR

   130

		Trackdir next_trackdir = INVALID_TRACKDIR;

   132

		if (pNode != NULL) {

   133

			// path was found or at least suggested

   134

			// walk through the path back to the origin

   135

			Node* pPrev = NULL;

   136

			while (pNode->m_parent != NULL) {

   137

				pPrev = pNode;

   138

				pNode = pNode->m_parent;

   139

			}

   140

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

   141

			Node& best_next_node = *pPrev;

   142

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

   143

			next_trackdir = best_next_node.GetTrackdir();

   144

		}

   145

		return next_trackdir;

   146

	}

   147

   148

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

   149

	{

   150

		Tpf pf;

   151

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

   152

	}

   153

   154

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

   155

	{

   156

		// create pathfinder instance

   157

		// set origin and destination nodes

   158

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

   159

		Yapf().SetDestination(v);

   160

   161

		// find the best path

   162

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

   163

   164

		if (!bFound) return false;

   165

   166

		// path was found

   167

		// walk through the path back to the origin

   169

		while (pNode->m_parent != NULL) {

   170

			pNode = pNode->m_parent;

   171

		}

   172

   173

		// check if it was reversed origin

   174

		Node& best_org_node = *pNode;

   175

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

   176

		return reversed;

   177

	}

   178

};

   179

   180

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

   181

struct CYapfRail_TypesT

   182

{

   183

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

   184

   185

	typedef Tpf_                                Tpf;

   186

	typedef Ttrack_follower                     TrackFollower;

   187

	typedef Tnode_list                          NodeList;

   188

	typedef CYapfBaseT<Types>                   PfBase;

   189

	typedef TfollowT<Types>                     PfFollow;

   190

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   191

	typedef TdestinationT<Types>                PfDestination;

   192

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   193

	typedef CYapfCostRailT<Types>               PfCost;

   194

};

   195

   196

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

   197

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

   198

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

   199

   200

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

   201

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

   202

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

   203

   204

   205

Trackdir YapfChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks, bool *path_not_found)

   206

{

   207

	// default is YAPF type 2

   208

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

   209

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   210

   211

	// check if non-default YAPF type needed

   212

	if (_patches.forbid_90_deg)

   213

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

   214

	else if (_patches.yapf.disable_node_optimization)

   215

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

   216

   217

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

   218

   219

	return td_ret;

   220

}

   221

   222

bool YapfCheckReverseTrain(Vehicle* v)

   223

{

   224

	// tile where the engine is

   225

	TileIndex tile = v->tile;

   226

	// tile where we have last wagon

   227

	Vehicle* last_veh = GetLastVehicleInChain(v);

   228

	// if we are in tunnel then give up

   229

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

   230

	// get trackdirs of both ends

   231

	Trackdir td = GetVehicleTrackdir(v);

   232

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   233

   234

   235

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

   236

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   237

   238

	// check if non-default YAPF type needed

   239

	if (_patches.forbid_90_deg)

   240

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

   241

	else if (_patches.yapf.disable_node_optimization)

   242

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

   243

   244

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

   245

   246

	return reverse;

   247

}

   248

   249

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

   250

{

   251

	*depot_tile = INVALID_TILE;

   252

	*reversed = false;

   253

   254

	Vehicle* last_veh = GetLastVehicleInChain(v);

   255

   256

	TileIndex tile = v->tile;

   257

	TileIndex last_tile = last_veh->tile;

   258

   259

	// their trackdirs

   260

	Trackdir td = GetVehicleTrackdir(v);

   261

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   262

   263

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

   264

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;

   265

   266

	// check if non-default YAPF type needed

   267

	if (_patches.forbid_90_deg)

   268

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

   269

	else if (_patches.yapf.disable_node_optimization)

   270

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

   271

   272

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

   273

	return ret;

   274

}

   275

   276

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

   277

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   278

   279

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