diff options
| -rw-r--r-- | ai_pathfinder.c | 4 | ||||
| -rw-r--r-- | aystar.c | 9 | ||||
| -rw-r--r-- | aystar.h | 4 | ||||
| -rw-r--r-- | npf.c | 68 | ||||
| -rw-r--r-- | npf.h | 20 | ||||
| -rw-r--r-- | settings.c | 4 | ||||
| -rw-r--r-- | train_cmd.c | 21 | ||||
| -rw-r--r-- | variables.h | 4 |
8 files changed, 96 insertions, 38 deletions
diff --git a/ai_pathfinder.c b/ai_pathfinder.c index 61a681eea..4fc273f58 100644 --- a/ai_pathfinder.c +++ b/ai_pathfinder.c @@ -116,7 +116,7 @@ AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFin for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) { for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) { start_node.node.tile = TILE_XY(x, y); - result->addstart(result, &start_node.node); + result->addstart(result, &start_node.node, 0); } } @@ -147,7 +147,7 @@ void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo if (!(IsTileType(TILE_XY(x, y), MP_CLEAR) || IsTileType(TILE_XY(x, y), MP_TREES))) continue; if (!TestCanBuildStationHere(TILE_XY(x, y), TEST_STATION_NO_DIR)) continue; start_node.node.tile = TILE_XY(x, y); - aystar->addstart(aystar, &start_node.node); + aystar->addstart(aystar, &start_node.node, 0); } } } @@ -56,7 +56,7 @@ static OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar) // Adds a node to the OpenList // It makes a copy of node, and puts the pointer of parent in the struct -static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g, int userdata) +static void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g) { // Add a new Node to the OpenList OpenListNode* new_node = malloc(sizeof(OpenListNode)); @@ -120,7 +120,7 @@ int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *pare aystar->OpenListQueue.push(&aystar->OpenListQueue, check, new_f); } else { // A new node, add him to the OpenList - AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g, 0); + AyStarMain_OpenList_Add(aystar, closedlist_parent, current, new_f, new_g); } return AYSTAR_DONE; @@ -248,13 +248,14 @@ int AyStarMain_Main(AyStar *aystar) { * if wanted. You should make sure that clear() is called before adding nodes * if the AyStar has been used before (though the normal main loop calls * clear() automatically when the algorithm finishes + * g is the cost for starting with this node. */ -void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node) { +void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g) { #ifdef AYSTAR_DEBUG printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n", TileX(start_node->tile), TileY(start_node->tile), start_node->direction); #endif - AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, 0, 0); + AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, g); } void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets) { @@ -97,7 +97,7 @@ typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current); typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current); // For internal use, see aystar.c -typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode* start_node); +typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode* start_node, uint g); typedef int AyStar_Main(AyStar *aystar); typedef int AyStar_Loop(AyStar *aystar); typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent); @@ -161,7 +161,7 @@ struct AyStar { }; -void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node); +void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node, uint g); int AyStarMain_Main(AyStar *aystar); int AyStarMain_Loop(AyStar *aystar); int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent); @@ -300,6 +300,7 @@ int32 NPFWaterPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { TileIndex tile = current->tile; int32 cost = 0; + /* Determine base length */ switch (GetTileType(tile)) { case MP_TUNNELBRIDGE: @@ -335,6 +336,7 @@ int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { TileIndex tile = current->tile; byte trackdir = current->direction; int32 cost = 0; + /* HACK: We create a OpenListNode manualy, so we can call EndNodeCheck */ OpenListNode new_node; /* Determine base length */ @@ -408,6 +410,13 @@ int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { //TODO, with realistic acceleration, also the amount of straight track between // curves should be taken into account, as this affects the speed limit. + /* Check for reverse in depot */ + if (IsTileDepotType(tile, TRANSPORT_RAIL) && !as->EndNodeCheck(as, &new_node)==AYSTAR_FOUND_END_NODE) + /* Penalise any depot tile that is not the last tile in the path. This + * _should_ penalise every occurence of reversing in a depot (and only + * that) */ + cost += _patches.npf_rail_depot_reverse_penalty; + /* Check for occupied track */ //TODO @@ -419,6 +428,9 @@ int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) { /* Will find any depot */ int32 NPFFindDepot(AyStar* as, OpenListNode *current) { TileIndex tile = current->path.node.tile; + + /* It's not worth caching the result with NPF_FLAG_IS_TARGET here as below, + * since checking the cache not that much faster than the actual check */ if (IsTileDepotType(tile, as->user_data[NPF_TYPE])) return AYSTAR_FOUND_END_NODE; else @@ -544,8 +556,11 @@ void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { else /* Train or road depot. Direction is stored the same for both, in map5 */ exitdir = GetDepotDirection(src_tile, type); - /* Let's see if were headed the right way */ - if (src_trackdir == _dir_to_diag_trackdir[_reverse_dir[exitdir]]) + /* Let's see if were headed the right way into the depot, and reverse + * otherwise (only for trains, since only with trains you can + * (sometimes) reach tiles after reversing that you couldn't reach + * without reversing. */ + if (src_trackdir == _dir_to_diag_trackdir[_reverse_dir[exitdir]] && type == TRANSPORT_RAIL) /* We are headed inwards. We can only reverse here, so we'll not * consider this direction, but jump ahead to the reverse direction. * It would be nicer to return one neighbour here (the reverse @@ -647,13 +662,14 @@ void NPFFollowTrack(AyStar* aystar, OpenListNode* current) { /* * Plan a route to the specified target (which is checked by target_proc), * from start1 and if not NULL, from start2 as well. The type of transport we - * are checking is in type. + * are checking is in type. reverse_penalty is applied to all routes that + * originate from the second start node. * When we are looking for one specific target (optionally multiple tiles), we * should use a good heuristic to perform aystar search. When we search for * multiple targets that are spread around, we should perform a breadth first * search by specifiying CalcZero as our heuristic. */ -NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner) { +NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFFindStationOrTileData* target, AyStar_EndNodeCheck target_proc, AyStar_CalculateH heuristic_proc, TransportType type, Owner owner, uint reverse_penalty) { int r; NPFFoundTargetData result; @@ -674,12 +690,12 @@ NPFFoundTargetData NPFRouteInternal(AyStarNode* start1, AyStarNode* start2, NPFF /* Initialize Start Node(s) */ start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff; start1->user_data[NPF_NODE_FLAGS] = 0; - _npf_aystar.addstart(&_npf_aystar, start1); + _npf_aystar.addstart(&_npf_aystar, start1, 0); if (start2) { start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff; start2->user_data[NPF_NODE_FLAGS] = 0; NPFSetFlag(start2, NPF_FLAG_REVERSE, true); - _npf_aystar.addstart(&_npf_aystar, start2); + _npf_aystar.addstart(&_npf_aystar, start2, reverse_penalty); } /* Initialize result */ @@ -717,38 +733,40 @@ NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1 start1.tile = tile1; start2.tile = tile2; + /* We set this in case the target is also the start tile, we will just + * return a not found then */ + start1.user_data[NPF_TRACKDIR_CHOICE] = 0xff; start1.direction = trackdir1; start2.direction = trackdir2; + start2.user_data[NPF_TRACKDIR_CHOICE] = 0xff; - return NPFRouteInternal(&start1, &start2, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner); + return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner, 0); } NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner) { - AyStarNode start; - - assert(tile != 0); - - start.tile = tile; - start.direction = trackdir; - /* We set this in case the target is also the start tile, we will just - * return a not found then */ - start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; - - return NPFRouteInternal(&start, NULL, target, NPFFindStationOrTile, NPFCalcStationOrTileHeuristic, type, owner); + return NPFRouteToStationOrTileTwoWay(tile, trackdir, INVALID_TILE, 0, target, type, owner); } -NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner) { - AyStarNode start; +NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, TransportType type, Owner owner, uint reverse_penalty) { + AyStarNode start1; + AyStarNode start2; - start.tile = tile; - start.direction = trackdir; + start1.tile = tile1; + start2.tile = tile2; /* We set this in case the target is also the start tile, we will just * return a not found then */ - start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; + start1.user_data[NPF_TRACKDIR_CHOICE] = 0xff; + start1.direction = trackdir1; + start2.direction = trackdir2; + start2.user_data[NPF_TRACKDIR_CHOICE] = 0xff; /* perform a breadth first search. Target is NULL, * since we are just looking for any depot...*/ - return NPFRouteInternal(&start, NULL, NULL, NPFFindDepot, NPFCalcZero, type, owner); + return NPFRouteInternal(&start1, (IsValidTile(tile2) ? &start2 : NULL), NULL, NPFFindDepot, NPFCalcZero, type, owner, reverse_penalty); +} + +NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner) { + return NPFRouteToDepotBreadthFirstTwoWay(tile, trackdir, INVALID_TILE, 0, type, owner, 0); } NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner) { @@ -826,7 +844,7 @@ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, Tran * return a not found then */ start.user_data[NPF_TRACKDIR_CHOICE] = 0xff; start.user_data[NPF_NODE_FLAGS] = 0; - _npf_aystar.addstart(&_npf_aystar, &start); + _npf_aystar.addstart(&_npf_aystar, &start, 0); /* Initialize result */ result.best_bird_dist = (uint)-1; @@ -14,6 +14,17 @@ enum { NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1 }; +enum { + /** This penalty is the equivalent of "inifite", which means that paths that + * get this penalty will be chosen, but only if there is no other route + * without it. Be careful with not applying this penalty to often, or the + * total path cost might overflow.. + * For now, this is just a Very Big Penalty, we might actually implement + * this in a nicer way :-) + */ + NPF_INFINITE_PENALTY = 1000 * NPF_TILE_LENGTH +}; + typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */ TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */ int station_index; /* station index we're heading for, or -1 when we're heading for a tile */ @@ -62,8 +73,15 @@ NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1 /* Will search a route to the closest depot. */ /* Search using breadth first. Good for little track choice and inaccurate - * heuristic, such as railway/road */ + * heuristic, such as railway/road.*/ NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner); +/* Same as above but with two start nodes, the second being the reverse. Call + * NPFGetBit(result.node, NPF_FLAG_REVERSE) to see from which node the path + * orginated. All pathfs from the second node will have the given + * reverse_penalty applied (NPF_TILE_LENGTH is the equivalent of one full + * tile). + */ +NPFFoundTargetData NPFRouteToDepotBreadthFirstTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, TransportType type, Owner owner, uint reverse_penalty); /* Search by trying each depot in order of Manhattan Distance. Good for lots * of choices and accurate heuristics, such as water. */ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner); diff --git a/settings.c b/settings.c index 2b6d52787..68411f2ab 100644 --- a/settings.c +++ b/settings.c @@ -966,6 +966,10 @@ const SettingDesc patch_settings[] = { * sure that it has a minimal impact on the pathfinding, only when two * paths have equal length it will make a difference */ {"npf_rail_curve_penalty", SDT_UINT32, (void*)(1), &_patches.npf_rail_curve_penalty, NULL}, + /* Ths penalty is applied when a vehicle reverses inside a depot (doesn't + * apply to ships, as they can just come out the other end). XXX: Is this a + * good value? */ + {"npf_rail_depot_reverse_penalty", SDT_UINT32, (void*)(NPF_TILE_LENGTH * 50), &_patches.npf_rail_depot_reverse_penalty, NULL}, {"npf_buoy_penalty", SDT_UINT32, (void*)(2 * NPF_TILE_LENGTH), &_patches.npf_buoy_penalty, NULL}, /* This penalty is applied when a ship makes a turn. It is bigger than the * rail curve penalty, since ships (realisticly) have more trouble with diff --git a/train_cmd.c b/train_cmd.c index 80400faf9..dc2ec32c0 100644 --- a/train_cmd.c +++ b/train_cmd.c @@ -1329,6 +1329,11 @@ typedef struct TrainFindDepotData { uint best_length; uint tile; byte owner; + /** + * true if reversing is necesarry for the train to get to this depot This + * value is unused when new depot finding and NPF are both disabled + */ + bool reverse; } TrainFindDepotData; static bool TrainFindDepotEnumProc(uint tile, TrainFindDepotData *tfdd, int track, uint length, byte *state) @@ -1365,6 +1370,7 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v) tfdd.owner = v->owner; tfdd.best_length = (uint)-1; + tfdd.reverse = false; if (IsTileDepotType(tile, TRANSPORT_RAIL)){ tfdd.tile = tile; @@ -1376,17 +1382,22 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v) if (_patches.new_pathfinding_all) { NPFFoundTargetData ftd; + Vehicle* last = GetLastVehicleInChain(v); byte trackdir = GetVehicleTrackdir(v); + byte trackdir_rev = REVERSE_TRACKDIR(GetVehicleTrackdir(last)); + assert (trackdir != 0xFF); - ftd = NPFRouteToDepotBreadthFirst(v->tile, trackdir, TRANSPORT_RAIL, v->owner); + ftd = NPFRouteToDepotBreadthFirstTwoWay(v->tile, trackdir, last->tile, trackdir_rev, TRANSPORT_RAIL, v->owner, NPF_INFINITE_PENALTY); if (ftd.best_bird_dist == 0) { /* Found target */ tfdd.tile = ftd.node.tile; - tfdd.best_length = ftd.best_path_dist / NPF_TILE_LENGTH; /* Our caller expects a number of tiles, so we just approximate that * number by this. It might not be completely what we want, but it will * work for now :-) We can possibly change this when the old pathfinder * is removed. */ + tfdd.best_length = ftd.best_path_dist / NPF_TILE_LENGTH; + if (NPFGetFlag(&ftd.node, NPF_FLAG_REVERSE)) + tfdd.reverse = true; } } else if (!_patches.new_depot_finding) { // search in all directions @@ -1398,6 +1409,7 @@ static TrainFindDepotData FindClosestTrainDepot(Vehicle *v) if (!(v->direction & 1) && v->u.rail.track != _state_dir_table[i]) { i = (i - 1) & 3; } NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL); 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; } @@ -1447,6 +1459,9 @@ int32 CmdTrainGotoDepot(int x, int y, uint32 flags, uint32 p1, uint32 p2) v->current_order.flags = OF_NON_STOP | OF_FULL_LOAD; v->current_order.station = GetDepotByTile(tfdd.tile)->index; InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR); + /* If there is no depot in front, reverse automatically */ + if (tfdd.reverse) + DoCommandByTile(v->tile, v->index, 0, DC_EXEC, CMD_REVERSE_TRAIN_DIRECTION); } return 0; @@ -1868,7 +1883,7 @@ static bool CheckReverseTrain(Vehicle *v) NPFFillWithOrderData(&fstd, v); trackdir = GetVehicleTrackdir(v); - trackdir_rev = REVERSE_TRACKDIR(GetVehicleTrackdir(v)); + trackdir_rev = REVERSE_TRACKDIR(GetVehicleTrackdir(last)); assert(trackdir != 0xff); assert(trackdir_rev != 0xff); diff --git a/variables.h b/variables.h index 71939cfd8..c55ce6a7b 100644 --- a/variables.h +++ b/variables.h @@ -212,6 +212,7 @@ typedef struct Patches { uint32 npf_rail_station_penalty; /* The penalty for station tiles */ uint32 npf_rail_slope_penalty; /* The penalty for sloping upwards */ uint32 npf_rail_curve_penalty; /* The penalty for curves */ + uint32 npf_rail_depot_reverse_penalty; /* The penalty for reversing in depots */ uint32 npf_buoy_penalty; /* The penalty for going over (through) a buoy */ uint32 npf_water_curve_penalty; /* The penalty for curves */ @@ -452,7 +453,8 @@ VARDEF byte _vehicle_design_names; /* tunnelbridge */ #define MAX_BRIDGES 13 -/* For new pathfinding. Define here so it is globally available */ +/* For new pathfinding. Define here so it is globally available without having + * to include npf.h */ #define NPF_TILE_LENGTH 100 /* Autoreplace vehicle stuff*/ |