1

/* $Id$ */

     2

     3

/** @file yapf_rail.cpp The rail pathfinding. */

     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

#include "../vehicle_func.h"

    12

    13

#define DEBUG_YAPF_CACHE 0

    14

    15

int _total_pf_time_us = 0;

    16

    17

    18

    19

    20

    21

template <class Types>

    22

class CYapfFollowAnyDepotRailT

    23

{

    24

public:

    25

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

    26

	typedef typename Types::TrackFollower TrackFollower;

    27

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

    28

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

    29

    30

protected:

    31

	/// to access inherited path finder

    32

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

    33

    34

public:

    35

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

    36

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

    37

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

    38

	inline void PfFollowNode(Node& old_node)

    39

	{

    40

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

    41

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

    42

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

    43

	}

    44

    45

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

    46

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

    47

    48

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

    49

	{

    50

		Tpf pf1;

    51

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

    52

    53

#if DEBUG_YAPF_CACHE

    54

		Tpf pf2;

    55

		TileIndex depot_tile2 = INVALID_TILE;

    56

		bool reversed2 = false;

    57

		pf2.DisableCache(true);

    58

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

    59

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

    60

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

    61

		}

    62

#endif

    63

    64

		return result1;

    65

	}

    66

    67

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

    68

	{

    69

		// set origin and destination nodes

    70

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

    71

		Yapf().SetDestination(v);

    72

		Yapf().SetMaxCost(YAPF_TILE_LENGTH * max_distance);

    73

    74

		// find the best path

    75

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

    76

		if (!bFound) return false;

    77

    78

		// some path found

    79

		// get found depot tile

    80

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

    81

		*depot_tile = n->GetLastTile();

    82

    83

		// walk through the path back to the origin

    84

		Node *pNode = n;

    85

		while (pNode->m_parent != NULL) {

    86

			pNode = pNode->m_parent;

    87

		}

    88

    89

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

    90

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

    91

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

    92

    93

		return true;

    94

	}

    95

};

    96

    97

template <class Types>

    98

class CYapfFollowRailT

    99

{

   100

public:

   101

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

   102

	typedef typename Types::TrackFollower TrackFollower;

   103

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

   104

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

   105

   106

protected:

   107

	/// to access inherited path finder

   108

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

   109

   110

public:

   111

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

   112

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

   113

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

   114

	inline void PfFollowNode(Node& old_node)

   115

	{

   116

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

   117

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

   118

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

   119

	}

   120

   121

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

   122

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

   123

   124

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

   125

	{

   126

		// create pathfinder instance

   127

		Tpf pf1;

   128

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

   129

   130

#if DEBUG_YAPF_CACHE

   131

		Tpf pf2;

   132

		pf2.DisableCache(true);

   133

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

   134

		if (result1 != result2) {

   135

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

   136

			DumpTarget dmp1, dmp2;

   137

			pf1.DumpBase(dmp1);

   138

			pf2.DumpBase(dmp2);

   139

			FILE *f1 = fopen("C:\\yapf1.txt", "wt");

   140

			FILE *f2 = fopen("C:\\yapf2.txt", "wt");

   141

			fwrite(dmp1.m_out.Data(), 1, dmp1.m_out.Size(), f1);

   142

			fwrite(dmp2.m_out.Data(), 1, dmp2.m_out.Size(), f2);

   143

			fclose(f1);

   144

			fclose(f2);

   145

		}

   146

#endif

   147

   148

		return result1;

   149

	}

   150

   151

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

   152

	{

   153

		// set origin and destination nodes

   154

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

   155

		Yapf().SetDestination(v);

   156

   157

		// find the best path

   158

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

   159

		if (path_not_found != NULL) {

   160

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

   161

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

   162

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

   163

		}

   164

   165

		// if path not found - return INVALID_TRACKDIR

   166

		Trackdir next_trackdir = INVALID_TRACKDIR;

   167

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

   168

		if (pNode != NULL) {

   169

			// path was found or at least suggested

   170

			// walk through the path back to the origin

   171

			Node* pPrev = NULL;

   172

			while (pNode->m_parent != NULL) {

   173

				pPrev = pNode;

   174

				pNode = pNode->m_parent;

   175

			}

   176

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

   177

			Node& best_next_node = *pPrev;

   178

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

   179

			next_trackdir = best_next_node.GetTrackdir();

   180

		}

   181

		return next_trackdir;

   182

	}

   183

   184

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

   185

	{

   186

		Tpf pf1;

   187

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

   188

   189

#if DEBUG_YAPF_CACHE

   190

		Tpf pf2;

   191

		pf2.DisableCache(true);

   192

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

   193

		if (result1 != result2) {

   194

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

   195

		}

   196

#endif

   197

   198

		return result1;

   199

	}

   200

   201

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

   202

	{

   203

		// create pathfinder instance

   204

		// set origin and destination nodes

   205

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

   206

		Yapf().SetDestination(v);

   207

   208

		// find the best path

   209

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

   210

   211

		if (!bFound) return false;

   212

   213

		// path was found

   214

		// walk through the path back to the origin

   215

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

   216

		while (pNode->m_parent != NULL) {

   217

			pNode = pNode->m_parent;

   218

		}

   219

   220

		// check if it was reversed origin

   221

		Node& best_org_node = *pNode;

   222

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

   223

		return reversed;

   224

	}

   225

};

   226

   227

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

   228

