1

/* $Id$ */

     2

     3

/** @file yapf_node_rail.hpp */

     4

     5

#ifndef  YAPF_NODE_RAIL_HPP

     6

#define  YAPF_NODE_RAIL_HPP

     7

     8

/** key for cached segment cost for rail YAPF */

     9

struct CYapfRailSegmentKey

    10

{

    11

	uint32    m_value;

    12

    13

	FORCEINLINE CYapfRailSegmentKey(const CYapfRailSegmentKey& src) : m_value(src.m_value) {}

    14

	FORCEINLINE CYapfRailSegmentKey(const CYapfNodeKeyTrackDir& node_key) {Set(node_key);}

    15

    16

	FORCEINLINE void Set(const CYapfRailSegmentKey& src) {m_value = src.m_value;}

    17

	FORCEINLINE void Set(const CYapfNodeKeyTrackDir& node_key) {m_value = (((int)node_key.m_tile) << 4) | node_key.m_td;}

    18

    19

	FORCEINLINE int32 CalcHash() const {return m_value;}

    20

	FORCEINLINE TileIndex GetTile() const {return (TileIndex)(m_value >> 4);}

    21

	FORCEINLINE Trackdir GetTrackdir() const {return (Trackdir)(m_value & 0x0F);}

    22

	FORCEINLINE bool operator == (const CYapfRailSegmentKey& other) const {return m_value == other.m_value;}

    23

    24

	void Dump(DumpTarget &dmp) const

    25

	{

    26

		dmp.WriteTile("tile", GetTile());

    27

		dmp.WriteEnumT("td", GetTrackdir());

    28

	}

    29

};

    30

    31

/* Enum used in PfCalcCost() to see why was the segment closed. */

    32

enum EndSegmentReason {

    33

	/* The following reasons can be saved into cached segment */

    34

	ESR_DEAD_END = 0,      ///< track ends here

    35

	ESR_RAIL_TYPE,         ///< the next tile has a different rail type than our tiles

    36

	ESR_INFINITE_LOOP,     ///< infinite loop detected

    37

	ESR_SEGMENT_TOO_LONG,  ///< the segment is too long (possible infinite loop)

    38

	ESR_CHOICE_FOLLOWS,    ///< the next tile contains a choice (the track splits to more than one segments)

    39

	ESR_DEPOT,             ///< stop in the depot (could be a target next time)

    40

	ESR_WAYPOINT,          ///< waypoint encountered (could be a target next time)

    41

	ESR_STATION,           ///< station encountered (could be a target next time)

    42

    43

	/* The following reasons are used only internally by PfCalcCost().

    44

	*   They should not be found in the cached segment. */

    45

	ESR_PATH_TOO_LONG,     ///< the path is too long (searching for the nearest depot in the given radius)

    46

	ESR_FIRST_TWO_WAY_RED, ///< first signal was 2-way and it was red

    47

	ESR_LOOK_AHEAD_END,    ///< we have just passed the last look-ahead signal

    48

	ESR_TARGET_REACHED,    ///< we have just reached the destination

    49

    50

	/* Special values */

    51

	ESR_NONE = 0xFF,          ///< no reason to end the segment here

    52

};

    53

    54

enum EndSegmentReasonBits {

    55

	ESRB_NONE = 0,

    56

    57

	ESRB_DEAD_END          = 1 << ESR_DEAD_END,

    58

	ESRB_RAIL_TYPE         = 1 << ESR_RAIL_TYPE,

    59

	ESRB_INFINITE_LOOP     = 1 << ESR_INFINITE_LOOP,

    60

	ESRB_SEGMENT_TOO_LONG  = 1 << ESR_SEGMENT_TOO_LONG,

    61

	ESRB_CHOICE_FOLLOWS    = 1 << ESR_CHOICE_FOLLOWS,

    62

	ESRB_DEPOT             = 1 << ESR_DEPOT,

    63

	ESRB_WAYPOINT          = 1 << ESR_WAYPOINT,

    64

