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

    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.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

   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_found && path_not_found != NULL) {

   122

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

   123

			*path_not_found = !path_found;

   124

		}

   125

   126

		// if path not found - return INVALID_TRACKDIR

   127

		Trackdir next_trackdir = INVALID_TRACKDIR;

   128

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

   129

		if (pNode != NULL) {

   130

			// path was found or at least suggested

   131

			// walk through the path back to the origin

   132

			Node* pPrev = NULL;

   133

			while (pNode->m_parent != NULL) {

   134

				pPrev = pNode;

   135

				pNode = pNode->m_parent;

   136

			}

   137

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

   138

			Node& best_next_node = *pPrev;

   139

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

   140

			next_trackdir = best_next_node.GetTrackdir();

   141

		}

   142

		return next_trackdir;

   143

	}

   144

   145

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

   146

	{

   147

		Tpf pf;

   148

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

   149

	}

   150

   151

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

   152

	{

   153

		// create pathfinder instance

   154

		// set origin and destination nodes

   155

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

   156

		Yapf().SetDestination(v);

   157

   158

		// find the best path

   159

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

   160

   161

		if (!bFound) return false;

   162

   163

		// path was found

   164

		// walk through the path back to the origin

   165

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

   166

		while (pNode->m_parent != NULL) {

   167

			pNode = pNode->m_parent;

   168

		}

   169

   170

		// check if it was reversed origin

   171

		Node& best_org_node = *pNode;

   172

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

   173

		return reversed;

   174

	}

   175

};

   176

   177

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

   178

struct CYapfRail_TypesT

   179

{

   180

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

   181

   182

	typedef Tpf_                                Tpf;

   183

	typedef Ttrack_follower                     TrackFollower;

   184

	typedef Tnode_list                          NodeList;

   185

	typedef CYapfBaseT<Types>                   PfBase;

   186

	typedef TfollowT<Types>                     PfFollow;

   187

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   188

	typedef TdestinationT<Types>                PfDestination;

   189

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   190

	typedef CYapfCostRailT<Types>               PfCost;

   191

};

   192

   193

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

   194

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

   195

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

   196

   197

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

   198

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

   199

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

   200

   201

   202

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

   203

{

   204

	// default is YAPF type 2

   205

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

   206

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   207

   208

	// check if non-default YAPF type needed

   209

	if (_patches.forbid_90_deg)

   210

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

   211

	else if (_patches.yapf.disable_node_optimization)

   212

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

   213

   214

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

   215

   216

	return td_ret;

   217

}

   218

   219

bool YapfCheckReverseTrain(Vehicle* v)

   220

{

   221

	// tile where the engine is

   222

	TileIndex tile = v->tile;

   223

	// tile where we have last wagon

   224

	Vehicle* last_veh = GetLastVehicleInChain(v);

   225

	// if we are in tunnel then give up

   226

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

   227

	// get trackdirs of both ends

   228

	Trackdir td = GetVehicleTrackdir(v);

   229

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   230

   231

   232

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

   233

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   234

   235

	// check if non-default YAPF type needed

   236

	if (_patches.forbid_90_deg)

   237

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

   238

	else if (_patches.yapf.disable_node_optimization)

   239

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

   240

   241

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

   242

   243

	return reverse;

   244

}

   245

   246

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

   247

   248

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

   249

{

   250

	*depot_tile = INVALID_TILE;

   251

	*reversed = false;

   252

   253

	Vehicle* last_veh = GetLastVehicleInChain(v);

   254

   255

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

   256

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

   257

   258

	// tile where the engine and last wagon are

   259

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

   260

	TileIndex last_tile = last_in_tunnel ? YapfGetVehicleOutOfTunnelTile(last_veh, true) : last_veh->tile;

   261

   262

	// their trackdirs

   263

	Trackdir td = GetVehicleTrackdir(v);

   264

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   265

   266

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

   267

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;

   268

   269

	// check if non-default YAPF type needed

   270

	if (_patches.forbid_90_deg)

   271

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

   272

	else if (_patches.yapf.disable_node_optimization)

   273

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

   274

   275

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

   276

	return ret;

   277

}

   278

   279

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

   280

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

   281

* direction for determining which end of the tunnel to find

   282

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

   283

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

   284

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

   285

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

   286

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

   287

* operation (YapfFindNearestRailDepotTwoWay).                              */

   288

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

   289

{

   290

	TileIndex tile = v->tile;

   291

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

   292

	TileIndexDiff delta = TileOffsByDiagDir(dir);

   293

	byte z = v->z_pos;

   294

   295

	if (bReverse) {

   296

		delta = -delta;

   297

	} else {

   298

		dir = ReverseDiagDir(dir);

   299

	}

   300

	while (

   301

		!IsTunnelTile(tile) ||

   302

		GetTunnelDirection(tile) != dir ||

   303

		GetTileZ(tile) != z

   304

		) {

   305

			tile += delta;

   306

	}

   307

	return tile;

   308

}

   309

   310

   311

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

   312

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   313

   314

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