diff options
author | matthijs <matthijs@openttd.org> | 2005-04-11 19:14:48 +0000 |
---|---|---|
committer | matthijs <matthijs@openttd.org> | 2005-04-11 19:14:48 +0000 |
commit | b02dde198240a27f53ca196e1d9bdff89ca2edcf (patch) | |
tree | 2cfb3fe1eaa3454e6c943f30efc3944c2eba1a02 /map.c | |
parent | a714444a8eed4e9eb7cba177026171e034ce3b7f (diff) | |
download | openttd-b02dde198240a27f53ca196e1d9bdff89ca2edcf.tar.xz |
(svn r2181) - Add: DistanceTrack() to calculate the distance over optimally laid out tracks.
- Codechange: [NPF] Removed unused heuristic function NPFCalcTileHeuristic().
- Codechange: [NPF] Use DistanceTrack() instead of DistanceManhattan() for ship and train heuristic.
- Codechange: Renamed variables x and y to dx and dy in some of the distance calculation functions.
Diffstat (limited to 'map.c')
-rw-r--r-- | map.c | 38 |
1 files changed, 26 insertions, 12 deletions
@@ -138,35 +138,49 @@ const TileIndexDiffC _tileoffs_by_dir[] = { uint DistanceManhattan(TileIndex t0, TileIndex t1) { - return - abs(TileX(t0) - TileX(t1)) + - abs(TileY(t0) - TileY(t1)); + const uint dx = abs(TileX(t0) - TileX(t1)); + const uint dy = abs(TileY(t0) - TileY(t1)); + return dx + dy; } uint DistanceSquare(TileIndex t0, TileIndex t1) { - const int x = TileX(t0) - TileX(t1); - const int y = TileY(t0) - TileY(t1); - return x * x + y * y; + const int dx = TileX(t0) - TileX(t1); + const int dy = TileY(t0) - TileY(t1); + return dx * dx + dy * dy; } uint DistanceMax(TileIndex t0, TileIndex t1) { - const uint x = abs(TileX(t0) - TileX(t1)); - const uint y = abs(TileY(t0) - TileY(t1)); - return x > y ? x : y; + const uint dx = abs(TileX(t0) - TileX(t1)); + const uint dy = abs(TileY(t0) - TileY(t1)); + return dx > dy ? dx : dy; } uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1) { - const uint x = abs(TileX(t0) - TileX(t1)); - const uint y = abs(TileY(t0) - TileY(t1)); - return x > y ? 2 * x + y : 2 * y + x; + const uint dx = abs(TileX(t0) - TileX(t1)); + const uint dy = abs(TileY(t0) - TileY(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) { |