From f523be81d4cb9be33741b993a804b146cd76da47 Mon Sep 17 00:00:00 2001 From: ludde Date: Tue, 12 Jul 2005 20:28:19 +0000 Subject: (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. --- pathfind.c | 182 ++++++++++++++++++++++++++++++++++++++++++--------------- settings.c | 8 ++- settings_gui.c | 1 - train_cmd.c | 115 ++++++++---------------------------- variables.h | 1 - 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 -- cgit v1.2.3-54-g00ecf