cpp/openttd-patchpack/source Changeset - r13827:a88b85af5397

Changeset - r13827:a88b85af5397

Parent rev.

Child rev.

[Not reviewed]

master

0 3 0

rubidium - 15 years ago 2009-12-01 23:22:41
rubidium@openttd.org

(svn r18366) -Codechange: move the OPF ship pathfinder 'magic' that was in ship_cmd.cpp to the pathfinder code itself

3 files changed with 117 insertions and 123 deletions:

src/pathfinder/opf/opf_ship.cpp

114

src/pathfinder/opf/opf_ship.h

src/ship_cmd.cpp

104

0 comments (0 inline, 0 general)

src/pathfinder/opf/opf_ship.cpp

➞

Show inline comments

@@ @@ -9,29 +9,50 @@ @@
 /** @file pathfind.cpp Implementation of the oldest supported pathfinder. */
 #include "../../stdafx.h"
 #include "../../debug.h"
 #include "../../tunnelbridge_map.h"
 #include "../../core/alloc_type.hpp"
 #include "../../tunnelbridge.h"
 #include "../../ship.h"
 #include "../../core/random_func.hpp"
 #include "opf_ship.h"
 struct RememberData {
 	uint16 cur_length;
 	byte depth;
 	Track last_choosen_track;
 };
 struct TrackPathFinder {
 	TPFEnumProc *enum_proc;
 	void *userdata;
 	TileIndex skiptile;
 	TileIndex dest_coords;
 	uint best_bird_dist;
 	uint best_length;
 	RememberData rd;
 	TrackdirByte the_dir;
 };
 static bool ShipTrackFollower(TileIndex tile, TrackPathFinder *pfs, uint length)
+{
 	/* Found dest? */
 	if (tile == pfs->dest_coords) {
 		pfs->best_bird_dist = 0;
 		pfs->best_length = minu(pfs->best_length, length);
 		return true;
+	}
 	/* Skip this tile in the calculation */
 	if (tile != pfs->skiptile) {
 		pfs->best_bird_dist = minu(pfs->best_bird_dist, DistanceMaxPlusManhattan(pfs->dest_coords, tile));
+	}
 	return false;
+}
 static void TPFModeShip(TrackPathFinder *tpf, TileIndex tile, DiagDirection direction)
