# HG changeset patch # User rubidium # Date 1213707992 0 # Node ID 203b90795f805865d4ee3b8cdecc6f3bf58d1516 # Parent 4dd4f4327c3a5d9ed41e14d430e3fb5b6cb95808 (svn r13547) [NoAI] -Add: functions to determine whether one can build connected roads given a tile, entry and exit 'point' or an abstract representation of a tile with entry and exit 'point'. Works on all valid slopes and it is aware of the build_on_slopes configuration setting. diff -r 4dd4f4327c3a -r 203b90795f80 src/ai/api/ai_road.cpp --- a/src/ai/api/ai_road.cpp Tue Jun 17 11:46:09 2008 +0000 +++ b/src/ai/api/ai_road.cpp Tue Jun 17 13:06:32 2008 +0000 @@ -4,11 +4,14 @@ #include "ai_road.hpp" #include "ai_map.hpp" +#include "ai_list.hpp" #include "../../openttd.h" #include "../../road_map.h" #include "../../station_map.h" #include "../../command_type.h" #include "../../player_func.h" +#include "../../settings_type.h" +#include "../../squirrel_helper_type.hpp" /* static */ bool AIRoad::IsRoadTile(TileIndex tile) { @@ -80,6 +83,301 @@ return HasBit(r1, dir_1) && HasBit(r2, dir_2); } +/* Helper functions for AIRoad::CanBuildConnectedRoadParts(). */ + +/** + * Check whether the given existing bits the start and end part can be build. + * As the function assumes the bits being build on a slope that does not + * allow level foundations all of the existing parts will always be in + * a straight line. This also needs to hold for the start and end parts, + * otherwise it is for sure not valid. Finally a check will be done to + * determine whether the existing road parts match the to-be-build parts. + * As they can only be placed in one direction, just checking the start + * part with the first existing part is enough. + * @param existing The existing road parts. + * @param start The part that should be build first. + * @param end The part that will be build second. + * @return True if and only if the road bits can be build. + */ +static bool CheckAutoExpandedRoadBits(const Array *existing, int32 start, int32 end) +{ + return (start + end == 0) && (existing->size == 0 || existing->array[0] == start || existing->array[0] == end); +} + +/** + * Lookup function for building road parts when building on slopes is disabled. + * @param slope The slope of the tile to examine. + * @param existing The existing road parts. + * @param start The part that should be build first. + * @param end The part that will be build second. + * @return 0 when the build parts do not connect, 1 when they do connect once + * they are build or 2 when building the first part automatically + * builds the second part. + */ +static int32 LookupWithoutBuildOnSlopes(::Slope slope, const Array *existing, int32 start, int32 end) +{ + switch (slope) { + /* Flat slopes can always be build. */ + case SLOPE_FLAT: + return 1; + + /* Only 4 of the slopes can be build upon. Testing the existing bits is + * necessary because these bits can be something else when the settings + * in the game have been changed. + */ + case SLOPE_NE: case SLOPE_SW: + return (CheckAutoExpandedRoadBits(existing, start, end) && (start == 1 || end == 1)) ? (existing->size == 0 ? 2 : 1) : 0; + case SLOPE_SE: case SLOPE_NW: + return (CheckAutoExpandedRoadBits(existing, start, end) && (start != 1 && end != 1)) ? (existing->size == 0 ? 2 : 1) : 0; + + /* Any other tile cannot be built on. */ + default: + return 0; + } +} + +/** + * Rotate a neighbour bit a single time clockwise. + * @param neighbour The neighbour. + * @return The rotate neighbour data. + */ +static int32 RotateNeighbour(int32 neighbour) +{ + switch (neighbour) { + case -2: return -1; + case -1: return 2; + case 1: return -2; + case 2: return 1; + default: NOT_REACHED(); + } +} + +/** + * Convert a neighbour to a road bit representation for easy internal use. + * @param neighbour The neighbour. + * @return The bits representing the direction. + */ +static RoadBits NeighbourToRoadBits(int32 neighbour) +{ + switch (neighbour) { + case -2: return ROAD_NW; + case -1: return ROAD_NE; + case 2: return ROAD_SE; + case 1: return ROAD_SW; + default: NOT_REACHED(); + } +} + +/** + * Lookup function for building road parts when building on slopes is enabled. + * @param slope The slope of the tile to examine. + * @param existing The existing neighbours. + * @param start The part that should be build first. + * @param end The part that will be build second. + * @return 0 when the build parts do not connect, 1 when they do connect once + * they are build or 2 when building the first part automatically + * builds the second part. + */ +static int32 LookupWithBuildOnSlopes(::Slope slope, Array *existing, int32 start, int32 end) +{ + if (::IsSteepSlope(slope)) { + switch (slope) { + /* On steep slopes one can only build straight roads that will be + * automatically expanded to a straight road. Just check that the existing + * road parts are in the same direction. */ + case SLOPE_STEEP_S: + case SLOPE_STEEP_W: + case SLOPE_STEEP_N: + case SLOPE_STEEP_E: + return CheckAutoExpandedRoadBits(existing, start, end) ? (existing->size == 0 ? 2 : 1) : 0; + + /* All other slopes are invalid slopes!. */ + default: + return -1; + } + } + + /* The slope is not steep. Furthermore lots of slopes are generally the + * same but are only rotated. So to reduce the amount of lookup work that + * needs to be done the data is made uniform. This means rotating the + * existing parts and updating the slope. */ + static const ::Slope base_slopes[] = { + SLOPE_FLAT, SLOPE_W, SLOPE_W, SLOPE_SW, + SLOPE_W, SLOPE_EW, SLOPE_SW, SLOPE_WSE, + SLOPE_W, SLOPE_SW, SLOPE_EW, SLOPE_WSE, + SLOPE_SW, SLOPE_WSE, SLOPE_WSE}; + static const byte base_rotates[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 3, 2, 3, 2, 2, 1}; + + if (slope >= (::Slope)lengthof(base_slopes)) { + /* This slope is an invalid slope, so ignore it. */ + return -1; + } + byte base_rotate = base_rotates[slope]; + slope = base_slopes[slope]; + + /* Some slopes don't need rotating, so return early when we know we do + * not need to rotate. */ + switch (slope) { + case SLOPE_FLAT: + /* Flat slopes can always be build. */ + return 1; + + case SLOPE_EW: + case SLOPE_WSE: + /* A slope similar to a SLOPE_EW or SLOPE_WSE will always cause + * foundations which makes them accessible from all sides. */ + return 1; + + case SLOPE_W: + case SLOPE_SW: + /* A slope for which we need perform some calculations. */ + break; + + default: + /* An invalid slope. */ + return -1; + } + + /* Now perform the actual rotation. */ + for (int j = 0; j < base_rotate; j++) { + for (int i = 0; i < existing->size; i++) { + existing->array[i] = RotateNeighbour(existing->array[i]); + } + start = RotateNeighbour(start); + end = RotateNeighbour(end); + } + + /* Create roadbits out of the data for easier handling. */ + RoadBits start_roadbits = NeighbourToRoadBits(start); + RoadBits new_roadbits = start_roadbits | NeighbourToRoadBits(end); + RoadBits existing_roadbits = ROAD_NONE; + for (int i = 0; i < existing->size; i++) { + existing_roadbits |= NeighbourToRoadBits(existing->array[i]); + } + + switch (slope) { + case SLOPE_W: + /* A slope similar to a SLOPE_W. */ + switch (new_roadbits) { + case 6: // ROAD_SE | ROAD_SW: + case 9: // ROAD_NE | ROAD_NW: + case 12: // ROAD_NE | ROAD_SE: + /* Cannot build anything with a turn from the low side. */ + return 0; + + case 5: // ROAD_SE | ROAD_NW: + case 10: // ROAD_NE | ROAD_SW: + /* A 'sloped' tile is going to be build. */ + if ((existing_roadbits | new_roadbits) != new_roadbits) { + /* There is already a foundation on the tile, or at least + * another slope that is not compatible with the new one. */ + return 0; + } + /* If the start is in the low part, it is automatically + * building the second part too. */ + return ((start_roadbits & (ROAD_NE | ROAD_SE)) && !(existing_roadbits & (ROAD_SW | ROAD_NW))) ? 2 : 1; + + default: + /* Roadbits causing a foundation are going to be build. + * When the existing roadbits are slopes (the lower bits + * are used), this cannot be done. */ + if ((existing_roadbits | new_roadbits) == new_roadbits) return 1; + return (existing_roadbits & (ROAD_NE | ROAD_SE)) ? 0 : 1; + } + + case SLOPE_SW: + /* A slope similar to a SLOPE_SW. */ + switch (new_roadbits) { + case 9: // ROAD_NE | ROAD_NW: + case 12: // ROAD_NE | ROAD_SE: + /* Cannot build anything with a turn from the low side. */ + return 0; + + case 10: // ROAD_NE | ROAD_SW: + /* A 'sloped' tile is going to be build. */ + if ((existing_roadbits | new_roadbits) != new_roadbits) { + /* There is already a foundation on the tile, or at least + * another slope that is not compatible with the new one. */ + return 0; + } + /* If the start is in the low part, it is automatically + * building the second part too. */ + return ((start_roadbits & ROAD_NE) && !(existing_roadbits & ROAD_SW)) ? 2 : 1; + + default: + /* Roadbits causing a foundation are going to be build. + * When the existing roadbits are slopes (the lower bits + * are used), this cannot be done. */ + return (existing_roadbits & ROAD_NE) ? 0 : 1; + } + + default: + NOT_REACHED(); + } +} + +/** + * Normalise all input data so we can easily handle it without needing + * to call the API lots of times or create large if-elseif-elseif-else + * constructs. + * In this case it means that a TileXY(0, -1) becomes -2 and TileXY(0, 1) + * becomes 2. TileXY(-1, 0) and TileXY(1, 0) stay respectively -1 and 1. + * Any other value means that it is an invalid tile offset. + * @param tile The tile to normalise. + * @return True if and only if the tile offset is valid. + */ +static bool NormaliseTileOffset(int32 *tile) +{ + if (*tile == 1 || *tile == -1) return true; + if (*tile == ::TileDiffXY(0, -1)) { + *tile = -2; + return true; + } + if (*tile == ::TileDiffXY(0, 1)) { + *tile = 2; + return true; + } + return false; +} + +/* static */ int32 AIRoad::CanBuildConnectedRoadParts(AITile::Slope slope_, Array *existing, TileIndex start_, TileIndex end_) +{ + ::Slope slope = (::Slope)slope_; + int32 start = start_; + int32 end = end_; + + /* The start tile and end tile cannot be the same tile either. */ + if (start == end) return -1; + + for (int i = 0; i < existing->size; i++) { + if (!NormaliseTileOffset(&existing->array[i])) return -1; + } + + if (!NormaliseTileOffset(&start)) return -1; + if (!NormaliseTileOffset(&end)) return -1; + + /* Without build on slopes the characteristics are vastly different, so use + * a different helper function (one that is much simpler). */ + return _settings_game.construction.build_on_slopes ? LookupWithBuildOnSlopes(slope, existing, start, end) : LookupWithoutBuildOnSlopes(slope, existing, start, end); +} + +/* static */ int32 AIRoad::CanBuildConnectedRoadPartsHere(TileIndex tile, TileIndex start, TileIndex end) +{ + if (!::IsValidTile(tile) || !::IsValidTile(start) || !::IsValidTile(end)) return -1; + if (::DistanceManhattan(tile, start) != 1 || ::DistanceManhattan(tile, end) != 1) return -1; + + static const TileIndex neighbours[] = {::TileDiffXY(-1, 0), ::TileDiffXY(1, 0), ::TileDiffXY(0, -1), ::TileDiffXY(0, 1)}; + Array *existing = (Array*)alloca(sizeof(Array) + lengthof(neighbours) * sizeof(int32)); + existing->size = 0; + + for (uint i = 0; i < lengthof(neighbours); i++) { + if (AIRoad::AreRoadTilesConnected(tile, tile + neighbours[i])) existing->array[existing->size++] = neighbours[i]; + } + + return AIRoad::CanBuildConnectedRoadParts(AITile::GetSlope(tile), existing, start - tile, end - tile); +} + + /* static */ int32 AIRoad::GetNeighbourRoadCount(TileIndex tile) { if (!::IsValidTile(tile)) return false; diff -r 4dd4f4327c3a -r 203b90795f80 src/ai/api/ai_road.hpp --- a/src/ai/api/ai_road.hpp Tue Jun 17 11:46:09 2008 +0000 +++ b/src/ai/api/ai_road.hpp Tue Jun 17 13:06:32 2008 +0000 @@ -7,6 +7,7 @@ #include "ai_object.hpp" #include "ai_error.hpp" +#include "ai_tile.hpp" /** * Class that handles all road related functions. @@ -124,6 +125,58 @@ static bool AreRoadTilesConnected(TileIndex tile_from, TileIndex tile_to); /** + * Lookup function for building road parts independend on whether the + * "building on slopes" setting is enabled or not. + * This implementation can be used for abstract reasoning about a tile as + * it needs the slope and existing road parts of the tile as information. + * @param slope The slope of the tile to examine. + * @param existing An array with the existing neighbours in the same format + * as "start" and "end", e.g. AIMap.GetTileIndex(0, 1). + * As a result of this all values of the existing array + * must be of type integer. + * @param start The tile from where the 'tile to be considered' will be + * entered. This is a relative tile, so valid parameters are: + * AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1), + * AIMap.GetTileIndex(1, 0) and AIMap.GetTileIndex(-1, 0). + * @param end The tile from where the 'tile to be considered' will be + * exited. This is a relative tile, sovalid parameters are: + * AIMap.GetTileIndex(0, 1), AIMap.GetTileIndex(0, -1), + * AIMap.GetTileIndex(1, 0) and AIMap.GetTileIndex(-1, 0). + * @pre start != end. + * @pre slope must be a valid slope, i.e. one specified in AITile::Slope. + * @note Passing data that would be invalid in-game, e.g. existing containing + * road parts that can not be build on a tile with the given slope, + * does not necessarily means that -1 is returned, i.e. not all + * preconditions written here or assumed by the game are extensively + * checked to make sure the data entered is valid. + * @return 0 when the build parts do not connect, 1 when they do connect once + * they are build or 2 when building the first part automatically + * builds the second part. -1 means the preconditions are not met. + */ + static int32 CanBuildConnectedRoadParts(AITile::Slope slope, struct Array *existing, TileIndex start, TileIndex end); + + /** + * Lookup function for building road parts independend on whether the + * "building on slopes" setting is enabled or not. + * This implementation can be used for reasoning about an existing tile. + * @param tile The the tile to examine. + * @param start The tile from where "tile" will be entered. + * @param end The tile from where "tile" will be exited. + * @pre start != end. + * @pre tile != start. + * @pre tile != end. + * @pre AIMap.IsValidTile(tile). + * @pre AIMap.IsValidTile(start). + * @pre AIMap.IsValidTile(end). + * @pre AIMap.GetDistanceManhattanToTile(tile, start) == 1. + * @pre AIMap.GetDistanceManhattanToTile(tile, end) == 1. + * @return 0 when the build parts do not connect, 1 when they do connect once + * they are build or 2 when building the first part automatically + * builds the second part. -1 means the preconditions are not met. + */ + static int32 CanBuildConnectedRoadPartsHere(TileIndex tile, TileIndex start, TileIndex end); + + /** * Count how many neighbours are road. * @param tile The tile to check on. * @pre AIMap::IsValidTile(tile). diff -r 4dd4f4327c3a -r 203b90795f80 src/ai/api/ai_road.hpp.sq --- a/src/ai/api/ai_road.hpp.sq Tue Jun 17 11:46:09 2008 +0000 +++ b/src/ai/api/ai_road.hpp.sq Tue Jun 17 13:06:32 2008 +0000 @@ -42,28 +42,30 @@ AIError::RegisterErrorMapString(AIRoad::ERR_ROAD_CANNOT_BUILD_ON_TOWN_ROAD, "ERR_ROAD_CANNOT_BUILD_ON_TOWN_ROAD"); AIError::RegisterErrorMapString(AIRoad::ERR_ROAD_ONE_WAY_ROADS_CANNOT_HAVE_JUNCTIONS, "ERR_ROAD_ONE_WAY_ROADS_CANNOT_HAVE_JUNCTIONS"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetClassName, "GetClassName", 1, "x"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadTile, "IsRoadTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadDepotTile, "IsRoadDepotTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadStationTile, "IsRoadStationTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsDriveThroughRoadStationTile, "IsDriveThroughRoadStationTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadTypeAvailable, "IsRoadTypeAvailable", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetCurrentRoadType, "GetCurrentRoadType", 1, "x"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::SetCurrentRoadType, "SetCurrentRoadType", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::HasRoadType, "HasRoadType", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::AreRoadTilesConnected, "AreRoadTilesConnected", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetNeighbourRoadCount, "GetNeighbourRoadCount", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetRoadDepotFrontTile, "GetRoadDepotFrontTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetRoadStationFrontTile, "GetRoadStationFrontTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetDriveThroughBackTile, "GetDriveThroughBackTile", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoad, "BuildRoad", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadFull, "BuildRoadFull", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadDepot, "BuildRoadDepot", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadStation, "BuildRoadStation", 5, "xiibb"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoad, "RemoveRoad", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadFull, "RemoveRoadFull", 3, "xii"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadDepot, "RemoveRoadDepot", 2, "xi"); - SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadStation, "RemoveRoadStation", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetClassName, "GetClassName", 1, "x"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadTile, "IsRoadTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadDepotTile, "IsRoadDepotTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadStationTile, "IsRoadStationTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsDriveThroughRoadStationTile, "IsDriveThroughRoadStationTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::IsRoadTypeAvailable, "IsRoadTypeAvailable", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetCurrentRoadType, "GetCurrentRoadType", 1, "x"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::SetCurrentRoadType, "SetCurrentRoadType", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::HasRoadType, "HasRoadType", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::AreRoadTilesConnected, "AreRoadTilesConnected", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::CanBuildConnectedRoadParts, "CanBuildConnectedRoadParts", 5, "xiaii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::CanBuildConnectedRoadPartsHere, "CanBuildConnectedRoadPartsHere", 4, "xiii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetNeighbourRoadCount, "GetNeighbourRoadCount", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetRoadDepotFrontTile, "GetRoadDepotFrontTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetRoadStationFrontTile, "GetRoadStationFrontTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::GetDriveThroughBackTile, "GetDriveThroughBackTile", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoad, "BuildRoad", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadFull, "BuildRoadFull", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadDepot, "BuildRoadDepot", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::BuildRoadStation, "BuildRoadStation", 5, "xiibb"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoad, "RemoveRoad", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadFull, "RemoveRoadFull", 3, "xii"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadDepot, "RemoveRoadDepot", 2, "xi"); + SQAIRoad.DefSQStaticMethod(engine, &AIRoad::RemoveRoadStation, "RemoveRoadStation", 2, "xi"); SQAIRoad.PostRegister(engine); }