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;

    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

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

    27

    28

public:

    29

	inline void PfFollowNode(Node& old_node)

    30

	{

    31

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

    32

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

    33

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

    34

	}

    35

    36

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

    37

    38

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

    39

	{

    40

		Tpf pf;

    41

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

    42

	}

    43

    44

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

    45

	{

    46

		// set origin and destination nodes

    47

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

    48

		Yapf().SetDestination(v);

    49

		Yapf().SetMaxCost(10 * max_distance);

    50

    51

		// find the best path

    52

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

    53

		if (!bFound) return false;

    54

    55

		// some path found

    56

		// get found depot tile

    57

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

    58

		*depot_tile = n.GetLastTile();

    59

    60

		// walk through the path back to the origin

    61

		Node* pNode = &n;

    62

		while (pNode->m_parent != NULL) {

    63

			pNode = pNode->m_parent;

    64

		}

    65

    66

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

    67

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

    68

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

    69

    70

		return true;

    71

	}

    72

};

    73

    74

template <class Types>

    75

class CYapfFollowRailT

    76

{

    77

public:

    78

	typedef typename Types::Tpf Tpf;

    79

	typedef typename Types::TrackFollower TrackFollower;

    80

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

    81

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

    82

    83

protected:

    84

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

    85

    86

public:

    87

	inline void PfFollowNode(Node& old_node)

    88

	{

    89

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

    90

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

    91

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

    92

	}

    93

    94

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

    95

    96

	static Trackdir stChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)

    97

	{

    98

		// create pathfinder instance

    99

		Tpf pf;

   100

		return pf.ChooseRailTrack(v, tile, enterdir, trackdirs);

   101

	}

   102

   103

	FORCEINLINE Trackdir ChooseRailTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackdirBits trackdirs)

   104

	{

   105

		// set origin and destination nodes

   106

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

   107

		Yapf().SetDestination(v);

   108

   109

		// find the best path

   110

		Yapf().FindPath(v);

   111

   112

		// if path not found - return INVALID_TRACKDIR

   113

		Trackdir next_trackdir = INVALID_TRACKDIR;

   114

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

   115

		if (pNode != NULL) {

   116

			// path was found or at least suggested

   117

			// walk through the path back to the origin

   118

			Node* pPrev = NULL;

   119

			while (pNode->m_parent != NULL) {

   120

				pPrev = pNode;

   121

				pNode = pNode->m_parent;

   122

			}

   123

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

   124

			Node& best_next_node = *pPrev;

   125

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

   126

			next_trackdir = best_next_node.GetTrackdir();

   127

		}

   128

		return next_trackdir;

   129

	}

   130

   131

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

   132

	{

   133

		Tpf pf;

   134

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

   135

	}

   136

   137

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

   138

	{

   139

		// create pathfinder instance

   140

		// set origin and destination nodes

   141

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

   142

		Yapf().SetDestination(v);

   143

   144

		// find the best path

   145

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

   146

   147

		if (!bFound) return false;

   148

   149

		// path was found

   150

		// walk through the path back to the origin

   151

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

   152

		while (pNode->m_parent != NULL) {

   153

			pNode = pNode->m_parent;

   154

		}

   155

   156

		// check if it was reversed origin

   157

		Node& best_org_node = *pNode;

   158

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

   159

		return reversed;

   160

	}

   161

};

   162

   163

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

   164

struct CYapfRail_TypesT

   165

{

   166

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

   167

   168

	typedef Tpf_                                Tpf;

   169

	typedef Ttrack_follower                     TrackFollower;

   170

	typedef Tnode_list                          NodeList;

   171

	typedef CYapfBaseT<Types>                   PfBase;

   172

	typedef TfollowT<Types>                     PfFollow;

   173

	typedef CYapfOriginTileTwoWayT<Types>       PfOrigin;

   174

	typedef TdestinationT<Types>                PfDestination;

   175

	typedef CYapfSegmentCostCacheGlobalT<Types> PfCache;

   176

	typedef CYapfCostRailT<Types>               PfCost;

   177

};

   178

   179

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

   180

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

   181

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

   182

   183

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

   184

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

   185

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

   186

   187

   188

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

   189

{

   190

	// default is YAPF type 2

   191

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

   192

	PfnChooseRailTrack pfnChooseRailTrack = &CYapfRail2::stChooseRailTrack;

   193

   194

	// check if non-default YAPF type needed

   195

	if (_patches.forbid_90_deg)

   196

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

   197

	else if (_patches.yapf.disable_node_optimization)

   198

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

   199

   200

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

   201

   202

	return td_ret;

   203

}

   204

   205

bool YapfCheckReverseTrain(Vehicle* v)

   206

{

   207

	// tile where the engine is

   208

	TileIndex tile = v->tile;

   209

	// tile where we have last wagon

   210

	Vehicle* last_veh = GetLastVehicleInChain(v);

   211

	// if we are in tunnel then give up

   212

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

   213

	// get trackdirs of both ends

   214

	Trackdir td = GetVehicleTrackdir(v);

   215

	Trackdir td_rev = ReverseTrackdir(GetVehicleTrackdir(last_veh));

   216

   217

   218

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

   219

	PfnCheckReverseTrain pfnCheckReverseTrain = CYapfRail2::stCheckReverseTrain;

   220

   221

	// check if non-default YAPF type needed

   222

	if (_patches.forbid_90_deg)

   223

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

   224

	else if (_patches.yapf.disable_node_optimization)

   225

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

   226

   227

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

   228

   229

	return reverse;

   230

}

   231

   232

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

   233

{

   234

	*depot_tile = INVALID_TILE;

   235

	*reversed = false;

   236

   237

	Vehicle* last_veh = GetLastVehicleInChain(v);

   238

   239

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

   240

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

   241

   242

	// tile where the engine and last wagon are

   243

	TileIndex tile = first_in_tunnel ? INVALID_TILE : v->tile;

   244

	TileIndex last_tile = last_in_tunnel ? INVALID_TILE : last_veh->tile;

   245

   246

	// their trackdirs

   247

	Trackdir td = first_in_tunnel ? INVALID_TRACKDIR : GetVehicleTrackdir(v);

   248

	Trackdir td_rev = last_in_tunnel ? INVALID_TRACKDIR : ReverseTrackdir(GetVehicleTrackdir(last_veh));

   249

   250

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

   251

	PfnFindNearestDepotTwoWay pfnFindNearestDepotTwoWay = &CYapfAnyDepotRail2::stFindNearestDepotTwoWay;

   252

   253

	// check if non-default YAPF type needed

   254

	if (_patches.forbid_90_deg)

   255

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

   256

	else if (_patches.yapf.disable_node_optimization)

   257

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

   258

   259

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

   260

	return ret;

   261

}

   262

   263

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

   264

int CSegmentCostCacheBase::s_rail_change_counter = 0;

   265

   266

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