From 788ace088d8b3ba2afd77a8b21b532abc40d9eba Mon Sep 17 00:00:00 2001 From: truelight Date: Fri, 20 Aug 2004 09:32:32 +0000 Subject: (svn r85) -Add: initial commit of new AI (enable in Patch menu) -Add: generalised A* Algorithm -Add: generalised queues (Fifo, Stack, InsSort, BinaryHeap) --- ai_pathfinder.c | 457 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 457 insertions(+) create mode 100644 ai_pathfinder.c (limited to 'ai_pathfinder.c') diff --git a/ai_pathfinder.c b/ai_pathfinder.c new file mode 100644 index 000000000..148ce1116 --- /dev/null +++ b/ai_pathfinder.c @@ -0,0 +1,457 @@ +#include "stdafx.h" +#include "ttd.h" +#include "command.h" +#include "ai.h" + +#define TEST_STATION_NO_DIR 0xFF + +// Tests if a station can be build on the given spot +// TODO: make it train compatible +bool TestCanBuildStationHere(uint tile, byte dir) { + Player *p = DEREF_PLAYER(_current_player); + if (dir == TEST_STATION_NO_DIR) { + // TODO: currently we only allow spots that can be access from al 4 directions... + // should be fixed!!! + for (dir=0;dir<4;dir++) { + int res = AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST); + if (res != CMD_ERROR) + return true; + } + return false; + } else { + int res = AiNew_Build_Station(p, p->ainew.tbt, tile, 1, 1, dir, DC_QUERY_COST); + if (res == CMD_ERROR) + return false; + } + return true; +} + +// Checks if a tile 'a' is between the tiles 'b' and 'c' +#define TILES_BETWEEN(a,b,c) (GET_TILE_X(a) >= GET_TILE_X(b) && GET_TILE_X(a) <= GET_TILE_X(c) && GET_TILE_Y(a) >= GET_TILE_Y(b) && GET_TILE_Y(a) <= GET_TILE_Y(c)) + +// Check if the current tile is in our end-area +int32 AyStar_AiPathFinder_EndNodeCheck(AyStar *aystar, OpenListNode *current) { + Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; + // It is not allowed to have a station on the end of a bridge or tunnel ;) + if (current->path.node.user_data[0] != 0) return AYSTAR_DONE; + if (TILES_BETWEEN(current->path.node.tile, PathFinderInfo->end_tile_tl, PathFinderInfo->end_tile_br)) + if (IS_TILETYPE(current->path.node.tile, MP_CLEAR) || IS_TILETYPE(current->path.node.tile, MP_TREES)) + if (current->path.parent == NULL || TestCanBuildStationHere(current->path.node.tile,AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile))) + return AYSTAR_FOUND_END_NODE; + + return AYSTAR_DONE; +} + +// Calculates the hash +// Currently it is a 10 bit hash, so the hash array has a max depth of 6 bits (so 64) +uint AiPathFinder_Hash(uint key1, uint key2) { + return (GET_TILE_X(key1) & 0x1F) + ((GET_TILE_Y(key1) & 0x1F) << 5); +} + +// Clear the memory of all the things +void AyStar_AiPathFinder_Free(AyStar *aystar) { + AyStarMain_Free(aystar); + free(aystar); +} + +static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent); +static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent); +static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current); +static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current); + +// This creates the AiPathFinder +AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFinderInfo) { + PathNode start_node; + uint x,y; + // Create AyStar + AyStar *result = malloc(sizeof(AyStar)); + init_AyStar(result, AiPathFinder_Hash, 1 << 10); + // Set the function pointers + result->CalculateG = AyStar_AiPathFinder_CalculateG; + result->CalculateH = AyStar_AiPathFinder_CalculateH; + result->EndNodeCheck = AyStar_AiPathFinder_EndNodeCheck; + result->FoundEndNode = AyStar_AiPathFinder_FoundEndNode; + result->GetNeighbours = AyStar_AiPathFinder_GetNeighbours; + + result->free = AyStar_AiPathFinder_Free; + + // Set some information + result->loops_per_tick = AI_PATHFINDER_LOOPS_PER_TICK; + result->max_path_cost = 0; + result->max_search_nodes = AI_PATHFINDER_MAX_SEARCH_NODES; + + // Set the user_data to the PathFinderInfo + result->user_target = PathFinderInfo; + + // Set the start node + start_node.parent = NULL; + start_node.node.direction = 0; + start_node.node.user_data[0] = 0; + + // Now we add all the starting tiles + for (x=GET_TILE_X(PathFinderInfo->start_tile_tl);x<=GET_TILE_X(PathFinderInfo->start_tile_br);x++) { + for (y=GET_TILE_Y(PathFinderInfo->start_tile_tl);y<=GET_TILE_Y(PathFinderInfo->start_tile_br);y++) { + start_node.node.tile = TILE_XY(x,y); + result->addstart(result, &start_node.node); + } + } + + return result; +} + +// To reuse AyStar we sometimes have to clean all the memory +void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo) { + PathNode start_node; + uint x,y; + + aystar->clear(aystar); + + // Set the user_data to the PathFinderInfo + aystar->user_target = PathFinderInfo; + + // Set the start node + start_node.parent = NULL; + start_node.node.direction = 0; + start_node.node.user_data[0] = 0; + start_node.node.tile = PathFinderInfo->start_tile_tl; + + // Now we add all the starting tiles + for (x=GET_TILE_X(PathFinderInfo->start_tile_tl);x<=GET_TILE_X(PathFinderInfo->start_tile_br);x++) { + for (y=GET_TILE_Y(PathFinderInfo->start_tile_tl);y<=GET_TILE_Y(PathFinderInfo->start_tile_br);y++) { + if (!(IS_TILETYPE(TILE_XY(x,y), MP_CLEAR) || IS_TILETYPE(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); + } + } +} + +// The h-value, simple calculation +static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent) { + Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; + int r, r2; + if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION) { + // The station is pointing to a direction, add a tile towards that direction, so the H-value is more accurate + r = GetTileDist(current->tile, PathFinderInfo->end_tile_tl + _tiles_around[PathFinderInfo->end_direction]); + r2 = GetTileDist(current->tile, PathFinderInfo->end_tile_br + _tiles_around[PathFinderInfo->end_direction]); + } else { + // No direction, so just get the fastest route to the station + r = GetTileDist(current->tile, PathFinderInfo->end_tile_tl); + r2 = GetTileDist(current->tile, PathFinderInfo->end_tile_br); + } + // See if the bottomright is faster then the topleft.. + if (r2 < r) r = r2; + return r * AI_PATHFINDER_H_MULTIPLER; +} + +// We found the end.. let's get the route back and put it in an array +static void AyStar_AiPathFinder_FoundEndNode(AyStar *aystar, OpenListNode *current) { + Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; + int i = 0; + PathNode *parent = ¤t->path; + + do { + PathFinderInfo->route_extra[i] = parent->node.user_data[0]; + PathFinderInfo->route[i++] = parent->node.tile; + if (i > lengthof(PathFinderInfo->route)) { + // We ran out of space for the PathFinder + DEBUG(ai,0)("[AiPathFinder] Ran out of spacein the route[] array!!!"); + PathFinderInfo->route_length = -1; // -1 indicates out of space + return; + } + parent = parent->parent; + } while (parent != NULL); + PathFinderInfo->route_length = i; + DEBUG(ai,1)("[Ai-PathFinding] Found route of %d nodes long in %d nodes of searching",i,Hash_Size(&aystar->ClosedListHash)); +} + +// What tiles are around us. +static void AyStar_AiPathFinder_GetNeighbours(AyStar *aystar, OpenListNode *current) { + int i, r, dir; + Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; + + aystar->num_neighbours = 0; + + // Go through all surrounding tiles and check if they are within the limits + for (i=0;i<4;i++) { + if (GET_TILE_X(_tiles_around[i] + current->path.node.tile) > 1 && GET_TILE_X(_tiles_around[i] + current->path.node.tile) < TILE_X_MAX - 1 && + GET_TILE_Y(_tiles_around[i] + current->path.node.tile) > 1 && GET_TILE_Y(_tiles_around[i] + current->path.node.tile) < TILE_Y_MAX - 1) { + // We also directly test if the current tile can connect to this tile.. + // We do this simply by just building the tile! + + // If the next step is a bridge, we have to enter it the right way + if (!PathFinderInfo->rail_or_road && AI_PATHFINDER_IS_ROAD(current->path.node.tile + _tiles_around[i])) { + if (IS_TILETYPE(current->path.node.tile + _tiles_around[i], MP_TUNNELBRIDGE)) { + // An existing bridge... let's test the direction ;) + if ((_map5[current->path.node.tile + _tiles_around[i]] & 1) != (i & 1)) continue; + // This problem only is valid for tunnels: + // When the last tile was not yet a tunnel, check if we enter from the right side.. + if (!IS_TILETYPE(current->path.node.tile, MP_TUNNELBRIDGE) && (_map5[current->path.node.tile + _tiles_around[i]] & 0x80) == 0) { + if ((i^2) != (_map5[current->path.node.tile + _tiles_around[i]] & 3)) continue; + } + } + } + // But also if we are on a bridge, we can only move a certain direction + if (!PathFinderInfo->rail_or_road && AI_PATHFINDER_IS_ROAD(current->path.node.tile)) { + if (IS_TILETYPE(current->path.node.tile, MP_TUNNELBRIDGE)) { + // An existing bridge/tunnel... let's test the direction ;) + if ((_map5[current->path.node.tile] & 1) != (i & 1)) continue; + } + } + + if ((AI_PATHFINDER_FLAG_BRIDGE & current->path.node.user_data[0]) != 0 || + (AI_PATHFINDER_FLAG_TUNNEL & current->path.node.user_data[0]) != 0) { + // We are a bridge/tunnel, how cool!! + // This means we can only point forward.. get the direction from the user_data + if (i != (current->path.node.user_data[0] >> 8)) continue; + } + dir = 0; + + // First, check if we have a parent + if (current->path.parent == NULL && current->path.node.user_data[0] == 0) { + // If not, this means we are at the starting station + if (PathFinderInfo->start_direction != AI_PATHFINDER_NO_DIRECTION) { + // We do need a direction? + if (AiNew_GetDirection(current->path.node.tile, current->path.node.tile + _tiles_around[i]) != PathFinderInfo->start_direction) + // We are not pointing the right way, invalid tile + continue; + } + } else if (current->path.node.user_data[0] == 0) { + if (PathFinderInfo->rail_or_road) { + // Rail check + dir = AiNew_GetRailDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + _tiles_around[i]); + r = DoCommandByTile(current->path.node.tile, 0, dir, DC_AUTO | DC_NO_WATER, CMD_BUILD_SINGLE_RAIL); + if (r == CMD_ERROR) continue; +#ifdef AI_PATHFINDER_NO_90DEGREES_TURN + if (current->path.parent->parent != NULL) { + // Check if we don't make a 90degree curve + int dir1 = AiNew_GetRailDirection(current->path.parent->parent->node.tile, current->path.parent->node.tile, current->path.node.tile); + if (_illegal_curves[dir1] == dir || _illegal_curves[dir] == dir1) { + continue; + } + } +#endif + } else { + // Road check + dir = AiNew_GetRoadDirection(current->path.parent->node.tile, current->path.node.tile, current->path.node.tile + _tiles_around[i]); + if (AI_PATHFINDER_IS_ROAD(current->path.node.tile)) { + if (IS_TILETYPE(current->path.node.tile, MP_TUNNELBRIDGE)) { + // We have a bridge, how nicely! We should mark it... + dir = 0; + } else { + // It already has road.. check if we miss any bits! + if ((_map5[current->path.node.tile] & dir) != dir) { + // We do miss some pieces :( + dir &= ~_map5[current->path.node.tile]; + } else { + dir = 0; + } + } + } + // Only destruct things if it is MP_CLEAR of MP_TREES + if (dir != 0) { + r = DoCommandByTile(current->path.node.tile, dir, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD); + if (r == CMD_ERROR) continue; + } + } + + } + + // The tile can be connected + aystar->neighbours[aystar->num_neighbours].tile = _tiles_around[i] + current->path.node.tile; + aystar->neighbours[aystar->num_neighbours].user_data[0] = 0; + aystar->neighbours[aystar->num_neighbours++].direction = 0; + } + } + + // Next step, check for bridges and tunnels + if (current->path.parent != NULL && current->path.node.user_data[0] == 0) { + + TileInfo ti; + // First we get the dir from this tile and his parent + int dir = AiNew_GetDirection(current->path.parent->node.tile, current->path.node.tile); + // It means we can only walk with the track, so the bridge has to be in the same direction + TileIndex tile = current->path.node.tile; + TileIndex new_tile = tile; + + FindLandscapeHeightByTile(&ti, tile); + + // Bridges can only be build on land that is not flat + // And if there is a road or rail blocking + if (ti.tileh != 0 || + (PathFinderInfo->rail_or_road && IS_TILETYPE(tile + _tiles_around[dir], MP_STREET)) || + (!PathFinderInfo->rail_or_road && IS_TILETYPE(tile + _tiles_around[dir], MP_RAILWAY))) { + + for (;;) { + new_tile += _tiles_around[dir]; + + // Precheck, is the length allowed? + if (!CheckBridge_Stuff(0,GetBridgeLength(tile, new_tile))) break; + + // Check if we hit the station-tile.. we don't like that! + if (TILES_BETWEEN(new_tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) break; + + // Try building the bridge.. + r = DoCommandByTile(tile, new_tile, (0<<8) + (MAX_BRIDGES / 2), DC_AUTO, CMD_BUILD_BRIDGE); + if (r == CMD_ERROR) continue; + // We can build a bridge here.. add him to the neighbours + aystar->neighbours[aystar->num_neighbours].tile = new_tile; + aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_BRIDGE + (dir << 8); + aystar->neighbours[aystar->num_neighbours++].direction = 0; + // We can only have 12 neighbours, and we need 1 left for tunnels + if (aystar->num_neighbours == 11) break; + } + } + + // Next, check for tunnels! + // Tunnels can only be build with tileh of 3, 6, 9 or 12, depending on the direction + // For now, we check both sides for this tile.. terraforming gives fuzzy result + if ((dir == 0 && ti.tileh == 12) || + (dir == 1 && ti.tileh == 6) || + (dir == 2 && ti.tileh == 3) || + (dir == 3 && ti.tileh == 9)) { + // Now simply check if a tunnel can be build + r = DoCommandByTile(tile, (PathFinderInfo->rail_or_road?0:0x200), 0, DC_AUTO, CMD_BUILD_TUNNEL); + FindLandscapeHeightByTile(&ti, _build_tunnel_endtile); + if (r != CMD_ERROR && (ti.tileh == 3 || ti.tileh == 6 || ti.tileh == 9 || ti.tileh == 12)) { + aystar->neighbours[aystar->num_neighbours].tile = _build_tunnel_endtile; + aystar->neighbours[aystar->num_neighbours].user_data[0] = AI_PATHFINDER_FLAG_TUNNEL + (dir << 8); + aystar->neighbours[aystar->num_neighbours++].direction = 0; + } + } + } +} + +extern uint GetRailFoundation(uint tileh, uint bits); +extern uint GetRoadFoundation(uint tileh, uint bits); +extern uint GetBridgeFoundation(uint tileh, byte direction); +enum { + BRIDGE_NO_FOUNDATION = 1 << 0 | 1 << 3 | 1 << 6 | 1 << 9 | 1 << 12, +}; + +// The most important function: it calculates the g-value +static int32 AyStar_AiPathFinder_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent) { + Ai_PathFinderInfo *PathFinderInfo = (Ai_PathFinderInfo*)aystar->user_target; + int r, res = 0; + TileInfo ti, parent_ti; + + // Gather some information about the tile.. + FindLandscapeHeightByTile(&ti, current->tile); + FindLandscapeHeightByTile(&parent_ti, parent->path.node.tile); + + // Check if we hit the end-tile + if (TILES_BETWEEN(current->tile,PathFinderInfo->end_tile_tl,PathFinderInfo->end_tile_br)) { + // We are at the end-tile, check if we had a direction or something... + if (PathFinderInfo->end_direction != AI_PATHFINDER_NO_DIRECTION && AiNew_GetDirection(current->tile, parent->path.node.tile) != PathFinderInfo->end_direction) + // We are not pointing the right way, invalid tile + return AYSTAR_INVALID_NODE; + // If it was valid, drop out.. we don't build on the endtile + return 0; + } + + // Give everything a small penalty + res += AI_PATHFINDER_PENALTY; + + if (!PathFinderInfo->rail_or_road) { + // Road has the lovely advantage it can use other road... check if + // the current tile is road, and if so, give a good bonus + if (AI_PATHFINDER_IS_ROAD(current->tile)) { + res -= AI_PATHFINDER_ROAD_ALREADY_EXISTS_BONUS; + } + } + + // We should give a penalty when the tile is going up or down.. this is one way to do so! + // Too bad we have to count it from the parent.. but that is not so bad + if (parent_ti.tileh != 0 && parent->path.parent != NULL) { + // Skip if the tile was from a bridge or tunnel + if (parent->path.node.user_data[0] == 0 && current->user_data[0] == 0) { + if (PathFinderInfo->rail_or_road) { + r = GetRailFoundation(parent_ti.tileh, 1 << AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile)); + // Maybe is BRIDGE_NO_FOUNDATION a bit strange here, but it contains just the right information.. + if (r >= 15 || (r == 0 && (BRIDGE_NO_FOUNDATION & (1 << ti.tileh)))) { + res += AI_PATHFINDER_TILE_GOES_UP_PENALTY; + } + } else { + if (!(AI_PATHFINDER_IS_ROAD(parent->path.node.tile) && IS_TILETYPE(parent->path.node.tile, MP_TUNNELBRIDGE))) { + r = GetRoadFoundation(parent_ti.tileh, AiNew_GetRoadDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile)); + if (r >= 15 || r == 0) + res += AI_PATHFINDER_TILE_GOES_UP_PENALTY; + } + } + } + } + + // Are we part of a tunnel? + if ((AI_PATHFINDER_FLAG_TUNNEL & current->user_data[0]) != 0) { + // Tunnels are very expensive when build on long routes.. + // Ironicly, we are using BridgeCode here ;) + r = AI_PATHFINDER_TUNNEL_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile); + res += r + (r >> 8); + } + + // Are we part of a bridge? + if ((AI_PATHFINDER_FLAG_BRIDGE & current->user_data[0]) != 0) { + // That means for every length a penalty + res += AI_PATHFINDER_BRIDGE_PENALTY * GetBridgeLength(current->tile, parent->path.node.tile); + // Check if we are going up or down, first for the starting point + // In user_data[0] is at the 8th bit the direction + if (!(BRIDGE_NO_FOUNDATION & (1 << parent_ti.tileh))) { + if (GetBridgeFoundation(parent_ti.tileh, (current->user_data[0] >> 8) & 1) < 15) + res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY; + } + // Second for the end point + if (!(BRIDGE_NO_FOUNDATION & (1 << ti.tileh))) { + if (GetBridgeFoundation(ti.tileh, (current->user_data[0] >> 8) & 1) < 15) + res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY; + } + if (parent_ti.tileh == 0) + res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY; + if (ti.tileh == 0) + res += AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY; + } + + // To prevent the AI from taking the fastest way in tiles, but not the fastest way + // in speed, we have to give a good penalty to direction changing + // This way, we get almost the fastest way in tiles, and a very good speed on the track + if (!PathFinderInfo->rail_or_road) { + if (parent->path.parent != NULL && + AiNew_GetDirection(current->tile, parent->path.node.tile) != AiNew_GetDirection(parent->path.node.tile, parent->path.parent->node.tile)) { + // When road exists, we don't like turning, but its free, so don't be to piggy about it + if (AI_PATHFINDER_IS_ROAD(parent->path.node.tile)) + res += AI_PATHFINDER_DIRECTION_CHANGE_ON_EXISTING_ROAD_PENALTY; + else + res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY; + } + } else { + // For rail we have 1 exeption: diagonal rail.. + // So we fetch 2 raildirection. That of the current one, and of the one before that + if (parent->path.parent != NULL && parent->path.parent->parent != NULL) { + int dir1 = AiNew_GetRailDirection(parent->path.parent->node.tile, parent->path.node.tile, current->tile); + int dir2 = AiNew_GetRailDirection(parent->path.parent->parent->node.tile, parent->path.parent->node.tile, parent->path.node.tile); + // First, see if we are on diagonal path, that is better then straight path + if (dir1 > 1) { res -= AI_PATHFINDER_DIAGONAL_BONUS; } + + // First see if they are different + if (dir1 != dir2) { + // dir 2 and 3 are 1 diagonal track, and 4 and 5. + if (!(((dir1 == 2 || dir1 == 3) && (dir2 == 2 || dir2 == 3)) || ((dir1 == 4 || dir1 == 5) && (dir2 == 4 || dir2 == 5)))) { + // It is not, so we changed of direction + res += AI_PATHFINDER_DIRECTION_CHANGE_PENALTY; + } + if (parent->path.parent->parent->parent != NULL) { + int dir3 = AiNew_GetRailDirection(parent->path.parent->parent->parent->node.tile, parent->path.parent->parent->node.tile, parent->path.parent->node.tile); + // Check if we changed 3 tiles of direction in 3 tiles.. bad!!! + if ((dir1 == 0 || dir1 == 1) && dir2 > 1 && (dir3 == 0 || dir3 == 1)) { + res += AI_PATHFINDER_CURVE_PENALTY; + } + } + } + } + } + + // Res should never be below zero.. if so, make it zero! + if (res < 0) { res = 0; } + + // Return our value + return res; +} -- cgit v1.2.3-54-g00ecf