	ESRB_STATION           = 1 << ESR_STATION,

    65

    66

	ESRB_PATH_TOO_LONG     = 1 << ESR_PATH_TOO_LONG,

    67

	ESRB_FIRST_TWO_WAY_RED = 1 << ESR_FIRST_TWO_WAY_RED,

    68

	ESRB_LOOK_AHEAD_END    = 1 << ESR_LOOK_AHEAD_END,

    69

	ESRB_TARGET_REACHED    = 1 << ESR_TARGET_REACHED,

    70

    71

	/* Additional (composite) values. */

    72

    73

	/* What reasons mean that the target can be found and needs to be detected. */

    74

	ESRB_POSSIBLE_TARGET = ESRB_DEPOT | ESRB_WAYPOINT | ESRB_STATION,

    75

    76

	/* What reasons can be stored back into cached segment. */

    77

	ESRB_CACHED_MASK = ESRB_DEAD_END | ESRB_RAIL_TYPE | ESRB_INFINITE_LOOP | ESRB_SEGMENT_TOO_LONG | ESRB_CHOICE_FOLLOWS | ESRB_DEPOT | ESRB_WAYPOINT | ESRB_STATION,

    78

    79

	/* Reasons to abort pathfinding in this direction. */

    80

	ESRB_ABORT_PF_MASK = ESRB_DEAD_END | ESRB_PATH_TOO_LONG | ESRB_INFINITE_LOOP | ESRB_FIRST_TWO_WAY_RED,

    81

};

    82

    83

DECLARE_ENUM_AS_BIT_SET(EndSegmentReasonBits);

    84

    85

inline CStrA ValueStr(EndSegmentReasonBits bits)

    86

{

    87

	static const char* end_segment_reason_names[] = {

    88

		"DEAD_END", "RAIL_TYPE", "INFINITE_LOOP", "SEGMENT_TOO_LONG", "CHOICE_FOLLOWS",

    89

		"DEPOT", "WAYPOINT", "STATION",

    90

		"PATH_TOO_LONG", "FIRST_TWO_WAY_RED", "LOOK_AHEAD_END", "TARGET_REACHED"

    91

	};

    92

    93

	CStrA out;

    94

	out.Format("0x%04X (%s)", bits, ComposeNameT(bits, end_segment_reason_names, "UNK", ESRB_NONE, "NONE").Data());

    95

	return out.Transfer();

    96

}

    97

    98

/** cached segment cost for rail YAPF */

    99

struct CYapfRailSegment

   100

{

   101

	typedef CYapfRailSegmentKey Key;

   102

   103

	CYapfRailSegmentKey    m_key;

   104

	TileIndex              m_last_tile;

   105

	Trackdir               m_last_td;

   106

	int                    m_cost;

   107

	TileIndex              m_last_signal_tile;

   108

	Trackdir               m_last_signal_td;

   109

	EndSegmentReasonBits   m_end_segment_reason;

   110

	CYapfRailSegment*      m_hash_next;

   111

   112

	FORCEINLINE CYapfRailSegment(const CYapfRailSegmentKey& key)

   113

		: m_key(key)

   114

		, m_last_tile(INVALID_TILE)

   115

		, m_last_td(INVALID_TRACKDIR)

   116

		, m_cost(-1)

   117

		, m_last_signal_tile(INVALID_TILE)

   118

		, m_last_signal_td(INVALID_TRACKDIR)

   119

		, m_end_segment_reason(ESRB_NONE)

   120

		, m_hash_next(NULL)

   121

	{}

   122

   123

	FORCEINLINE const Key& GetKey() const {return m_key;}

   124

	FORCEINLINE TileIndex GetTile() const {return m_key.GetTile();}

   125

	FORCEINLINE CYapfRailSegment* GetHashNext() {return m_hash_next;}

   126

	FORCEINLINE void SetHashNext(CYapfRailSegment* next) {m_hash_next = next;}

   127

   128

	void Dump(DumpTarget &dmp) const

   129

	{

   130

		dmp.WriteStructT("m_key", &m_key);

   131

		dmp.WriteTile("m_last_tile", m_last_tile);

   132

		dmp.WriteEnumT("m_last_td", m_last_td);

   133

		dmp.WriteLine("m_cost = %d", m_cost);

   134

		dmp.WriteTile("m_last_signal_tile", m_last_signal_tile);

   135

		dmp.WriteEnumT("m_last_signal_td", m_last_signal_td);

   136

		dmp.WriteEnumT("m_end_segment_reason", m_end_segment_reason);

   137

	}

   138

};

   139

   140

