From 6f45959d1e05a41f1fceb55c72a244942fa98270 Mon Sep 17 00:00:00 2001 From: matthijs Date: Fri, 9 Sep 2005 23:14:38 +0000 Subject: (svn r2929) * Move DistanceTrack from map.c to npf.c and rename to NPFDistanceTrack. * Make NPFDistanceTrack return the distance multiplied by NPF_TILE_LENGTH to prevent rounding This should make ship and train pathfinding more accurate and faster. * Update IsEndOfLine to prevent trains from trying to go off a slope onto a tunnel entrance. --- map.c | 15 --------------- map.h | 1 - npf.c | 34 +++++++++++++++++++++++++++++++--- 3 files changed, 31 insertions(+), 19 deletions(-) diff --git a/map.c b/map.c index 166119772..5d7ff2b80 100644 --- a/map.c +++ b/map.c @@ -155,21 +155,6 @@ uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1) return dx > dy ? 2 * dx + dy : 2 * dy + dx; } -uint DistanceTrack(TileIndex t0, TileIndex t1) -{ - const uint dx = abs(TileX(t0) - TileX(t1)); - const uint dy = abs(TileY(t0) - TileY(t1)); - - const uint straightTracks = 2 * min(dx, dy); /* The number of straight (not full length) tracks */ - /* OPTIMISATION: - * Original: diagTracks = max(dx, dy) - min(dx,dy); - * Proof: - * (dx-dy) - straightTracks == (min + max) - straightTracks = min + // max - 2 * min = max - min */ - const uint diagTracks = dx + dy - straightTracks; /* The number of diagonal (full tile length) tracks. */ - - return diagTracks + straightTracks * STRAIGHT_TRACK_LENGTH; -} - uint DistanceFromEdge(TileIndex tile) { const uint xl = TileX(tile); diff --git a/map.h b/map.h index e57d2f2e3..5a1705710 100644 --- a/map.h +++ b/map.h @@ -144,7 +144,6 @@ uint DistanceManhattan(TileIndex, TileIndex); // also known as L1-Norm. Is the s uint DistanceSquare(TileIndex, TileIndex); // euclidian- or L2-Norm squared uint DistanceMax(TileIndex, TileIndex); // also known as L-Infinity-Norm uint DistanceMaxPlusManhattan(TileIndex, TileIndex); // Max + Manhattan -uint DistanceTrack(TileIndex, TileIndex); // Returns the shortest distance one could go over tracks uint DistanceFromEdge(TileIndex); // shortest distance from any edge of the map diff --git a/npf.c b/npf.c index 512979fe3..37e9e1058 100644 --- a/npf.c +++ b/npf.c @@ -24,6 +24,29 @@ static const uint _trackdir_length[TRACKDIR_END] = { NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH }; +/** + * Calculates the minimum distance traveled to get from t0 to t1 when only + * using tracks (ie, only making 45 degree turns). Returns the distance in the + * NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to + * prevent rounding. + */ +uint NPFDistanceTrack(TileIndex t0, TileIndex t1) +{ + const uint dx = abs(TileX(t0) - TileX(t1)); + const uint dy = abs(TileY(t0) - TileY(t1)); + + const uint straightTracks = 2 * min(dx, dy); /* The number of straight (not full length) tracks */ + /* OPTIMISATION: + * Original: diagTracks = max(dx, dy) - min(dx,dy); + * Proof: + * (dx+dy) - straightTracks == (min + max) - straightTracks = min + max - 2 * min = max - min */ + const uint diagTracks = dx + dy - straightTracks; /* The number of diagonal (full tile length) tracks. */ + + /* Don't factor out NPF_TILE_LENGTH below, this will round values and lose + * precision */ + return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH; +} + /** * Check if a rail track is the end of the line. Will also consider 1-way signals to be the end of a line. * @param tile The tile on which the current track is. @@ -36,11 +59,11 @@ bool IsEndOfLine(TileIndex tile, Trackdir trackdir, RailType enginetype) TileIndex dst_tile; uint32 ts; - // tunnel entrance? + /* Can always go into a tunnel */ if (IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0xF0)==0 && (_m[tile].m5 & 3) == exitdir) return false; - // depot + /* Cannot go through the back of a depot */ if (IsTileDepotType(tile, TRANSPORT_RAIL) && (exitdir != GetDepotDirection(tile, TRANSPORT_RAIL))) return true; @@ -60,9 +83,14 @@ bool IsEndOfLine(TileIndex tile, Trackdir trackdir, RailType enginetype) if (GetTileOwner(tile) != GetTileOwner(dst_tile)) return true; + /* Prevent us from entering a depot from behind */ if (IsTileDepotType(dst_tile, TRANSPORT_RAIL) && (exitdir != ReverseDiagdir(GetDepotDirection(dst_tile, TRANSPORT_RAIL)))) return true; + /* Prevent us from falling off a slope into a tunnel exit */ + if (IsTileType(dst_tile, MP_TUNNELBRIDGE) && (_m[dst_tile].m5 & 0xF0)==0 && (DiagDirection)(_m[dst_tile].m5 & 3) == ReverseDiagdir(exitdir)) + return true; + /* Check for oneway signal against us */ if (IsTileType(dst_tile, MP_RAILWAY) && GetRailTileType(dst_tile) == RAIL_TYPE_SIGNALS) { if (HasSignalOnTrackdir(dst_tile, ReverseTrackdir(FindFirstBit2x64(ts))) && !HasSignalOnTrackdir(dst_tile, FindFirstBit2x64(ts))) @@ -235,7 +263,7 @@ static int32 NPFCalcStationOrTileHeuristic(AyStar* as, AyStarNode* current, Open dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH; else /* Ships and trains can also go diagonal, so the minimum distance is shorter */ - dist = DistanceTrack(from, to) * NPF_TILE_LENGTH; + dist = NPFDistanceTrack(from, to); DEBUG(npf, 4)("Calculating H for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), dist); -- cgit v1.2.3-70-g09d2