(svn r2553) - Fix: [pathfinding] Remove old-old train pathfinder. Enhanced old pathfinder.

  - Penalties for red signals and for slopes. 
  - Increased the search depth to work better with large train networks.

5 files changed, 168 insertions, 139 deletions

diff --git a/pathfind.c b/pathfind.c
index fc8b543db..9fff85d08 100644
--- a/pathfind.c
+++ b/pathfind.c
@@ -3,6 +3,8 @@
 #include "map.h"
 #include "tile.h"
 #include "pathfind.h"
+#include "rail.h"
+#include "debug.h"
 
 // remember which tiles we have already visited so we don't visit them again.
 static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)
@@ -42,8 +44,10 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)
 
 			/* allocate a link. if out of links, handle this by returning
 			 * that a tile was already visisted. */
-			if (tpf->num_links_left == 0)
+			if (tpf->num_links_left == 0) {
+				DEBUG(misc, 4) ("[NTP] no links left\n");
 				return false;
+			}
 			tpf->num_links_left--;
 			link = tpf->new_link++;
 
@@ -79,8 +83,10 @@ static bool TPFSetTileBit(TrackPathFinder *tpf, TileIndex tile, int dir)
 
 	/* get here if we need to add a new link to link,
 	 * first, allocate a new link, in the same way as before */
-	if (tpf->num_links_left == 0)
+	if (tpf->num_links_left == 0) {
+			DEBUG(misc, 4)("[NTP] no links left\n");
 			return false;
+	}
 	tpf->num_links_left--;
 	new_link = tpf->new_link++;
 
