19 NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, |
19 NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, |
20 0, 0, |
20 0, 0, |
21 NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH |
21 NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH |
22 }; |
22 }; |
23 |
23 |
|
24 /** |
|
25 * Check if a rail track is the end of the line. Will also consider 1-way signals to be the end of a line. |
|
26 * @param tile The tile on which the current track is. |
|
27 * @param trackdir The (track)direction in which you want to look |
|
28 */ |
|
29 bool IsEndOfLine(TileIndex tile, Trackdir trackdir) |
|
30 { |
|
31 byte exitdir = TrackdirToExitdir(trackdir); |
|
32 TileIndex dst_tile; |
|
33 uint32 ts; |
|
34 |
|
35 // tunnel entrance? |
|
36 if (IsTileType(tile, MP_TUNNELBRIDGE) && (_map5[tile] & 0xF0)==0 && (_map5[tile] & 3) == exitdir) |
|
37 return false; |
|
38 |
|
39 // depot |
|
40 if (IsTileDepotType(tile, TRANSPORT_RAIL)) |
|
41 return false; |
|
42 |
|
43 /* Calculate next tile */ |
|
44 dst_tile = tile + TileOffsByDir(exitdir); |
|
45 // determine the track status on the next tile. |
|
46 ts = GetTileTrackStatus(dst_tile, TRANSPORT_RAIL) & TrackdirReachesTrackdirs(trackdir); |
|
47 |
|
48 // when none of the trackdir bits are set, we cant enter the new tile |
|
49 if ( (ts & TRACKDIR_BIT_MASK) == 0) |
|
50 return true; |
|
51 |
|
52 { |
|
53 byte src_type = GetTileRailType(tile, trackdir); |
|
54 byte dst_type = GetTileRailType(dst_tile, TrackdirToExitdir(trackdir)); |
|
55 if (src_type != dst_type) { |
|
56 return true; |
|
57 } |
|
58 if (GetTileOwner(tile) != GetTileOwner(dst_tile)) |
|
59 return true; |
|
60 |
|
61 if (IsTileDepotType(dst_tile, TRANSPORT_RAIL) && (TrackdirToExitdir(trackdir) != ReverseDiagdir(GetDepotDirection(dst_tile, TRANSPORT_RAIL)))) |
|
62 return true; |
|
63 |
|
64 /* Check for oneway signal against us */ |
|
65 if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TYPE_SIGNALS) { |
|
66 if (HasSignalOnTrackdir(dst_tile, ReverseTrackdir(FindFirstBit2x64(ts))) && !HasSignalOnTrackdir(dst_tile, FindFirstBit2x64(ts))) |
|
67 // if one way signal not pointing towards us, stop going in this direction. |
|
68 return true; |
|
69 } |
|
70 |
|
71 return false; |
|
72 } |
|
73 }; |
|
74 |
24 static uint NTPHash(uint key1, uint key2) |
75 static uint NTPHash(uint key1, uint key2) |
25 { |
76 { |
26 /* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */ |
77 /* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */ |
27 return PATHFIND_HASH_TILE(key1); |
78 return PATHFIND_HASH_TILE(key1); |
28 } |
79 } |
74 |
125 |
75 // return the tile of our target coordinates |
126 // return the tile of our target coordinates |
76 return TileXY(x, y); |
127 return TileXY(x, y); |
77 }; |
128 }; |
78 |
129 |
|
130 /* On PBS pathfinding runs, this is called before pathfinding ends (BeforeExit aystar callback), and will |
|
131 * reserve the appropriate tracks, if needed. */ |
|
132 void NPFReservePBSPath(AyStar *as) |
|
133 { |
|
134 NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
|
135 bool eol_end = false; |
|
136 |
|
137 if (ftd->best_trackdir == 0xFF) |
|
138 return; |
|
139 |
|
140 if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_EXIT) && IsEndOfLine(ftd->node.tile, ftd->node.direction) && !NPFGetFlag(&ftd->node, NPF_FLAG_SEEN_SIGNAL)) { |
|
141 /* The path ends in an end of line, we'll need to reserve a path. |
|
142 * We treat and end of line as a red exit signal */ |
|
143 eol_end = true; |
|
144 NPFSetFlag(&ftd->node, NPF_FLAG_PBS_EXIT, true); |
|
145 if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_TARGET_SEEN)) |
|
146 NPFSetFlag(&ftd->node, NPF_FLAG_PBS_RED, true); |
|
147 } |
|
148 |
|
149 if (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_CHOICE)) { |
|
150 /* there have been no choices to make on our path, we dont care if our end signal is red */ |
|
151 NPFSetFlag(&ftd->node, NPF_FLAG_PBS_RED, false); |
|
152 } |
|
153 |
|
154 if (NPFGetFlag(&ftd->node, NPF_FLAG_PBS_EXIT) && // we passed an exit signal |
|
155 !NPFGetFlag(&ftd->node, NPF_FLAG_PBS_BLOCKED) && // we didnt encounter reserver tracks |
|
156 ((as->user_data[NPF_PBS_MODE] != PBS_MODE_GREEN) || (!NPFGetFlag(&ftd->node, NPF_FLAG_PBS_RED))) ) { // our mode permits having a red exit signal, or the signal is green |
|
157 PathNode parent; |
|
158 PathNode *curr; |
|
159 PathNode *prev; |
|
160 TileIndex start = INVALID_TILE; |
|
161 byte trackdir = 0; |
|
162 |
|
163 parent.node = ftd->node; |
|
164 parent.parent = &ftd->path; |
|
165 curr = &parent; |
|
166 prev = NULL; |
|
167 |
|
168 do { |
|
169 if (!NPFGetFlag(&curr->node, NPF_FLAG_PBS_EXIT) || eol_end) { |
|
170 /* check for already reserved track on this path, if they clash with what we |
|
171 currently trying to reserve, we have a self-crossing path :-( */ |
|
172 if ((PBSTileUnavail(curr->node.tile) & (1 << curr->node.direction)) |
|
173 && !(PBSTileReserved(curr->node.tile) & (1 << (curr->node.direction & 7))) |
|
174 && (start != INVALID_TILE)) { |
|
175 /* It's actually quite bad if this happens, it means the pathfinder |
|
176 * found a path that is intersecting with itself, which is a very bad |
|
177 * thing in a pbs block. Also there is not much we can do about it at |
|
178 * this point.... |
|
179 * BUT, you have to have a pretty fucked up junction layout for this to happen, |
|
180 * so we'll just stop this train, the user will eventually notice, so he can fix it. |
|
181 */ |
|
182 PBSClearPath(start, trackdir); |
|
183 NPFSetFlag(&ftd->node, NPF_FLAG_PBS_BLOCKED, true); |
|
184 DEBUG(pbs, 1) ("PBS: Self-crossing path!!!"); |
|
185 return; |
|
186 }; |
|
187 |
|
188 PBSReserveTrack(curr->node.tile, (curr->node.direction & 7) ); |
|
189 |
|
190 /* we want to reserve the last tile (with the signal) on the path too */ |
|
191 if (prev != NULL && start == INVALID_TILE) { |
|
192 PBSReserveTrack(prev->node.tile, (prev->node.direction & 7) ); |
|
193 start = prev->node.tile; |
|
194 trackdir = ReverseTrackdir(prev->node.direction); |
|
195 } |
|
196 } |
|
197 |
|
198 prev = curr; |
|
199 curr = curr->parent; |
|
200 } while (curr != NULL); |
|
201 } |
|
202 |
|
203 } |
|
204 |
|
205 |
79 /* Calcs the heuristic to the target station or tile. For train stations, it |
206 /* Calcs the heuristic to the target station or tile. For train stations, it |
80 * takes into account the direction of approach. |
207 * takes into account the direction of approach. |
81 */ |
208 */ |
82 static int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) |
209 static int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, OpenListNode* parent) |
83 { |
210 { |
96 dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
223 dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; |
97 else |
224 else |
98 /* Ships and trains can also go diagonal, so the minimum distance is shorter */ |
225 /* Ships and trains can also go diagonal, so the minimum distance is shorter */ |
99 dist = DistanceTrack(from, to) * NPF_TILE_LENGTH; |
226 dist = DistanceTrack(from, to) * NPF_TILE_LENGTH; |
100 |
227 |
101 if (dist < ftd->best_bird_dist) { |
228 DEBUG(npf, 4)("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
|
229 |
|
230 /* for pbs runs, we ignore tiles inside the pbs block for the tracking |
|
231 of the 'closest' tile */ |
|
232 if ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) |
|
233 && (!NPFGetFlag(current , NPF_FLAG_SEEN_SIGNAL)) |
|
234 && (!IsEndOfLine(current->tile, current->direction))) |
|
235 return dist; |
|
236 |
|
237 if ((dist < ftd->best_bird_dist) || |
|
238 /* for pbs runs, prefer tiles that pass a green exit signal to the pbs blocks */ |
|
239 ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) && !NPFGetFlag(current, NPF_FLAG_PBS_RED) && NPFGetFlag(&ftd->node, NPF_FLAG_PBS_RED)) |
|
240 ) { |
102 ftd->best_bird_dist = dist; |
241 ftd->best_bird_dist = dist; |
103 ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; |
242 ftd->best_trackdir = current->user_data[NPF_TRACKDIR_CHOICE]; |
104 } |
243 ftd->path = parent->path; |
105 DEBUG(npf, 4)("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); |
244 ftd->node = *current; |
|
245 } |
106 return dist; |
246 return dist; |
107 } |
247 } |
108 |
|
109 |
248 |
110 /* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to |
249 /* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to |
111 * get here, either getting it from the current choice or from the parent's |
250 * get here, either getting it from the current choice or from the parent's |
112 * choice */ |
251 * choice */ |
113 static void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) |
252 static void NPFFillTrackdirChoice(AyStarNode* current, OpenListNode* parent) |
299 break; |
438 break; |
300 } |
439 } |
301 |
440 |
302 /* Determine extra costs */ |
441 /* Determine extra costs */ |
303 |
442 |
|
443 /* Check for reserved tracks (PBS) */ |
|
444 if ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) && !(NPFGetFlag(current, NPF_FLAG_PBS_EXIT)) && !(NPFGetFlag(current, NPF_FLAG_PBS_BLOCKED)) && (PBSTileUnavail(tile) & (1<<trackdir))) { |
|
445 NPFSetFlag(current, NPF_FLAG_PBS_BLOCKED, true); |
|
446 }; |
|
447 |
304 /* Check for signals */ |
448 /* Check for signals */ |
305 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir)) { |
449 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir)) { |
306 /* Ordinary track with signals */ |
450 /* Ordinary track with signals */ |
307 if (GetSignalState(tile, trackdir) == SIGNAL_STATE_RED) { |
451 if (GetSignalState(tile, trackdir) == SIGNAL_STATE_RED) { |
308 /* Signal facing us is red */ |
452 /* Signal facing us is red */ |
315 if (sigtype == SIGTYPE_EXIT || sigtype == SIGTYPE_COMBO) |
459 if (sigtype == SIGTYPE_EXIT || sigtype == SIGTYPE_COMBO) |
316 /* Penalise exit and combo signals differently (heavier) */ |
460 /* Penalise exit and combo signals differently (heavier) */ |
317 cost += _patches.npf_rail_firstred_exit_penalty; |
461 cost += _patches.npf_rail_firstred_exit_penalty; |
318 else |
462 else |
319 cost += _patches.npf_rail_firstred_penalty; |
463 cost += _patches.npf_rail_firstred_penalty; |
|
464 |
|
465 /* for pbs runs, store the fact that the exit signal to the pbs block was red */ |
|
466 if (!(NPFGetFlag(current, NPF_FLAG_PBS_EXIT)) && !(NPFGetFlag(current, NPF_FLAG_PBS_RED)) && NPFGetFlag(current, NPF_FLAG_PBS_CHOICE)) |
|
467 NPFSetFlag(current, NPF_FLAG_PBS_RED, true); |
320 } |
468 } |
321 /* Record the state of this signal */ |
469 /* Record the state of this signal */ |
322 NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true); |
470 NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, true); |
323 } else { |
471 } else { |
324 /* Record the state of this signal */ |
472 /* Record the state of this signal */ |
325 NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false); |
473 NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false); |
|
474 } |
|
475 |
|
476 if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL) && NPFGetFlag(current, NPF_FLAG_PBS_BLOCKED)) { |
|
477 /* penalise a path through the pbs block if it crosses reserved tracks */ |
|
478 cost += 1000; |
|
479 } |
|
480 if ((PBSIsPbsSignal(tile, trackdir)) && !NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
|
481 /* we've encountered an exit signal to the pbs block */ |
|
482 NPFSetFlag(current, NPF_FLAG_PBS_EXIT, true); |
326 } |
483 } |
327 NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true); |
484 NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true); |
328 } |
485 } |
329 |
486 |
330 /* Penalise the tile if it is a target tile and the last signal was |
487 /* Penalise the tile if it is a target tile and the last signal was |
342 if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction)) |
499 if (current->direction != NextTrackdir((Trackdir)parent->path.node.direction)) |
343 cost += _patches.npf_rail_curve_penalty; |
500 cost += _patches.npf_rail_curve_penalty; |
344 //TODO, with realistic acceleration, also the amount of straight track between |
501 //TODO, with realistic acceleration, also the amount of straight track between |
345 // curves should be taken into account, as this affects the speed limit. |
502 // curves should be taken into account, as this affects the speed limit. |
346 |
503 |
347 /* Check for reverse in depot */ |
504 |
348 if (IsTileDepotType(tile, TRANSPORT_RAIL) && !as->EndNodeCheck(as, &new_node)==AYSTAR_FOUND_END_NODE) |
505 /* Check for depots */ |
|
506 if (IsTileDepotType(tile, TRANSPORT_RAIL)) { |
349 /* Penalise any depot tile that is not the last tile in the path. This |
507 /* Penalise any depot tile that is not the last tile in the path. This |
350 * _should_ penalise every occurence of reversing in a depot (and only |
508 * _should_ penalise every occurence of reversing in a depot (and only |
351 * that) */ |
509 * that) */ |
352 cost += _patches.npf_rail_depot_reverse_penalty; |
510 if (as->EndNodeCheck(as, &new_node) != AYSTAR_FOUND_END_NODE) |
|
511 cost += _patches.npf_rail_depot_reverse_penalty; |
|
512 |
|
513 /* Do we treat this depot as a pbs signal? */ |
|
514 if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
|
515 if (NPFGetFlag(current, NPF_FLAG_PBS_BLOCKED)) { |
|
516 cost += 1000; |
|
517 } |
|
518 if (PBSIsPbsDepot(tile)) { |
|
519 NPFSetFlag(current, NPF_FLAG_PBS_EXIT, true); |
|
520 NPFSetFlag(current, NPF_FLAG_SEEN_SIGNAL, true); |
|
521 } |
|
522 } |
|
523 NPFSetFlag(current, NPF_FLAG_LAST_SIGNAL_RED, false); |
|
524 } |
353 |
525 |
354 /* Check for occupied track */ |
526 /* Check for occupied track */ |
355 //TODO |
527 //TODO |
356 |
528 |
357 NPFMarkTile(tile); |
529 NPFMarkTile(tile); |
377 { |
549 { |
378 NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
550 NPFFindStationOrTileData* fstd = (NPFFindStationOrTileData*)as->user_target; |
379 AyStarNode *node = ¤t->path.node; |
551 AyStarNode *node = ¤t->path.node; |
380 TileIndex tile = node->tile; |
552 TileIndex tile = node->tile; |
381 |
553 |
|
554 if (tile == 0x4611c) { |
|
555 tile++; |
|
556 tile--; |
|
557 } |
|
558 |
382 /* If GetNeighbours said we could get here, we assume the station type |
559 /* If GetNeighbours said we could get here, we assume the station type |
383 * is correct */ |
560 * is correct */ |
384 if ( |
561 if ( |
385 (fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */ |
562 (fstd->station_index == -1 && tile == fstd->dest_coords) || /* We've found the tile, or */ |
386 (IsTileType(tile, MP_STATION) && _map2[tile] == fstd->station_index) /* the station */ |
563 (IsTileType(tile, MP_STATION) && _map2[tile] == fstd->station_index) || /* the station */ |
|
564 (NPFGetFlag(node, NPF_FLAG_PBS_TARGET_SEEN)) /* or, we've passed it already (for pbs) */ |
387 ) { |
565 ) { |
|
566 NPFSetFlag(¤t->path.node, NPF_FLAG_PBS_TARGET_SEEN, true); |
|
567 /* for pbs runs, only accept we've found the target if we've also found a way out of the block */ |
|
568 if ((as->user_data[NPF_PBS_MODE] != PBS_MODE_NONE) && !NPFGetFlag(node, NPF_FLAG_SEEN_SIGNAL) && !IsEndOfLine(node->tile, node->direction)) |
|
569 return AYSTAR_DONE; |
388 return AYSTAR_FOUND_END_NODE; |
570 return AYSTAR_FOUND_END_NODE; |
389 } else { |
571 } else { |
390 return AYSTAR_DONE; |
572 return AYSTAR_DONE; |
391 } |
573 } |
392 } |
574 } |
400 NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
582 NPFFoundTargetData* ftd = (NPFFoundTargetData*)as->user_path; |
401 ftd->best_trackdir = (Trackdir)current->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
583 ftd->best_trackdir = (Trackdir)current->path.node.user_data[NPF_TRACKDIR_CHOICE]; |
402 ftd->best_path_dist = current->g; |
584 ftd->best_path_dist = current->g; |
403 ftd->best_bird_dist = 0; |
585 ftd->best_bird_dist = 0; |
404 ftd->node = current->path.node; |
586 ftd->node = current->path.node; |
|
587 ftd->path = current->path; |
405 } |
588 } |
406 |
589 |
407 /** |
590 /** |
408 * Finds out if a given player's vehicles are allowed to enter a given tile. |
591 * Finds out if a given player's vehicles are allowed to enter a given tile. |
409 * @param owner The owner of the vehicle. |
592 * @param owner The owner of the vehicle. |
476 TransportType type = aystar->user_data[NPF_TYPE]; |
659 TransportType type = aystar->user_data[NPF_TYPE]; |
477 /* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
660 /* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
478 aystar->num_neighbours = 0; |
661 aystar->num_neighbours = 0; |
479 DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
662 DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
480 |
663 |
|
664 aystar->EndNodeCheck(aystar, current); |
|
665 |
481 /* Find dest tile */ |
666 /* Find dest tile */ |
482 if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (DiagDirection)(_map5[src_tile] & 3) == src_exitdir) { |
667 if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (DiagDirection)(_map5[src_tile] & 3) == src_exitdir) { |
483 /* This is a tunnel. We know this tunnel is our type, |
668 /* This is a tunnel. We know this tunnel is our type, |
484 * otherwise we wouldn't have got here. It is also facing us, |
669 * otherwise we wouldn't have got here. It is also facing us, |
485 * so we should skip it's body */ |
670 * so we should skip it's body */ |
553 * the back */ |
738 * the back */ |
554 ts = TrackdirToTrackdirBits(DiagdirToDiagTrackdir(ReverseDiagdir(exitdir))); |
739 ts = TrackdirToTrackdirBits(DiagdirToDiagTrackdir(ReverseDiagdir(exitdir))); |
555 } else { |
740 } else { |
556 ts = GetTileTrackStatus(dst_tile, type); |
741 ts = GetTileTrackStatus(dst_tile, type); |
557 } |
742 } |
558 trackdirbits = ts & 0x3F3F; /* Filter out signal status and the unused bits */ |
743 trackdirbits = ts & TRACKDIR_BIT_MASK; /* Filter out signal status and the unused bits */ |
559 |
744 |
560 DEBUG(npf, 4)("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirbits); |
745 DEBUG(npf, 4)("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirbits); |
561 /* Select only trackdirs we can reach from our current trackdir */ |
746 /* Select only trackdirs we can reach from our current trackdir */ |
562 trackdirbits &= TrackdirReachesTrackdirs(src_trackdir); |
747 trackdirbits &= TrackdirReachesTrackdirs(src_trackdir); |
563 if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
748 if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
564 trackdirbits &= ~TrackdirCrossesTrackdirs(src_trackdir); |
749 |
|
750 trackdirbits &= ~TrackdirCrossesTrackdirs(src_trackdir); |
|
751 |
|
752 if (KillFirstBit2x64(trackdirbits) != 0) |
|
753 NPFSetFlag(¤t->path.node, NPF_FLAG_PBS_CHOICE, true); |
|
754 |
|
755 /* When looking for 'any' route, ie when already inside a pbs block, discard all tracks that would cross |
|
756 other reserved tracks, so we *always* will find a valid route if there is one */ |
|
757 if (!(NPFGetFlag(¤t->path.node, NPF_FLAG_PBS_EXIT)) && (aystar->user_data[NPF_PBS_MODE] == PBS_MODE_ANY)) |
|
758 trackdirbits &= ~PBSTileUnavail(dst_tile); |
|
759 |
565 DEBUG(npf,6)("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirbits); |
760 DEBUG(npf,6)("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirbits); |
566 |
761 |
567 i = 0; |
762 i = 0; |
568 /* Enumerate possible track */ |
763 /* Enumerate possible track */ |
569 while (trackdirbits != 0) { |
764 while (trackdirbits != 0) { |
600 * When we are looking for one specific target (optionally multiple tiles), we |
795 * When we are looking for one specific target (optionally multiple tiles), we |
601 * should use a good heuristic to perform aystar search. When we search for |
796 * should use a good heuristic to perform aystar search. When we search for |
602 * multiple targets that are spread around, we should perform a breadth first |
797 * multiple targets that are spread around, we should perform a breadth first |
603 * search by specifiying CalcZero as our heuristic. |
798 * search by specifiying CalcZero as our heuristic. |
604 */ |
799 */ |
605 static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner, RailType railtype, uint reverse_penalty) |
800 static NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner, RailType railtype, uint reverse_penalty, byte pbs_mode) |
606 { |
801 { |
607 int r; |
802 int r; |
608 NPFFoundTargetData result; |
803 NPFFoundTargetData result; |
609 |
804 |
610 /* Initialize procs */ |
805 /* Initialize procs */ |
619 else if (type == TRANSPORT_WATER) |
814 else if (type == TRANSPORT_WATER) |
620 _npf_aystar.CalculateG = NPFWaterPathCost; |
815 _npf_aystar.CalculateG = NPFWaterPathCost; |
621 else |
816 else |
622 assert(0); |
817 assert(0); |
623 |
818 |
|
819 if (pbs_mode != PBS_MODE_NONE) |
|
820 _npf_aystar.BeforeExit = NPFReservePBSPath; |
|
821 else |
|
822 _npf_aystar.BeforeExit = NULL; |
|
823 |
624 /* Initialize Start Node(s) */ |
824 /* Initialize Start Node(s) */ |
625 start1->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
825 start1->user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
626 start1->user_data[NPF_NODE_FLAGS] = 0; |
826 start1->user_data[NPF_NODE_FLAGS] = 0; |
627 _npf_aystar.addstart(&_npf_aystar, start1, 0); |
827 _npf_aystar.addstart(&_npf_aystar, start1, 0); |
628 if (start2) { |
828 if (start2) { |
674 start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
875 start1.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
675 start1.direction = trackdir1; |
876 start1.direction = trackdir1; |
676 start2.direction = trackdir2; |
877 start2.direction = trackdir2; |
677 start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
878 start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
678 |
879 |
679 return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner, railtype, 0); |
880 return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner, railtype, 0, pbs_mode); |
680 } |
881 } |
681 |
882 |
682 NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailType railtype) |
883 NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner, RailType railtype, byte pbs_mode) |
683 { |
884 { |
684 return NPFRouteToStationOrTileTwoWay(tile, trackdir, INVALID_TILE, 0, target, type, owner, railtype); |
885 return NPFRouteToStationOrTileTwoWay(tile, trackdir, INVALID_TILE, 0, target, type, owner, railtype, pbs_mode); |
685 } |
886 } |
686 |
887 |
687 NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, Owner owner, RailType railtype, uint reverse_penalty) |
888 NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, Trackdir trackdir1, TileIndex tile2, Trackdir trackdir2, TransportType type, Owner owner, RailType railtype, uint reverse_penalty) |
688 { |
889 { |
689 AyStarNode start1; |
890 AyStarNode start1; |
698 start2.direction = trackdir2; |
899 start2.direction = trackdir2; |
699 start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
900 start2.user_data[NPF_TRACKDIR_CHOICE] = INVALID_TRACKDIR; |
700 |
901 |
701 /* perform a breadth first search. Target is NULL, |
902 /* perform a breadth first search. Target is NULL, |
702 * since we are just looking for any depot...*/ |
903 * since we are just looking for any depot...*/ |
703 return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), NULL, NPFFindDepot, NPFCalcZero, type, owner, railtype, reverse_penalty); |
904 return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), NULL, NPFFindDepot, NPFCalcZero, type, owner, railtype, reverse_penalty, PBS_MODE_NONE); |
704 } |
905 } |
705 |
906 |
706 NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailType railtype) |
907 NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, Trackdir trackdir, TransportType type, Owner owner, RailType railtype) |
707 { |
908 { |
708 return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, INVALID_TILE, 0, type, owner, railtype, 0); |
909 return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, INVALID_TILE, 0, type, owner, railtype, 0); |
751 else if (type == TRANSPORT_WATER) |
952 else if (type == TRANSPORT_WATER) |
752 _npf_aystar.CalculateG = NPFWaterPathCost; |
953 _npf_aystar.CalculateG = NPFWaterPathCost; |
753 else |
954 else |
754 assert(0); |
955 assert(0); |
755 |
956 |
|
957 _npf_aystar.BeforeExit = NULL; |
|
958 |
756 /* Initialize target */ |
959 /* Initialize target */ |
757 target.station_index = -1; /* We will initialize dest_coords inside the loop below */ |
960 target.station_index = -1; /* We will initialize dest_coords inside the loop below */ |
758 _npf_aystar.user_target = ⌖ |
961 _npf_aystar.user_target = ⌖ |
759 |
962 |
760 /* Initialize user_data */ |
963 /* Initialize user_data */ |
761 _npf_aystar.user_data[NPF_TYPE] = type; |
964 _npf_aystar.user_data[NPF_TYPE] = type; |
762 _npf_aystar.user_data[NPF_OWNER] = owner; |
965 _npf_aystar.user_data[NPF_OWNER] = owner; |
|
966 _npf_aystar.user_data[NPF_PBS_MODE] = PBS_MODE_NONE; |
763 |
967 |
764 /* Initialize Start Node */ |
968 /* Initialize Start Node */ |
765 start.tile = tile; |
969 start.tile = tile; |
766 start.direction = trackdir; /* We will initialize user_data inside the loop below */ |
970 start.direction = trackdir; /* We will initialize user_data inside the loop below */ |
767 |
971 |