126 |
126 |
127 /* Will return the cost of the tunnel. If it is an entry, it will return the |
127 /* Will return the cost of the tunnel. If it is an entry, it will return the |
128 * cost of that tile. If the tile is an exit, it will return the tunnel length |
128 * cost of that tile. If the tile is an exit, it will return the tunnel length |
129 * including the exit tile. Requires that this is a Tunnel tile */ |
129 * including the exit tile. Requires that this is a Tunnel tile */ |
130 uint NPFTunnelCost(AyStarNode* current) { |
130 uint NPFTunnelCost(AyStarNode* current) { |
131 byte exitdir = _trackdir_to_exitdir[current->direction]; |
131 byte exitdir = TrackdirToExitdir(current->direction); |
132 TileIndex tile = current->tile; |
132 TileIndex tile = current->tile; |
133 if ( (uint)(_map5[tile] & 3) == ReverseDiagdir(exitdir)) { |
133 if ( (uint)(_map5[tile] & 3) == ReverseDiagdir(exitdir)) { |
134 /* We just popped out if this tunnel, since were |
134 /* We just popped out if this tunnel, since were |
135 * facing the tunnel exit */ |
135 * facing the tunnel exit */ |
136 FindLengthOfTunnelResult flotr; |
136 FindLengthOfTunnelResult flotr; |
289 } |
289 } |
290 |
290 |
291 /* Determine extra costs */ |
291 /* Determine extra costs */ |
292 |
292 |
293 /* Check for signals */ |
293 /* Check for signals */ |
294 if (IsTileType(tile, MP_RAILWAY) && (_map5[tile] & 0xC0) == 0x40 && (_map3_lo[tile] & _signal_along_trackdir[trackdir]) != 0) { |
294 if (IsTileType(tile, MP_RAILWAY) && HasSignalOnTrackdir(tile, trackdir)) { |
295 /* Ordinary track with signals */ |
295 /* Ordinary track with signals */ |
296 if ((_map2[tile] & _signal_along_trackdir[trackdir]) == 0) { |
296 if (GetSignalState(tile, trackdir) == SIGNAL_STATE_RED) { |
297 /* Signal facing us is red */ |
297 /* Signal facing us is red */ |
298 if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
298 if (!NPFGetFlag(current, NPF_FLAG_SEEN_SIGNAL)) { |
299 /* Penalize the first signal we |
299 /* Penalize the first signal we |
300 * encounter, if it is red */ |
300 * encounter, if it is red */ |
301 |
301 |
302 /* Is this a presignal exit or combo? */ |
302 /* Is this a presignal exit or combo? */ |
303 if ((_map3_hi[tile] & 0x3) == 0x2 || (_map3_hi[tile] & 0x3) == 0x3) |
303 SignalType sigtype = GetSignalType(tile, trackdir); |
|
304 if (sigtype == SIGTYPE_EXIT || sigtype == SIGTYPE_COMBO) |
304 /* Penalise exit and combo signals differently (heavier) */ |
305 /* Penalise exit and combo signals differently (heavier) */ |
305 cost += _patches.npf_rail_firstred_exit_penalty; |
306 cost += _patches.npf_rail_firstred_exit_penalty; |
306 else |
307 else |
307 cost += _patches.npf_rail_firstred_penalty; |
308 cost += _patches.npf_rail_firstred_penalty; |
308 } |
309 } |
323 |
324 |
324 /* Check for slope */ |
325 /* Check for slope */ |
325 cost += NPFSlopeCost(current); |
326 cost += NPFSlopeCost(current); |
326 |
327 |
327 /* Check for turns */ |
328 /* Check for turns */ |
328 if (current->direction != _next_trackdir[parent->path.node.direction]) |
329 if (current->direction != NextTrackdir(parent->path.node.direction)) |
329 cost += _patches.npf_rail_curve_penalty; |
330 cost += _patches.npf_rail_curve_penalty; |
330 //TODO, with realistic acceleration, also the amount of straight track between |
331 //TODO, with realistic acceleration, also the amount of straight track between |
331 // curves should be taken into account, as this affects the speed limit. |
332 // curves should be taken into account, as this affects the speed limit. |
332 |
333 |
333 /* Check for reverse in depot */ |
334 /* Check for reverse in depot */ |
434 * an argument to GetTileTrackStatus. Will skip tunnels, meaning that the |
435 * an argument to GetTileTrackStatus. Will skip tunnels, meaning that the |
435 * entry and exit are neighbours. Will fill |
436 * entry and exit are neighbours. Will fill |
436 * AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and |
437 * AyStarNode.user_data[NPF_TRACKDIR_CHOICE] with an appropriate value, and |
437 * copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */ |
438 * copy AyStarNode.user_data[NPF_NODE_FLAGS] from the parent */ |
438 void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { |
439 void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { |
439 byte src_trackdir = current->path.node.direction; |
440 Trackdir src_trackdir = current->path.node.direction; |
440 TileIndex src_tile = current->path.node.tile; |
441 TileIndex src_tile = current->path.node.tile; |
441 byte src_exitdir = _trackdir_to_exitdir[src_trackdir]; |
442 DiagDirection src_exitdir = TrackdirToExitdir(src_trackdir); |
442 FindLengthOfTunnelResult flotr; |
443 FindLengthOfTunnelResult flotr; |
443 TileIndex dst_tile; |
444 TileIndex dst_tile; |
444 int i = 0; |
445 int i = 0; |
445 uint trackdirs, ts; |
446 TrackdirBits trackdirbits, ts; |
446 TransportType type = aystar->user_data[NPF_TYPE]; |
447 TransportType type = aystar->user_data[NPF_TYPE]; |
447 /* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
448 /* Initialize to 0, so we can jump out (return) somewhere an have no neighbours */ |
448 aystar->num_neighbours = 0; |
449 aystar->num_neighbours = 0; |
449 DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
450 DEBUG(npf, 4)("Expanding: (%d, %d, %d) [%d]", TileX(src_tile), TileY(src_tile), src_trackdir, src_tile); |
450 |
451 |
451 /* Find dest tile */ |
452 /* Find dest tile */ |
452 if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (_map5[src_tile] & 3) == src_exitdir) { |
453 if (IsTileType(src_tile, MP_TUNNELBRIDGE) && (_map5[src_tile] & 0xF0)==0 && (DiagDirection)(_map5[src_tile] & 3) == src_exitdir) { |
453 /* This is a tunnel. We know this tunnel is our type, |
454 /* This is a tunnel. We know this tunnel is our type, |
454 * otherwise we wouldn't have got here. It is also facing us, |
455 * otherwise we wouldn't have got here. It is also facing us, |
455 * so we should skip it's body */ |
456 * so we should skip it's body */ |
456 flotr = FindLengthOfTunnel(src_tile, src_exitdir); |
457 flotr = FindLengthOfTunnel(src_tile, src_exitdir); |
457 dst_tile = flotr.tile; |
458 dst_tile = flotr.tile; |
470 |
471 |
471 /* Let's see if were headed the right way into the depot, and reverse |
472 /* Let's see if were headed the right way into the depot, and reverse |
472 * otherwise (only for trains, since only with trains you can |
473 * otherwise (only for trains, since only with trains you can |
473 * (sometimes) reach tiles after reversing that you couldn't reach |
474 * (sometimes) reach tiles after reversing that you couldn't reach |
474 * without reversing. */ |
475 * without reversing. */ |
475 if (src_trackdir == _dir_to_diag_trackdir[ReverseDiagdir(exitdir)] && type == TRANSPORT_RAIL) |
476 if (src_trackdir == DiagdirToDiagTrackdir(ReverseDiagdir(exitdir)) && type == TRANSPORT_RAIL) |
476 /* We are headed inwards. We can only reverse here, so we'll not |
477 /* We are headed inwards. We can only reverse here, so we'll not |
477 * consider this direction, but jump ahead to the reverse direction. |
478 * consider this direction, but jump ahead to the reverse direction. |
478 * It would be nicer to return one neighbour here (the reverse |
479 * It would be nicer to return one neighbour here (the reverse |
479 * trackdir of the one we are considering now) and then considering |
480 * trackdir of the one we are considering now) and then considering |
480 * that one to return the tracks outside of the depot. But, because |
481 * that one to return the tracks outside of the depot. But, because |
481 * the code layout is cleaner this way, we will just pretend we are |
482 * the code layout is cleaner this way, we will just pretend we are |
482 * reversed already */ |
483 * reversed already */ |
483 src_trackdir = _reverse_trackdir[src_trackdir]; |
484 src_trackdir = ReverseTrackdir(src_trackdir); |
484 } |
485 } |
485 /* This a normal tile, a bridge, a tunnel exit, etc. */ |
486 /* This a normal tile, a bridge, a tunnel exit, etc. */ |
486 dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(_trackdir_to_exitdir[src_trackdir])); |
487 dst_tile = AddTileIndexDiffCWrap(src_tile, TileIndexDiffCByDir(TrackdirToExitdir(src_trackdir))); |
487 if (dst_tile == INVALID_TILE) { |
488 if (dst_tile == INVALID_TILE) { |
488 /* We reached the border of the map */ |
489 /* We reached the border of the map */ |
489 /* TODO Nicer control flow for this */ |
490 /* TODO Nicer control flow for this */ |
490 return; |
491 return; |
491 } |
492 } |
495 * XXX: This now compares with the previous tile, which should not pose a |
496 * XXX: This now compares with the previous tile, which should not pose a |
496 * problem, but it might be nicer to compare with the first tile, or even |
497 * problem, but it might be nicer to compare with the first tile, or even |
497 * the type of the vehicle... Maybe an NPF_RAILTYPE userdata sometime? */ |
498 * the type of the vehicle... Maybe an NPF_RAILTYPE userdata sometime? */ |
498 if (type == TRANSPORT_RAIL) { |
499 if (type == TRANSPORT_RAIL) { |
499 byte src_type = GetTileRailType(src_tile, src_trackdir); |
500 byte src_type = GetTileRailType(src_tile, src_trackdir); |
500 byte dst_type = GetTileRailType(dst_tile, _trackdir_to_exitdir[src_trackdir]); |
501 byte dst_type = GetTileRailType(dst_tile, TrackdirToExitdir(src_trackdir)); |
501 if (src_type != dst_type) { |
502 if (src_type != dst_type) { |
502 return; |
503 return; |
503 } |
504 } |
504 } |
505 } |
505 |
506 |
529 * the back */ |
530 * the back */ |
530 ts = TrackdirToTrackdirBits(DiagdirToDiagTrackdir(ReverseDiagdir(exitdir))); |
531 ts = TrackdirToTrackdirBits(DiagdirToDiagTrackdir(ReverseDiagdir(exitdir))); |
531 } else { |
532 } else { |
532 ts = GetTileTrackStatus(dst_tile, type); |
533 ts = GetTileTrackStatus(dst_tile, type); |
533 } |
534 } |
534 trackdirs = ts & 0x3F3F; /* Filter out signal status and the unused bits */ |
535 trackdirbits = ts & 0x3F3F; /* Filter out signal status and the unused bits */ |
535 |
536 |
536 DEBUG(npf, 4)("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirs); |
537 DEBUG(npf, 4)("Next node: (%d, %d) [%d], possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), dst_tile, trackdirbits); |
537 /* Select only trackdirs we can reach from our current trackdir */ |
538 /* Select only trackdirs we can reach from our current trackdir */ |
538 trackdirs &= TrackdirReachesTrackdirs(src_trackdir); |
539 trackdirbits &= TrackdirReachesTrackdirs(src_trackdir); |
539 if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
540 if (_patches.forbid_90_deg && (type == TRANSPORT_RAIL || type == TRANSPORT_WATER)) /* Filter out trackdirs that would make 90 deg turns for trains */ |
540 trackdirs &= ~_trackdir_crosses_trackdirs[src_trackdir]; |
541 trackdirbits &= ~TrackdirCrossesTrackdirs(src_trackdir); |
541 DEBUG(npf,6)("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirs); |
542 DEBUG(npf,6)("After filtering: (%d, %d), possible trackdirs: %#x", TileX(dst_tile), TileY(dst_tile), trackdirbits); |
542 |
543 |
543 /* Enumerate possible track */ |
544 /* Enumerate possible track */ |
544 while (trackdirs != 0) { |
545 while (trackdirbits != 0) { |
545 byte dst_trackdir; |
546 byte dst_trackdir; |
546 dst_trackdir = FindFirstBit2x64(trackdirs); |
547 dst_trackdir = FindFirstBit2x64(trackdirbits); |
547 trackdirs = KillFirstBit2x64(trackdirs); |
548 trackdirbits = KillFirstBit2x64(trackdirbits); |
548 DEBUG(npf, 5)("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirs); |
549 DEBUG(npf, 5)("Expanded into trackdir: %d, remaining trackdirs: %#x", dst_trackdir, trackdirbits); |
549 |
550 |
550 /* Check for oneway signal against us */ |
551 /* Check for oneway signal against us */ |
551 if (IsTileType(dst_tile, MP_RAILWAY) && (_map5[dst_tile]&0xC0) == 0x40) { |
552 if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TYPE_SIGNALS) { |
552 // the tile has a signal |
553 if (HasSignalOnTrackdir(dst_tile, ReverseTrackdir(dst_trackdir)) && !HasSignalOnTrackdir(dst_tile, dst_trackdir)) |
553 byte signal_present = _map3_lo[dst_tile]; |
|
554 if (!(signal_present & _signal_along_trackdir[dst_trackdir])) { |
|
555 // if one way signal not pointing towards us, stop going in this direction. |
554 // if one way signal not pointing towards us, stop going in this direction. |
556 if (signal_present & _signal_against_trackdir[dst_trackdir]) |
555 break; |
557 break; |
|
558 } |
|
559 } |
556 } |
560 { |
557 { |
561 /* We've found ourselves a neighbour :-) */ |
558 /* We've found ourselves a neighbour :-) */ |
562 AyStarNode* neighbour = &aystar->neighbours[i]; |
559 AyStarNode* neighbour = &aystar->neighbours[i]; |
563 neighbour->tile = dst_tile; |
560 neighbour->tile = dst_tile; |