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

#define DEBUG_YAPF_CACHE 0

    13

    14

int _total_pf_time_us = 0;

    15

    16

    17

    18

    19

    20

template <class Types>

    21

class CYapfFollowAnyDepotRailT

    22

{

    23

public:

    24

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

    25

	typedef typename Types::TrackFollower TrackFollower;

    26

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

    27

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

    28

    29

protected:

    30

	/// to access inherited path finder

    31

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

    32

    33

public:

    34

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

    35

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

    36

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

    37

	inline void PfFollowNode(Node& old_node)

    38

	{

    39

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

    40

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

    41

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

    42

	}

    43

    44

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

    45

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

    46

    47

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

    48

	{

    49

		Tpf pf1;

    50

		bool result1 = pf1.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, depot_tile, reversed);

    51

    52

#if DEBUG_YAPF_CACHE

    53

		Tpf pf2;

    54

		TileIndex depot_tile2 = INVALID_TILE;

    55

		bool reversed2 = false;

    56

		pf2.DisableCache(true);

    57

		bool result2 = pf2.FindNearestDepotTwoWay(v, t1, td1, t2, td2, max_distance, reverse_penalty, &depot_tile2, &reversed2);

    58

		if (result1 != result2 || (result1 && (*depot_tile != depot_tile2 || *reversed != reversed2))) {

    59

			DEBUG(yapf, 0, "CACHE ERROR: FindNearestDepotTwoWay() = [%s, %s]", result1 ? "T" : "F", result2 ? "T" : "F");

    60

		}

    61

#endif

    62

    63

		return result1;

    64

	}

    65

    66

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

    67

	{

    68

		// set origin and destination nodes

    69

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

    70

		Yapf().SetDestination(v);

    71

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

    72

    73

		// find the best path

    74

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

    75

		if (!bFound) return false;

    76

    77

		// some path found

    78

		// get found depot tile

    79

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

    80

		*depot_tile = n->GetLastTile();

    81

    82

		// walk through the path back to the origin

    83

		Node *pNode = n;

    84

		while (pNode->m_parent != NULL) {

    85

			pNode = pNode->m_parent;

    86

		}

    87

    88

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

    89

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

    90

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

    91

    92

		return true;

    93

	}

    94

};

    95

    96

template <class Types>

    97

class CYapfFollowRailT

    98