struct CYapfRail_TypesT

   229

{

   230

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

   231

   232

	typedef Tpf_                                Tpf;

   233

	typedef Ttrack_follower                     TrackFollower;

   234

	typedef Tnode_list                          NodeList;

   235

	typedef CYapfBaseT<Types>                   PfBase;

   236

	typedef TfollowT<Types>                     PfFollow;

   237

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   238

	typedef TdestinationT<Types>                PfDestination;

   239

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   240

	typedef CYapfCostRailT<Types>               PfCost;

   241

};

   242

   243

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

   244

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

   245

   246

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

   247

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

   248

   249

   250

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

   251

{

   252

	// default is YAPF type 2

   253

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

   254

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail1::stChooseRailTrack;

   255

   256

	// check if non-default YAPF type needed

   257

	if (_settings_game.pf.forbid_90_deg) {

   258

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

   259

	}

   260

   261

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

   262

   263

	return td_ret;

   264

}

   265

   266

bool YapfCheckReverseTrain(const Vehicle* v)

   267

{

   268

	/* last wagon */

   269

	const Vehicle *last_veh = GetLastVehicleInChain(v);

   270

   271

	// get trackdirs of both ends

   272

	Trackdir td = GetVehicleTrackdir(v);

   273

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   274

   275

	/* tiles where front and back are */

   276

	TileIndex tile = v->tile;

   277

	TileIndex tile_rev = last_veh->tile;

   278

   279

	int reverse_penalty = 0;

   280

   281

	if (v->u.rail.track == TRACK_BIT_WORMHOLE) {

   282

		/* front in tunnel / on bridge */

   283

		DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile);

   284

   285

		if (TrackdirToExitdir(td) == dir_into_wormhole) tile = GetOtherTunnelBridgeEnd(tile);

   286

		/* Now 'tile' is the tunnel entry/bridge ramp the train will reach when driving forward */

   287

   288

		/* Current position of the train in the wormhole */

   289

		TileIndex cur_tile = TileVirtXY(v->x_pos, v->y_pos);

   290

   291

		/* Add distance to drive in the wormhole as penalty for the forward path, i.e. bonus for the reverse path

   292

		 * Note: Negative penalties are ok for the start tile. */

   293

		reverse_penalty -= DistanceManhattan(cur_tile, tile) * YAPF_TILE_LENGTH;

   294

	}

   295

   296

	if (last_veh->u.rail.track == TRACK_BIT_WORMHOLE) {

   297

		/* back in tunnel / on bridge */

   298

		DiagDirection dir_into_wormhole = GetTunnelBridgeDirection(tile_rev);

   299

   300

		if (TrackdirToExitdir(td_rev) == dir_into_wormhole) tile_rev = GetOtherTunnelBridgeEnd(tile_rev);

   301

		/* Now 'tile_rev' is the tunnel entry/bridge ramp the train will reach when reversing */

   302

   303

		/* Current position of the last wagon in the wormhole */

   304

		TileIndex cur_tile = TileVirtXY(last_veh->x_pos, last_veh->y_pos);

   305

   306

		/* Add distance to drive in the wormhole as penalty for the revere path. */

   307

		reverse_penalty += DistanceManhattan(cur_tile, tile_rev) * YAPF_TILE_LENGTH;

   308

	}

   309

   310

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

   311

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail1::stCheckReverseTrain;

   312

   313

	// check if non-default YAPF type needed

   314

	if (_settings_game.pf.forbid_90_deg) {

   315

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

   316

	}

   317

   318

	/* slightly hackish: If the pathfinders finds a path, the cost of the first node is tested to distinguish between forward- and reverse-path. */

   319

	if (reverse_penalty == 0) reverse_penalty = 1;

   320

   321

	bool reverse = pfnCheckReverseTrain(v, tile, td, tile_rev, td_rev, reverse_penalty);

   322

   323

	return reverse;

   324

}

   325

   326

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

   327

{

   328

	*depot_tile = INVALID_TILE;

   329

	*reversed = false;

   330

   331

	const Vehicle *last_veh = GetLastVehicleInChain(v);

   332

   333

	TileIndex tile = v->tile;

   334

	TileIndex last_tile = last_veh->tile;

   335

   336

	// their trackdirs

   337

	Trackdir td = GetVehicleTrackdir(v);

   338

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   339

   340

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

   341

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail1::stFindNearestDepotTwoWay;

   342

   343

	// check if non-default YAPF type needed

   344

	if (_settings_game.pf.forbid_90_deg) {

   345

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

   346

	}

   347

   348

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

   349

	return ret;

   350

}

   351

   352

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

   353

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   354

   355

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