diff options
author | truelight <truelight@openttd.org> | 2004-08-22 15:56:56 +0000 |
---|---|---|
committer | truelight <truelight@openttd.org> | 2004-08-22 15:56:56 +0000 |
commit | 309ebe5f3f998a22e4f128728064227271ea0d98 (patch) | |
tree | 7a2fb0308e3d02fb0bfdd38b7a6d24286a7050ca /ai_pathfinder.c | |
parent | 86443602642a467ac3219a5da5d08ee0cc99de72 (diff) | |
download | openttd-309ebe5f3f998a22e4f128728064227271ea0d98.tar.xz |
(svn r111) -Fix: converted all linebreaks to UNIX-linebreak (\n)
Diffstat (limited to 'ai_pathfinder.c')
-rw-r--r-- | ai_pathfinder.c | 914 |
1 files changed, 457 insertions, 457 deletions
diff --git a/ai_pathfinder.c b/ai_pathfinder.c index 148ce1116..01ce2198e 100644 --- a/ai_pathfinder.c +++ b/ai_pathfinder.c @@ -1,457 +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;
-}
+#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; +} |