583 |
583 |
584 link->next = NTP_GET_LINK_OFFS(tpf, new_link); |
584 link->next = NTP_GET_LINK_OFFS(tpf, new_link); |
585 return true; |
585 return true; |
586 } |
586 } |
587 |
587 |
|
588 /** |
|
589 * Checks if the shortest path to the given tile/dir so far is still the given |
|
590 * length. |
|
591 * @return true if the length is still the same |
|
592 * @pre The given tile/dir combination should be present in the hash, by a |
|
593 * previous call to NtpVisit(). |
|
594 */ |
588 static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length) |
595 static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length) |
589 { |
596 { |
590 uint hash,head,offs; |
597 uint hash,head,offs; |
591 HashLink *link; |
598 HashLink *link; |
592 |
599 |
664 // Tile is the tile the train is at. |
671 // Tile is the tile the train is at. |
665 // direction is the tile the train is moving towards. |
672 // direction is the tile the train is moving towards. |
666 |
673 |
667 static void NTPEnum(NewTrackPathFinder *tpf, TileIndex tile, uint direction) |
674 static void NTPEnum(NewTrackPathFinder *tpf, TileIndex tile, uint direction) |
668 { |
675 { |
669 uint bits, tile_org, track; |
676 TrackBits bits, allbits; |
|
677 uint track; |
|
678 TileIndex tile_org; |
670 StackedItem si; |
679 StackedItem si; |
671 FindLengthOfTunnelResult flotr; |
680 FindLengthOfTunnelResult flotr; |
672 int estimation; |
681 int estimation; |
673 |
682 |
674 |
683 |
743 // Determine which tracks that exist on this tile. |
752 // Determine which tracks that exist on this tile. |
744 bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction]; |
753 bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction]; |
745 bits = (bits | (bits >> 8)) & 0x3F; |
754 bits = (bits | (bits >> 8)) & 0x3F; |
746 |
755 |
747 // Check that the tile contains exactly one track |
756 // Check that the tile contains exactly one track |
748 if (bits == 0 || KILL_FIRST_BIT(bits) != 0) |
757 if (bits == 0 || KILL_FIRST_BIT(bits) != 0) break; |
749 break; |
|
750 |
758 |
751 /////////////////// |
759 /////////////////// |
752 // If we reach here, the tile has exactly one track. |
760 // If we reach here, the tile has exactly one track. |
753 // tile - index to a tile that is not rail tile, but still straight (with optional signals) |
761 // tile - index to a tile that is not rail tile, but still straight (with optional signals) |
754 // bits - bitmask of which track that exist on the tile (exactly one bit is set) |
762 // bits - bitmask of which track that exist on the tile (exactly one bit is set) |
757 si.track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
765 si.track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
758 si.cur_length += _length_of_track[si.track]; |
766 si.cur_length += _length_of_track[si.track]; |
759 goto callback_and_continue; |
767 goto callback_and_continue; |
760 } |
768 } |
761 |
769 |
762 // Regular rail tile, determine which tracks exist. |
770 /* Regular rail tile, determine which tracks exist. */ |
763 bits = _m[tile].m5 & _bits_mask[direction]; |
771 allbits = _m[tile].m5 & TRACK_BIT_MASK; |
764 |
772 /* Which tracks are reachable? */ |
765 // The tile has no reachable tracks, or |
773 bits = allbits & DiagdirReachesTracks(direction); |
766 // does the tile contain more than one track? |
774 |
767 if (bits == 0 || KILL_FIRST_BIT(bits) != 0) |
775 /* The tile has no reachable tracks => End of rail segment |
768 break; |
776 * or Intersection => End of rail segment. We check this agains all the |
769 |
777 * bits, not just reachable ones, to prevent infinite loops. */ |
770 // If we reach here, the tile has exactly one track, and this |
778 if (bits == 0 || TracksOverlap(allbits)) break; |
771 // track is reachable. |
779 |
|
780 /* If we reach here, the tile has exactly one track, and this |
|
781 track is reachable => Rail segment continues */ |
772 |
782 |
773 track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
783 track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
774 assert(track != 0xff); |
784 assert(track != 0xff); |
775 |
785 |
776 si.cur_length += _length_of_track[track]; |
786 si.cur_length += _length_of_track[track]; |
786 if (HasSignals(tile)) { |
796 if (HasSignals(tile)) { |
787 byte m3; |
797 byte m3; |
788 |
798 |
789 m3 = _m[tile].m3; |
799 m3 = _m[tile].m3; |
790 if (!(m3 & SignalAlongTrackdir(track))) { |
800 if (!(m3 & SignalAlongTrackdir(track))) { |
791 // if one way signal not pointing towards us, stop going in this direction. |
801 // if one way signal not pointing towards us, stop going in this direction => End of rail segment. |
792 if (m3 & SignalAgainstTrackdir(track)) { |
802 if (m3 & SignalAgainstTrackdir(track)) { |
793 bits = 0; |
803 bits = 0; |
794 break; |
804 break; |
795 } |
805 } |
796 } else if (_m[tile].m2 & SignalAlongTrackdir(track)) { |
806 } else if (_m[tile].m2 & SignalAlongTrackdir(track)) { |
798 si.state |= 3; |
808 si.state |= 3; |
799 } else { |
809 } else { |
800 // reached a red signal. |
810 // reached a red signal. |
801 if (m3 & SignalAgainstTrackdir(track)) { |
811 if (m3 & SignalAgainstTrackdir(track)) { |
802 // two way red signal. unless we passed another green signal on the way, |
812 // two way red signal. unless we passed another green signal on the way, |
803 // stop going in this direction. |
813 // stop going in this direction => End of rail segment. |
804 // this is to prevent us from going into a full platform. |
814 // this is to prevent us from going into a full platform. |
805 if (!(si.state&1)) { |
815 if (!(si.state&1)) { |
806 bits = 0; |
816 bits = 0; |
807 break; |
817 break; |
808 } |
818 } |
817 break; |
827 break; |
818 } |
828 } |
819 } |
829 } |
820 |
830 |
821 if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length)) |
831 if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length)) |
822 return; |
832 return; /* Don't process this tile any further */ |
823 } |
833 } |
824 |
834 |
825 // continue with the next track |
835 // continue with the next track |
826 direction = _tpf_new_direction[track]; |
836 direction = _tpf_new_direction[track]; |
827 |
837 |
862 if (si.depth == 0) |
872 if (si.depth == 0) |
863 continue; /* We overflowed our depth. No more searching in this direction. */ |
873 continue; /* We overflowed our depth. No more searching in this direction. */ |
864 si.tile = tile; |
874 si.tile = tile; |
865 do { |
875 do { |
866 si.track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
876 si.track = _new_track[FIND_FIRST_BIT(bits)][direction]; |
|
877 assert(si.track != 0xFF); |
867 si.priority = si.cur_length + estimation; |
878 si.priority = si.cur_length + estimation; |
868 |
879 |
869 // out of stack items, bail out? |
880 // out of stack items, bail out? |
870 if (tpf->nstack >= lengthof(tpf->stack)) { |
881 if (tpf->nstack >= lengthof(tpf->stack)) { |
871 DEBUG(ntp, 1) ("[NTP] out of stack"); |
882 DEBUG(ntp, 1) ("[NTP] out of stack"); |