{

    99

public:

   100

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

   101

	typedef typename Types::TrackFollower TrackFollower;

   102

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

   103

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

   104

   105

protected:

   106

	/// to access inherited path finder

   107

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

   108

   109

public:

   110

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

   111

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

   112

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

   113

	inline void PfFollowNode(Node& old_node)

   114

	{

   115

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

   116

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

   117

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

   118

	}

   119

   120

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

   121

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

   122

   123

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

   124

	{

   125

		// create pathfinder instance

   126

		Tpf pf1;

   127

		Trackdir result1 = pf1.ChooseRailTrack(v, tile, enterdir, tracks, path_not_found);

   128

   129

#if DEBUG_YAPF_CACHE

   130

		Tpf pf2;

   131

		pf2.DisableCache(true);

   132

		Trackdir result2 = pf2.ChooseRailTrack(v, tile, enterdir, tracks, path_not_found);

   133

		if (result1 != result2) {

   134

			DEBUG(yapf, 0, "CACHE ERROR: ChooseRailTrack() = [%d, %d]", result1, result2);

   144

		}

   145

#endif

   146

   147

		return result1;

   148

	}

   149

   150

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

   151

	{

   152

		// set origin and destination nodes

   153

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

   154

		Yapf().SetDestination(v);

   155

   156

		// find the best path

   157

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

   158

		if (path_not_found != NULL) {

   159

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

   160

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

   161

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

   162

		}

   163

   164

		// if path not found - return INVALID_TRACKDIR

   165

		Trackdir next_trackdir = INVALID_TRACKDIR;

   166

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

   167

		if (pNode != NULL) {

   168

			// path was found or at least suggested

   169

			// walk through the path back to the origin

   170

			Node* pPrev = NULL;

   171

			while (pNode->m_parent != NULL) {

   172

				pPrev = pNode;

   173

				pNode = pNode->m_parent;

   174

			}

   175

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

   176

			Node& best_next_node = *pPrev;

   177

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

   178

			next_trackdir = best_next_node.GetTrackdir();

   179

		}

   180

		return next_trackdir;

   181

	}

   182

   183

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

   184

	{

   185

		Tpf pf1;

   186

		bool result1 = pf1.CheckReverseTrain(v, t1, td1, t2, td2);

   187

   188

#if DEBUG_YAPF_CACHE

   189

		Tpf pf2;

   190

		pf2.DisableCache(true);

   191

		bool result2 = pf2.CheckReverseTrain(v, t1, td1, t2, td2);

   192

		if (result1 != result2) {

   193

			DEBUG(yapf, 0, "CACHE ERROR: CheckReverseTrain() = [%s, %s]", result1 ? "T" : "F", result2 ? "T" : "F");

   194

		}

   195

#endif

   196

   197

		return result1;

   198

	}

   199

   200

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

   201

	{

   202

		// create pathfinder instance

   203

		// set origin and destination nodes

   204

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

   205

		Yapf().SetDestination(v);

   206

   207

		// find the best path

   208

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

   209

   210

		if (!bFound) return false;

   211

   212

		// path was found

   213

		// walk through the path back to the origin

   214

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

   215

		while (pNode->m_parent != NULL) {

   216

			pNode = pNode->m_parent;

   217

		}

   218

   219

		// check if it was reversed origin

   220

		Node& best_org_node = *pNode;

   221

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

   222

		return reversed;

   223

	}

   224

};

   225

   226

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

   227

struct CYapfRail_TypesT

   228

{

   229

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

   230

   231

	typedef Tpf_                                Tpf;

   232

	typedef Ttrack_follower                     TrackFollower;

   233

	typedef Tnode_list                          NodeList;

   234

	typedef CYapfBaseT<Types>                   PfBase;

   235

	typedef TfollowT<Types>                     PfFollow;

   236

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   237

	typedef TdestinationT<Types>                PfDestination;

   238

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   239

	typedef CYapfCostRailT<Types>               PfCost;

   240

};

   241

   242

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

   243

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

   244

   245

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

   246

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

   247

   248

   249

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

   250

{

   251

	// default is YAPF type 2

   252

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

   253

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;

   254

   255

	// check if non-default YAPF type needed

   256

	if (_patches.forbid_90_deg) {

   257

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

   258

	}

   259

   260

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

   261

   262

	return td_ret;

   263

}

   264

   265

bool YapfCheckReverseTrain(Vehicle* v)

   266

{

   267

	// tile where the engine is

   268

	TileIndex tile = v->tile;

   269

	// tile where we have last wagon

   270

	Vehicle* last_veh = GetLastVehicleInChain(v);

   271

	// if we are in tunnel then give up

   272

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

   273

	// get trackdirs of both ends

   274

	Trackdir td = GetVehicleTrackdir(v);

   275

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   276

   277

   278

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

   279

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;

   280

   281

	// check if non-default YAPF type needed

   282

	if (_patches.forbid_90_deg) {

   283

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

   284

	}

   285

   286

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

   287

   288

	return reverse;

   289

}

   290

   291

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

   292

{

   293

	*depot_tile = INVALID_TILE;

   294

	*reversed = false;

   295

   296

	Vehicle* last_veh = GetLastVehicleInChain(v);

   297

   298

	TileIndex tile = v->tile;

   299

	TileIndex last_tile = last_veh->tile;

   300

   301

	// their trackdirs

   302

	Trackdir td = GetVehicleTrackdir(v);

   303

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   304

   305

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

   306

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;

   307

   308

	// check if non-default YAPF type needed

   309

	if (_patches.forbid_90_deg) {

   310

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

   311

	}

   312

   313

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

   314

	return ret;

   315

}

   316

   317

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

   318

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   319

   320

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