diff options
| -rw-r--r-- | pathfind.c | 39 | ||||
| -rw-r--r-- | rail.h | 58 |
2 files changed, 76 insertions, 21 deletions
diff --git a/pathfind.c b/pathfind.c index 2895a8026..9552129bc 100644 --- a/pathfind.c +++ b/pathfind.c @@ -585,6 +585,13 @@ static bool NtpVisit(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint len return true; } +/** + * Checks if the shortest path to the given tile/dir so far is still the given + * length. + * @return true if the length is still the same + * @pre The given tile/dir combination should be present in the hash, by a + * previous call to NtpVisit(). + */ static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint length) { uint hash,head,offs; @@ -666,7 +673,9 @@ static const byte _length_of_track[16] = { static void NTPEnum(NewTrackPathFinder *tpf, TileIndex tile, uint direction) { - uint bits, tile_org, track; + TrackBits bits, allbits; + uint track; + TileIndex tile_org; StackedItem si; FindLengthOfTunnelResult flotr; int estimation; @@ -745,8 +754,7 @@ start_at: bits = (bits | (bits >> 8)) & 0x3F; // Check that the tile contains exactly one track - if (bits == 0 || KILL_FIRST_BIT(bits) != 0) - break; + if (bits == 0 || KILL_FIRST_BIT(bits) != 0) break; /////////////////// // If we reach here, the tile has exactly one track. @@ -759,16 +767,18 @@ start_at: goto callback_and_continue; } - // Regular rail tile, determine which tracks exist. - bits = _m[tile].m5 & _bits_mask[direction]; + /* Regular rail tile, determine which tracks exist. */ + allbits = _m[tile].m5 & TRACK_BIT_MASK; + /* Which tracks are reachable? */ + bits = allbits & DiagdirReachesTracks(direction); - // The tile has no reachable tracks, or - // does the tile contain more than one track? - if (bits == 0 || KILL_FIRST_BIT(bits) != 0) - break; + /* The tile has no reachable tracks => End of rail segment + * or Intersection => End of rail segment. We check this agains all the + * bits, not just reachable ones, to prevent infinite loops. */ + if (bits == 0 || TracksOverlap(allbits)) break; - // If we reach here, the tile has exactly one track, and this - // track is reachable. + /* If we reach here, the tile has exactly one track, and this + track is reachable => Rail segment continues */ track = _new_track[FIND_FIRST_BIT(bits)][direction]; assert(track != 0xff); @@ -788,7 +798,7 @@ start_at: m3 = _m[tile].m3; if (!(m3 & SignalAlongTrackdir(track))) { - // if one way signal not pointing towards us, stop going in this direction. + // if one way signal not pointing towards us, stop going in this direction => End of rail segment. if (m3 & SignalAgainstTrackdir(track)) { bits = 0; break; @@ -800,7 +810,7 @@ start_at: // reached a red signal. if (m3 & SignalAgainstTrackdir(track)) { // two way red signal. unless we passed another green signal on the way, - // stop going in this direction. + // stop going in this direction => End of rail segment. // this is to prevent us from going into a full platform. if (!(si.state&1)) { bits = 0; @@ -819,7 +829,7 @@ start_at: } if (tpf->enum_proc(tile, tpf->userdata, si.first_track, si.cur_length)) - return; + return; /* Don't process this tile any further */ } // continue with the next track @@ -864,6 +874,7 @@ start_at: si.tile = tile; do { si.track = _new_track[FIND_FIRST_BIT(bits)][direction]; + assert(si.track != 0xFF); si.priority = si.cur_length + estimation; // out of stack items, bail out? @@ -341,27 +341,37 @@ static inline Trackdir ReverseTrackdir(Trackdir trackdir) { return _reverse_trackdir[trackdir]; } -/* +/** * Maps a Track to the corresponding TrackBits value */ static inline TrackBits TrackToTrackBits(Track track) { return (TrackBits)(1 << track); } -/* Returns the Track that a given Trackdir represents */ +/** + * Returns the Track that a given Trackdir represents + */ static inline Track TrackdirToTrack(Trackdir trackdir) { return (Track)(trackdir & 0x7); } -/* Returns a Trackdir for the given Track. Since every Track corresponds to +/** + * Returns a Trackdir for the given Track. Since every Track corresponds to * two Trackdirs, we choose the one which points between NE and S. * Note that the actual implementation is quite futile, but this might change * in the future. */ static inline Trackdir TrackToTrackdir(Track track) { return (Trackdir)track; } -/* Returns a TrackdirBit mask that contains the two TrackdirBits that +/** + * Returns a TrackdirBit mask that contains the two TrackdirBits that * correspond with the given Track (one for each direction). */ static inline TrackdirBits TrackToTrackdirBits(Track track) { Trackdir td = TrackToTrackdir(track); return TrackdirToTrackdirBits(td) | TrackdirToTrackdirBits(ReverseTrackdir(td));} /** + * Discards all directional information from the given TrackdirBits. Any + * Track which is present in either direction will be present in the result. + */ +static inline TrackBits TrackdirBitsToTrackBits(TrackdirBits bits) { return bits | (bits >> 8); } + +/** * Maps a trackdir to the trackdir that you will end up on if you go straight * ahead. This will be the same trackdir for diagonal trackdirs, but a * different (alternating) one for straight trackdirs @@ -424,14 +434,28 @@ static inline Trackdir DiagdirToDiagTrackdir(DiagDirection diagdir) { return _dir_to_diag_trackdir[diagdir]; } +extern const TrackdirBits _exitdir_reaches_trackdirs[DIAGDIR_END]; + +/** + * Returns all trackdirs that can be reached when entering a tile from a given + * (diagonal) direction. This will obviously include 90 degree turns, since no + * information is available about the exact angle of entering */ +static inline TrackdirBits DiagdirReachesTrackdirs(DiagDirection diagdir) { return _exitdir_reaches_trackdirs[diagdir]; } + +/** + * Returns all tracks that can be reached when entering a tile from a given + * (diagonal) direction. This will obviously include 90 degree turns, since no + * information is available about the exact angle of entering */ +static inline TrackBits DiagdirReachesTracks(DiagDirection diagdir) { return TrackdirBitsToTrackBits(DiagdirReachesTrackdirs(diagdir)); } + /** * Maps a trackdir to the trackdirs that can be reached from it (ie, when - * entering the next tile. This + * entering the next tile. This will include 90 degree turns! */ -extern const TrackdirBits _exitdir_reaches_trackdirs[DIAGDIR_END]; +static inline TrackdirBits TrackdirReachesTrackdirs(Trackdir trackdir) { return _exitdir_reaches_trackdirs[TrackdirToExitdir(trackdir)]; } /* Note that there is no direct table for this function (there used to be), * but it uses two simpeler tables to achieve the result */ -static inline TrackdirBits TrackdirReachesTrackdirs(Trackdir trackdir) { return _exitdir_reaches_trackdirs[TrackdirToExitdir(trackdir)]; } + /** * Maps a trackdir to all trackdirs that make 90 deg turns with it. @@ -594,6 +618,26 @@ static inline bool IsCompatibleRail(RailType enginetype, RailType tiletype) return HASBIT(GetRailTypeInfo(enginetype)->compatible_railtypes, tiletype); } +/** + * Checks if the given tracks overlap, ie form a crossing. Basically this + * means when there is more than one track on the tile, exept when there are + * two parallel tracks. + * @param bits The tracks present. + * @return Whether the tracks present overlap in any way. + */ +static inline bool TracksOverlap(TrackBits bits) +{ + /* With no, or only one track, there is no overlap */ + if (bits == 0 || KILL_FIRST_BIT(bits) == 0) + return false; + /* We know that there are at least two tracks present. When there are more + * than 2 tracks, they will surely overlap. When there are two, they will + * always overlap unless they are lower & upper or right & left. */ + if ((bits == (TRACK_BIT_UPPER|TRACK_BIT_LOWER)) || (bits == (TRACK_BIT_LEFT | TRACK_BIT_RIGHT))) + return false; + return true; +} + void DrawTrackBits(TileInfo *ti, TrackBits track, bool earth, bool snow, bool flat); void DrawTrainDepotSprite(int x, int y, int image, RailType railtype); void DrawDefaultWaypointSprite(int x, int y, RailType railtype); |