|
1 /* $Id$ */ |
|
2 |
|
3 #include "../stdafx.h" |
|
4 |
|
5 #include "yapf.hpp" |
|
6 |
|
7 /** Node Follower module of YAPF for ships */ |
|
8 template <class Types> |
|
9 class CYapfFollowShipT |
|
10 { |
|
11 public: |
|
12 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
13 typedef typename Types::TrackFollower TrackFollower; |
|
14 typedef typename Types::NodeList::Titem Node; ///< this will be our node type |
|
15 typedef typename Node::Key Key; ///< key to hash tables |
|
16 |
|
17 protected: |
|
18 /// to access inherited path finder |
|
19 FORCEINLINE Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
|
20 |
|
21 public: |
|
22 /** Called by YAPF to move from the given node to the next tile. For each |
|
23 * reachable trackdir on the new tile creates new node, initializes it |
|
24 * and adds it to the open list by calling Yapf().AddNewNode(n) */ |
|
25 inline void PfFollowNode(Node& old_node) |
|
26 { |
|
27 TrackFollower F; |
|
28 if (F.Follow(old_node.m_key.m_tile, old_node.m_key.m_td)) |
|
29 Yapf().AddMultipleNodes(&old_node, F.m_new_tile, F.m_new_td_bits); |
|
30 } |
|
31 |
|
32 /// return debug report character to identify the transportation type |
|
33 FORCEINLINE char TransportTypeChar() const {return 'w';} |
|
34 |
|
35 static Trackdir ChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks) |
|
36 { |
|
37 // handle special case - when next tile is destination tile |
|
38 if (tile == v->dest_tile) { |
|
39 // convert tracks to trackdirs |
|
40 TrackdirBits trackdirs = (TrackdirBits)(tracks | ((int)tracks << 8)); |
|
41 // choose any trackdir reachable from enterdir |
|
42 trackdirs &= DiagdirReachesTrackdirs(enterdir); |
|
43 return (Trackdir)FindFirstBit2x64(trackdirs); |
|
44 } |
|
45 |
|
46 // move back to the old tile/trackdir (where ship is coming from) |
|
47 TileIndex src_tile = TILE_ADD(tile, TileOffsByDiagDir(ReverseDiagDir(enterdir))); |
|
48 Trackdir trackdir = GetVehicleTrackdir(v); |
|
49 assert(IsValidTrackdir(trackdir)); |
|
50 |
|
51 // convert origin trackdir to TrackdirBits |
|
52 TrackdirBits trackdirs = TrackdirToTrackdirBits(trackdir); |
|
53 // get available trackdirs on the destination tile |
|
54 TrackdirBits dest_trackdirs = (TrackdirBits)(GetTileTrackStatus(v->dest_tile, TRANSPORT_WATER) & TRACKDIR_BIT_MASK); |
|
55 |
|
56 // create pathfinder instance |
|
57 Tpf pf; |
|
58 // set origin and destination nodes |
|
59 pf.SetOrigin(src_tile, trackdirs); |
|
60 pf.SetDestination(v->dest_tile, dest_trackdirs); |
|
61 // find best path |
|
62 bool bFound = pf.FindPath(v); |
|
63 |
|
64 Trackdir next_trackdir = INVALID_TRACKDIR; // this would mean "path not found" |
|
65 if (bFound) { |
|
66 // path was found |
|
67 // walk through the path back to the origin |
|
68 Node* pNode = &pf.GetBestNode(); |
|
69 Node* pPrevNode = NULL; |
|
70 while (pNode->m_parent != NULL) { |
|
71 pPrevNode = pNode; |
|
72 pNode = pNode->m_parent; |
|
73 } |
|
74 // return trackdir from the best next node (direct child of origin) |
|
75 Node& best_next_node = *pPrevNode; |
|
76 assert(best_next_node.GetTile() == tile); |
|
77 next_trackdir = best_next_node.GetTrackdir(); |
|
78 } |
|
79 return next_trackdir; |
|
80 } |
|
81 }; |
|
82 |
|
83 /** Cost Provider module of YAPF for ships */ |
|
84 template <class Types> |
|
85 class CYapfCostShipT |
|
86 { |
|
87 public: |
|
88 typedef typename Types::Tpf Tpf; ///< the pathfinder class (derived from THIS class) |
|
89 typedef typename Types::NodeList::Titem Node; ///< this will be our node type |
|
90 typedef typename Node::Key Key; ///< key to hash tables |
|
91 |
|
92 protected: |
|
93 /// to access inherited path finder |
|
94 Tpf& Yapf() {return *static_cast<Tpf*>(this);} |
|
95 |
|
96 public: |
|
97 /** Called by YAPF to calculate the cost from the origin to the given node. |
|
98 * Calculates only the cost of given node, adds it to the parent node cost |
|
99 * and stores the result into Node::m_cost member */ |
|
100 FORCEINLINE bool PfCalcCost(Node& n) |
|
101 { |
|
102 // base tile cost depending on distance |
|
103 int c = IsDiagonalTrackdir(n.GetTrackdir()) ? 10 : 7; |
|
104 // additional penalty for curves |
|
105 if (n.m_parent != NULL && n.GetTrackdir() != n.m_parent->GetTrackdir()) c += 3; |
|
106 // apply it |
|
107 n.m_cost = n.m_parent->m_cost + c; |
|
108 return true; |
|
109 } |
|
110 }; |
|
111 |
|
112 /** Config struct of YAPF for ships. |
|
113 * Defines all 6 base YAPF modules as classes providing services for CYapfBaseT. |
|
114 */ |
|
115 template <class Tpf_, class Ttrack_follower, class Tnode_list> |
|
116 struct CYapfShip_TypesT |
|
117 { |
|
118 /** Types - shortcut for this struct type */ |
|
119 typedef CYapfShip_TypesT<Tpf_, Ttrack_follower, Tnode_list> Types; |
|
120 |
|
121 /** Tpf - pathfinder type */ |
|
122 typedef Tpf_ Tpf; |
|
123 /** track follower helper class */ |
|
124 typedef Ttrack_follower TrackFollower; |
|
125 /** node list type */ |
|
126 typedef Tnode_list NodeList; |
|
127 /** pathfinder components (modules) */ |
|
128 typedef CYapfBaseT<Types> PfBase; // base pathfinder class |
|
129 typedef CYapfFollowShipT<Types> PfFollow; // node follower |
|
130 typedef CYapfOriginTileT<Types> PfOrigin; // origin provider |
|
131 typedef CYapfDestinationTileT<Types> PfDestination; // destination/distance provider |
|
132 typedef CYapfSegmentCostCacheNoneT<Types> PfCache; // segment cost cache provider |
|
133 typedef CYapfCostShipT<Types> PfCost; // cost provider |
|
134 }; |
|
135 |
|
136 // YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns |
|
137 struct CYapfShip1 : CYapfT<CYapfShip_TypesT<CYapfShip1, CFollowTrackWater , CShipNodeListTrackDir> > {}; |
|
138 // YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns |
|
139 struct CYapfShip2 : CYapfT<CYapfShip_TypesT<CYapfShip2, CFollowTrackWater , CShipNodeListExitDir > > {}; |
|
140 // YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns |
|
141 struct CYapfShip3 : CYapfT<CYapfShip_TypesT<CYapfShip3, CFollowTrackWaterNo90, CShipNodeListTrackDir> > {}; |
|
142 |
|
143 /** Ship controller helper - path finder invoker */ |
|
144 Trackdir YapfChooseShipTrack(Vehicle *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks) |
|
145 { |
|
146 // default is YAPF type 2 |
|
147 typedef Trackdir (*PfnChooseShipTrack)(Vehicle*, TileIndex, DiagDirection, TrackBits); |
|
148 PfnChooseShipTrack pfnChooseShipTrack = CYapfShip2::ChooseShipTrack; // default: ExitDir, allow 90-deg |
|
149 |
|
150 // check if non-default YAPF type needed |
|
151 if (_patches.forbid_90_deg) |
|
152 pfnChooseShipTrack = &CYapfShip3::ChooseShipTrack; // Trackdir, forbid 90-deg |
|
153 else if (_patches.yapf.disable_node_optimization) |
|
154 pfnChooseShipTrack = &CYapfShip1::ChooseShipTrack; // Trackdir, allow 90-deg |
|
155 |
|
156 Trackdir td_ret = pfnChooseShipTrack(v, tile, enterdir, tracks); |
|
157 return td_ret; |
|
158 } |
|
159 |
|
160 /** performance measurement helper */ |
|
161 void* NpfBeginInterval() |
|
162 { |
|
163 CPerformanceTimer& perf = *new CPerformanceTimer; |
|
164 perf.Start(); |
|
165 return &perf; |
|
166 } |
|
167 |
|
168 /** performance measurement helper */ |
|
169 int NpfEndInterval(void* vperf) |
|
170 { |
|
171 CPerformanceTimer& perf = *(CPerformanceTimer*)vperf; |
|
172 perf.Stop(); |
|
173 int t = perf.Get(1000000); |
|
174 delete &perf; |
|
175 return t; |
|
176 } |