summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authormatthijs <matthijs@openttd.org>2005-09-09 23:14:38 +0000
committermatthijs <matthijs@openttd.org>2005-09-09 23:14:38 +0000
commitcd54bf48d1b78ad51a5bf91d96e41d6b8cd8513b (patch)
tree2f3cffa2f8a0c0f0c06f6a3666f430e20d0c6957
parenta744b15907b55c56569f9028ada63d5b04ef6229 (diff)
downloadopenttd-cd54bf48d1b78ad51a5bf91d96e41d6b8cd8513b.tar.xz
(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.
-rw-r--r--map.c15
-rw-r--r--map.h1
-rw-r--r--npf.c34
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
@@ -25,6 +25,29 @@ static const uint _trackdir_length[TRACKDIR_END] = {
};
/**
+ * 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.
* @param trackdir The (track)direction in which you want to look.
@@ -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);