@@ -524,7 +530,7 @@ static bool NtpVisit(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint len
 	uint hash,head;
 	HashLink *link, *new_link;
 
-	assert(length < 1024);
+	assert(length < 16384-1);
 
 	hash = PATHFIND_HASH_TILE(tile);
 
@@ -622,6 +628,25 @@ static bool NtpCheck(NewTrackPathFinder *tpf, TileIndex tile, uint dir, uint len
 }
 
 
+static const uint16 _is_upwards_slope[15] = {
+	0, // no tileh
+	(1 << TRACKDIR_DIAG1_SW) | (1 << TRACKDIR_DIAG2_NW), // 1
+	(1 << TRACKDIR_DIAG1_SW) | (1 << TRACKDIR_DIAG2_SE), // 2
+	(1 << TRACKDIR_DIAG1_SW), // 3
+	(1 << TRACKDIR_DIAG1_NE) | (1 << TRACKDIR_DIAG2_SE), // 4
+	0, // 5
+	(1 << TRACKDIR_DIAG2_SE), // 6
+	0, // 7
+	(1 << TRACKDIR_DIAG1_NE) | (1 << TRACKDIR_DIAG2_NW), // 8,
+	(1 << TRACKDIR_DIAG2_NW), // 9
+	0, //10
+	0, //11,
+	(1 << TRACKDIR_DIAG1_NE), //12
+	0, //13
+	0, //14
+};
+
+
 // new more optimized pathfinder for trains...
 static void NTPEnum(NewTrackPathFinder *tpf, TileIndex tile, uint direction)
 {
@@ -642,7 +667,7 @@ restart:
 			if ( (uint)(_map5[tile] & 3) != direction || ((_map5[tile]>>1)&6) != tpf->tracktype)
 				/* We are not driving into the tunnel, or it
 				 * is an invalid tunnel */
-				goto popnext;
+				goto stop_search;
 			flotr = FindLengthOfTunnel(tile, direction);
 			si.cur_length += flotr.length;
 			tile = flotr.tile;
@@ -653,68 +678,128 @@ restart:
 	tile_org = tile;
 
 	for(;;) {
+		int track;
+
 		tile += TileOffsByDir(direction);
 
 		// too long search length? bail out.
-		if (++si.cur_length >= tpf->maxlength)
-			goto popnext;
+		if (++si.cur_length >= tpf->maxlength) {
+			DEBUG(misc,4) ("[NTP] cur_length too big\n");
+			goto stop_search;
+		}
 
-		// not a regular rail tile?
-		if (!IsTileType(tile, MP_RAILWAY) || (bits = _map5[tile]) & 0xC0) {
+		// Not a regular rail tile?
+		// Then we can't use the code below, but revert to more general code.
+		if (!IsTileType(tile, MP_RAILWAY) || (bits = _map5[tile]) & 0x80) {
 			bits = GetTileTrackStatus(tile, TRANSPORT_RAIL) & _tpfmode1_and[direction];
 			bits = (bits | (bits >> 8)) & 0x3F;
+			if (bits == 0) goto stop_search;
 			break;
 		}
 
 		// regular rail tile, determine the tracks that are actually reachable.
 		bits &= _bits_mask[direction];
-		if (bits == 0) goto popnext; // no tracks there? stop searching.
+		if (bits == 0) goto stop_search; // no tracks there? stop searching.
 
-		// complex tile?, let the generic handler handle that..
+		// intersection? then we need to branch the search space,
+		// can't handle that from here.
 		if (KILL_FIRST_BIT(bits) != 0) break;
 
-		// don't bother calling the callback when we have regular tracks only.
-		// it's usually not needed anyway. that will speed up things.
-		direction = _new_dir[FIND_FIRST_BIT(bits)][direction];
+		track = _new_track[FIND_FIRST_BIT(bits)][direction];
+
+		// Check if this rail is an upwards slope. If it is, then add a penalty.
+		if ((track & 7) <= 5 && (_is_upwards_slope[GetTileSlope(tile, NULL)] & (1 << track)) ) {
+			// upwards slope. add some penalty.
+			si.cur_length += 2;
+		}
+
+		// railway tile with signals..?
+		if (_map5[tile] & 0x40) {
+			byte m3;
+
+			m3 = _map3_lo[tile];
+			if (!(m3 & SignalAlongTrackdir(track))) {
+				// if one way signal not pointing towards us, stop going in this direction.
+				if (m3 & SignalAgainstTrackdir(track))
+					goto stop_search;
+			} else if (_map2[tile] & SignalAlongTrackdir(track)) {
+				// green signal in our direction. either one way or two way.
+				si.state |= 1;
+			} else {
+				// reached a red signal.
+				if (m3 & SignalAgainstTrackdir(track)) {
+					// two way red signal. unless we passed another green signal on the way,
+					// stop going in this direction.
+					// this is to prevent us from going into a full platform.
+					if (!(si.state&1))
+						goto stop_search;
+				}
+				// add some penalty since this path has a red signal on it.
+				// only add this penalty max 2 times.
+				if ((si.state & 6) != 4) {
+					si.cur_length += 10;
+					si.state += 2; // remember that we added penalty.
+				}
+			}
+
+			if (tpf->enum_proc(tile, tpf->userdata, track, si.cur_length, &si.state))
+				goto stop_search; // we should stop searching in this direction
+		}
+
+		// continue with the next track
+		direction = _tpf_new_direction[track];
 		assert(direction != 0xFF);
-		if (tile == tile_org) goto popnext; // detect infinite loop..
-	}
 
-	if (!bits) goto popnext;
+		// check if we're running around chasing our tail... (infinite loop)
+		if (tile == tile_org)
+			goto stop_search;
+	}
 
-	// if only one reachable track, use tail recursion optimization.
+	// if only one possible track to choose from, just continue
 	if (KILL_FIRST_BIT(bits) == 0) {
 		i = _new_track[FIND_FIRST_BIT(bits)][direction];
-		// call the callback
+		// call the callback to check if we've reached the destination
 		if (tpf->enum_proc(tile, tpf->userdata, i, si.cur_length, &si.state))
-			goto popnext; // we should stop searching in this direction.
+			goto stop_search; // we should stop searching in this direction.
 
 		// we should continue searching. determine new direction.
 		direction = _tpf_new_direction[i];
 		goto restart; // use tail recursion optimization.
 	}
 
-	// too high recursion depth.. bail out..
-	if (si.depth >= _patches.pf_maxdepth)
-		goto popnext;
-
-	si.depth++; // increase recursion depth.
+	////////////////
+	// We got multiple tracks to choose between (intersection).
+	// Branch the search space into several branches.
+	// Push each alternative on the stack.
+	////////////////
+
+	// Increase recursion depth counter, and
+	// Check so the depth is not too big.. to prevent enourmous slowdown.
+	if (si.depth >= _patches.pf_maxdepth) {
+		DEBUG(misc, 4) ("[NTP] depth too big\n");
+		goto stop_search;
+	}
+	si.depth++;
 
-	// see if this tile was already visited..?
+	// Check if we've already visited this intersection.
+	// If we've already visited it with a better length, then
+	// there's no point in visiting it again.
 	if (NtpVisit(tpf, tile, direction, si.cur_length)) {
-		// push all possible alternatives
+		// Push all possible alternatives that we can reach from here
+		// onto the priority heap.
 		si.tile = tile;
 		do {
 			si.track = _new_track[FIND_FIRST_BIT(bits)][direction];
-
 			// out of stack items, bail out?
-			if (tpf->nstack >= lengthof(tpf->stack))
+			if (tpf->nstack >= lengthof(tpf->stack)) {
+				DEBUG(misc, 4) ("[NTP] out of stack\n");
 				break;
+			}
 			tpf->stack[tpf->nstack] = si;
 			HeapifyUp(tpf);
 		} while ((bits = KILL_FIRST_BIT(bits)) != 0);
 
-		// if this is the first recursion step, we need to fill the first_track member.
+		// If this is the first intersection, we need to fill the first_track member.
 		// so the code outside knows which path is better.
 		// also randomize the order in which we search through them.
 		if (si.depth == 1) {
@@ -732,13 +817,21 @@ restart:
 		}
 	}
 
-popnext:
-	// where to continue.
+
+stop_search:
+	// Now continue searching from the intersection that has the lowest
+	// cost.
+	// Pop the lowest cost item from the priority heap.
 	do {
-		if (tpf->nstack == 0) return; // nothing left?
+		if (tpf->nstack == 0)
+			return; // nothing left? then we're done!
 		si = tpf->stack[0];
 		tile = si.tile;
 		HeapifyDown(tpf);
+
+	// First check if we've already visited the tile we're just about to continue at.
+	// If we've already visited it, no point in continuing from there.
+	// Then call the callback.
 	} while (
 		!NtpCheck(tpf, tile, _tpf_prev_direction[si.track], si.cur_length) || // already have better path to that tile?
 		tpf->enum_proc(tile, tpf->userdata, si.track, si.cur_length, &si.state)
@@ -752,20 +845,17 @@ popnext:
 // new pathfinder for trains. better and faster.
 void NewTrainPathfind(TileIndex tile, byte direction, TPFEnumProc *enum_proc, void *data, byte *cache)
 {
-	if (!_patches.new_pathfinding) {
-		FollowTrack(tile, 0x3000 | TRANSPORT_RAIL, direction, enum_proc, NULL, data);
-	} else {
-		NewTrackPathFinder tpf;
-		tpf.userdata = data;
-		tpf.enum_proc = enum_proc;
-		tpf.tracktype = 0;
-		tpf.maxlength = _patches.pf_maxlength;
-		tpf.nstack = 0;
-		tpf.new_link = tpf.links;
-		tpf.num_links_left = lengthof(tpf.links);
-		memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
+	NewTrackPathFinder tpf;
 
-		NTPEnum(&tpf, tile, direction);
-	}
+	tpf.userdata = data;
+	tpf.enum_proc = enum_proc;
+	tpf.tracktype = 0;
+	tpf.maxlength = _patches.pf_maxlength;
+	tpf.nstack = 0;
+	tpf.new_link = tpf.links;
+	tpf.num_links_left = lengthof(tpf.links);
+	memset(tpf.hash_head, 0, sizeof(tpf.hash_head));
+
+	NTPEnum(&tpf, tile, direction);
 }
 
diff --git a/settings.c b/settings.c
index f6dfdf3df..a06bb9770 100644
--- a/settings.c
+++ b/settings.c
@@ -890,7 +890,6 @@ const SettingDesc patch_settings[] = {
 	{"servint_aircraft",		SDT_UINT16, (void*)100,		&_patches.servint_aircraft,			NULL},
 	{"no_servicing_if_no_breakdowns", SDT_BOOL, (void*)0, &_patches.no_servicing_if_no_breakdowns, NULL},
 
-	{"new_pathfinding",			SDT_BOOL,		(void*)true,	&_patches.new_pathfinding,			NULL},
 	{"pf_maxlength",				SDT_UINT16, (void*)512,		&_patches.pf_maxlength,					NULL},
 	{"pf_maxdepth",					SDT_UINT8,	(void*)16,		&_patches.pf_maxdepth,					NULL},
 
@@ -1084,4 +1083,11 @@ void CheckConfig(void)
 			break;
 		}
 	}
+
+	// Increase old default values for pf_maxdepth and pf_maxlength
+	// to support big networks.
+	if (_patches.pf_maxdepth == 16 && _patches.pf_maxlength == 512) {
+		_patches.pf_maxdepth = 48;
+		_patches.pf_maxlength = 4096;
+	}
 }
diff --git a/settings_gui.c b/settings_gui.c
index 14458be3d..b9a0e0037 100644
--- a/settings_gui.c
+++ b/settings_gui.c
@@ -680,7 +680,6 @@ static const PatchEntry _patches_vehicles[] = {
 	{PE_BOOL,		0, STR_CONFIG_PATCHES_GOTODEPOT,				"goto_depot", 			&_patches.gotodepot,								0,  0,  0, NULL},
 	{PE_BOOL,		0, STR_CONFIG_PATCHES_ROADVEH_QUEUE,		"roadveh_queue", 		&_patches.roadveh_queue,						0,  0,  0, NULL},
 	{PE_BOOL,		0, STR_CONFIG_PATCHES_NEW_DEPOT_FINDING,"depot_finding", 		&_patches.new_depot_finding,				0,  0,  0, NULL},
-	{PE_BOOL,		0, STR_CONFIG_PATCHES_NEW_TRAIN_PATHFIND,"new_pathfinding", &_patches.new_pathfinding,	0,  0,  0, NULL},
 	{PE_BOOL,		0, STR_CONFIG_PATCHES_NEW_PATHFINDING_ALL, "new_pathfinding_all", &_patches.new_pathfinding_all,		0,  0,  0, NULL},
 
 	{PE_BOOL,		PF_PLAYERBASED, STR_CONFIG_PATCHES_WARN_INCOME_LESS, "train_income_warn", &_patches.train_income_warn,				0,  0,  0, NULL},
diff --git a/train_cmd.c b/train_cmd.c
index b23c6e9e4..5ed6ab43d 100644
--- a/train_cmd.c
+++ b/train_cmd.c
@@ -1882,33 +1882,16 @@ typedef struct TrainTrackFollowerData {
 
 static bool TrainTrackFollower(TileIndex tile, TrainTrackFollowerData *ttfd, int track, uint length, byte *state)
 {
-	if (IsTileType(tile, MP_RAILWAY) && (_map5[tile]&0xC0) == 0x40) {
-		// the tile has a signal
-		byte m3 = _map3_lo[tile];
-		if (!(m3 & SignalAlongTrackdir(track))) {
-			// if one way signal not pointing towards us, stop going in this direction.
-			if (m3 & SignalAgainstTrackdir(track))
-				return true;
-		} else if (_map2[tile] & SignalAlongTrackdir(track)) {
-			// green signal in our direction. either one way or two way.
-			*state = true;
-		} else if (m3 & SignalAgainstTrackdir(track)) {
-			// two way signal. unless we passed another green signal on the way,
-			// stop going in this direction.
-			if (!*state) return true;
-		}
-	}
-
 	// heading for nowhere?
 	if (ttfd->dest_coords == 0)
 		return false;
 
 	// did we reach the final station?
- if ((ttfd->station_index == INVALID_STATION && tile == ttfd->dest_coords) ||
-  (IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0, 8) && _map2[tile] == ttfd->station_index)) {
-  /* We do not check for dest_coords if we have a station_index,
-   * because in that case the dest_coords are just an
-   * approximation of where the station is */
+	if ((ttfd->station_index == INVALID_STATION && tile == ttfd->dest_coords) ||
+		(IsTileType(tile, MP_STATION) && IS_BYTE_INSIDE(_map5[tile], 0, 8) && _map2[tile] == ttfd->station_index)) {
+		/* We do not check for dest_coords if we have a station_index,
+		 * because in that case the dest_coords are just an
+		 * approximation of where the station is */
 		// found station
 		ttfd->best_bird_dist = 0;
 		if (length < ttfd->best_track_dist) {
@@ -1970,6 +1953,7 @@ static const byte _search_directions[6][4] = {
 
 static const byte _pick_track_table[6] = {1, 3, 2, 2, 0, 0};
 #if PF_BENCHMARK
+#if !defined(_MSC_VER)
 unsigned int rdtsc()
 {
      unsigned int high, low;
@@ -1977,7 +1961,17 @@ unsigned int rdtsc()
      __asm__ __volatile__ ("rdtsc" : "=a" (low), "=d" (high));
      return low;
 }
+#else
+static unsigned int _declspec(naked) rdtsc(void)
+{
+	_asm {
+		rdtsc
+		ret
+	}
+}
 #endif
+#endif
+
 
 
 /* choose a track */
@@ -2035,79 +2029,20 @@ static byte ChooseTrainTrack(Vehicle *v, TileIndex tile, int enterdir, TrackdirB
 			best_track = TrackdirToTrack(ftd.best_trackdir);
 		}
 	} else {
-
 		FillWithStationData(&fd, v);
 
-		if (_patches.new_pathfinding) {
-			/* New train pathfinding */
-			fd.best_bird_dist = (uint)-1;
-			fd.best_track_dist = (uint)-1;
-			fd.best_track = 0xFF;
-			NewTrainPathfind(tile - TileOffsByDir(enterdir), enterdir, (TPFEnumProc*)TrainTrackFollower, &fd, NULL);
+		/* New train pathfinding */
+		fd.best_bird_dist = (uint)-1;
+		fd.best_track_dist = (uint)-1;
+		fd.best_track = 0xFF;
 
-	//		printf("Train %d %s\n", v->unitnumber, fd.best_track_dist == -1 ? "NOTFOUND" : "FOUND");
+		NewTrainPathfind(tile - TileOffsByDir(enterdir), enterdir, (TPFEnumProc*)TrainTrackFollower, &fd, NULL);
 
-			if (fd.best_track == 0xff) {
-				// blaha
-				best_track = FIND_FIRST_BIT(trackdirbits);
-			} else {
-				best_track = fd.best_track & 7;
-			}
+		if (fd.best_track == 0xff) {
+			// blaha
+			best_track = FIND_FIRST_BIT(trackdirbits);
 		} else {
-			/* Original pathfinding */
-			int i, r;
-			uint best_bird_dist  = 0;
-			uint best_track_dist = 0;
-			byte train_dir = v->direction & 3;
-
-
-			best_track = (uint)-1;
-
-			do {
-				i = FIND_FIRST_BIT(trackdirbits);
-				trackdirbits = KILL_FIRST_BIT(trackdirbits);
-
-				fd.best_bird_dist = (uint)-1;
-				fd.best_track_dist = (uint)-1;
-
-				NewTrainPathfind(tile, _search_directions[i][enterdir], (TPFEnumProc*)TrainTrackFollower, &fd, NULL);
-				if (best_track != (uint)-1) {
-					if (best_track_dist == (uint)-1) {
-						if (fd.best_track_dist == (uint)-1) {
-							/* neither reached the destination, pick the one with the smallest bird dist */
-							if (fd.best_bird_dist > best_bird_dist) goto bad;
-							if (fd.best_bird_dist < best_bird_dist) goto good;
-						} else {
-							/* we found the destination for the first time */
-							goto good;
-						}
-					} else {
-						if (fd.best_track_dist == (uint)-1) {
-							/* didn't find destination, but we've found the destination previously */
-							goto bad;
-						} else {
-							/* both old & new reached the destination, compare track length */
-							if (fd.best_track_dist > best_track_dist) goto bad;
-							if (fd.best_track_dist < best_track_dist) goto good;
-						}
-					}
-
-					/* if we reach this position, there's two paths of equal value so far.
-					 * pick one randomly. */
-					r = (byte)Random();
-					if (_pick_track_table[i] == train_dir) r += 80;
-					if (_pick_track_table[best_track] == train_dir) r -= 80;
-
-					if (r <= 127) goto bad;
-				}
-		good:;
-				best_track = i;
-				best_bird_dist = fd.best_bird_dist;
-				best_track_dist = fd.best_track_dist;
-		bad:;
-			} while (trackdirbits != 0);
-	//		printf("Train %d %s\n", v->unitnumber, best_track_dist == -1 ? "NOTFOUND" : "FOUND");
-			assert(best_track != (uint)-1);
+			best_track = fd.best_track & 7;
 		}
 	}
 
diff --git a/variables.h b/variables.h
index 5d505af41..3514ad54f 100644
--- a/variables.h
+++ b/variables.h
@@ -157,7 +157,6 @@ typedef struct Patches {
 	int16 autorenew_months;
 	int32 autorenew_money;
 
-	bool new_pathfinding;		// use optimized pathfinding algoritm for trains
 	byte pf_maxdepth;				// maximum recursion depth when searching for a train route for new pathfinder
 	uint16 pf_maxlength;		// maximum length when searching for a train route for new pathfinder