cpp/openttd-patchpack/source Changeset - r2403:6989f240f99b

Changeset - r2403:6989f240f99b

Parent rev.

Child rev.

[Not reviewed]

master

0 3 0

matthijs - 19 years ago 2005-09-09 23:14:38
matthijs@openttd.org

(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.

3 files changed with 31 insertions and 19 deletions:

map.c

map.h

npf.c

0 comments (0 inline, 0 general)

map.c

➞

Show inline comments

@@ @@ -155,21 +155,6 @@ uint DistanceMaxPlusManhattan(TileIndex @@
 	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);

map.h

➞

Show inline comments

@@ @@ -144,7 +144,6 @@ uint DistanceManhattan(TileIndex, TileIn @@
 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

npf.c

➞

Show inline comments

@@ @@ -25,6 +25,29 @@ static const uint _trackdir_length[TRACK @@
 };
 /**
  * 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, Trackdi @@
 	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, Trackdi @@
 		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 NPFCalcStationOrTileHeurist @@
 		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);

0 comments (0 inline, 0 general)