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);

    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);

   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

   116

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

   117

		Yapf().SetDestination(v);

   118

   119

		// find the best path

   120

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

   121

		if (path_not_found != NULL) {

   122

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

   123

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

   124

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

   125

		}

   126

   127

		// if path not found - return INVALID_TRACKDIR

   128

		Trackdir next_trackdir = INVALID_TRACKDIR;

   129

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

   130

		if (pNode != NULL) {

   131

			// path was found or at least suggested

   132

			// walk through the path back to the origin

   133

			Node* pPrev = NULL;

   134

			while (pNode->m_parent != NULL) {

   135

				pPrev = pNode;

   136

				pNode = pNode->m_parent;

   137

			}

   138

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

   139

			Node& best_next_node = *pPrev;

   140

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

   141

			next_trackdir = best_next_node.GetTrackdir();

   142

		}

   143

		return next_trackdir;

   144

	}

   145

   146

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

   147

	{

   148

		Tpf pf;

   149

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

   150

	}

   151

   152

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

   153

	{

   154

		// create pathfinder instance

   155

		// set origin and destination nodes

   156

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

   157

		Yapf().SetDestination(v);

   158

   159

		// find the best path

   160

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

   161

   162

		if (!bFound) return false;

   163

   164

		// path was found

   165

		// walk through the path back to the origin

   166

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

   167

		while (pNode->m_parent != NULL) {

   168

			pNode = pNode->m_parent;

   169

		}

   170

   171

		// check if it was reversed origin

   172

		Node& best_org_node = *pNode;

   173

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

   174

		return reversed;

   175

	}

   176

};

   177

   178

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

   179

struct CYapfRail_TypesT

   180

{

   181

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

   182

   183

	typedef Tpf_                                Tpf;

   184

	typedef Ttrack_follower                     TrackFollower;

   185

	typedef Tnode_list                          NodeList;

   186

	typedef CYapfBaseT<Types>                   PfBase;

   187

	typedef TfollowT<Types>                     PfFollow;

   188

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   189

	typedef TdestinationT<Types>                PfDestination;

   190

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   191

	typedef CYapfCostRailT<Types>               PfCost;

   192

};

   193

   194

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

   195

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

   196

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

   197

   198

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

   199

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

   200

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

   201

   202

   203

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

   204

{

   205

	// default is YAPF type 2

   206

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

   207

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   208

   209

	// check if non-default YAPF type needed

   210

	if (_patches.forbid_90_deg)

   211

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

   212

	else if (_patches.yapf.disable_node_optimization)

   213

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

   214

   215

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

   216

   217

	return td_ret;

   218

}

   219

   220

bool YapfCheckReverseTrain(Vehicle* v)

   221

{

   222

	// tile where the engine is

   223

	TileIndex tile = v->tile;

   224

	// tile where we have last wagon

   225

	Vehicle* last_veh = GetLastVehicleInChain(v);

   226

	// if we are in tunnel then give up

   227

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

   228

	// get trackdirs of both ends

   229

	Trackdir td = GetVehicleTrackdir(v);

   230

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   231

   232

   233

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

   234

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   235

   236

	// check if non-default YAPF type needed

   237

	if (_patches.forbid_90_deg)

   238

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

   239

	else if (_patches.yapf.disable_node_optimization)

   240

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

   241

   242

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

   243

   244

	return reverse;

   245

}

   246

   247

static TileIndex YapfGetVehicleOutOfTunnelTile(const Vehicle *v, bool bReverse);

   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

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

   257

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

   258

   259

	// tile where the engine and last wagon are

   260

	TileIndex tile = first_in_tunnel ? YapfGetVehicleOutOfTunnelTile(v, false) : v->tile;

   261

	TileIndex last_tile = last_in_tunnel ? YapfGetVehicleOutOfTunnelTile(last_veh, true) : 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

/** Retrieve the exit-tile of the vehicle from inside a tunnel

   281

* Very similar to GetOtherTunnelEnd(), but we use the vehicle's

   282

* direction for determining which end of the tunnel to find

   283

* @param v the vehicle which is inside the tunnel and needs an exit

   284

* @param bReverse should we search for the tunnel exit in the opposite direction?

   285

* @return the exit-tile of the tunnel based on the vehicle's direction

   286

* taken from tunnelbridge_cmd.c where the function body was disabled by

   287

* #if 1 #else #endif (at r5951). Added bReverse argument to allow two-way

   288

* operation (YapfFindNearestRailDepotTwoWay).                              */

   289

static TileIndex YapfGetVehicleOutOfTunnelTile(const Vehicle *v, bool bReverse)

   290

{

   291

	TileIndex tile = v->tile;

   292

	DiagDirection dir = DirToDiagDir((Direction)v->direction);

   293

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   294

	byte z = v->z_pos;

   295

   296

	if (bReverse) {

   297

		delta = -delta;

   298

	} else {

   299

		dir = ReverseDiagDir(dir);

   300

	}

   301

	while (

   302

		!IsTunnelTile(tile) ||

   303

		GetTunnelDirection(tile) != dir ||

   304

		GetTileZ(tile) != z

   305

		) {

   306

			tile += delta;

   307

	}

   308

	return tile;

   309

}

   310

   311

   312

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

   313

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   314

   315

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