/** Yapf Node for rail YAPF */

   141

template <class Tkey_>

   142

struct CYapfRailNodeT

   143

	: CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> >

   144

{

   145

	typedef CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > base;

   146

	typedef CYapfRailSegment CachedData;

   147

   148

	CYapfRailSegment *m_segment;

   149

	uint16            m_num_signals_passed;

   150

	union {

   151

		uint32          m_inherited_flags;

   152

		struct {

   153

			bool          m_targed_seen : 1;

   154

			bool          m_choice_seen : 1;

   155

			bool          m_last_signal_was_red : 1;

   156

		} flags_s;

   157

	} flags_u;

   158

	SignalType        m_last_red_signal_type;

   159

   160

	FORCEINLINE void Set(CYapfRailNodeT* parent, TileIndex tile, Trackdir td, bool is_choice)

   161

	{

   162

		base::Set(parent, tile, td, is_choice);

   163

		m_segment = NULL;

   164

		if (parent == NULL) {

   165

			m_num_signals_passed      = 0;

   166

			flags_u.m_inherited_flags = 0;

   167

			m_last_red_signal_type    = SIGTYPE_NORMAL;

   168

		} else {

   169

			m_num_signals_passed      = parent->m_num_signals_passed;

   170

			flags_u.m_inherited_flags = parent->flags_u.m_inherited_flags;

   171

			m_last_red_signal_type    = parent->m_last_red_signal_type;

   172

		}

   173

		flags_u.flags_s.m_choice_seen |= is_choice;

   174

	}

   175

   176

	FORCEINLINE TileIndex GetLastTile() const {assert(m_segment != NULL); return m_segment->m_last_tile;}

   177

	FORCEINLINE Trackdir GetLastTrackdir() const {assert(m_segment != NULL); return m_segment->m_last_td;}

   178

	FORCEINLINE void SetLastTileTrackdir(TileIndex tile, Trackdir td) {assert(m_segment != NULL); m_segment->m_last_tile = tile; m_segment->m_last_td = td;}

   179

   180

	void Dump(DumpTarget &dmp) const

   181

	{

   182

		base::Dump(dmp);

   183

		dmp.WriteStructT("m_segment", m_segment);

   184

		dmp.WriteLine("m_num_signals_passed = %d", m_num_signals_passed);

   185

		dmp.WriteLine("m_targed_seen = %s", flags_u.flags_s.m_targed_seen ? "Yes" : "No");

   186

		dmp.WriteLine("m_choice_seen = %s", flags_u.flags_s.m_choice_seen ? "Yes" : "No");

   187

		dmp.WriteLine("m_last_signal_was_red = %s", flags_u.flags_s.m_last_signal_was_red ? "Yes" : "No");

   188

		dmp.WriteEnumT("m_last_red_signal_type", m_last_red_signal_type);

   189

	}

   190

};

   191

   192

// now define two major node types (that differ by key type)

   193

typedef CYapfRailNodeT<CYapfNodeKeyExitDir>  CYapfRailNodeExitDir;

   194

typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir;

   195

   196

// Default NodeList types

   197

typedef CNodeList_HashTableT<CYapfRailNodeExitDir , 10, 12> CRailNodeListExitDir;

   198

typedef CNodeList_HashTableT<CYapfRailNodeTrackDir, 12, 16> CRailNodeListTrackDir;

   199

   200

   201

   202

#endif /* YAPF_NODE_RAIL_HPP */