394 static const DiagDirection _road_pf_directions[] = { |
396 static const DiagDirection _road_pf_directions[] = { |
395 DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE, INVALID_DIAGDIR, INVALID_DIAGDIR, |
397 DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_NE, DIAGDIR_SE, DIAGDIR_SW, DIAGDIR_SE, INVALID_DIAGDIR, INVALID_DIAGDIR, |
396 DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, INVALID_DIAGDIR, INVALID_DIAGDIR |
398 DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NW, DIAGDIR_SW, DIAGDIR_NW, DIAGDIR_NE, INVALID_DIAGDIR, INVALID_DIAGDIR |
397 }; |
399 }; |
398 |
400 |
399 static bool EnumRoadSignalFindDepot(TileIndex tile, void* data, Trackdir trackdir, uint length, byte* state) |
401 static bool EnumRoadSignalFindDepot(TileIndex tile, void* data, Trackdir trackdir, uint length) |
400 { |
402 { |
401 RoadFindDepotData* rfdd = (RoadFindDepotData*)data; |
403 RoadFindDepotData* rfdd = (RoadFindDepotData*)data; |
402 |
404 |
403 tile += TileOffsByDiagDir(_road_pf_directions[trackdir]); |
405 tile += TileOffsByDiagDir(_road_pf_directions[trackdir]); |
404 |
406 |
405 if (IsTileType(tile, MP_ROAD) && |
407 if (IsRoadDepotTile(tile) && |
406 GetRoadTileType(tile) == ROAD_TILE_DEPOT && |
|
407 IsTileOwner(tile, rfdd->owner) && |
408 IsTileOwner(tile, rfdd->owner) && |
408 length < rfdd->best_length) { |
409 length < rfdd->best_length) { |
409 rfdd->best_length = length; |
410 rfdd->best_length = length; |
410 rfdd->tile = tile; |
411 rfdd->tile = tile; |
411 } |
412 } |
412 return false; |
413 return false; |
413 } |
414 } |
414 |
415 |
415 static const Depot* FindClosestRoadDepot(const Vehicle* v) |
416 static const Depot* FindClosestRoadDepot(const Vehicle* v) |
416 { |
417 { |
417 TileIndex tile = v->tile; |
418 switch (_patches.pathfinder_for_roadvehs) { |
418 |
419 case VPF_YAPF: /* YAPF */ |
419 if (_patches.yapf.road_use_yapf) { |
420 return YapfFindNearestRoadDepot(v); |
420 Depot* ret = YapfFindNearestRoadDepot(v); |
421 |
421 return ret; |
422 case VPF_NPF: { /* NPF */ |
422 } else if (_patches.new_pathfinding_all) { |
423 /* See where we are now */ |
423 NPFFoundTargetData ftd; |
424 Trackdir trackdir = GetVehicleTrackdir(v); |
424 /* See where we are now */ |
425 |
425 Trackdir trackdir = GetVehicleTrackdir(v); |
426 NPFFoundTargetData ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, false, v->tile, ReverseTrackdir(trackdir), false, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); |
426 |
427 |
427 ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, v->tile, ReverseTrackdir(trackdir), TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES, 0); |
428 if (ftd.best_bird_dist == 0) return GetDepotByTile(ftd.node.tile); /* Target found */ |
428 if (ftd.best_bird_dist == 0) { |
429 } break; |
429 return GetDepotByTile(ftd.node.tile); /* Target found */ |
430 |
430 } else { |
431 default: |
431 return NULL; /* Target not found */ |
432 case VPF_OPF: { /* OPF */ |
432 } |
433 RoadFindDepotData rfdd; |
433 /* We do not search in two directions here, why should we? We can't reverse right now can we? */ |
434 |
434 } else { |
435 rfdd.owner = v->owner; |
435 RoadFindDepotData rfdd; |
436 rfdd.best_length = UINT_MAX; |
436 |
437 |
437 rfdd.owner = v->owner; |
438 /* search in all directions */ |
438 rfdd.best_length = (uint)-1; |
439 for (DiagDirection d = DIAGDIR_BEGIN; d < DIAGDIR_END; d++) { |
439 |
440 FollowTrack(v->tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, d, EnumRoadSignalFindDepot, NULL, &rfdd); |
440 /* search in all directions */ |
441 } |
441 for (DiagDirection i = DIAGDIR_BEGIN; i != DIAGDIR_END; i++) { |
442 |
442 FollowTrack(tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, i, EnumRoadSignalFindDepot, NULL, &rfdd); |
443 if (rfdd.best_length != UINT_MAX) return GetDepotByTile(rfdd.tile); |
443 } |
444 } break; |
444 |
445 } |
445 if (rfdd.best_length == (uint)-1) return NULL; |
446 |
446 |
447 return NULL; /* Target not found */ |
447 return GetDepotByTile(rfdd.tile); |
|
448 } |
|
449 } |
448 } |
450 |
449 |
451 /** Send a road vehicle to the depot. |
450 /** Send a road vehicle to the depot. |
452 * @param tile unused |
451 * @param tile unused |
453 * @param flags operation to perform |
452 * @param flags operation to perform |
1007 |
1006 |
1008 struct OvertakeData { |
1007 struct OvertakeData { |
1009 const Vehicle* u; |
1008 const Vehicle* u; |
1010 const Vehicle* v; |
1009 const Vehicle* v; |
1011 TileIndex tile; |
1010 TileIndex tile; |
1012 uint16 tilebits; |
1011 Trackdir trackdir; |
1013 }; |
1012 }; |
1014 |
1013 |
1015 static void* EnumFindVehToOvertake(Vehicle* v, void* data) |
1014 static void* EnumFindVehBlockingOvertake(Vehicle* v, void* data) |
1016 { |
1015 { |
1017 const OvertakeData* od = (OvertakeData*)data; |
1016 const OvertakeData* od = (OvertakeData*)data; |
1018 |
1017 |
1019 return |
1018 return |
1020 v->type == VEH_ROAD && v->First() == v && v != od->u && v != od->v ? |
1019 v->type == VEH_ROAD && v->First() == v && v != od->u && v != od->v ? |
1021 v : NULL; |
1020 v : NULL; |
1022 } |
1021 } |
1023 |
1022 |
1024 static bool FindRoadVehToOvertake(OvertakeData *od) |
1023 /** |
1025 { |
1024 * Check if overtaking is possible on a piece of track |
1026 uint32 bits; |
1025 * |
1027 |
1026 * @param od Information about the tile and the involved vehicles |
1028 bits = GetTileTrackStatus(od->tile, TRANSPORT_ROAD, od->v->u.road.compatible_roadtypes); |
1027 * @return true if we have to abort overtaking |
1029 bits |= bits >> 8; |
1028 */ |
1030 |
1029 static bool CheckRoadBlockedForOvertaking(OvertakeData *od) |
1031 if (!(od->tilebits & bits) || (bits & 0x3C3C) || (bits & 0x3F3F0000)) |
1030 { |
1032 return true; |
1031 TrackStatus ts = GetTileTrackStatus(od->tile, TRANSPORT_ROAD, od->v->u.road.compatible_roadtypes); |
1033 return VehicleFromPos(od->tile, od, EnumFindVehToOvertake) != NULL; |
1032 TrackdirBits trackdirbits = TrackStatusToTrackdirBits(ts); |
|
1033 TrackdirBits red_signals = TrackStatusToRedSignals(ts); // barred level crossing |
|
1034 TrackBits trackbits = TrackdirBitsToTrackBits(trackdirbits); |
|
1035 |
|
1036 /* Track does not continue along overtaking direction || track has junction || levelcrossing is barred */ |
|
1037 if (!HasBit(trackdirbits, od->trackdir) || (trackbits & ~TRACK_BIT_CROSS) || (red_signals != TRACKDIR_BIT_NONE)) return true; |
|
1038 |
|
1039 /* Are there more vehicles on the tile except the two vehicles involved in overtaking */ |
|
1040 return VehicleFromPos(od->tile, od, EnumFindVehBlockingOvertake) != NULL; |
1034 } |
1041 } |
1035 |
1042 |
1036 static void RoadVehCheckOvertake(Vehicle *v, Vehicle *u) |
1043 static void RoadVehCheckOvertake(Vehicle *v, Vehicle *u) |
1037 { |
1044 { |
1038 OvertakeData od; |
1045 OvertakeData od; |
1039 uint16 tt; |
|
1040 |
1046 |
1041 od.v = v; |
1047 od.v = v; |
1042 od.u = u; |
1048 od.u = u; |
1043 |
1049 |
1044 if (u->max_speed >= v->max_speed && |
1050 if (u->max_speed >= v->max_speed && |
1054 if (IsTileType(v->tile, MP_STATION)) return; |
1060 if (IsTileType(v->tile, MP_STATION)) return; |
1055 |
1061 |
1056 /* For now, articulated road vehicles can't overtake anything. */ |
1062 /* For now, articulated road vehicles can't overtake anything. */ |
1057 if (RoadVehHasArticPart(v)) return; |
1063 if (RoadVehHasArticPart(v)) return; |
1058 |
1064 |
|
1065 /* Vehicles are not driving in same direction || direction is not a diagonal direction */ |
1059 if (v->direction != u->direction || !(v->direction & 1)) return; |
1066 if (v->direction != u->direction || !(v->direction & 1)) return; |
1060 |
1067 |
1061 /* Check if vehicle is in a road stop, depot, tunnel or bridge or not on a straight road */ |
1068 /* Check if vehicle is in a road stop, depot, tunnel or bridge or not on a straight road */ |
1062 if (v->u.road.state >= RVSB_IN_ROAD_STOP || !IsStraightRoadTrackdir((Trackdir)(v->u.road.state & RVSB_TRACKDIR_MASK))) return; |
1069 if (v->u.road.state >= RVSB_IN_ROAD_STOP || !IsStraightRoadTrackdir((Trackdir)(v->u.road.state & RVSB_TRACKDIR_MASK))) return; |
1063 |
1070 |
1064 tt = GetTileTrackStatus(v->tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes); |
1071 od.trackdir = DiagdirToDiagTrackdir(DirToDiagDir(v->direction)); |
1065 tt |= tt >> 8; |
1072 |
1066 tt &= 0x3F; |
1073 /* Are the current and the next tile suitable for overtaking? |
1067 |
1074 * - Does the track continue along od.trackdir |
1068 if ((tt & 3) == 0) return; |
1075 * - No junctions |
1069 if ((tt & 0x3C) != 0) return; |
1076 * - No barred levelcrossing |
1070 |
1077 * - No other vehicles in the way |
1071 if (tt == 3) tt = (v->direction & 2) ? 2 : 1; |
1078 */ |
1072 od.tilebits = tt; |
|
1073 |
|
1074 od.tile = v->tile; |
1079 od.tile = v->tile; |
1075 if (FindRoadVehToOvertake(&od)) return; |
1080 if (CheckRoadBlockedForOvertaking(&od)) return; |
1076 |
1081 |
1077 od.tile = v->tile + TileOffsByDiagDir(DirToDiagDir(v->direction)); |
1082 od.tile = v->tile + TileOffsByDiagDir(DirToDiagDir(v->direction)); |
1078 if (FindRoadVehToOvertake(&od)) return; |
1083 if (CheckRoadBlockedForOvertaking(&od)) return; |
1079 |
1084 |
1080 if (od.u->cur_speed == 0 || od.u->vehstatus& VS_STOPPED) { |
1085 if (od.u->cur_speed == 0 || od.u->vehstatus& VS_STOPPED) { |
1081 v->u.road.overtaking_ctr = 0x11; |
1086 v->u.road.overtaking_ctr = 0x11; |
1082 v->u.road.overtaking = 0x10; |
1087 v->u.road.overtaking = 0x10; |
1083 } else { |
1088 } else { |
1084 // if (FindRoadVehToOvertake(&od)) return; |
1089 // if (CheckRoadBlockedForOvertaking(&od)) return; |
1085 v->u.road.overtaking_ctr = 0; |
1090 v->u.road.overtaking_ctr = 0; |
1086 v->u.road.overtaking = 0x10; |
1091 v->u.road.overtaking = 0x10; |
1087 } |
1092 } |
1088 } |
1093 } |
1089 |
1094 |
1215 /* Only one track to choose between? */ |
1220 /* Only one track to choose between? */ |
1216 if (KillFirstBit(trackdirs) == TRACKDIR_BIT_NONE) { |
1221 if (KillFirstBit(trackdirs) == TRACKDIR_BIT_NONE) { |
1217 return_track(FindFirstBit2x64(trackdirs)); |
1222 return_track(FindFirstBit2x64(trackdirs)); |
1218 } |
1223 } |
1219 |
1224 |
1220 if (_patches.yapf.road_use_yapf) { |
1225 switch (_patches.pathfinder_for_roadvehs) { |
1221 Trackdir trackdir = YapfChooseRoadTrack(v, tile, enterdir); |
1226 case VPF_YAPF: { /* YAPF */ |
1222 if (trackdir != INVALID_TRACKDIR) return_track(trackdir); |
1227 Trackdir trackdir = YapfChooseRoadTrack(v, tile, enterdir); |
1223 return_track(PickRandomBit(trackdirs)); |
1228 if (trackdir != INVALID_TRACKDIR) return_track(trackdir); |
1224 } else if (_patches.new_pathfinding_all) { |
1229 return_track(PickRandomBit(trackdirs)); |
1225 NPFFindStationOrTileData fstd; |
1230 } break; |
1226 NPFFoundTargetData ftd; |
1231 |
1227 Trackdir trackdir; |
1232 case VPF_NPF: { /* NPF */ |
1228 |
1233 NPFFindStationOrTileData fstd; |
1229 NPFFillWithOrderData(&fstd, v); |
1234 |
1230 trackdir = DiagdirToDiagTrackdir(enterdir); |
1235 NPFFillWithOrderData(&fstd, v); |
1231 //debug("Finding path. Enterdir: %d, Trackdir: %d", enterdir, trackdir); |
1236 Trackdir trackdir = DiagdirToDiagTrackdir(enterdir); |
1232 |
1237 //debug("Finding path. Enterdir: %d, Trackdir: %d", enterdir, trackdir); |
1233 ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES); |
1238 |
1234 if (ftd.best_trackdir == INVALID_TRACKDIR) { |
1239 NPFFoundTargetData ftd = PerfNPFRouteToStationOrTile(tile - TileOffsByDiagDir(enterdir), trackdir, true, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES); |
1235 /* We are already at our target. Just do something |
1240 if (ftd.best_trackdir == INVALID_TRACKDIR) { |
1236 * @todo: maybe display error? |
1241 /* We are already at our target. Just do something |
1237 * @todo: go straight ahead if possible? */ |
1242 * @todo: maybe display error? |
1238 return_track(FindFirstBit2x64(trackdirs)); |
1243 * @todo: go straight ahead if possible? */ |
1239 } else { |
1244 return_track(FindFirstBit2x64(trackdirs)); |
1240 /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains |
1245 } else { |
1241 the direction we need to take to get there, if ftd.best_bird_dist is not 0, |
1246 /* If ftd.best_bird_dist is 0, we found our target and ftd.best_trackdir contains |
1242 we did not find our target, but ftd.best_trackdir contains the direction leading |
1247 * the direction we need to take to get there, if ftd.best_bird_dist is not 0, |
1243 to the tile closest to our target. */ |
1248 * we did not find our target, but ftd.best_trackdir contains the direction leading |
1244 return_track(ftd.best_trackdir); |
1249 * to the tile closest to our target. */ |
1245 } |
1250 return_track(ftd.best_trackdir); |
1246 } else { |
1251 } |
1247 DiagDirection dir; |
1252 } break; |
1248 |
1253 |
1249 if (IsTileType(desttile, MP_ROAD)) { |
1254 default: |
1250 if (GetRoadTileType(desttile) == ROAD_TILE_DEPOT) { |
1255 case VPF_OPF: { /* OPF */ |
1251 dir = GetRoadDepotDirection(desttile); |
1256 DiagDirection dir; |
1252 goto do_it; |
1257 |
1253 } |
1258 if (IsTileType(desttile, MP_ROAD)) { |
1254 } else if (IsTileType(desttile, MP_STATION)) { |
1259 if (IsRoadDepot(desttile)) { |
1255 /* For drive-through stops we can head for the actual station tile */ |
1260 dir = GetRoadDepotDirection(desttile); |
1256 if (IsStandardRoadStopTile(desttile)) { |
1261 goto do_it; |
1257 dir = GetRoadStopDir(desttile); |
1262 } |
|
1263 } else if (IsTileType(desttile, MP_STATION)) { |
|
1264 /* For drive-through stops we can head for the actual station tile */ |
|
1265 if (IsStandardRoadStopTile(desttile)) { |
|
1266 dir = GetRoadStopDir(desttile); |
1258 do_it:; |
1267 do_it:; |
1259 /* When we are heading for a depot or station, we just |
1268 /* When we are heading for a depot or station, we just |
1260 * pretend we are heading for the tile in front, we'll |
1269 * pretend we are heading for the tile in front, we'll |
1261 * see from there */ |
1270 * see from there */ |
1262 desttile += TileOffsByDiagDir(dir); |
1271 desttile += TileOffsByDiagDir(dir); |
1263 if (desttile == tile && trackdirs & _road_exit_dir_to_incoming_trackdirs[dir]) { |
1272 if (desttile == tile && trackdirs & _road_exit_dir_to_incoming_trackdirs[dir]) { |
1264 /* If we are already in front of the |
1273 /* If we are already in front of the |
1265 * station/depot and we can get in from here, |
1274 * station/depot and we can get in from here, |
1266 * we enter */ |
1275 * we enter */ |
1267 return_track(FindFirstBit2x64(trackdirs & _road_exit_dir_to_incoming_trackdirs[dir])); |
1276 return_track(FindFirstBit2x64(trackdirs & _road_exit_dir_to_incoming_trackdirs[dir])); |
|
1277 } |
1268 } |
1278 } |
1269 } |
1279 } |
1270 } |
1280 /* Do some pathfinding */ |
1271 /* Do some pathfinding */ |
1281 frd.dest = desttile; |
1272 frd.dest = desttile; |
1282 |
1273 |
1283 best_track = INVALID_TRACKDIR; |
1274 best_track = INVALID_TRACKDIR; |
1284 uint best_dist = UINT_MAX; |
1275 uint best_dist = (uint)-1; |
1285 uint best_maxlen = UINT_MAX; |
1276 uint best_maxlen = (uint)-1; |
1286 uint bitmask = (uint)trackdirs; |
1277 uint bitmask = (uint)trackdirs; |
1287 uint i; |
1278 uint i; |
1288 FOR_EACH_SET_BIT(i, bitmask) { |
1279 FOR_EACH_SET_BIT(i, bitmask) { |
1289 if (best_track == INVALID_TRACKDIR) best_track = (Trackdir)i; // in case we don't find the path, just pick a track |
1280 if (best_track == INVALID_TRACKDIR) best_track = (Trackdir)i; // in case we don't find the path, just pick a track |
1290 frd.maxtracklen = UINT_MAX; |
1281 frd.maxtracklen = (uint)-1; |
1291 frd.mindist = UINT_MAX; |
1282 frd.mindist = (uint)-1; |
1292 FollowTrack(tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, _road_pf_directions[i], EnumRoadTrackFindDist, NULL, &frd); |
1283 FollowTrack(tile, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, _road_pf_directions[i], EnumRoadTrackFindDist, NULL, &frd); |
1293 |
1284 |
1294 if (frd.mindist < best_dist || (frd.mindist == best_dist && frd.maxtracklen < best_maxlen)) { |
1285 if (frd.mindist < best_dist || (frd.mindist == best_dist && frd.maxtracklen < best_maxlen)) { |
1295 best_dist = frd.mindist; |
1286 best_dist = frd.mindist; |
1296 best_maxlen = frd.maxtracklen; |
1287 best_maxlen = frd.maxtracklen; |
1297 best_track = (Trackdir)i; |
1288 best_track = (Trackdir)i; |
1298 } |
1289 } |
1299 } |
1290 } |
1300 } break; |
1291 } |
1301 } |
1292 |
1302 |
1293 found_best_track:; |
1303 found_best_track:; |
1294 |
1304 |
1295 if (HasBit(signal, best_track)) return INVALID_TRACKDIR; |
1305 if (HasBit(red_signals, best_track)) return INVALID_TRACKDIR; |
1296 |
1306 |
1297 return best_track; |
1307 return best_track; |
1298 } |
1308 } |
1299 |
1309 |
1300 static uint RoadFindPathToStop(const Vehicle *v, TileIndex tile) |
1310 static uint RoadFindPathToStop(const Vehicle *v, TileIndex tile) |
1301 { |
1311 { |
1302 uint dist; |
1312 if (_patches.pathfinder_for_roadvehs == VPF_YAPF) { |
1303 if (_patches.yapf.road_use_yapf) { |
|
1304 /* use YAPF */ |
1313 /* use YAPF */ |
1305 dist = YapfRoadVehDistanceToTile(v, tile); |
1314 return YapfRoadVehDistanceToTile(v, tile); |
1306 } else { |
1315 } |
1307 /* use NPF */ |
1316 |
1308 NPFFindStationOrTileData fstd; |
1317 /* use NPF */ |
1309 Trackdir trackdir = GetVehicleTrackdir(v); |
1318 Trackdir trackdir = GetVehicleTrackdir(v); |
1310 assert(trackdir != INVALID_TRACKDIR); |
1319 assert(trackdir != INVALID_TRACKDIR); |
1311 |
1320 |
1312 fstd.dest_coords = tile; |
1321 NPFFindStationOrTileData fstd; |
1313 fstd.station_index = INVALID_STATION; // indicates that the destination is a tile, not a station |
1322 fstd.dest_coords = tile; |
1314 |
1323 fstd.station_index = INVALID_STATION; // indicates that the destination is a tile, not a station |
1315 dist = NPFRouteToStationOrTile(v->tile, trackdir, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES).best_path_dist; |
1324 |
1316 /* change units from NPF_TILE_LENGTH to # of tiles */ |
1325 uint dist = NPFRouteToStationOrTile(v->tile, trackdir, false, &fstd, TRANSPORT_ROAD, v->u.road.compatible_roadtypes, v->owner, INVALID_RAILTYPES).best_path_dist; |
1317 if (dist != UINT_MAX) |
1326 /* change units from NPF_TILE_LENGTH to # of tiles */ |
1318 dist = (dist + NPF_TILE_LENGTH - 1) / NPF_TILE_LENGTH; |
1327 if (dist != UINT_MAX) dist = (dist + NPF_TILE_LENGTH - 1) / NPF_TILE_LENGTH; |
1319 } |
1328 |
1320 return dist; |
1329 return dist; |
1321 } |
1330 } |
1322 |
1331 |
1323 enum { |
1332 enum { |
1324 RDE_NEXT_TILE = 0x80, |
1333 RDE_NEXT_TILE = 0x80, |