/* $Id$ */
/** @file yapf_node_rail.hpp Node tailored for rail pathfinding. */
#ifndef YAPF_NODE_RAIL_HPP
#define YAPF_NODE_RAIL_HPP
/** key for cached segment cost for rail YAPF */
struct CYapfRailSegmentKey
{
uint32 m_value;
FORCEINLINE CYapfRailSegmentKey(const CYapfRailSegmentKey& src) : m_value(src.m_value) {}
FORCEINLINE CYapfRailSegmentKey(const CYapfNodeKeyTrackDir& node_key) {Set(node_key);}
FORCEINLINE void Set(const CYapfRailSegmentKey& src) {m_value = src.m_value;}
FORCEINLINE void Set(const CYapfNodeKeyTrackDir& node_key) {m_value = (((int)node_key.m_tile) << 4) | node_key.m_td;}
FORCEINLINE int32 CalcHash() const {return m_value;}
FORCEINLINE TileIndex GetTile() const {return (TileIndex)(m_value >> 4);}
FORCEINLINE Trackdir GetTrackdir() const {return (Trackdir)(m_value & 0x0F);}
FORCEINLINE bool operator == (const CYapfRailSegmentKey& other) const {return m_value == other.m_value;}
void Dump(DumpTarget &dmp) const
{
dmp.WriteTile("tile", GetTile());
dmp.WriteEnumT("td", GetTrackdir());
}
};
/* Enum used in PfCalcCost() to see why was the segment closed. */
enum EndSegmentReason {
/* The following reasons can be saved into cached segment */
ESR_DEAD_END = 0, ///< track ends here
ESR_RAIL_TYPE, ///< the next tile has a different rail type than our tiles
ESR_INFINITE_LOOP, ///< infinite loop detected
ESR_SEGMENT_TOO_LONG, ///< the segment is too long (possible infinite loop)
ESR_CHOICE_FOLLOWS, ///< the next tile contains a choice (the track splits to more than one segments)
ESR_DEPOT, ///< stop in the depot (could be a target next time)
ESR_WAYPOINT, ///< waypoint encountered (could be a target next time)
ESR_STATION, ///< station encountered (could be a target next time)
ESR_SAFE_TILE, ///< safe waiting position found (could be a target)
/* The following reasons are used only internally by PfCalcCost().
* They should not be found in the cached segment. */
ESR_PATH_TOO_LONG, ///< the path is too long (searching for the nearest depot in the given radius)
ESR_FIRST_TWO_WAY_RED, ///< first signal was 2-way and it was red
ESR_LOOK_AHEAD_END, ///< we have just passed the last look-ahead signal
ESR_TARGET_REACHED, ///< we have just reached the destination
/* Special values */
ESR_NONE = 0xFF, ///< no reason to end the segment here
};
enum EndSegmentReasonBits {
ESRB_NONE = 0,
ESRB_DEAD_END = 1 << ESR_DEAD_END,
ESRB_RAIL_TYPE = 1 << ESR_RAIL_TYPE,
ESRB_INFINITE_LOOP = 1 << ESR_INFINITE_LOOP,
ESRB_SEGMENT_TOO_LONG = 1 << ESR_SEGMENT_TOO_LONG,
ESRB_CHOICE_FOLLOWS = 1 << ESR_CHOICE_FOLLOWS,
ESRB_DEPOT = 1 << ESR_DEPOT,
ESRB_WAYPOINT = 1 << ESR_WAYPOINT,
ESRB_STATION = 1 << ESR_STATION,
ESRB_SAFE_TILE = 1 << ESR_SAFE_TILE,
ESRB_PATH_TOO_LONG = 1 << ESR_PATH_TOO_LONG,
ESRB_FIRST_TWO_WAY_RED = 1 << ESR_FIRST_TWO_WAY_RED,
ESRB_LOOK_AHEAD_END = 1 << ESR_LOOK_AHEAD_END,
ESRB_TARGET_REACHED = 1 << ESR_TARGET_REACHED,
/* Additional (composite) values. */
/* What reasons mean that the target can be found and needs to be detected. */
ESRB_POSSIBLE_TARGET = ESRB_DEPOT | ESRB_WAYPOINT | ESRB_STATION | ESRB_SAFE_TILE,
/* What reasons can be stored back into cached segment. */
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 | ESRB_SAFE_TILE,
/* Reasons to abort pathfinding in this direction. */
ESRB_ABORT_PF_MASK = ESRB_DEAD_END | ESRB_PATH_TOO_LONG | ESRB_INFINITE_LOOP | ESRB_FIRST_TWO_WAY_RED,
};
DECLARE_ENUM_AS_BIT_SET(EndSegmentReasonBits);
inline CStrA ValueStr(EndSegmentReasonBits bits)
{
static const char* end_segment_reason_names[] = {
"DEAD_END", "RAIL_TYPE", "INFINITE_LOOP", "SEGMENT_TOO_LONG", "CHOICE_FOLLOWS",
"DEPOT", "WAYPOINT", "STATION",
"PATH_TOO_LONG", "FIRST_TWO_WAY_RED", "LOOK_AHEAD_END", "TARGET_REACHED"
};
CStrA out;
out.Format("0x%04X (%s)", bits, ComposeNameT(bits, end_segment_reason_names, "UNK", ESRB_NONE, "NONE").Data());
return out.Transfer();
}
/** cached segment cost for rail YAPF */
struct CYapfRailSegment
{
typedef CYapfRailSegmentKey Key;
CYapfRailSegmentKey m_key;
TileIndex m_last_tile;
Trackdir m_last_td;
int m_cost;
TileIndex m_last_signal_tile;
Trackdir m_last_signal_td;
EndSegmentReasonBits m_end_segment_reason;
CYapfRailSegment* m_hash_next;
FORCEINLINE CYapfRailSegment(const CYapfRailSegmentKey& key)
: m_key(key)
, m_last_tile(INVALID_TILE)
, m_last_td(INVALID_TRACKDIR)
, m_cost(-1)
, m_last_signal_tile(INVALID_TILE)
, m_last_signal_td(INVALID_TRACKDIR)
, m_end_segment_reason(ESRB_NONE)
, m_hash_next(NULL)
{}
FORCEINLINE const Key& GetKey() const {return m_key;}
FORCEINLINE TileIndex GetTile() const {return m_key.GetTile();}
FORCEINLINE CYapfRailSegment* GetHashNext() {return m_hash_next;}
FORCEINLINE void SetHashNext(CYapfRailSegment* next) {m_hash_next = next;}
void Dump(DumpTarget &dmp) const
{
dmp.WriteStructT("m_key", &m_key);
dmp.WriteTile("m_last_tile", m_last_tile);
dmp.WriteEnumT("m_last_td", m_last_td);
dmp.WriteLine("m_cost = %d", m_cost);
dmp.WriteTile("m_last_signal_tile", m_last_signal_tile);
dmp.WriteEnumT("m_last_signal_td", m_last_signal_td);
dmp.WriteEnumT("m_end_segment_reason", m_end_segment_reason);
}
};
/** Yapf Node for rail YAPF */
template <class Tkey_>
struct CYapfRailNodeT
: CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> >
{
typedef CYapfNodeT<Tkey_, CYapfRailNodeT<Tkey_> > base;
typedef CYapfRailSegment CachedData;
CYapfRailSegment *m_segment;
uint16 m_num_signals_passed;
union {
uint32 m_inherited_flags;
struct {
bool m_targed_seen : 1;
bool m_choice_seen : 1;
bool m_last_signal_was_red : 1;
} flags_s;
} flags_u;
SignalType m_last_red_signal_type;
FORCEINLINE void Set(CYapfRailNodeT* parent, TileIndex tile, Trackdir td, bool is_choice)
{
base::Set(parent, tile, td, is_choice);
m_segment = NULL;
if (parent == NULL) {
m_num_signals_passed = 0;
flags_u.m_inherited_flags = 0;
m_last_red_signal_type = SIGTYPE_NORMAL;
} else {
m_num_signals_passed = parent->m_num_signals_passed;
flags_u.m_inherited_flags = parent->flags_u.m_inherited_flags;
m_last_red_signal_type = parent->m_last_red_signal_type;
}
flags_u.flags_s.m_choice_seen |= is_choice;
}
FORCEINLINE TileIndex GetLastTile() const {assert(m_segment != NULL); return m_segment->m_last_tile;}
FORCEINLINE Trackdir GetLastTrackdir() const {assert(m_segment != NULL); return m_segment->m_last_td;}
FORCEINLINE void SetLastTileTrackdir(TileIndex tile, Trackdir td) {assert(m_segment != NULL); m_segment->m_last_tile = tile; m_segment->m_last_td = td;}
template <class Tbase, class Tfunc, class Tpf>
bool IterateTiles(const Vehicle *v, Tpf &yapf, Tbase &obj, bool (Tfunc::*func)(TileIndex, Trackdir)) const
{
typename Tbase::TrackFollower ft(v, yapf.GetCompatibleRailTypes());
TileIndex cur = base::GetTile();
Trackdir cur_td = base::GetTrackdir();
while (cur != GetLastTile() || cur_td != GetLastTrackdir()) {
if (!((obj.*func)(cur, cur_td))) return false;
ft.Follow(cur, cur_td);
cur = ft.m_new_tile;
assert(KillFirstBit(ft.m_new_td_bits) == TRACKDIR_BIT_NONE);
cur_td = FindFirstTrackdir(ft.m_new_td_bits);
}
return (obj.*func)(cur, cur_td);
}
void Dump(DumpTarget &dmp) const
{
base::Dump(dmp);
dmp.WriteStructT("m_segment", m_segment);
dmp.WriteLine("m_num_signals_passed = %d", m_num_signals_passed);
dmp.WriteLine("m_targed_seen = %s", flags_u.flags_s.m_targed_seen ? "Yes" : "No");
dmp.WriteLine("m_choice_seen = %s", flags_u.flags_s.m_choice_seen ? "Yes" : "No");
dmp.WriteLine("m_last_signal_was_red = %s", flags_u.flags_s.m_last_signal_was_red ? "Yes" : "No");
dmp.WriteEnumT("m_last_red_signal_type", m_last_red_signal_type);
}
};
// now define two major node types (that differ by key type)
typedef CYapfRailNodeT<CYapfNodeKeyExitDir> CYapfRailNodeExitDir;
typedef CYapfRailNodeT<CYapfNodeKeyTrackDir> CYapfRailNodeTrackDir;
// Default NodeList types
typedef CNodeList_HashTableT<CYapfRailNodeExitDir , 10, 12> CRailNodeListExitDir;
typedef CNodeList_HashTableT<CYapfRailNodeTrackDir, 12, 16> CRailNodeListTrackDir;
#endif /* YAPF_NODE_RAIL_HPP */