9 struct CYapfRailSegmentKey |
9 struct CYapfRailSegmentKey |
10 { |
10 { |
11 uint32 m_value; |
11 uint32 m_value; |
12 |
12 |
13 FORCEINLINE CYapfRailSegmentKey(const CYapfRailSegmentKey& src) : m_value(src.m_value) {} |
13 FORCEINLINE CYapfRailSegmentKey(const CYapfRailSegmentKey& src) : m_value(src.m_value) {} |
14 FORCEINLINE CYapfRailSegmentKey(const CYapfNodeKeyExitDir& node_key) {Set(node_key);} |
14 FORCEINLINE CYapfRailSegmentKey(const CYapfNodeKeyTrackDir& node_key) {Set(node_key);} |
15 |
15 |
16 FORCEINLINE void Set(const CYapfRailSegmentKey& src) {m_value = src.m_value;} |
16 FORCEINLINE void Set(const CYapfRailSegmentKey& src) {m_value = src.m_value;} |
17 FORCEINLINE void Set(const CYapfNodeKeyExitDir& node_key) {m_value = (((int)node_key.m_tile) << 2) | node_key.m_exitdir;} |
17 FORCEINLINE void Set(const CYapfNodeKeyTrackDir& node_key) {m_value = (((int)node_key.m_tile) << 4) | node_key.m_td;} |
18 |
18 |
19 FORCEINLINE int32 CalcHash() const {return m_value;} |
19 FORCEINLINE int32 CalcHash() const {return m_value;} |
20 FORCEINLINE TileIndex GetTile() const {return (TileIndex)(m_value >> 2);} |
20 FORCEINLINE TileIndex GetTile() const {return (TileIndex)(m_value >> 4);} |
21 FORCEINLINE DiagDirection GetExitDir() const {return (DiagDirection)(m_value & 3);} |
21 FORCEINLINE Trackdir GetTrackdir() const {return (Trackdir)(m_value & 0x0F);} |
22 FORCEINLINE bool operator == (const CYapfRailSegmentKey& other) const {return m_value == other.m_value;} |
22 FORCEINLINE bool operator == (const CYapfRailSegmentKey& other) const {return m_value == other.m_value;} |
23 }; |
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 } |
24 |
97 |
25 /** cached segment cost for rail YAPF */ |
98 /** cached segment cost for rail YAPF */ |
26 struct CYapfRailSegment |
99 struct CYapfRailSegment |
27 { |
100 { |
28 typedef CYapfRailSegmentKey Key; |
101 typedef CYapfRailSegmentKey Key; |
31 TileIndex m_last_tile; |
104 TileIndex m_last_tile; |
32 Trackdir m_last_td; |
105 Trackdir m_last_td; |
33 int m_cost; |
106 int m_cost; |
34 TileIndex m_last_signal_tile; |
107 TileIndex m_last_signal_tile; |
35 Trackdir m_last_signal_td; |
108 Trackdir m_last_signal_td; |
|
109 EndSegmentReasonBits m_end_segment_reason; |
36 CYapfRailSegment* m_hash_next; |
110 CYapfRailSegment* m_hash_next; |
37 union { |
|
38 byte m_flags; |
|
39 struct { |
|
40 bool m_end_of_line : 1; |
|
41 } flags_s; |
|
42 } flags_u; |
|
43 byte m_reserve[3]; |
|
44 |
111 |
45 FORCEINLINE CYapfRailSegment(const CYapfRailSegmentKey& key) |
112 FORCEINLINE CYapfRailSegment(const CYapfRailSegmentKey& key) |
46 : m_key(key) |
113 : m_key(key) |
47 , m_last_tile(INVALID_TILE) |
114 , m_last_tile(INVALID_TILE) |
48 , m_last_td(INVALID_TRACKDIR) |
115 , m_last_td(INVALID_TRACKDIR) |
49 , m_cost(-1) |
116 , m_cost(-1) |
50 , m_last_signal_tile(INVALID_TILE) |
117 , m_last_signal_tile(INVALID_TILE) |
51 , m_last_signal_td(INVALID_TRACKDIR) |
118 , m_last_signal_td(INVALID_TRACKDIR) |
|
119 , m_end_segment_reason(ESRB_NONE) |
52 , m_hash_next(NULL) |
120 , m_hash_next(NULL) |
53 { |
121 {} |
54 flags_u.m_flags = 0; |
|
55 } |
|
56 |
122 |
57 FORCEINLINE const Key& GetKey() const {return m_key;} |
123 FORCEINLINE const Key& GetKey() const {return m_key;} |
58 FORCEINLINE TileIndex GetTile() const {return m_key.GetTile();} |
124 FORCEINLINE TileIndex GetTile() const {return m_key.GetTile();} |
59 FORCEINLINE DiagDirection GetExitDir() const {return m_key.GetExitDir();} |
|
60 FORCEINLINE CYapfRailSegment* GetHashNext() {return m_hash_next;} |
125 FORCEINLINE CYapfRailSegment* GetHashNext() {return m_hash_next;} |
61 FORCEINLINE void SetHashNext(CYapfRailSegment* next) {m_hash_next = 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 } |
62 }; |
138 }; |
63 |
139 |
64 /** Yapf Node for rail YAPF */ |
140 /** Yapf Node for rail YAPF */ |
65 template <class Tkey_> |
141 template <class Tkey_> |
66 struct CYapfRailNodeT |
142 struct CYapfRailNodeT |
98 } |
174 } |
99 |
175 |
100 FORCEINLINE TileIndex GetLastTile() const {assert(m_segment != NULL); return m_segment->m_last_tile;} |
176 FORCEINLINE TileIndex GetLastTile() const {assert(m_segment != NULL); return m_segment->m_last_tile;} |
101 FORCEINLINE Trackdir GetLastTrackdir() const {assert(m_segment != NULL); return m_segment->m_last_td;} |
177 FORCEINLINE Trackdir GetLastTrackdir() const {assert(m_segment != NULL); return m_segment->m_last_td;} |
102 FORCEINLINE void SetLastTileTrackdir(TileIndex tile, Trackdir td) {assert(m_segment != NULL); m_segment->m_last_tile = tile; m_segment->m_last_td = 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 } |
103 }; |
190 }; |
104 |
191 |
105 // now define two major node types (that differ by key type) |
192 // now define two major node types (that differ by key type) |
106 typedef CYapfRailNodeT<CYapfNodeKeyExitDir> CYapfRailNodeExitDir; |
193 typedef CYapfRailNodeT<CYapfNodeKeyExitDir> CYapfRailNodeExitDir; |
107 typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir; |
194 typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir; |