author | tron |
Fri, 04 Feb 2005 17:14:36 +0000 | |
changeset 1287 | adb8820d4600 |
parent 1248 | 60d36b03da86 |
child 1299 | 39c06aba09aa |
permissions | -rw-r--r-- |
1247 | 1 |
#include "stdafx.h" |
2 |
#include "ttd.h" |
|
3 |
#include "npf.h" |
|
4 |
#include "aystar.h" |
|
5 |
#include "macros.h" |
|
6 |
#include "pathfind.h" |
|
7 |
#include "station.h" |
|
8 |
#include "tile.h" |
|
9 |
||
10 |
AyStar _train_find_station; |
|
11 |
AyStar _train_find_depot; |
|
12 |
AyStar _road_find_station; |
|
13 |
AyStar _road_find_depot; |
|
14 |
AyStar _npf_aystar; |
|
15 |
||
16 |
/* Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
17 |
* direction along with the trackdir */ |
|
18 |
const byte _signal_along_trackdir[14] = { |
|
19 |
0x80, 0x80, 0x80, 0x20, 0x40, 0x10, 0, 0, |
|
20 |
0x40, 0x40, 0x40, 0x10, 0x80, 0x20 |
|
21 |
}; |
|
22 |
||
23 |
/* Maps a trackdir to the bit that stores its status in the map arrays, in the |
|
24 |
* direction against the trackdir */ |
|
25 |
const byte _signal_against_trackdir[14] = { |
|
26 |
0x40, 0x40, 0x40, 0x10, 0x80, 0x20, 0, 0, |
|
27 |
0x80, 0x80, 0x80, 0x20, 0x40, 0x10 |
|
28 |
}; |
|
29 |
||
30 |
/* Maps a trackdir to the trackdirs that can be reached from it (ie, when |
|
31 |
* entering the next tile */ |
|
32 |
const uint16 _trackdir_reaches_trackdirs[14] = { |
|
33 |
0x1009, 0x0016, 0x1009, 0x0016, 0x0520, 0x0016, 0, 0, |
|
34 |
0x0520, 0x2A00, 0x2A00, 0x0520, 0x2A00, 0x1009 |
|
35 |
}; |
|
36 |
||
37 |
/* Maps a trackdir to all trackdirs that make 90 deg turns with it. */ |
|
38 |
const uint16 _trackdir_crosses_trackdirs[14] = { |
|
39 |
0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C, 0, 0, |
|
40 |
0x0202, 0x0101, 0x3030, 0x3030, 0x0C0C, 0x0C0C |
|
41 |
}; |
|
42 |
||
43 |
/* Maps a track to all tracks that make 90 deg turns with it. */ |
|
44 |
const byte _track_crosses_tracks[6] = { |
|
45 |
0x2, /* Track 1 -> Track 2 */ |
|
46 |
0x1, /* Track 2 -> Track 1 */ |
|
47 |
0x30, /* Upper -> Left | Right */ |
|
48 |
0x30, /* Lower -> Left | Right */ |
|
49 |
0x0C, /* Left -> Upper | Lower */ |
|
50 |
0x0C, /* Right -> Upper | Lower */ |
|
51 |
}; |
|
52 |
||
53 |
/* Maps a trackdir to the (4-way) direction the tile is exited when following |
|
54 |
* that trackdir */ |
|
55 |
const byte _trackdir_to_exitdir[14] = { |
|
56 |
0,1,0,1,2,1, 0,0, |
|
57 |
2,3,3,2,3,0, |
|
58 |
}; |
|
59 |
||
60 |
const byte _track_exitdir_to_trackdir[6][4] = { |
|
61 |
{0, 0xff, 8, 0xff}, |
|
62 |
{0xff, 1, 0xff, 9}, |
|
63 |
{2, 0xff, 0xff, 10}, |
|
64 |
{0xff, 3, 11, 0xf}, |
|
65 |
{0xff, 0xff, 4, 12}, |
|
66 |
{13, 5, 0xff, 0xff} |
|
67 |
}; |
|
68 |
||
69 |
const byte _track_direction_to_trackdir[6][8] = { |
|
70 |
{0xff, 0, 0xff, 0xff, 0xff, 8, 0xff, 0xff}, |
|
71 |
{0xff, 0xff, 0xff, 1, 0xff, 0xff, 0xff, 9}, |
|
72 |
{0xff, 0xff, 2, 0xff, 0xff, 0xff, 10, 0xff}, |
|
73 |
{0xff, 0xff, 3, 0xff, 0xff, 0xff, 11, 0xff}, |
|
74 |
{12, 0xff, 0xff, 0xff, 4, 0xff, 0xff, 0xff}, |
|
75 |
{13, 0xff, 0xff, 0xff, 5, 0xff, 0xff, 0xff} |
|
76 |
}; |
|
77 |
||
78 |
const byte _dir_to_diag_trackdir[4] = { |
|
79 |
0, 1, 8, 9, |
|
80 |
}; |
|
81 |
||
82 |
const byte _reverse_dir[4] = { |
|
83 |
2, 3, 0, 1 |
|
84 |
}; |
|
85 |
||
86 |
const byte _reverse_trackdir[14] = { |
|
87 |
8, 9, 10, 11, 12, 13, 0xFF, 0xFF, |
|
88 |
0, 1, 2, 3, 4, 5 |
|
89 |
}; |
|
90 |
||
91 |
/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH, |
|
92 |
* the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071 |
|
93 |
*/ |
|
94 |
#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * 0.7071) |
|
95 |
static const uint _trackdir_length[14] = { |
|
96 |
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, 0, 0, |
|
97 |
NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH |
|
98 |
}; |
|
99 |
||
100 |
uint NTPHash(uint key1, uint key2) |
|
101 |
{ |
|
102 |
return PATHFIND_HASH_TILE(key1); |
|
103 |
} |
|
104 |
||
105 |
int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
106 |
return 0; |
|
107 |
} |
|
108 |
||
109 |
/* Calcs the heuristic to the target station (using NPFFindStationOrTileData). After |
|
110 |
* will save the heuristic into NPFFoundTargetData if it is the smallest until |
|
111 |
* now. It will then also save AyStarNode.user_data[NPF_TRACKDIR_CHOICE] in |
|
112 |
* best_trackdir |
|
113 |
*/ |
|
114 |
int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
115 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
|
116 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
|
117 |
TileIndex from = current->tile; |
|
118 |
TileIndex to = fstd->dest_coords; |
|
119 |
uint dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
|
120 |
||
121 |
if (dist < ftd->best_bird_dist) { |
|
122 |
ftd->best_bird_dist = dist; |
|
123 |
ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; |
|
124 |
} |
|
125 |
#ifdef NPF_DEBUG |
|
126 |
debug("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
|
127 |
#endif |
|
128 |
return dist; |
|
129 |
} |
|
130 |
||
131 |
/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to |
|
132 |
* get here, either getting it from the current choice or from the parent's |
|
133 |
* choice */ |
|
134 |
void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) |
|
135 |
{ |
|
136 |
if (parent->path.parent == NULL) { |
|
137 |
byte trackdir = current->direction; |
|
138 |
/* This is a first order decision, so we'd better save the |
|
139 |
* direction we chose */ |
|
140 |
current->user_data[NPF_TRACKDIR_CHOICE] = trackdir; |
|
141 |
#ifdef NPF_DEBUG |
|
142 |
debug("Saving trackdir: %#x", trackdir); |
|
143 |
#endif |
|
144 |
} else { |
|
145 |
/* We've already made the decision, so just save our parent's |
|
146 |
* decision */ |
|
147 |
current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
|
148 |
} |
|
149 |
||
150 |
} |
|
151 |
||
152 |
/* Will return the cost of the tunnel. If it is an entry, it will return the |
|
153 |
* cost of that tile. If the tile is an exit, it will return the tunnel length |
|
154 |
* including the exit tile. Requires that this is a Tunnel tile */ |
|
155 |
uint NPFTunnelCost(AyStarNode* current) { |
|
156 |
byte exitdir = _trackdir_to_exitdir[current->direction]; |
|
157 |
TileIndex tile = current->tile; |
|
158 |
if ( (uint)(_map5[tile] & 3) == _reverse_dir[exitdir]) { |
|
159 |
/* We just popped out if this tunnel, since were |
|
160 |
* facing the tunnel exit */ |
|
161 |
FindLengthOfTunnelResult flotr; |
|
162 |
flotr = FindLengthOfTunnel(tile, _reverse_dir[exitdir]); |
|
163 |
return flotr.length * NPF_TILE_LENGTH; |
|
164 |
//TODO: Penalty for tunnels? |
|
165 |
} else { |
|
166 |
/* We are entering the tunnel, the enter tile is just a |
|
167 |
* straight track */ |
|
168 |
return NPF_TILE_LENGTH; |
|
169 |
} |
|
170 |
} |
|
171 |
||
172 |
uint NPFSlopeCost(AyStarNode* current) { |
|
173 |
TileIndex next = current->tile + TileOffsByDir(_trackdir_to_exitdir[current->direction]); |
|
174 |
if (GetTileZ(next) > GetTileZ(current->tile)) { |
|
175 |
/* Slope up */ |
|
176 |
return _patches.npf_rail_slope_penalty; |
|
177 |
} |
|
178 |
return 0; |
|
179 |
/* Should we give a bonus for slope down? Probably not, we |
|
180 |
* could just substract that bonus from the penalty, because |
|
181 |
* there is only one level of steepness... */ |
|
182 |
} |
|
183 |
||
184 |
void NPFMarkTile(TileIndex tile) { |
|
185 |
switch(GetTileType(tile)) { |
|
186 |
case MP_RAILWAY: |
|
187 |
case MP_STREET: |
|
188 |
/* DEBUG: mark visited tiles by mowing the grass under them |
|
189 |
* ;-) */ |
|
190 |
_map2[tile] &= ~15; |
|
191 |
MarkTileDirtyByTile(tile); |
|
192 |
break; |
|
193 |
default: |
|
194 |
break; |
|
195 |
} |
|
196 |
} |
|
197 |
||
198 |
int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
199 |
//TileIndex tile = current->tile; |
|
200 |
int32 cost = 0; |
|
201 |
byte trackdir = current->direction; |
|
202 |
||
203 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
204 |
||
205 |
/* TODO Penalties? */ |
|
206 |
||
207 |
return cost; |
|
208 |
} |
|
209 |
||
210 |
/* Determine the cost of this node, for road tracks */ |
|
211 |
int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
212 |
TileIndex tile = current->tile; |
|
213 |
int32 cost = 0; |
|
214 |
/* Determine base length */ |
|
215 |
switch (GetTileType(tile)) { |
|
216 |
case MP_TUNNELBRIDGE: |
|
217 |
if ((_map5[tile] & 0xF0)==0) { |
|
218 |
cost = NPFTunnelCost(current); |
|
219 |
break; |
|
220 |
} |
|
221 |
/* Fall through if above if is false, it is a bridge |
|
222 |
* then. We treat that as ordinary rail */ |
|
223 |
case MP_STREET: |
|
224 |
cost = NPF_TILE_LENGTH; |
|
225 |
break; |
|
226 |
default: |
|
227 |
break; |
|
228 |
} |
|
229 |
||
230 |
/* Determine extra costs */ |
|
231 |
||
232 |
/* Check for slope */ |
|
233 |
cost += NPFSlopeCost(current); |
|
234 |
||
235 |
/* Check for turns */ |
|
236 |
//TODO |
|
237 |
||
238 |
#ifdef NPF_MARKROUTE |
|
239 |
NPFMarkTile(tile); |
|
240 |
#endif |
|
241 |
#ifdef NPF_DEBUG |
|
242 |
debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
|
243 |
#endif |
|
244 |
return cost; |
|
245 |
} |
|
246 |
||
247 |
||
248 |
/* Determine the cost of this node, for railway tracks */ |
|
249 |
int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { |
|
250 |
TileIndex tile = current->tile; |
|
251 |
byte trackdir = current->direction; |
|
252 |
int32 cost = 0; |
|
253 |
/* Determine base length */ |
|
254 |
switch (GetTileType(tile)) { |
|
255 |
case MP_TUNNELBRIDGE: |
|
256 |
if ((_map5[tile] & 0xF0)==0) { |
|
257 |
cost = NPFTunnelCost(current); |
|
258 |
break; |
|
259 |
} |
|
260 |
/* Fall through if above if is false, it is a bridge |
|
261 |
* then. We treat that as ordinary rail */ |
|
262 |
case MP_RAILWAY: |
|
263 |
cost = _trackdir_length[trackdir]; /* Should be different for diagonal tracks */ |
|
264 |
break; |
|
265 |
case MP_STREET: /* Railway crossing */ |
|
266 |
cost = NPF_TILE_LENGTH; |
|
267 |
break; |
|
268 |
default: |
|
269 |
break; |
|
270 |
} |
|
271 |
||
272 |
/* Determine extra costs */ |
|
273 |
||
274 |
/* Ordinary track with signals */ |
|
275 |
if (IsTileType(tile, MP_RAILWAY) && (_map5[tile] & 0xC0) == 0x40) { |
|
276 |
if ((_map2[tile] & _signal_along_trackdir[trackdir]) == 0) { |
|
277 |
/* Signal facing us is red */ |
|
278 |
if (!(current->user_data[NPF_NODE_FLAGS] & NPF_FLAG_SEEN_SIGNAL)) { |
|
279 |
/* Penalize the first signal we |
|
280 |
* encounter, if it is red */ |
|
281 |
cost += _patches.npf_rail_firstred_penalty; |
|
282 |
} |
|
283 |
} |
|
284 |
current->user_data[NPF_NODE_FLAGS] |= NPF_FLAG_SEEN_SIGNAL; |
|
285 |
} |
|
286 |
||
287 |
/* Check for slope */ |
|
288 |
cost += NPFSlopeCost(current); |
|
289 |
||
290 |
/* Check for turns */ |
|
291 |
//TODO |
|
292 |
||
293 |
/* Check for occupied track */ |
|
294 |
//TODO |
|
295 |
||
296 |
/* Check for station tiles */ |
|
297 |
if (IsTileType(tile, MP_STATION)) { |
|
298 |
/* We give a station tile a penalty. Logically we would only |
|
299 |
* want to give station tiles that are not our destination |
|
300 |
* this penalty. This would discourage trains to drive through |
|
301 |
* busy stations. But, we can just give any station tile a |
|
302 |
* penalty, because every possible route will get this penalty |
|
303 |
* exactly once, on its end tile (if it's a station) and it |
|
304 |
* will therefore not make a difference. */ |
|
305 |
cost += _patches.npf_rail_station_penalty; |
|
306 |
} |
|
307 |
||
308 |
#ifdef NPF_MARKROUTE |
|
309 |
NPFMarkTile(tile); |
|
310 |
#endif |
|
311 |
#ifdef NPF_DEBUG |
|
312 |
debug("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost); |
|
313 |
#endif |
|
314 |
return cost; |
|
315 |
} |
|
316 |
||
317 |
/* Will find any depot */ |
|
318 |
int32 NPFFindDepot(AyStar* as, OpenListNode *current) { |
|
319 |
TileIndex tile = current->path.node.tile; |
|
320 |
bool isDepot; |
|
321 |
switch(GetTileType(tile)) { |
|
322 |
case MP_RAILWAY: |
|
323 |
/* Check if this is a rail depot */ |
|
324 |
isDepot = IsTrainDepotTile(tile); |
|
325 |
break; |
|
326 |
case MP_STREET: |
|
327 |
/* Check if this is a road depot */ |
|
328 |
isDepot = IsRoadDepotTile(tile); |
|
329 |
break; |
|
330 |
case MP_WATER: |
|
331 |
isDepot = IsShipDepotTile(tile); |
|
332 |
break; |
|
333 |
default: |
|
334 |
isDepot = false; |
|
335 |
break; |
|
336 |
} |
|
337 |
if (isDepot) |
|
338 |
return AYSTAR_FOUND_END_NODE; |
|
339 |
else |
|
340 |
return AYSTAR_DONE; |
|
341 |
} |
|
342 |
||
343 |
/* Will find a station identified using the NPFFindStationOrTileData */ |
|
344 |
int32 NPFFindStationOrTile(AyStar* as, OpenListNode *current) { |
|
345 |
/* If GetNeighbours said we could get here, we assume the station type |
|
346 |
* is correct */ |
|
347 |
NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
|
348 |
TileIndex tile = current->path.node.tile; |
|
349 |
if ( (fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */ |
|
350 |
(IsTileType(tile, MP_STATION) && _map2[tile] == fstd->station_index) /* the station */ |
|
351 |
) |
|
352 |
return AYSTAR_FOUND_END_NODE; |
|
353 |
else |
|
354 |
return AYSTAR_DONE; |
|
355 |
} |
|
356 |
||
357 |
/* To be called when current contains the (shortest route to) the target node. |
|
358 |
* Will fill the contents of the NPFFoundTargetData using |
|
359 |
* AyStarNode[NPF_TRACKDIR_CHOICE]. |
|
360 |
*/ |
|
361 |
void NPFSaveTargetData(AyStar* as, OpenListNode* current) { |
|
362 |
NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
|
363 |
ftd->best_trackdir = current->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
|
364 |
ftd->best_path_dist = current->g; |
|
365 |
ftd->best_bird_dist = 0; |
|
366 |
ftd->node = current->path.node; |
|
367 |
} |
|
368 |
||
369 |
/* Will just follow the results of GetTileTrackStatus concerning where we can |
|
370 |
* go and where not. Uses AyStar.user_data[NPF_TYPE] as the transport type and |
|
371 |
* an argument to GetTileTrackStatus. Will skip tunnels, meaning that the |
|
372 |
* entry and exit are neighbours. Will fill AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an |
|
373 |
* appropriate value, and copy AyStarNode.user_data[NPF_NODE_FLAGS] from the |
|
374 |
* parent */ |
|
375 |
void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { |
|
376 |
byte src_trackdir = current->path.node.direction; |
|
377 |
TileIndex src_tile = current->path.node.tile; |
|
378 |
byte src_exitdir = _trackdir_to_exitdir[src_trackdir]; |
|
379 |
FindLengthOfTunnelResult flotr; |
|
380 |
TileIndex dst_tile; |
|
381 |
int i = 0; |
|
382 |
uint trackdirs, ts; |
|
383 |
TransportType type = aystar->user_data[NPF_TYPE]; |
|
384 |
/* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
|
385 |
aystar->num_neighbours = 0; |
|
386 |
#ifdef NPF_DEBUG |
|
387 |
debug("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
|
388 |
#endif |
|
389 |
||
390 |
/* Find dest tile */ |
|
391 |
if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (_map5[src_tile] & 3) == src_exitdir) { |
|
392 |
/* This is a tunnel. We know this tunnel is our type, |
|
393 |
* otherwise we wouldn't have got here. It is also facing us, |
|
394 |
* so we should skip it's body */ |
|
395 |
flotr = FindLengthOfTunnel(src_tile, src_exitdir); |
|
396 |
dst_tile = flotr.tile; |
|
397 |
} else { |
|
398 |
if ( |
|
399 |
(type == TRANSPORT_ROAD && IsRoadStationTile(src_tile)) |
|
400 |
|| (type == TRANSPORT_ROAD && IsRoadDepotTile(src_tile)) |
|
401 |
|| (type == TRANSPORT_RAIL && IsTrainDepotTile(src_tile)) |
|
402 |
){ |
|
403 |
/* This is a road station or a train or road depot. We can enter and exit |
|
404 |
* those from one side only. Trackdirs don't support that (yet), so we'll |
|
405 |
* do this here. */ |
|
406 |
||
407 |
byte exitdir; |
|
408 |
/* Find out the exit direction first */ |
|
409 |
if (IsRoadStationTile(src_tile)) |
|
410 |
exitdir = GetRoadStationDir(src_tile); |
|
411 |
else /* Train or road depot. Direction is stored the same for both, in map5 */ |
|
412 |
exitdir = _map5[src_tile] & 3; /* Extract the direction from the map */ |
|
413 |
||
414 |
/* Let's see if were headed the right way */ |
|
415 |
if (src_trackdir != _dir_to_diag_trackdir[exitdir]) |
|
416 |
/* Not going out of the station/depot through the exit, but the back. No |
|
417 |
* neighbours then. */ |
|
418 |
return; |
|
419 |
} |
|
420 |
/* This a normal tile, a bridge, a tunnel exit, etc. */ |
|
421 |
dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(_trackdir_to_exitdir[src_trackdir])); |
|
422 |
if (dst_tile == INVALID_TILE) { |
|
423 |
/* We reached the border of the map */ |
|
424 |
/* TODO Nicer control flow for this */ |
|
425 |
return; |
|
426 |
} |
|
427 |
} |
|
428 |
||
429 |
// TODO: check correct rail type (mono, maglev, etc) |
|
430 |
// TODO: check tile owner |
|
431 |
||
432 |
/* Determine available tracks */ |
|
433 |
if (type == TRANSPORT_ROAD && (IsRoadStationTile(dst_tile) || IsRoadDepotTile(dst_tile))){ |
|
434 |
byte exitdir; |
|
435 |
/* Road stations and depots return 0 on GTTS, so we have to do this by hand... */ |
|
436 |
if (IsRoadStationTile(dst_tile)) |
|
437 |
exitdir = GetRoadStationDir(dst_tile); |
|
438 |
else /* Road depot */ |
|
439 |
exitdir = _map5[dst_tile] & 3; /* Extract the direction from the map */ |
|
440 |
ts = (1 << _dir_to_diag_trackdir[exitdir]) | |
|
441 |
(1 << _dir_to_diag_trackdir[_reverse_dir[exitdir]]); |
|
442 |
/* Find the trackdirs that are available for a station with this orientation. They are in both directions */ |
|
443 |
} else { |
|
444 |
ts = GetTileTrackStatus(dst_tile, type); |
|
445 |
} |
|
446 |
trackdirs = ts & 0x3F3F; /* Filter out signal status and the unused bits */ |
|
447 |
||
448 |
#ifdef NPF_DEBUG |
|
449 |
debug("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirs); |
|
450 |
#endif |
|
451 |
/* Select only trackdirs we can reach from our current trackdir */ |
|
452 |
trackdirs &= _trackdir_reaches_trackdirs[src_trackdir]; |
|
453 |
if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
|
454 |
trackdirs &= ~_trackdir_crosses_trackdirs[src_trackdir]; |
|
455 |
#ifdef NPF_DEBUG |
|
456 |
debug("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirs); |
|
457 |
#endif |
|
458 |
||
459 |
/* Enumerate possible track */ |
|
460 |
while (trackdirs != 0) { |
|
461 |
byte dst_trackdir; |
|
462 |
dst_trackdir = FindFirstBit2x64(trackdirs); |
|
463 |
trackdirs = KillFirstBit2x64(trackdirs); |
|
464 |
#ifdef NPF_DEBUG |
|
465 |
debug("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirs); |
|
466 |
#endif |
|
467 |
||
468 |
/* Check for oneway signal against us */ |
|
469 |
if (IsTileType(dst_tile, MP_RAILWAY) && (_map5[dst_tile]&0xC0) == 0x40) { |
|
470 |
// the tile has a signal |
|
471 |
byte signal_present = _map3_lo[dst_tile]; |
|
472 |
if (!(signal_present & _signal_along_trackdir[dst_trackdir])) { |
|
473 |
// if one way signal not pointing towards us, stop going in this direction. |
|
474 |
if (signal_present & _signal_against_trackdir[dst_trackdir]) |
|
475 |
break; |
|
476 |
} |
|
477 |
} |
|
478 |
{ |
|
479 |
/* We've found ourselves a neighbour :-) */ |
|
480 |
AyStarNode* neighbour = &aystar->neighbours[i]; |
|
481 |
neighbour->tile = dst_tile; |
|
482 |
neighbour->direction = dst_trackdir; |
|
483 |
/* Save user data */ |
|
484 |
neighbour->user_data[NPF_NODE_FLAGS] = current->path.node.user_data[NPF_NODE_FLAGS]; |
|
485 |
NPFFillTrackdirChoice(neighbour, current); |
|
486 |
} |
|
487 |
i++; |
|
488 |
} |
|
489 |
aystar->num_neighbours = i; |
|
490 |
} |
|
491 |
||
492 |
/* |
|
493 |
* Plan a route to the specified target (which is checked by target_proc), |
|
494 |
* from start1 and if not NULL, from start2 as well. The type of transport we |
|
495 |
* are checking is in type. |
|
496 |
* When we are looking for one specific target (optionally multiple tiles), we |
|
497 |
* should use a good heuristic to perform aystar search. When we search for |
|
498 |
* multiple targets that are spread around, we should perform a breadth first |
|
499 |
* search by specifiying CalcZero as our heuristic. |
|
500 |
*/ |
|
501 |
NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type) { |
|
502 |
int r; |
|
503 |
NPFFoundTargetData result; |
|
504 |
||
505 |
/* Initialize procs */ |
|
506 |
_npf_aystar.CalculateH = heuristic_proc; |
|
507 |
_npf_aystar.EndNodeCheck = target_proc; |
|
508 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
509 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
510 |
if (type == TRANSPORT_RAIL) |
|
511 |
_npf_aystar.CalculateG = NPFRailPathCost; |
|
512 |
else if (type == TRANSPORT_ROAD) |
|
513 |
_npf_aystar.CalculateG = NPFRoadPathCost; |
|
514 |
else if (type == TRANSPORT_WATER) |
|
515 |
_npf_aystar.CalculateG = NPFWaterPathCost; |
|
516 |
else |
|
517 |
assert(0); |
|
518 |
||
519 |
/* Initialize Start Node(s) */ |
|
520 |
start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
521 |
start1->user_data[NPF_NODE_FLAGS] = 0; |
|
522 |
_npf_aystar.addstart(&_npf_aystar, start1); |
|
523 |
if (start2) { |
|
524 |
start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
525 |
start2->user_data[NPF_NODE_FLAGS] = NPF_FLAG_REVERSE; |
|
526 |
_npf_aystar.addstart(&_npf_aystar, start2); |
|
527 |
} |
|
528 |
||
529 |
/* Initialize result */ |
|
530 |
result.best_bird_dist = (uint)-1; |
|
531 |
result.best_path_dist = (uint)-1; |
|
532 |
result.best_trackdir = 0xff; |
|
533 |
_npf_aystar.user_path = &result; |
|
534 |
||
535 |
/* Initialize target */ |
|
536 |
_npf_aystar.user_target = target; |
|
537 |
||
538 |
/* Initialize user_data */ |
|
539 |
_npf_aystar.user_data[NPF_TYPE] = type; |
|
540 |
||
541 |
/* GO! */ |
|
542 |
r = AyStarMain_Main(&_npf_aystar); |
|
543 |
assert(r != AYSTAR_STILL_BUSY); |
|
544 |
||
545 |
if (result.best_bird_dist != 0) { |
|
546 |
if (target) { |
|
547 |
DEBUG(misc, 1) ("NPF: Could not find route to 0x%x from 0x%x.", target->dest_coords, start1->tile); |
|
548 |
} else { |
|
549 |
/* Assumption: target == NULL, so we are looking for a depot */ |
|
550 |
DEBUG(misc, 1) ("NPF: Could not find route to a depot from 0x%x.", start1->tile); |
|
551 |
} |
|
552 |
||
553 |
} |
|
554 |
return result; |
|
555 |
} |
|
556 |
||
557 |
NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type) { |
|
558 |
AyStarNode start1; |
|
559 |
AyStarNode start2; |
|
560 |
||
561 |
start1.tile = tile1; |
|
562 |
start2.tile = tile2; |
|
563 |
start1.direction = trackdir1; |
|
564 |
start2.direction = trackdir2; |
|
565 |
||
566 |
return NPFRouteInternal(&start1, &start2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type); |
|
567 |
} |
|
568 |
||
569 |
NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type) { |
|
570 |
AyStarNode start; |
|
571 |
||
572 |
assert(tile != 0); |
|
573 |
||
574 |
start.tile = tile; |
|
575 |
start.direction = trackdir; |
|
576 |
/* We set this in case the target is also the start tile, we will just |
|
577 |
* return a not found then */ |
|
578 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
579 |
||
580 |
return NPFRouteInternal(&start, NULL, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type); |
|
581 |
} |
|
582 |
||
583 |
NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type) { |
|
584 |
AyStarNode start; |
|
585 |
||
586 |
start.tile = tile; |
|
587 |
start.direction = trackdir; |
|
588 |
/* We set this in case the target is also the start tile, we will just |
|
589 |
* return a not found then */ |
|
590 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
591 |
||
592 |
/* perform a breadth first search. Target is NULL, |
|
593 |
* since we are just looking for any depot...*/ |
|
594 |
return NPFRouteInternal(&start, NULL, NULL, NPFFindDepot, NPFCalcZero, type); |
|
595 |
} |
|
596 |
||
597 |
NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type) { |
|
598 |
/* Okay, what we're gonna do. First, we look at all depots, calculate |
|
599 |
* the manhatten distance to get to each depot. We then sort them by |
|
600 |
* distance. We start by trying to plan a route to the closest, then |
|
601 |
* the next closest, etc. We stop when the best route we have found so |
|
602 |
* far, is shorter than the manhattan distance. This will obviously |
|
603 |
* always find the closest depot. It will probably be most efficient |
|
604 |
* for ships, since the heuristic will not be to far off then. I hope. |
|
605 |
*/ |
|
606 |
Queue depots; |
|
607 |
uint i; |
|
608 |
TileType tiletype = 0; |
|
609 |
int r; |
|
610 |
NPFFoundTargetData best_result; |
|
611 |
NPFFoundTargetData result; |
|
612 |
NPFFindStationOrTileData target; |
|
613 |
AyStarNode start; |
|
614 |
Depot* current; |
|
615 |
||
616 |
||
617 |
/* This is a little ugly, but it works :-S */ |
|
618 |
if (type == TRANSPORT_ROAD) |
|
619 |
tiletype = MP_STREET; |
|
620 |
else if (type == TRANSPORT_RAIL) |
|
621 |
tiletype = MP_RAILWAY; |
|
622 |
else if (type == TRANSPORT_WATER) |
|
623 |
tiletype = MP_WATER; |
|
624 |
else |
|
625 |
assert(0); |
|
626 |
||
627 |
init_InsSort(&depots); |
|
628 |
/* Okay, let's find all depots that we can use first */ |
|
629 |
for (i=0;i<lengthof(_depots);i++) { |
|
630 |
int depot_tile = _depots[i].xy; |
|
631 |
if (IsTileType(depot_tile, tiletype)) |
|
632 |
depots.push(&depots, &_depots[i], DistanceManhattan(tile, depot_tile)); |
|
633 |
||
634 |
} |
|
635 |
||
636 |
/* Now, let's initialise the aystar */ |
|
637 |
||
638 |
/* Initialize procs */ |
|
639 |
_npf_aystar.CalculateH = NPFCalcStationOrTileHeuristic; |
|
640 |
_npf_aystar.EndNodeCheck = NPFFindStationOrTile; |
|
641 |
_npf_aystar.FoundEndNode = NPFSaveTargetData; |
|
642 |
_npf_aystar.GetNeighbours = NPFFollowTrack; |
|
643 |
if (type == TRANSPORT_RAIL) |
|
644 |
_npf_aystar.CalculateG = NPFRailPathCost; |
|
645 |
else if (type == TRANSPORT_ROAD) |
|
646 |
_npf_aystar.CalculateG = NPFRoadPathCost; |
|
647 |
else if (type == TRANSPORT_WATER) |
|
648 |
_npf_aystar.CalculateG = NPFWaterPathCost; |
|
649 |
else |
|
650 |
assert(0); |
|
651 |
||
652 |
/* Initialize target */ |
|
653 |
target.station_index = -1; /* We will initialize dest_coords inside the loop below */ |
|
654 |
_npf_aystar.user_target = ⌖ |
|
655 |
||
656 |
/* Initialize user_data */ |
|
657 |
_npf_aystar.user_data[NPF_TYPE] = type; |
|
658 |
||
659 |
/* Initialize Start Node */ |
|
660 |
start.tile = tile; |
|
661 |
start.direction = trackdir; /* We will initialize user_data inside the loop below */ |
|
662 |
||
663 |
/* Initialize Result */ |
|
664 |
_npf_aystar.user_path = &result; |
|
665 |
best_result.best_path_dist = (uint)-1; |
|
666 |
||
667 |
/* Just iterate the depots in order of increasing distance */ |
|
668 |
while ((current = depots.pop(&depots))) { |
|
669 |
/* Check to see if we already have a path shorter than this |
|
670 |
* depot's manhattan distance. Hack: We call DistanceManhattan |
|
671 |
* again, we should probably modify the queue to give us that |
|
672 |
* value... */ |
|
673 |
if ( DistanceManhattan(tile, current->xy * NPF_TILE_LENGTH) > best_result.best_path_dist) |
|
674 |
break; |
|
675 |
||
676 |
/* Initialize Start Node */ |
|
677 |
/* We set this in case the target is also the start tile, we will just |
|
678 |
* return a not found then */ |
|
679 |
start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; |
|
680 |
start.user_data[NPF_NODE_FLAGS] = 0; |
|
681 |
_npf_aystar.addstart(&_npf_aystar, &start); |
|
682 |
||
683 |
/* Initialize result */ |
|
684 |
result.best_bird_dist = (uint)-1; |
|
685 |
result.best_path_dist = (uint)-1; |
|
686 |
result.best_trackdir = 0xff; |
|
687 |
||
688 |
/* Initialize target */ |
|
689 |
target.dest_coords = current->xy; |
|
690 |
||
691 |
/* GO! */ |
|
692 |
r = AyStarMain_Main(&_npf_aystar); |
|
693 |
assert(r != AYSTAR_STILL_BUSY); |
|
694 |
||
695 |
/* This depot is closer */ |
|
696 |
if (result.best_path_dist < best_result.best_path_dist) |
|
697 |
best_result = result; |
|
698 |
} |
|
699 |
if (result.best_bird_dist != 0) { |
|
700 |
DEBUG(misc, 1) ("NPF: Could not find route to any depot from 0x%x.", tile); |
|
701 |
} |
|
702 |
return best_result; |
|
703 |
} |
|
704 |
||
705 |
void InitializeNPF(void) |
|
706 |
{ |
|
707 |
init_AyStar(&_npf_aystar, NTPHash, 1024); |
|
708 |
_npf_aystar.loops_per_tick = 0; |
|
709 |
_npf_aystar.max_path_cost = 0; |
|
710 |
_npf_aystar.max_search_nodes = 0; |
|
711 |
/* |
|
712 |
init_AyStar(&_train_find_station, NTPHash, 1024); |
|
713 |
init_AyStar(&_train_find_depot, NTPHash, 1024); |
|
714 |
init_AyStar(&_road_find_station, NTPHash, 1024); |
|
715 |
init_AyStar(&_road_find_depot, NTPHash, 1024); |
|
716 |
||
717 |
_train_find_station.loops_per_tick = 0; |
|
718 |
_train_find_depot.loops_per_tick = 0; |
|
719 |
_road_find_station.loops_per_tick = 0; |
|
720 |
_road_find_depot.loops_per_tick = 0; |
|
721 |
||
722 |
_train_find_station.max_path_cost = 0; |
|
723 |
_train_find_depot.max_path_cost = 0; |
|
724 |
_road_find_station.max_path_cost = 0; |
|
725 |
_road_find_depot.max_path_cost = 0; |
|
726 |
||
727 |
_train_find_station.max_search_nodes = 0; |
|
728 |
_train_find_depot.max_search_nodes = 0; |
|
729 |
_road_find_station.max_search_nodes = 0; |
|
730 |
_road_find_depot.max_search_nodes = 0; |
|
731 |
||
732 |
_train_find_station.CalculateG = NPFRailPathCost; |
|
733 |
_train_find_depot.CalculateG = NPFRailPathCost; |
|
734 |
_road_find_station.CalculateG = NPFRoadPathCost; |
|
735 |
_road_find_depot.CalculateG = NPFRoadPathCost; |
|
736 |
||
737 |
_train_find_station.CalculateH = NPFCalcStationHeuristic; |
|
738 |
_train_find_depot.CalculateH = NPFCalcStationHeuristic; |
|
739 |
_road_find_station.CalculateH = NPFCalcStationHeuristic; |
|
740 |
_road_find_depot.CalculateH = NPFCalcStationHeuristic; |
|
741 |
||
742 |
_train_find_station.EndNodeCheck = NPFFindStationOrTile; |
|
743 |
_train_find_depot.EndNodeCheck = NPFFindStationOrTile; |
|
744 |
_road_find_station.EndNodeCheck = NPFFindStationOrTile; |
|
745 |
_road_find_depot.EndNodeCheck = NPFFindStationOrTile; |
|
746 |
||
747 |
_train_find_station.FoundEndNode = NPFSaveTargetData; |
|
748 |
_train_find_depot.FoundEndNode = NPFSaveTargetData; |
|
749 |
_road_find_station.FoundEndNode = NPFSaveTargetData; |
|
750 |
_road_find_depot.FoundEndNode = NPFSaveTargetData; |
|
751 |
||
752 |
_train_find_station.GetNeighbours = NPFFollowTrack; |
|
753 |
_train_find_depot.GetNeighbours = NPFFollowTrack; |
|
754 |
_road_find_station.GetNeighbours = NPFFollowTrack; |
|
755 |
_road_find_depot.GetNeighbours = NPFFollowTrack; |
|
756 |
*/ |
|
757 |
} |
|
758 |
||
759 |
void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v) { |
|
760 |
/* Ships don't really reach their stations, but the tile in front. So don't |
|
761 |
* save the station id for ships. For roadvehs we don't store it either, |
|
762 |
* because multistop depends on vehicles actually reaching the exact |
|
763 |
* dest_tile, not just any stop of that station. |
|
764 |
* So only for train orders to stations we fill fstd->station_index, for all |
|
765 |
* others only dest_coords */ |
|
766 |
if ((v->current_order.type) == OT_GOTO_STATION && v->type == VEH_Train) { |
|
1248
60d36b03da86
(svn r1752) - Fix: MSVC acting up once again, as well as project file updates for the missing files.
darkvater
parents:
1247
diff
changeset
|
767 |
const Station* st = GetStation(v->current_order.station); |
60d36b03da86
(svn r1752) - Fix: MSVC acting up once again, as well as project file updates for the missing files.
darkvater
parents:
1247
diff
changeset
|
768 |
TileIndexDiffC center = {st->trainst_w/2, st->trainst_h/2}; |
1247 | 769 |
fstd->station_index = v->current_order.station; |
770 |
/* Let's take the center of the station as our target tile for trains */ |
|
771 |
fstd->dest_coords = TILE_ADD(st->train_tile, ToTileIndexDiff(center)); |
|
772 |
} else { |
|
773 |
fstd->dest_coords = v->dest_tile; |
|
774 |
fstd->station_index = -1; |
|
775 |
} |
|
776 |
} |