From 3e97dda275f59b2bcaea44c48ceba7a0ed054d9c Mon Sep 17 00:00:00 2001 From: ludde Date: Tue, 19 Jul 2005 11:42:40 +0000 Subject: (svn r2635) Fix: [ntp/misc] Improve the old pathfinder. Changed it to A* instead of Dijkstra. - Benchmark shows that NTP is now around 10x faster than NPF. - Made IsTunnelTile macro to determine if a tile is a tunnel. - Added some useful debugging functions for making tiles red / getting accurate timestamps. - Remove old depot finding algorithm. - Disable warning for signed/unsigned comparisons. --- train_cmd.c | 75 ++++++++++++++++++------------------------------------------- 1 file changed, 22 insertions(+), 53 deletions(-) (limited to 'train_cmd.c') diff --git a/train_cmd.c b/train_cmd.c index 5fe2b0a6d..6508eaa58 100644 --- a/train_cmd.c +++ b/train_cmd.c @@ -666,11 +666,6 @@ int32 CmdBuildRailVehicle(int x, int y, uint32 flags, uint32 p1, uint32 p2) return value; } -static bool IsTunnelTile(TileIndex tile) -{ - return IsTileType(tile, MP_TUNNELBRIDGE) && (_m[tile].m5 & 0x80) == 0; -} - /* Check if all the wagons of the given train are in a depot, returns the * number of cars (including loco) then. If not, sets the error message to @@ -1307,9 +1302,7 @@ TileIndex GetVehicleTileOutOfTunnel(const Vehicle *v, bool reverse) return v->tile; for (tile = v->tile;; tile += delta) { - if (IsTileType(tile, MP_TUNNELBRIDGE) && - (_m[tile].m5 & 0xF3) != (direction) && - GetTileZ(tile) == v->z_pos) + if (IsTunnelTile(tile) && (_m[tile].m5 & 0x3) != (direction) && GetTileZ(tile) == v->z_pos) break; } return tile; @@ -1569,26 +1562,17 @@ typedef struct TrainFindDepotData { bool reverse; } TrainFindDepotData; -static bool TrainFindDepotEnumProc(TileIndex tile, TrainFindDepotData *tfdd, int track, uint length, byte *state) +static bool NtpCallbFindDepot(TileIndex tile, TrainFindDepotData *tfdd, int track, uint length) { if (IsTileType(tile, MP_RAILWAY) && IsTileOwner(tile, tfdd->owner)) { if ((_m[tile].m5 & ~0x3) == 0xC0) { - if (length < tfdd->best_length) { - tfdd->best_length = length; - tfdd->tile = tile; - } + tfdd->best_length = length; + tfdd->tile = tile; return true; } - - // make sure the train doesn't run against a oneway signal - if ((_m[tile].m5 & 0xC0) == 0x40) { - if (!(_m[tile].m3 & SignalAlongTrackdir(track)) && _m[tile].m3 & SignalAgainstTrackdir(track)) - return true; - } } - // stop searching if we've found a destination that is closer already. - return length >= tfdd->best_length; + return false; } // returns the tile of a depot to goto to. The given vehicle must not be @@ -1632,21 +1616,17 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v) if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) tfdd.reverse = true; } - } else if (!_patches.new_depot_finding) { - // search in all directions - for(i=0; i!=4; i++) - NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL); } else { // search in the forward direction first. i = v->direction >> 1; if (!(v->direction & 1) && v->u.rail.track != _state_dir_table[i]) { i = (i - 1) & 3; } - NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL); + NewTrainPathfind(tile, 0, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); if (tfdd.best_length == (uint)-1){ tfdd.reverse = true; // search in backwards direction i = (v->direction^4) >> 1; if (!(v->direction & 1) && v->u.rail.track != _state_dir_table[i]) { i = (i - 1) & 3; } - NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL); + NewTrainPathfind(tile, 0, i, (NTPEnumProc*)NtpCallbFindDepot, &tfdd); } } @@ -1887,7 +1867,7 @@ typedef struct TrainTrackFollowerData { byte best_track; } TrainTrackFollowerData; -static bool TrainTrackFollower(TileIndex tile, TrainTrackFollowerData *ttfd, int track, uint length, byte *state) +static bool NtpCallbFindStation(TileIndex tile, TrainTrackFollowerData *ttfd, int track, uint length) { // heading for nowhere? if (ttfd->dest_coords == 0) @@ -1900,24 +1880,16 @@ static bool TrainTrackFollower(TileIndex tile, TrainTrackFollowerData *ttfd, int * 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) { - ttfd->best_track_dist = length; - ttfd->best_track = state[1]; - } + ttfd->best_track = track; return true; } else { uint dist; - // we've actually found the destination already. no point searching in directions longer than this. - if (ttfd->best_track_dist != (uint)-1) - return length >= ttfd->best_track_dist; - - // didn't find station + // didn't find station, keep track of the best path so far. dist = DistanceManhattan(tile, ttfd->dest_coords); if (dist < ttfd->best_bird_dist) { ttfd->best_bird_dist = dist; - ttfd->best_track = state[1]; + ttfd->best_track = track; } return false; } @@ -2046,7 +2018,8 @@ static byte ChooseTrainTrack(Vehicle *v, TileIndex tile, int enterdir, TrackdirB fd.best_track_dist = (uint)-1; fd.best_track = 0xFF; - NewTrainPathfind(tile - TileOffsByDir(enterdir), enterdir, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); + NewTrainPathfind(tile - TileOffsByDir(enterdir), v->dest_tile, + enterdir, (NTPEnumProc*)NtpCallbFindStation, &fd); if (fd.best_track == 0xff) { // blaha @@ -2118,7 +2091,7 @@ static bool CheckReverseTrain(Vehicle *v) fd.best_bird_dist = (uint)-1; fd.best_track_dist = (uint)-1; - NewTrainPathfind(v->tile, reverse ^ i, (TPFEnumProc*)TrainTrackFollower, &fd, NULL); + NewTrainPathfind(v->tile, v->dest_tile, reverse ^ i, (NTPEnumProc*)NtpCallbFindStation, &fd); if (best_track != -1) { if (best_bird_dist != 0) { @@ -2861,18 +2834,15 @@ green_light: /* in tunnel */ GetNewVehiclePos(v, &gp); - if (IsTileType(gp.new_tile, MP_TUNNELBRIDGE) && - !(_m[gp.new_tile].m5 & 0xF0)) { - r = VehicleEnterTile(v, gp.new_tile, gp.x, gp.y); - if (r & 0x4) goto common; + // Check if to exit the tunnel... + if (!IsTunnelTile(gp.new_tile) || + !(VehicleEnterTile(v, gp.new_tile, gp.x, gp.y)&0x4) ) { + v->x_pos = gp.x; + v->y_pos = gp.y; + VehiclePositionChanged(v); + continue; } - - v->x_pos = gp.x; - v->y_pos = gp.y; - VehiclePositionChanged(v); - continue; } -common:; /* update image of train, as well as delta XY */ newdir = GetNewVehicleDirection(v, gp.x, gp.y); @@ -3125,8 +3095,7 @@ static bool TrainCheckIfLineEnds(Vehicle *v) tile = v->tile; // tunnel entrance? - if (IsTileType(tile, MP_TUNNELBRIDGE) && - (_m[tile].m5 & 0xF0) == 0 && (byte)((_m[tile].m5 & 3)*2+1) == v->direction) + if (IsTunnelTile(tile) && (byte)((_m[tile].m5 & 3)*2+1) == v->direction) return true; // depot? -- cgit v1.2.3-54-g00ecf