4 * This file is part of OpenTTD.
5 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
6 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
7 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
10 /** @file yapf_ship.cpp Implementation of YAPF for ships. */
12 #include "../../stdafx.h"
13 #include "../../ship.h"
17 /** Yapf Node for ships */
18 template <class Tkey_
>
19 struct CYapfShipNodeT
: CYapfNodeT
<Tkey_
, CYapfShipNodeT
<Tkey_
> > {
20 CYapfShipNodeT (const CYapfShipNodeT
*parent
, const ShipPathPos
&pos
)
21 : CYapfNodeT
<Tkey_
, CYapfShipNodeT
<Tkey_
> > (parent
, pos
)
26 /* now define two major node types (that differ by key type) */
27 typedef CYapfShipNodeT
<CYapfNodeKeyExitDir
<ShipPathPos
> > CYapfShipNodeExitDir
;
28 typedef CYapfShipNodeT
<CYapfNodeKeyTrackDir
<ShipPathPos
> > CYapfShipNodeTrackDir
;
30 /* Default Astar types */
31 typedef Astar
<CYapfShipNodeExitDir
, 10, 12> AstarShipExitDir
;
32 typedef Astar
<CYapfShipNodeTrackDir
, 10, 12> AstarShipTrackDir
;
35 /** YAPF class for ships */
36 template <class TAstar
>
37 class CYapfShipT
: public TAstar
{
39 typedef typename
TAstar::Node Node
; ///< this will be our node type
42 const Ship
*const m_veh
; ///< vehicle that we are trying to drive
43 const Station
*const m_dest_station
; ///< destination station, or NULL if target is not a station
44 const TileIndex m_dest_tile
; ///< destination tile, or the special marker INVALID_TILE to search for any depot
45 const ShipVehicleInfo
*const svi
; ///< ship vehicle info
46 const bool m_allow_90deg
; ///< whether to allow 90-degree turns
48 CYapfShipT (const Ship
*ship
, bool allow_90deg
, bool depot
= false)
50 , m_dest_station (!depot
&& ship
->current_order
.IsType(OT_GOTO_STATION
) ? Station::Get(ship
->current_order
.GetDestination()) : NULL
)
51 , m_dest_tile (depot
? INVALID_TILE
:
52 ship
->current_order
.IsType (OT_GOTO_STATION
) ?
53 m_dest_station
->GetClosestTile (ship
->tile
, m_dest_station
->dock_area
) :
55 , svi(ShipVehInfo(ship
->engine_type
))
56 , m_allow_90deg(allow_90deg
)
61 /** Called by the A-star underlying class to find the neighbours of a node. */
62 inline void Follow (const Node
*old_node
)
64 const ShipPathPos
&old_pos
= old_node
->GetPos();
65 DiagDirection exitdir
= TrackdirToExitdir (old_pos
.td
);
67 assert((GetTileWaterwayStatus(old_pos
.tile
) & TrackdirToTrackdirBits(old_pos
.td
)) != 0);
69 PathMPos
<ShipPathPos
> new_pos
;
71 if (IsAqueductTile(old_pos
.tile
) && exitdir
== GetTunnelBridgeDirection(old_pos
.tile
)) {
72 /* we are entering the aqueduct */
73 TileIndex other_end
= GetOtherBridgeEnd (old_pos
.tile
);
74 tiles_skipped
= GetTunnelBridgeLength (old_pos
.tile
, other_end
);
75 new_pos
.set (other_end
, DiagDirToDiagTrackdir (exitdir
));
77 /* normal tile, do one step */
78 new_pos
.set_tile (TileAddByDiagDir (old_pos
.tile
, exitdir
));
81 if (IsAqueductTile (new_pos
.tile
)) {
82 /* aqueducts can be entered only from proper direction */
83 if (GetTunnelBridgeDirection (new_pos
.tile
) != exitdir
) {
87 new_pos
.set_trackdir (DiagDirToDiagTrackdir (exitdir
));
89 TrackdirBits trackdirs
= GetTileWaterwayStatus(new_pos
.tile
) & DiagdirReachesTrackdirs(exitdir
);
90 if (trackdirs
== TRACKDIR_BIT_NONE
) return;
93 trackdirs
&= (TrackdirBits
)~(int)TrackdirCrossesTrackdirs(old_pos
.td
);
94 if (trackdirs
== TRACKDIR_BIT_NONE
) return;
97 new_pos
.set_trackdirs (trackdirs
);
101 /* precompute trackdir-independent costs */
102 int cc
= old_node
->m_cost
+ YAPF_TILE_LENGTH
* tiles_skipped
;
104 /* Ocean/canal speed penalty. */
105 byte speed_frac
= (GetEffectiveWaterClass(new_pos
.tile
) == WATER_CLASS_SEA
) ? svi
->ocean_speed_frac
: svi
->canal_speed_frac
;
106 if (speed_frac
> 0) cc
+= YAPF_TILE_LENGTH
* (1 + tiles_skipped
) * speed_frac
/ (256 - speed_frac
);
108 /* detect destination */
109 TileIndex new_tile
= new_pos
.tile
;
110 bool is_target
= (m_dest_station
!= NULL
) ? m_dest_station
->IsDockingTile (new_tile
) :
111 (m_dest_tile
!= INVALID_TILE
) ? (new_tile
== m_dest_tile
) :
112 IsShipDepotTile (new_tile
) && IsTileOwner (new_tile
, m_veh
->owner
);
114 for (TrackdirBits rtds
= new_pos
.trackdirs
; rtds
!= TRACKDIR_BIT_NONE
; rtds
= KillFirstBit(rtds
)) {
115 Trackdir td
= FindFirstTrackdir (rtds
);
117 /* base tile cost depending on distance */
118 int c
= IsDiagonalTrackdir(td
) ? YAPF_TILE_LENGTH
: YAPF_TILE_CORNER_LENGTH
;
119 /* additional penalty for curves */
120 if (td
!= NextTrackdir (old_node
->GetPos().td
)) {
121 /* new trackdir does not match the next one when going straight */
122 c
+= YAPF_TILE_LENGTH
;
125 /* create the node */
126 Node
n (old_node
, ShipPathPos (new_tile
, td
));
129 /* compute estimated cost */
131 n
.m_estimate
= n
.m_cost
;
132 TAstar::InsertTarget (n
);
134 if (m_dest_tile
== INVALID_TILE
) {
135 n
.m_estimate
= n
.m_cost
;
137 n
.m_estimate
= n
.m_cost
+ YapfCalcEstimate (n
.GetPos(), m_dest_tile
);
138 assert (n
.m_estimate
>= n
.m_parent
->m_estimate
);
141 TAstar::InsertNode(n
);
147 /** Call the node follower */
148 static inline void Follow (CYapfShipT
*pf
, const Node
*n
)
153 /** Invoke the underlying pathfinder. */
154 inline bool FindPath (void)
156 #ifndef NO_DEBUG_MESSAGES
157 CPerformanceTimer perf
;
159 #endif /* !NO_DEBUG_MESSAGES */
161 bool bDestFound
= TAstar::FindPath (Follow
, _settings_game
.pf
.yapf
.max_search_nodes
);
163 #ifndef NO_DEBUG_MESSAGES
165 if (_debug_yapf_level
>= 2) {
166 int t
= perf
.Get(1000000);
167 _total_pf_time_us
+= t
;
169 if (_debug_yapf_level
>= 3) {
170 int cost
= bDestFound
? TAstar::best
->m_cost
: -1;
171 int dist
= bDestFound
? TAstar::best
->m_estimate
- TAstar::best
->m_cost
: -1;
173 DEBUG(yapf
, 3, "[YAPFw]%c%4d- %d us - %d rounds - %d open - %d closed - CHR 0.0%% - C %d D %d - c0(sc0, ts0, o0) -- ",
174 bDestFound
? '-' : '!', m_veh
->unitnumber
, t
, TAstar::num_steps
, TAstar::OpenCount(), TAstar::ClosedCount(),
179 #endif /* !NO_DEBUG_MESSAGES */
185 template <class TAstar
, bool allow_90deg
>
186 struct CYapfShip
: CYapfShipT
<TAstar
> {
187 CYapfShip (const Ship
*ship
, bool depot
= false)
188 : CYapfShipT
<TAstar
> (ship
, allow_90deg
, depot
)
193 /* YAPF type 1 - uses TileIndex/Trackdir as Node key, allows 90-deg turns */
194 typedef CYapfShip
<AstarShipTrackDir
, true> CYapfShip1
;
196 /* YAPF type 2 - uses TileIndex/DiagDirection as Node key, allows 90-deg turns */
197 typedef CYapfShip
<AstarShipExitDir
, true> CYapfShip2
;
199 /* YAPF type 3 - uses TileIndex/Trackdir as Node key, forbids 90-deg turns */
200 typedef CYapfShip
<AstarShipTrackDir
, false> CYapfShip3
;
204 static Trackdir
ChooseShipTrack(const Ship
*v
, const ShipPathPos
&pos
, TrackdirBits trackdirs
, bool &path_found
)
206 /* create pathfinder instance */
208 /* set origin node */
209 pf
.InsertInitialNode (typename
Tpf::Node (NULL
, pos
));
211 path_found
= pf
.FindPath();
213 const typename
Tpf::Node
*n
= pf
.GetBestNode();
214 if (n
== NULL
) return INVALID_TRACKDIR
; // path not found
215 assert (n
->m_parent
!= NULL
);
217 /* walk through the path back to the origin */
218 while (n
->m_parent
->m_parent
!= NULL
) {
222 /* return trackdir from the best next node (direct child of origin) */
223 assert(n
->m_parent
->GetPos().tile
== pos
.tile
);
224 return n
->GetPos().td
;
227 /** Ship controller helper - path finder invoker */
228 Trackdir
YapfShipChooseTrack(const Ship
*v
, TileIndex tile
, DiagDirection enterdir
, TrackdirBits trackdirs
, bool &path_found
)
230 /* move back to the old tile/trackdir (where ship is coming from) */
231 ShipPathPos pos
= v
->GetPos();
232 assert(pos
.tile
== TileAddByDiagDir (tile
, ReverseDiagDir(enterdir
)));
233 assert(IsValidTrackdir(pos
.td
));
235 /* handle special case - when next tile is destination tile */
236 if (v
->current_order
.IsType(OT_GOTO_STATION
) ?
237 Station::Get(v
->current_order
.GetDestination())->IsDockingTile(tile
) :
238 tile
== v
->dest_tile
) {
239 /* use vehicle's current direction if that's possible, otherwise use first usable one. */
240 Trackdir veh_dir
= pos
.td
;
241 return ((trackdirs
& TrackdirToTrackdirBits(veh_dir
)) != 0) ? veh_dir
: FindFirstTrackdir(trackdirs
);
244 /* default is YAPF type 2 */
245 typedef Trackdir (*PfnChooseShipTrack
)(const Ship
*, const ShipPathPos
&, TrackdirBits
, bool &path_found
);
246 PfnChooseShipTrack pfnChooseShipTrack
= ChooseShipTrack
<CYapfShip2
>; // default: ExitDir, allow 90-deg
248 /* check if non-default YAPF type needed */
249 if (_settings_game
.pf
.forbid_90_deg
) {
250 pfnChooseShipTrack
= &ChooseShipTrack
<CYapfShip3
>; // Trackdir, forbid 90-deg
251 } else if (_settings_game
.pf
.yapf
.disable_node_optimization
) {
252 pfnChooseShipTrack
= &ChooseShipTrack
<CYapfShip1
>; // Trackdir, allow 90-deg
255 return pfnChooseShipTrack(v
, pos
, trackdirs
, path_found
);
260 * Check whether a ship should reverse to reach its destination.
261 * Called when leaving depot.
263 * @param pos Current position
264 * @return true if the reverse direction is better
267 static bool CheckShipReverse(const Ship
*v
, const ShipPathPos
&pos
)
269 /* create pathfinder instance */
271 /* set origin nodes */
272 pf
.InsertInitialNode (typename
Tpf::Node (NULL
, pos
));
273 pf
.InsertInitialNode (typename
Tpf::Node (NULL
,
274 ShipPathPos (pos
.tile
, ReverseTrackdir (pos
.td
))));
276 if (!pf
.FindPath()) return false;
278 const typename
Tpf::Node
*n
= pf
.GetBestNode();
279 if (n
== NULL
) return false;
281 /* path was found; walk through the path back to the origin */
282 while (n
->m_parent
!= NULL
) {
286 Trackdir best_trackdir
= n
->GetPos().td
;
287 assert(best_trackdir
== pos
.td
|| best_trackdir
== ReverseTrackdir(pos
.td
));
288 return best_trackdir
!= pos
.td
;
291 bool YapfShipCheckReverse(const Ship
*v
)
293 ShipPathPos pos
= v
->GetPos();
295 typedef bool (*PfnCheckReverseShip
)(const Ship
*, const ShipPathPos
&);
296 PfnCheckReverseShip pfnCheckReverseShip
= CheckShipReverse
<CYapfShip2
>; // default: ExitDir, allow 90-deg
298 /* check if non-default YAPF type needed */
299 if (_settings_game
.pf
.forbid_90_deg
) {
300 pfnCheckReverseShip
= &CheckShipReverse
<CYapfShip3
>; // Trackdir, forbid 90-deg
301 } else if (_settings_game
.pf
.yapf
.disable_node_optimization
) {
302 pfnCheckReverseShip
= &CheckShipReverse
<CYapfShip1
>; // Trackdir, allow 90-deg
305 bool reverse
= pfnCheckReverseShip(v
, pos
);
312 * Find the nearest depot to a ship
314 * @param max_distance maximum allowed distance, or 0 for any distance
315 * @return the tile of the nearest depot
318 static TileIndex
FindNearestDepot (const Ship
*v
, uint max_distance
)
321 pf
.InsertInitialNode (typename
Tpf::Node (NULL
, v
->GetPos()));
322 if (!pf
.FindPath()) return INVALID_TILE
;
324 /* some path found; get found depot tile */
325 const typename
Tpf::Node
*n
= pf
.GetBestNode();
326 if (max_distance
> 0 && n
->m_cost
> 0 && (uint
)n
->m_cost
> max_distance
) return INVALID_TILE
;
327 return n
->GetPos().tile
;
330 TileIndex
YapfShipFindNearestDepot (const Ship
*v
, uint max_distance
)
332 if (_settings_game
.pf
.forbid_90_deg
) {
333 return FindNearestDepot
<CYapfShip3
> (v
, max_distance
);
334 } else if (_settings_game
.pf
.yapf
.disable_node_optimization
) {
335 return FindNearestDepot
<CYapfShip1
> (v
, max_distance
);
337 return FindNearestDepot
<CYapfShip2
> (v
, max_distance
);