+{
 	if (IsTileType(tile, MP_TUNNELBRIDGE)) {
 		/* wrong track type */
 		if (GetTunnelBridgeTransportType(tile) != TRANSPORT_WATER) return;
@@ @@ -51,14 +72,13 @@ static void TPFModeShip(TrackPathFinder @@
 	/* This addition will sometimes overflow by a single tile.
 	 * The use of TILE_MASK here makes sure that we still point at a valid
 	 * tile, and then this tile will be in the sentinel row/col, so GetTileTrackStatus will fail. */
 	tile = TILE_MASK(tile + TileOffsByDiagDir(direction));
 	if (++tpf->rd.cur_length > 50)
 		return;
 	if (++tpf->rd.cur_length > 50) return;
 	TrackBits bits = TrackStatusToTrackBits(GetTileTrackStatus(tile, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(direction);
 	if (bits == TRACK_BIT_NONE) return;
 	assert(TileX(tile) != MapMaxX() && TileY(tile) != MapMaxY());
@@ @@ -76,32 +96,112 @@ static void TPFModeShip(TrackPathFinder @@
+			}
 			tpf->rd.last_choosen_track = track;
+		}
 		tpf->the_dir = TrackEnterdirToTrackdir(track, direction);
-		if (!tpf->enum_proc(tile, tpf->userdata, tpf->the_dir, tpf->rd.cur_length)) {
+		if (!ShipTrackFollower(tile, tpf, tpf->rd.cur_length)) {
 			TPFModeShip(tpf, tile, TrackdirToExitdir(tpf->the_dir));
+		}
 		tpf->rd = rd;
 	} while (bits != TRACK_BIT_NONE);
+}
-void OPFShipFollowTrack(TileIndex tile, DiagDirection direction, TPFEnumProc *enum_proc, void *data)
+static void OPFShipFollowTrack(TileIndex tile, DiagDirection direction, TrackPathFinder *tpf)
+{
 	assert(IsValidDiagDirection(direction));
 	SmallStackSafeStackAlloc<TrackPathFinder, 1> tpf;
 	/* initialize path finder variables */
 	tpf->userdata = data;
 	tpf->enum_proc = enum_proc;
 	tpf->rd.cur_length = 0;
 	tpf->rd.depth = 0;
 	tpf->rd.last_choosen_track = INVALID_TRACK;
-	tpf->enum_proc(tile, data, INVALID_TRACKDIR, 0);
+	ShipTrackFollower(tile, tpf, 0);
 	TPFModeShip(tpf, tile, direction);
+}
 static const byte _ship_search_directions[6][4] = {
 	{ 0, 9, 2, 9 },
 	{ 9, 1, 9, 3 },
 	{ 9, 0, 3, 9 },
 	{ 1, 9, 9, 2 },
 	{ 3, 2, 9, 9 },
 	{ 9, 9, 1, 0 },
 };
 static const byte _pick_shiptrack_table[6] = {1, 3, 2, 2, 0, 0};
 static uint FindShipTrack(Ship *v, TileIndex tile, DiagDirection dir, TrackBits bits, TileIndex skiptile, Track *track)
+{
 	TrackPathFinder pfs;
 	uint best_bird_dist = 0;
 	uint best_length    = 0;
 	byte ship_dir = v->direction & 3;
 	pfs.dest_coords = v->dest_tile;
 	pfs.skiptile = skiptile;
 	Track best_track = INVALID_TRACK;
 	do {
 		Track i = RemoveFirstTrack(&bits);
 		pfs.best_bird_dist = UINT_MAX;
 		pfs.best_length = UINT_MAX;
 		OPFShipFollowTrack(tile, (DiagDirection)_ship_search_directions[i][dir], &pfs);
 		if (best_track != INVALID_TRACK) {
 			if (pfs.best_bird_dist != 0) {
 				/* neither reached the destination, pick the one with the smallest bird dist */
 				if (pfs.best_bird_dist > best_bird_dist) goto bad;
 				if (pfs.best_bird_dist < best_bird_dist) goto good;
 			} else {
 				if (pfs.best_length > best_length) goto bad;
 				if (pfs.best_length < best_length) goto good;
+			}
 			/* if we reach this position, there's two paths of equal value so far.
 			 * pick one randomly. */
 			uint r = GB(Random(), 0, 8);
 			if (_pick_shiptrack_table[i] == ship_dir) r += 80;
 			if (_pick_shiptrack_table[best_track] == ship_dir) r -= 80;
 			if (r <= 127) goto bad;
+		}
 good:;
 		best_track = i;
 		best_bird_dist = pfs.best_bird_dist;
 		best_length = pfs.best_length;
 bad:;
 	} while (bits != 0);
 	*track = best_track;
 	return best_bird_dist;
+}
 /** returns the track to choose on the next tile, or -1 when it's better to
  * reverse. The tile given is the tile we are about to enter, enterdir is the
  * direction in which we are entering the tile */
 Track OPFShipChooseTrack(Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks)
+{
 	assert(IsValidDiagDirection(enterdir));
 	TileIndex tile2 = TILE_ADD(tile, -TileOffsByDiagDir(enterdir));
 	Track track;
 	/* Let's find out how far it would be if we would reverse first */
 	TrackBits b = TrackStatusToTrackBits(GetTileTrackStatus(tile2, TRANSPORT_WATER, 0)) & DiagdirReachesTracks(ReverseDiagDir(enterdir)) & v->state;
 	uint distr = UINT_MAX; // distance if we reversed
 	if (b != 0) {
 		distr = FindShipTrack(v, tile2, ReverseDiagDir(enterdir), b, tile, &track);
 		if (distr != UINT_MAX) distr++; // penalty for reversing
+	}
 	/* And if we would not reverse? */
 	uint dist = FindShipTrack(v, tile, enterdir, tracks, 0, &track);
 	if (dist <= distr) return track;
 	return INVALID_TRACK; // We could better reverse
+}

src/pathfinder/opf/opf_ship.h

➞

Show inline comments

@@ @@ -9,13 +9,9 @@ @@
 /** @file opf_ship.h Original pathfinder for ships; very simple. */
 #ifndef OPF_SHIP_H
 #define OPF_SHIP_H
 #include "../../direction_type.h"
 typedef bool TPFEnumProc(TileIndex tile, void *data, Trackdir trackdir, uint length);
 void OPFShipFollowTrack(TileIndex tile, DiagDirection direction, TPFEnumProc *enum_proc, void *data);
 Track OPFShipChooseTrack(Ship *v, TileIndex tile, DiagDirection enterdir, TrackBits tracks);
 #endif /* OPF_SHIP_H */

src/ship_cmd.cpp

➞

Show inline comments

@@ @@ -365,98 +365,12 @@ static void ShipArrivesAt(const Vehicle @@
 			st->index
 		);
 		AI::NewEvent(v->owner, new AIEventStationFirstVehicle(st->index, v->index));
+	}
+}
 struct PathFindShip {
 	TileIndex skiptile;
 	TileIndex dest_coords;
 	uint best_bird_dist;
 	uint best_length;
 };
 static bool ShipTrackFollower(TileIndex tile, PathFindShip *pfs, int track, uint length)
+{
 	/* Found dest? */
 	if (tile == pfs->dest_coords) {
 		pfs->best_bird_dist = 0;
 		pfs->best_length = minu(pfs->best_length, length);
 		return true;
+	}
 	/* Skip this tile in the calculation */
 	if (tile != pfs->skiptile) {
 		pfs->best_bird_dist = minu(pfs->best_bird_dist, DistanceMaxPlusManhattan(pfs->dest_coords, tile));
+	}
 	return false;
+}
 static const byte _ship_search_directions[6][4] = {
 	{ 0, 9, 2, 9 },
 	{ 9, 1, 9, 3 },
 	{ 9, 0, 3, 9 },
 	{ 1, 9, 9, 2 },
 	{ 3, 2, 9, 9 },
 	{ 9, 9, 1, 0 },
 };
 static const byte _pick_shiptrack_table[6] = {1, 3, 2, 2, 0, 0};
 static uint FindShipTrack(Vehicle *v, TileIndex tile, DiagDirection dir, TrackBits bits, TileIndex skiptile, Track *track)
+{
 	PathFindShip pfs;
 	Track i, best_track;
 	uint best_bird_dist = 0;
 	uint best_length    = 0;
 	uint r;
 	byte ship_dir = v->direction & 3;
 	pfs.dest_coords = v->dest_tile;
 	pfs.skiptile = skiptile;
 	best_track = INVALID_TRACK;
 	do {
 		i = RemoveFirstTrack(&bits);
 		pfs.best_bird_dist = UINT_MAX;
 		pfs.best_length = UINT_MAX;
 		OPFShipFollowTrack(tile, (DiagDirection)_ship_search_directions[i][dir], (TPFEnumProc*)ShipTrackFollower, &pfs);
 		if (best_track != INVALID_TRACK) {
 			if (pfs.best_bird_dist != 0) {
 				/* neither reached the destination, pick the one with the smallest bird dist */
 				if (pfs.best_bird_dist > best_bird_dist) goto bad;
 				if (pfs.best_bird_dist < best_bird_dist) goto good;
 			} else {
 				if (pfs.best_length > best_length) goto bad;
 				if (pfs.best_length < best_length) goto good;
+			}
 			/* if we reach this position, there's two paths of equal value so far.
 			 * pick one randomly. */
 			r = GB(Random(), 0, 8);
 			if (_pick_shiptrack_table[i] == ship_dir) r += 80;
 			if (_pick_shiptrack_table[best_track] == ship_dir) r -= 80;
 			if (r <= 127) goto bad;
+		}
 good:;
 		best_track = i;
 		best_bird_dist = pfs.best_bird_dist;
 		best_length = pfs.best_length;
 bad:;
 	} while (bits != 0);
 	*track = best_track;
 	return best_bird_dist;
+}
 static inline NPFFoundTargetData PerfNPFRouteToStationOrTile(TileIndex tile, Trackdir trackdir, bool ignore_start_tile, NPFFindStationOrTileData *target, TransportType type, Owner owner, RailTypes railtypes)
+{
 	void *perf = NpfBeginInterval();
 	NPFFoundTargetData ret = NPFRouteToStationOrTile(tile, trackdir, ignore_start_tile, target, type, 0, owner, railtypes);
@@ @@ -491,31 +405,15 @@ static Track ChooseShipTrack(Ship *v, Ti @@
 			 * the direction we need to take to get there, if ftd.best_bird_dist is not 0,
 			 * we did not find our target, but ftd.best_trackdir contains the direction leading
 			 * to the tile closest to our target. */
 			if (ftd.best_trackdir != 0xff) return TrackdirToTrack(ftd.best_trackdir); // TODO: Wrapper function?
 		} break;
 		default:
 		case VPF_OPF: { // OPF
 			TileIndex tile2 = TILE_ADD(tile, -TileOffsByDiagDir(enterdir));
 			Track track;
 			/* Let's find out how far it would be if we would reverse first */
 			TrackBits b = GetTileShipTrackStatus(tile2) & DiagdirReachesTracks(ReverseDiagDir(enterdir)) & v->state;
 		default: NOT_REACHED();
 			uint distr = UINT_MAX; // distance if we reversed
 			if (b != 0) {
 				distr = FindShipTrack(v, tile2, ReverseDiagDir(enterdir), b, tile, &track);
 				if (distr != UINT_MAX) distr++; // penalty for reversing
+			}
 			/* And if we would not reverse? */
 			uint dist = FindShipTrack(v, tile, enterdir, tracks, 0, &track);
 			if (dist <= distr) return track;
 		} break;
 		case VPF_OPF: return OPFShipChooseTrack(v, tile, enterdir, tracks);
+	}
 	return INVALID_TRACK; // We could better reverse
+}
 static const Direction _new_vehicle_direction_table[] = {

0 comments (0 inline, 0 general)