/** Directions to search towards given track bits and the ship's enter direction. */
static const DiagDirection _ship_search_directions[6][4] = {
	{ DIAGDIR_NE,      INVALID_DIAGDIR, DIAGDIR_SW,      INVALID_DIAGDIR },
	{ INVALID_DIAGDIR, DIAGDIR_SE,      INVALID_DIAGDIR, DIAGDIR_NW      },
	{ INVALID_DIAGDIR, DIAGDIR_NE,      DIAGDIR_NW,      INVALID_DIAGDIR },
	{ DIAGDIR_SE,      INVALID_DIAGDIR, INVALID_DIAGDIR, DIAGDIR_SW      },
	{ DIAGDIR_NW,      DIAGDIR_SW,      INVALID_DIAGDIR, INVALID_DIAGDIR },
	{ INVALID_DIAGDIR, INVALID_DIAGDIR, DIAGDIR_SE,      DIAGDIR_NE      },
};

/** Track to "direction (& 3)" mapping. */
static const byte _pick_shiptrack_table[6] = {DIR_NE, DIR_SE, DIR_E, DIR_E, DIR_N, DIR_N};

static uint FindShipTrack(const 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;

	assert(bits != TRACK_BIT_NONE);
	do {
		Track i = RemoveFirstTrack(&bits);

		pfs.best_bird_dist = UINT_MAX;
		pfs.best_length = UINT_MAX;

		OPFShipFollowTrack(tile, _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;
			}

			TileIndex tile_i = TileAddByDiagDir(tile, TrackdirToExitdir(TrackEnterdirToTrackdir(i, dir)));
			TileIndex tile_best_track = TileAddByDiagDir(tile, TrackdirToExitdir(TrackEnterdirToTrackdir(best_track, dir)));
			if (IsValidTile(tile_i) && IsValidTile(tile_best_track)) {

				uint distancempm_i = DistanceMaxPlusManhattan(pfs.dest_coords, tile_i);
				uint distancempm_best_track = DistanceMaxPlusManhattan(pfs.dest_coords, tile_best_track);
				uint distancem_i = DistanceManhattan(pfs.dest_coords, tile_i);
				uint distancem_best_track = DistanceManhattan(pfs.dest_coords, tile_best_track);
				uint distances_i = DistanceSquare(pfs.dest_coords, tile_i);
				uint distances_best_track = DistanceSquare(pfs.dest_coords, tile_best_track);

				assert((distancempm_i < distancempm_best_track) == (distances_i < distances_best_track));
				assert((distancempm_i == distancempm_best_track) == (distances_i == distances_best_track));
				assert((distancempm_i > distancempm_best_track) == (distances_i > distances_best_track));

				if (distancempm_i > distancempm_best_track) goto bad;
				if (distancempm_i < distancempm_best_track) goto good;

				if (distances_i > distances_best_track) goto bad;
				if (distances_i < distances_best_track) goto good;

				if (distancem_i > distancem_best_track) goto bad;
				if (distancem_i < distancem_best_track) 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 != TRACK_BIT_NONE);

	*track = best_track;
	return best_bird_dist;
}