diff options
| author | truelight <truelight@openttd.org> | 2004-08-20 09:32:32 +0000 |
|---|---|---|
| committer | truelight <truelight@openttd.org> | 2004-08-20 09:32:32 +0000 |
| commit | 788ace088d8b3ba2afd77a8b21b532abc40d9eba (patch) | |
| tree | 493248c0850e836b9a0d35c0fdddf9673b2a01b3 | |
| parent | 80b1e25b6ce190a773ab9fe50927a983c8f2d038 (diff) | |
| download | openttd-788ace088d8b3ba2afd77a8b21b532abc40d9eba.tar.xz | |
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
-Add: generalised A* Algorithm
-Add: generalised queues (Fifo, Stack, InsSort, BinaryHeap)
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | ai.h | 243 | ||||
| -rw-r--r-- | ai_build.c | 257 | ||||
| -rw-r--r-- | ai_new.c | 1221 | ||||
| -rw-r--r-- | ai_pathfinder.c | 457 | ||||
| -rw-r--r-- | ai_shared.c | 82 | ||||
| -rw-r--r-- | aircraft_cmd.c | 3 | ||||
| -rw-r--r-- | aystar.c | 271 | ||||
| -rw-r--r-- | aystar.h | 169 | ||||
| -rw-r--r-- | lang/english.txt | 4 | ||||
| -rw-r--r-- | misc_cmd.c | 9 | ||||
| -rw-r--r-- | player.h | 71 | ||||
| -rw-r--r-- | players.c | 8 | ||||
| -rw-r--r-- | queue.c | 659 | ||||
| -rw-r--r-- | queue.h | 202 | ||||
| -rw-r--r-- | rail_cmd.c | 6 | ||||
| -rw-r--r-- | road_cmd.c | 9 | ||||
| -rw-r--r-- | settings.c | 2 | ||||
| -rw-r--r-- | settings_gui.c | 10 | ||||
| -rw-r--r-- | station_cmd.c | 6 | ||||
| -rw-r--r-- | ttd.c | 3 | ||||
| -rw-r--r-- | tunnelbridge_cmd.c | 16 | ||||
| -rw-r--r-- | variables.h | 4 |
23 files changed, 3688 insertions, 27 deletions
@@ -434,7 +434,8 @@ ttd_SOURCES = \ texteff.c town_cmd.c town_gui.c train_cmd.c train_gui.c tree_cmd.c \ ttd.c tunnelbridge_cmd.c unmovable_cmd.c vehicle.c viewport.c \ water_cmd.c widget.c window.c minilzo.c screenshot.c settings.c rev.c \ - grfspecial.c terraform_gui.c network_gui.c + grfspecial.c terraform_gui.c network_gui.c aystar.c queue.c \ + ai_new.c ai_build.c ai_pathfinder.c ai_shared.c ifdef WITH_SDL ttd_SOURCES += sdl.c @@ -0,0 +1,243 @@ +#ifndef AI_H
+#define AI_H
+
+#include "aystar.h"
+
+/*
+ * These defines can be altered to change the behavoir of the AI
+ *
+ * WARNING:
+ * This can also alter the AI in a negative way. I will never claim these settings
+ * are perfect, but don't change them if you don't know what the effect is.
+ */
+
+// How many times it the H multiplied. The higher, the more it will go straight to the
+// end point. The lower, how more it will find the route with the lowest cost.
+// also: the lower, the longer it takes before route is calculated..
+#define AI_PATHFINDER_H_MULTIPLER 100
+
+// How many loops may AyStar do before it stops
+// 0 = infinite
+#define AI_PATHFINDER_LOOPS_PER_TICK 5
+
+// How long may the AI search for one route?
+// 0 = infinite
+// This number is the number of tiles tested.
+// It takes (AI_PATHFINDER_MAX_SEARCH_NODES / AI_PATHFINDER_LOOPS_PER_TICK) ticks
+// to get here.. with 5000 / 10 = 500. 500 / 74 (one day) = 8 days till it aborts
+// (that is: if the AI is on VERY FAST! :p
+#define AI_PATHFINDER_MAX_SEARCH_NODES 5000
+
+// If you enable this, the AI is not allowed to make 90degree turns
+#define AI_PATHFINDER_NO_90DEGREES_TURN
+
+// Below are defines for the g-calculation
+
+// Standard penalty given to a tile
+#define AI_PATHFINDER_PENALTY 150
+// The penalty given to a tile that is going up
+#define AI_PATHFINDER_TILE_GOES_UP_PENALTY 450
+// Changing direction is a penalty, to prevent curved ways (with that: slow ways)
+#define AI_PATHFINDER_DIRECTION_CHANGE_PENALTY 200
+// Same penalty, only for when road already exists
+#define AI_PATHFINDER_DIRECTION_CHANGE_ON_EXISTING_ROAD_PENALTY 50
+// A diagonal track cost the same as a straigh, but a diagonal is faster... so give
+// a bonus for using diagonal track
+#ifdef AI_PATHFINDER_NO_90DEGREES_TURN
+#define AI_PATHFINDER_DIAGONAL_BONUS 95
+#else
+#define AI_PATHFINDER_DIAGONAL_BONUS 75
+#endif
+// If a roadblock already exists, it gets a bonus
+#define AI_PATHFINDER_ROAD_ALREADY_EXISTS_BONUS 140
+// To prevent 3 direction changes in 3 tiles, this penalty is given in such situation
+#define AI_PATHFINDER_CURVE_PENALTY 200
+
+// Penalty a bridge gets per length
+#define AI_PATHFINDER_BRIDGE_PENALTY 180
+// The penalty for a bridge going up
+#define AI_PATHFINDER_BRIDGE_GOES_UP_PENALTY 1000
+
+// Tunnels are expensive...
+// Because of that, every tile the cost is increased with 1/8th of his value
+// This is also true if you are building a tunnel yourself
+#define AI_PATHFINDER_TUNNEL_PENALTY 350
+
+/*
+ * Ai_New defines
+ */
+
+// How long may we search cities and industry for a new route?
+#define AI_LOCATE_ROUTE_MAX_COUNTER 200
+
+// How many days must there be between building the first station and the second station
+// within one city. This number is in days and should be more then 4 months.
+#define AI_CHECKCITY_DATE_BETWEEN 180
+
+// How many cargo is needed for one station in a city?
+#define AI_CHECKCITY_CARGO_PER_STATION 60
+// How much cargo must there not be used in a city before we can build a new station?
+#define AI_CHECKCITY_NEEDED_CARGO 50
+// When there is already a station which takes the same good and the rating of that
+// city is higher then this numer, we are not going to attempt to build anything
+// there
+#define AI_CHECKCITY_CARGO_RATING 50
+// But, there is a chance of 1 out of this number, that we do ;)
+#define AI_CHECKCITY_CARGO_RATING_CHANCE 5
+// If a city is too small to contain a station, there is a small chance
+// that we still do so.. just to make the city bigger!
+#define AI_CHECKCITY_CITY_CHANCE 5
+
+// This number indicates for every unit of cargo, how many tiles two stations maybe be away
+// from eachother. In other words: if we have 120 units of cargo in one station, and 120 units
+// of the cargo in the other station, both stations can be 96 units away from eachother, if the
+// next number is 0.4.
+#define AI_LOCATEROUTE_BUS_CARGO_DISTANCE 0.4
+#define AI_LOCATEROUTE_TRUCK_CARGO_DISTANCE 0.7
+// In whole tiles, the minimum distance for a truck route
+#define AI_LOCATEROUTE_TRUCK_MIN_DISTANCE 30
+
+// The amount of tiles in a square from -X to +X that is scanned for a station spot
+// (so if this number is 10, 20x20 = 400 tiles are scanned for _the_ perfect spot
+// Safe values are between 15 and 5
+#define AI_FINDSTATION_TILE_RANGE 10
+
+// Building on normal speed goes very fast. Idle this amount of ticks between every
+// building part. It is calculated like this: (4 - competitor_speed) * num + 1
+// where competitor_speed is between 0 (very slow) to 4 (very fast)
+#define AI_BUILDPATH_PAUSE 10
+
+// Minimum % of reliabilty a vehicle has to have before the AI buys it
+#define AI_VEHICLE_MIN_RELIABILTY 60
+
+// The minimum amount of money a player should always have
+#define AI_MINIMUM_MONEY 15000
+
+// If the most cheap route is build, how much is it going to cost..
+// This is to prevent the AI from trying to build a route which can not be paid for
+#define AI_MINIMUM_BUS_ROUTE_MONEY 25000
+#define AI_MINIMUM_TRUCK_ROUTE_MONEY 35000
+
+// The minimum amount of money before we are going to repay any money
+#define AI_MINIMUM_LOAN_REPAY_MONEY 40000
+// How many repays do we do if we have enough money to do so?
+// Every repay is 10000
+#define AI_LOAN_REPAY 2
+// How much income must we have before paying back a loan? Month-based (and looked at the last month)
+#define AI_MINIMUM_INCOME_FOR_LOAN 7000
+
+// If there is <num> time as much cargo in the station then the vehicle can handle
+// reuse the station instead of building a new one!
+#define AI_STATION_REUSE_MULTIPLER 2
+
+// No more then this amount of vehicles per station..
+#define AI_CHECK_MAX_VEHICLE_PER_STATION 10
+
+// How many thick between building 2 vehicles
+#define AI_BUILD_VEHICLE_TIME_BETWEEN 74
+
+/*
+ * End of defines
+ */
+
+
+// This stops 90degrees curves
+static const byte _illegal_curves[6] = {
+ 255, 255, // Horz and vert, don't have the effect
+ 5, // upleft and upright are not valid
+ 4, // downright and downleft are not valid
+ 2, // downleft and upleft are not valid
+ 3, // upright and downright are not valid
+};
+
+static const TileIndexDiff _tiles_around[4] = {
+ TILE_XY(-1,0),
+ TILE_XY(0,1),
+ TILE_XY(1,0),
+ TILE_XY(0,-1),
+};
+
+enum {
+ AI_STATE_STARTUP = 0,
+ AI_STATE_FIRST_TIME,
+ AI_STATE_NOTHING,
+ AI_STATE_WAKE_UP,
+ AI_STATE_LOCATE_ROUTE,
+ AI_STATE_FIND_STATION,
+ AI_STATE_FIND_PATH,
+ AI_STATE_FIND_DEPOT,
+ AI_STATE_VERIFY_ROUTE,
+ AI_STATE_BUILD_STATION,
+ AI_STATE_BUILD_PATH,
+ AI_STATE_BUILD_DEPOT,
+ AI_STATE_BUILD_VEHICLE,
+ AI_STATE_GIVE_ORDERS,
+ AI_STATE_START_VEHICLE,
+ AI_STATE_REPAY_MONEY,
+ AI_STATE_ACTION_DONE,
+ AI_STATE_STOP, // Temporary function to stop the AI
+};
+
+// Used for tbt (train/bus/truck)
+enum {
+ AI_TRAIN = 0,
+ AI_BUS,
+ AI_TRUCK,
+};
+
+enum {
+ AI_ACTION_NONE = 0,
+ AI_ACTION_BUS_ROUTE,
+ AI_ACTION_TRUCK_ROUTE,
+ AI_ACTION_REPAY_LOAN,
+};
+
+// Used for from_type/to_type
+enum {
+ AI_NO_TYPE = 0,
+ AI_CITY,
+ AI_INDUSTRY,
+};
+
+#define AI_NO_CARGO 0xFF // Means that there is no cargo defined yet (used for industry)
+#define AI_NEED_CARGO 0xFE // Used when the AI needs to find out a cargo for the route
+#define AI_STATION_RANGE TILE_XY(TILE_X_MAX, TILE_Y_MAX)
+
+#define AI_PATHFINDER_NO_DIRECTION (byte)-1
+
+// Flags used in user_data
+#define AI_PATHFINDER_FLAG_BRIDGE 1
+#define AI_PATHFINDER_FLAG_TUNNEL 2
+
+// A macro for mp_street, where 0x20 is depot
+// mp_tunnelbridge, where 0xf0 is a bridge, and 0x4/0x2 means: roadtunnel/bridge
+#define AI_PATHFINDER_IS_ROAD(tile) ((IS_TILETYPE(tile, MP_STREET) && !(_map5[tile] & 0x20)) || \
+(IS_TILETYPE(tile, MP_TUNNELBRIDGE) && \
+ (((_map5[tile] & 0x80) == 0 && (_map5[tile] & 0x4) == 0x4) || \
+ ((_map5[tile] & 0x80) != 0 && (_map5[tile] & 0x2) == 0x2))))
+
+typedef void AiNew_StateFunction(Player *p);
+
+// ai_new.c
+void AiNewDoGameLoop(Player *p);
+
+// ai_pathfinder.c
+AyStar *new_AyStar_AiPathFinder(int max_tiles_around, Ai_PathFinderInfo *PathFinderInfo);
+void clean_AyStar_AiPathFinder(AyStar *aystar, Ai_PathFinderInfo *PathFinderInfo);
+
+// ai_shared.c
+int AiNew_GetRailDirection(uint tile_a, uint tile_b, uint tile_c);
+int AiNew_GetRoadDirection(uint tile_a, uint tile_b, uint tile_c);
+int AiNew_GetDirection(uint tile_a, uint tile_b);
+
+// ai_build.c
+bool AiNew_Build_CompanyHQ(Player *p, uint tile);
+int AiNew_Build_Station(Player *p, byte type, uint tile, byte length, byte numtracks, byte direction, byte flag);
+int AiNew_Build_Bridge(Player *p, uint tile_a, uint tile_b, byte flag);
+int AiNew_Build_RoutePart(Player *p, Ai_PathFinderInfo *PathFinderInfo, byte flag);
+int AiNew_PickVehicle(Player *p);
+int AiNew_Build_Vehicle(Player *p, uint tile, byte flag);
+int AiNew_Build_Depot(Player *p, uint tile, byte direction, byte flag);
+
+
+#endif
diff --git a/ai_build.c b/ai_build.c new file mode 100644 index 000000000..6a565342b --- /dev/null +++ b/ai_build.c @@ -0,0 +1,257 @@ +#include "stdafx.h"
+#include "ttd.h"
+#include "command.h"
+#include "ai.h"
+#include "engine.h"
+
+// Build HQ
+// Params:
+// tile : tile where HQ is going to be build
+bool AiNew_Build_CompanyHQ(Player *p, uint tile) {
+ if (DoCommandByTile(tile, 0, 0, DC_AUTO | DC_NO_WATER, CMD_BUILD_COMPANY_HQ) == CMD_ERROR)
+ return false;
+ DoCommandByTile(tile, 0, 0, DC_EXEC | DC_AUTO | DC_NO_WATER, CMD_BUILD_COMPANY_HQ);
+ return true;
+}
+
+// Build station
+// Params:
+// type : AI_TRAIN/AI_BUS/AI_TRUCK : indicates the type of station
+// tile : tile where station is going to be build
+// length : in case of AI_TRAIN: length of station
+// numtracks : in case of AI_TRAIN: tracks of station
+// direction : the direction of the station
+// flag : flag passed to DoCommand (normally 0 to get the cost or DC_EXEC to build it)
+int AiNew_Build_Station(Player *p, byte type, uint tile, byte length, byte numtracks, byte direction, byte flag) {
+ if (type == AI_TRAIN)
+ return DoCommandByTile(tile, direction + (numtracks << 8) + (length << 16), 0, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_RAILROAD_STATION);
+ else if (type == AI_BUS)
+ return DoCommandByTile(tile, direction, 0, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_BUS_STATION);
+ else
+ return DoCommandByTile(tile, direction, 0, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_TRUCK_STATION);
+}
+
+// Builds a brdige. The second best out of the ones available for this player
+// Params:
+// tile_a : starting point
+// tile_b : end point
+// flag : flag passed to DoCommand
+int AiNew_Build_Bridge(Player *p, uint tile_a, uint tile_b, byte flag) {
+ int bridge_type, bridge_len, type, type2;
+
+ // Find a good bridgetype (the best money can buy)
+ bridge_len = GetBridgeLength(tile_a, tile_b);
+ type = type2 = 0;
+ for (bridge_type = MAX_BRIDGES-1; bridge_type >= 0; bridge_type--) {
+ if (CheckBridge_Stuff(bridge_type, bridge_len)) {
+ type2 = type;
+ type = bridge_type;
+ // We found two bridges, exit
+ if (type2 != 0)
+ break;
+ }
+ }
+ // There is only one bridge that can be build..
+ if (type2 == 0 && type != 0) type2 = type;
+
+ // Now, simply, build the bridge!
+ if (p->ainew.tbt == AI_TRAIN)
+ return DoCommandByTile(tile_a, tile_b, (0<<8) + type2, flag | DC_AUTO, CMD_BUILD_BRIDGE);
+ else
+ return DoCommandByTile(tile_a, tile_b, (0x80 << 8) + type2, flag | DC_AUTO, CMD_BUILD_BRIDGE);
+}
+
+
+// Build the route part by part
+// Basicly what this function do, is build that amount of parts of the route
+// that go in the same direction. It sets 'part' to the last part of the route builded.
+// The return value is the cost for the builded parts
+//
+// Params:
+// PathFinderInfo : Pointer to the PathFinderInfo used for AiPathFinder
+// part : Which part we need to build
+//
+// TODO: skip already builded road-pieces (e.g.: cityroad)
+int AiNew_Build_RoutePart(Player *p, Ai_PathFinderInfo *PathFinderInfo, byte flag) {
+ int part = PathFinderInfo->position;
+ byte *route_extra = PathFinderInfo->route_extra;
+ TileIndex *route = PathFinderInfo->route;
+ int dir;
+ int old_dir = -1;
+ int cost = 0;
+ int res;
+ // We need to calculate the direction with the parent of the parent.. so we skip
+ // the first pieces and the last piece
+ if (part < 1) part = 1;
+ // When we are done, stop it
+ if (part >= PathFinderInfo->route_length - 1) { PathFinderInfo->position = -2; return 0; }
+
+
+ if (PathFinderInfo->rail_or_road) {
+ // Tunnel code
+ if ((AI_PATHFINDER_FLAG_TUNNEL & route_extra[part]) != 0) {
+ cost += DoCommandByTile(route[part], 0, 0, flag, CMD_BUILD_TUNNEL);
+ PathFinderInfo->position++;
+ // TODO: problems!
+ if (cost == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildPath] We have a serious problem: tunnel could not be build!");
+ return 0;
+ }
+ return cost;
+ }
+ // Bridge code
+ if ((AI_PATHFINDER_FLAG_BRIDGE & route_extra[part]) != 0) {
+ cost += AiNew_Build_Bridge(p, route[part], route[part-1], flag);
+ PathFinderInfo->position++;
+ // TODO: problems!
+ if (cost == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildPath] We have a serious problem: bridge could not be build!");
+ return 0;
+ }
+ return cost;
+ }
+
+ // Build normal rail
+ // Keep it doing till we go an other way
+ if (route_extra[part-1] == 0 && route_extra[part] == 0) {
+ while (route_extra[part] == 0) {
+ // Get the current direction
+ dir = AiNew_GetRailDirection(route[part-1], route[part], route[part+1]);
+ // Is it the same as the last one?
+ if (old_dir != -1 && old_dir != dir) break;
+ old_dir = dir;
+ // Build the tile
+ res = DoCommandByTile(route[part], 0, dir, flag, CMD_BUILD_SINGLE_RAIL);
+ if (res == CMD_ERROR) {
+ // Problem.. let's just abort it all!
+ p->ainew.state = AI_STATE_NOTHING;
+ return 0;
+ }
+ cost += res;
+ // Go to the next tile
+ part++;
+ // Check if it is still in range..
+ if (part >= PathFinderInfo->route_length - 1) break;
+ }
+ part--;
+ }
+ // We want to return the last position, so we go back one
+ PathFinderInfo->position = part;
+ } else {
+ // Tunnel code
+ if ((AI_PATHFINDER_FLAG_TUNNEL & route_extra[part]) != 0) {
+ cost += DoCommandByTile(route[part], 0x200, 0, flag, CMD_BUILD_TUNNEL);
+ PathFinderInfo->position++;
+ // TODO: problems!
+ if (cost == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildPath] We have a serious problem: tunnel could not be build!");
+ return 0;
+ }
+ return cost;
+ }
+ // Bridge code
+ if ((AI_PATHFINDER_FLAG_BRIDGE & route_extra[part]) != 0) {
+ cost += AiNew_Build_Bridge(p, route[part], route[part+1], flag);
+ PathFinderInfo->position++;
+ // TODO: problems!
+ if (cost == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildPath] We have a serious problem: bridge could not be build!");
+ return 0;
+ }
+ return cost;
+ }
+
+ // Build normal road
+ // Keep it doing till we go an other way
+ // EnsureNoVehicle makes sure we don't build on a tile where a vehicle is. This way
+ // it will wait till the vehicle is gone..
+ if (route_extra[part-1] == 0 && route_extra[part] == 0 && (flag != DC_EXEC || EnsureNoVehicle(route[part]))) {
+ while (route_extra[part] == 0 && (flag != DC_EXEC || EnsureNoVehicle(route[part]))) {
+ // Get the current direction
+ dir = AiNew_GetRoadDirection(route[part-1], route[part], route[part+1]);
+ // Is it the same as the last one?
+ if (old_dir != -1 && old_dir != dir) break;
+ old_dir = dir;
+ // There is already some road, and it is a bridge.. don't build!!!
+ if (!IS_TILETYPE(route[part], MP_TUNNELBRIDGE)) {
+ // Build the tile
+ res = DoCommandByTile(route[part], dir, 0, flag | DC_NO_WATER, CMD_BUILD_ROAD);
+ // Currently, we ignore CMD_ERRORs!
+ if (res == CMD_ERROR && !IS_TILETYPE(route[part], MP_STREET) && (flag == DC_EXEC && !EnsureNoVehicle(route[part]))) {
+ // Problem.. let's just abort it all!
+ DEBUG(ai,0)("Darn, the route could not be builded.. aborting!");
+ p->ainew.state = AI_STATE_NOTHING;
+ return 0;
+ } else {
+ if (res != CMD_ERROR)
+ cost += res;
+ }
+ }
+ // Go to the next tile
+ part++;
+ // Check if it is still in range..
+ if (part >= PathFinderInfo->route_length - 1) break;
+ }
+ part--;
+ // We want to return the last position, so we go back one
+ }
+ if (!EnsureNoVehicle(route[part]) && flag == DC_EXEC) part--;
+ PathFinderInfo->position = part;
+ }
+
+ return cost;
+}
+
+// This functions tries to find the best vehicle for this type of cargo
+// It returns vehicle_id or -1 if not found
+int AiNew_PickVehicle(Player *p) {
+ if (p->ainew.tbt == AI_TRAIN) {
+ // Not supported yet
+ return -1;
+ } else {
+ int start, count, i, r = CMD_ERROR;
+ start = _cargoc.ai_roadveh_start[p->ainew.cargo];
+ count = _cargoc.ai_roadveh_count[p->ainew.cargo];
+
+ // Let's check it backwards.. we simply want to best engine available..
+ for (i=start+count-1;i>=start;i--) {
+ // Is it availiable?
+ // Also, check if the reliability of the vehicle is above the AI_VEHICLE_MIN_RELIABILTY
+ if (!HASBIT(_engines[i].player_avail, _current_player) || _engines[i].reliability * 100 < AI_VEHICLE_MIN_RELIABILTY << 16) continue;
+ // Can we build it?
+ r = DoCommandByTile(0, i, 0, DC_QUERY_COST, CMD_BUILD_ROAD_VEH);
+ if (r != CMD_ERROR) break;
+ }
+ // We did not find a vehicle :(
+ if (r == CMD_ERROR) { return -1; }
+ return i;
+ }
+}
+
+// Builds the best vehicle possible
+int AiNew_Build_Vehicle(Player *p, uint tile, byte flag) {
+ int i = AiNew_PickVehicle(p);
+ if (i == -1) return CMD_ERROR;
+
+ if (p->ainew.tbt == AI_TRAIN) {
+ return CMD_ERROR;
+ } else {
+ return DoCommandByTile(tile, i, 0, flag, CMD_BUILD_ROAD_VEH);
+ }
+}
+
+int AiNew_Build_Depot(Player *p, uint tile, byte direction, byte flag) {
+ static const byte _roadbits_by_dir[4] = {2,1,8,4};
+ int r, r2;
+ if (p->ainew.tbt == AI_TRAIN) {
+ return DoCommandByTile(tile, 0, direction, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_TRAIN_DEPOT);
+ } else {
+ r = DoCommandByTile(tile, direction, 0, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD_DEPOT);
+ if (r == CMD_ERROR) return r;
+ // Try to build the road from the depot
+ r2 = DoCommandByTile(tile + _tileoffs_by_dir[direction], _roadbits_by_dir[direction], 0, flag | DC_AUTO | DC_NO_WATER, CMD_BUILD_ROAD);
+ // If it fails, ignore it..
+ if (r2 == CMD_ERROR) return r;
+ return r + r2;
+ }
+}
diff --git a/ai_new.c b/ai_new.c new file mode 100644 index 000000000..1a79a50bf --- /dev/null +++ b/ai_new.c @@ -0,0 +1,1221 @@ +/*
+ * Next part is in Dutch, and only here for me, TrueLight, the maker of this new AI
+ */
+
+// TODO: als iemand een vehicle stil zet op een weg waar de AI wil bouwen
+// doet de AI helemaal niets meer
+// TODO: depot rondjes rijden stom iets dingus
+// TODO: jezelf afvragen of competitor_intelligence op niveau 2 wel meer geld moet opleverne...
+// TODO: als er iets in path komt, bouwt AI gewoon verder :(
+// TODO: mail routes
+
+/*
+ * End of Dutch part
+ */
+
+#include "stdafx.h"
+#include "ttd.h"
+#include "command.h"
+#include "ai.h"
+#include "town.h"
+#include "industry.h"
+#include "station.h"
+#include "engine.h"
+#include "gui.h"
+
+// This function is called after StartUp. It is the init of an AI
+static void AiNew_State_FirstTime(Player *p) {
+ // This assert is used to protect those function from misuse
+ // You have quickly a small mistake in the state-array
+ // With that, everything would go wrong. Finding that, is almost impossible
+ // With this assert, that problem can never happen.
+ assert(p->ainew.state == AI_STATE_FIRST_TIME);
+ // We first have to init some things
+
+ if (_current_player == 1) {
+ ShowErrorMessage(-1, TEMP_AI_IN_PROGRESS, 0, 0);
+ }
+
+ // The PathFinder (AyStar)
+ // TODO: Maybe when an AI goes bankrupt, this is de-init
+ // or when coming from a savegame.. should be checked out!
+ p->ainew.path_info.start_tile_tl = 0;
+ p->ainew.path_info.start_tile_br = 0;
+ p->ainew.path_info.end_tile_tl = 0;
+ p->ainew.path_info.end_tile_br = 0;
+ p->ainew.pathfinder = new_AyStar_AiPathFinder(12, &p->ainew.path_info);
+
+ p->ainew.idle = 0;
+
+ // We ALWAYS start with a bus route.. just some basic money ;)
+ p->ainew.action = AI_ACTION_BUS_ROUTE;
+
+ // Let's popup the news, and after that, start building..
+ p->ainew.state = AI_STATE_WAKE_UP;
+}
+
+// This function just waste some time
+// It keeps it more real. The AI can build on such tempo no normal user
+// can ever keep up with that. The competitor_speed already delays a bit
+// but after the AI finished a track it really needs to go to sleep.
+//
+// Let's say, we sleep between one and three days if the AI is put on Very Fast.
+// This means that on Very Slow it will be between 16 and 48 days.. slow enough?
+static void AiNew_State_Nothing(Player *p) {
+ assert(p->ainew.state == AI_STATE_NOTHING);
+ // If we are done idling, start over again
+ // There go 74 ticks in a day
+ if (p->ainew.idle == 0) p->ainew.idle = RandomRange(74 * 2) + 74;
+ if (--p->ainew.idle == 0) {
+ // We are done idling.. what you say? Let's do something!
+ // I mean.. the next tick ;)
+ p->ainew.state = AI_STATE_WAKE_UP;
+ }
+}
+
+// This function picks out a task we are going to do.
+// Currently supported:
+// - Make new route
+// - Check route
+// - Build HQ
+static void AiNew_State_WakeUp(Player *p) {
+ int32 money;
+ int c;
+ assert(p->ainew.state == AI_STATE_WAKE_UP);
+ // First, check if we have a HQ
+ if (p->location_of_house == 0) {
+ // We have no HQ yet, build one on a random place
+ // Random till we found a place for it!
+ // TODO: this should not be on a random place..
+ while (!AiNew_Build_CompanyHQ(p, (Random()&0xFFFF))) { }
+ // Enough for now, but we want to come back here the next time
+ // so we do not change any status
+ return;
+ }
+
+ money = p->player_money - AI_MINIMUM_MONEY;
+
+ // Let's pick an action!
+ if (p->ainew.action == AI_ACTION_NONE) {
+ c = Random() & 0xFF;
+ if (p->current_loan > 0 && p->old_economy[1].income > AI_MINIMUM_INCOME_FOR_LOAN &&
+ c < 10) {
+ p->ainew.action = AI_ACTION_REPAY_LOAN;
+ } else if (c < 100 && !_patches.ai_disable_veh_roadveh) {
+ // Do we have any spots for road-vehicles left open?
+ if (GetFreeUnitNumber(VEH_Road) <= _patches.max_roadveh) {
+ if (c < 65) p->ainew.action = AI_ACTION_TRUCK_ROUTE;
+ else p->ainew.action = AI_ACTION_BUS_ROUTE;
+ }
+ }/* else if (c < 200 && !_patches.ai_disable_veh_train) {
+ if (GetFreeUnitNumber(VEH_Train) <= _patches.max_trains) {
+ p->ainew.action = AI_ACTION_TRAIN_ROUTE;
+ }
+ }*/
+ }
+
+ if (_patches.ai_disable_veh_roadveh && (
+ p->ainew.action == AI_ACTION_BUS_ROUTE || p->ainew.action == AI_ACTION_TRUCK_ROUTE)) {
+ p->ainew.action = AI_ACTION_NONE;
+ return;
+ }
+
+ if (_patches.ai_disable_veh_roadveh && (
+ p->ainew.action == AI_ACTION_BUS_ROUTE || p->ainew.action == AI_ACTION_TRUCK_ROUTE)) {
+ p->ainew.action = AI_ACTION_NONE;
+ return;
+ }
+
+ if (p->ainew.action == AI_ACTION_REPAY_LOAN && money > AI_MINIMUM_LOAN_REPAY_MONEY) {
+ // We start repaying some money..
+ p->ainew.state = AI_STATE_REPAY_MONEY;
+ return;
+ }
+
+ // It is useless to start finding a route if we don't have enough money
+ // to build the route anyway..
+ if (p->ainew.action == AI_ACTION_BUS_ROUTE && money > AI_MINIMUM_BUS_ROUTE_MONEY) {
+ if (GetFreeUnitNumber(VEH_Road) > _patches.max_roadveh) {
+ p->ainew.action = AI_ACTION_NONE;
+ return;
+ }
+ p->ainew.cargo = AI_NEED_CARGO;
+ p->ainew.state = AI_STATE_LOCATE_ROUTE;
+ p->ainew.tbt = AI_BUS; // Bus-route
+ return;
+ }
+ if (p->ainew.action == AI_ACTION_TRUCK_ROUTE && money > AI_MINIMUM_TRUCK_ROUTE_MONEY) {
+ if (GetFreeUnitNumber(VEH_Road) > _patches.max_roadveh) {
+ p->ainew.action = AI_ACTION_NONE;
+ return;
+ }
+ p->ainew.cargo = AI_NEED_CARGO;
+ p->ainew.last_id = 0;
+ p->ainew.state = AI_STATE_LOCATE_ROUTE;
+ p->ainew.tbt = AI_TRUCK;
+ return;
+ }
+
+ p->ainew.state = AI_STATE_NOTHING;
+}
+
+static void AiNew_State_ActionDone(Player *p) {
+ p->ainew.action = AI_ACTION_NONE;
+ p->ainew.state = AI_STATE_NOTHING;
+}
+
+// Check if a city or industry is good enough to start a route there
+static bool AiNew_Check_City_or_Industry(Player *p, int ic, byte type) {
+ if (type == AI_CITY) {
+ Town *t = DEREF_TOWN(ic);
+ Station *st;
+ int count = 0;
+ int j = 0;
+
+ // We don't like roadconstructions, don't even true such a city
+ if (t->road_build_months != 0) return false;
+
+ // Check if the rating in a city is high enough
+ // If not, take a chance if we want to continue
+ if (t->ratings[_current_player] < 0 && CHANCE16(1,4)) return false;
+
+ if (t->max_pass - t->act_pass < AI_CHECKCITY_NEEDED_CARGO && !CHANCE16(1,AI_CHECKCITY_CITY_CHANCE)) return false;
+
+ // Check if we have build a station in this town the last 6 months
+ // else we don't do it. This is done, because stat updates can be slow
+ // and sometimes it takes up to 4 months before the stats are corectly.
+ // This way we don't get 12 busstations in one city of 100 population ;)
+ FOR_ALL_STATIONS(st) {
+ // Is it an active station
+ if (st->xy == 0) continue;
+ // Do we own it?
+ if (st->owner == _current_player) {
+ // Are we talking busses?
+ if (p->ainew.tbt == AI_BUS && (FACIL_BUS_STOP & st->facilities) != FACIL_BUS_STOP) continue;
+ // Is it the same city as we are in now?
+ if (st->town != t) continue;
+ // When was this station build?
+ if (_date - st->build_date < AI_CHECKCITY_DATE_BETWEEN) return false;
+ // Cound the amount of stations in this city that we own
+ count++;
+ } else {
+ // We do not own it, request some info about the station
+ // we want to know if this station gets the same good. If so,
+ // we want to know its rating. If it is too high, we are not going
+ // to build there
+ if (!st->goods[CT_PASSENGERS].last_speed) continue;
+ // Is it around our city
+ if (GetTileDist(st->xy, t->xy) > 10) continue;
+ // It does take this cargo.. what is his rating?
+ if (st->goods[CT_PASSENGERS].rating < AI_CHECKCITY_CARGO_RATING) continue;
+ j++;
+ // When this is the first station, we build a second with no problem ;)
+ if (j == 1) continue;
+ // The rating is high.. second station...
+ // a little chance that we still continue
+ // But if there are 3 stations of this size, we never go on...
+ if (j == 2 && CHANCE16(1, AI_CHECKCITY_CARGO_RATING_CHANCE)) continue;
+ // We don't like this station :(
+ return false;
+ }
+ }
+
+ // We are about to add one...
+ count++;
+ // Check if we the city can provide enough cargo for this amount of stations..
+ if (count * AI_CHECKCITY_CARGO_PER_STATION > t->max_pass) return false;
+
+ // All check are okay, so we can build here!
+ return true;
+ }
+ if (type == AI_INDUSTRY) {
+ Industry *i = DEREF_INDUSTRY(ic);
+ Station *st;
+ int count = 0;
+ int j = 0;
+
+ if (i->town->ratings[_current_player] < 0 && CHANCE16(1,4)) return false;
+
+ // No limits on delevering stations!
+ // Or for industry that does not give anything yet
+ if (i->produced_cargo[0] == 0xFF || i->total_production[0] == 0) return true;
+
+ if (i->total_production[0] - i->total_transported[0] < AI_CHECKCITY_NEEDED_CARGO) return false;
+
+ // Check if we have build a station in this town the last 6 months
+ // else we don't do it. This is done, because stat updates can be slow
+ // and sometimes it takes up to 4 months before the stats are corectly.
+ FOR_ALL_STATIONS(st) {
+ // Is it an active station
+ if (st->xy == 0) continue;
+
+ // Do we own it?
+ if (st->owner == _current_player) {
+ // Are we talking trucks?
+ if (p->ainew.tbt == AI_TRUCK && (FACIL_TRUCK_STOP & st->facilities) != FACIL_TRUCK_STOP) continue;
+ // Is it the same city as we are in now?
+ if (st->town != i->town) continue;
+ // When was this station build?
+ if (_date - st->build_date < AI_CHECKCITY_DATE_BETWEEN) return false;
+ // Cound the amount of stations in this city that we own
+ count++;
+ } else {
+ // We do not own it, request some info about the station
+ // we want to know if this station gets the same good. If so,
+ // we want to know its rating. If it is too high, we are not going
+ // to build there
+ if (i->produced_cargo[0] == 0xFF) continue;
+ // It does not take this cargo
+ if (!st->goods[i->produced_cargo[0]].last_speed) continue;
+ // Is it around our industry
+ if (GetTileDist(st->xy, i->xy) > 5) continue;
+ // It does take this cargo.. what is his rating?
+ if (st->goods[i->produced_cargo[0]].rating < AI_CHECKCITY_CARGO_RATING) continue;
+ j++;
+ // The rating is high.. a little chance that we still continue
+ // But if there are 2 stations of this size, we never go on...
+ if (j == 1 && CHANCE16(1, AI_CHECKCITY_CARGO_RATING_CHANCE)) continue;
+ // We don't like this station :(
+ return false;
+ }
+ }
+
+ // We are about to add one...
+ count++;
+ // Check if we the city can provide enough cargo for this amount of stations..
+ if (count * AI_CHECKCITY_CARGO_PER_STATION > i->total_production[0]) return false;
+
+ // All check are okay, so we can build here!
+ return true;
+ }
+
+ return true;
+}
+
+// This functions tries to locate a good route
+static void AiNew_State_LocateRoute(Player *p) {
+ assert(p->ainew.state == AI_STATE_LOCATE_ROUTE);
+ // For now, we only support PASSENGERS, CITY and BUSSES
+
+ // We don't have a route yet
+ if (p->ainew.cargo == AI_NEED_CARGO) {
+ p->ainew.new_cost = 0; // No cost yet
+ p->ainew.temp = -1;
+ // Reset the counter
+ p->ainew.counter = 0;
+
+ p->ainew.from_ic = -1;
+ p->ainew.to_ic = -1;
+ if (p->ainew.tbt == AI_BUS) {
+ // For now we only have a passenger route
+ p->ainew.cargo = CT_PASSENGERS;
+
+ // Find a route to cities
+ p->ainew.from_type = AI_CITY;
+ p->ainew.to_type = AI_CITY;
+ } else if (p->ainew.tbt == AI_TRUCK) {
+ p->ainew.cargo = AI_NO_CARGO;
+
+ p->ainew.from_type = AI_INDUSTRY;
+ p->ainew.to_type = AI_INDUSTRY;
+ }
+
+ // Now we are doing initing, we wait one tick
+ return;
+ }
+
+ // Increase the counter and abort if it is taking too long!
+ p->ainew.counter++;
+ if (p->ainew.counter > AI_LOCATE_ROUTE_MAX_COUNTER) {
+ // Switch back to doing nothing!
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+
+ // We are going to locate a city from where we are going to connect
+ if (p->ainew.from_ic == -1) {
+ if (p->ainew.temp == -1) {
+ // First, we pick a random spot to search from
+ if (p->ainew.from_type == AI_CITY)
+ p->ainew.temp = RandomRange(_total_towns);
+ else
+ p->ainew.temp = RandomRange(_total_industries);
+ }
+
+ if (!AiNew_Check_City_or_Industry(p, p->ainew.temp, p->ainew.from_type)) {
+ // It was not a valid city
+ // increase the temp with one, and return. We will come back later here
+ // to try again
+ p->ainew.temp++;
+ if (p->ainew.from_type == AI_CITY) {
+ if (p->ainew.temp >= _total_towns) p->ainew.temp = 0;
+ } else {
+ if (p->ainew.temp >= _total_industries) p->ainew.temp = 0;
+ }
+
+ // Don't do an attempt if we are trying the same id as the last time...
+ if (p->ainew.last_id == p->ainew.temp) return;
+ p->ainew.last_id = p->ainew.temp;
+
+ return;
+ }
+
+ // We found a good city/industry, save the data of it
+ p->ainew.from_ic = p->ainew.temp;
+
+ // Start the next tick with finding a to-city
+ p->ainew.temp = -1;
+ return;
+ }
+
+ // Find a to-city
+ if (p->ainew.temp == -1) {
+ // First, we pick a random spot to search to
+ if (p->ainew.to_type == AI_CITY)
+ p->ainew.temp = RandomRange(_total_towns);
+ else
+ p->ainew.temp = RandomRange(_total_industries);
+ }
+
+ // The same city is not allowed
+ // Also check if the city is valid
+ if (p->ainew.temp != p->ainew.from_ic && AiNew_Check_City_or_Industry(p, p->ainew.temp, p->ainew.to_type)) {
+ // Maybe it is valid..
+
+ // We need to know if they are not to far apart from eachother..
+ // We do that by checking how much cargo we have to move and how long the route
+ // is.
+
+ if (p->ainew.from_type == AI_CITY && p->ainew.tbt == AI_BUS) {
+ int max_cargo = DEREF_TOWN(p->ainew.from_ic)->max_pass + DEREF_TOWN(p->ainew.temp)->max_pass;
+ max_cargo -= DEREF_TOWN(p->ainew.from_ic)->act_pass + DEREF_TOWN(p->ainew.temp)->act_pass;
+ // max_cargo is now the amount of cargo we can move between the two cities
+ // If it is more then the distance, we allow it
+ if (GetTileDist(DEREF_TOWN(p->ainew.from_ic)->xy, DEREF_TOWN(p->ainew.temp)->xy) <= max_cargo * AI_LOCATEROUTE_BUS_CARGO_DISTANCE) {
+ // We found a good city/industry, save the data of it
+ p->ainew.to_ic = p->ainew.temp;
+ p->ainew.state = AI_STATE_FIND_STATION;
+
+ DEBUG(ai,1)("[AiNew - LocateRoute] Found bus-route of %d tiles long (from %d to %d)",GetTileDist(DEREF_TOWN(p->ainew.from_ic)->xy, DEREF_TOWN(p->ainew.temp)->xy), p->ainew.from_ic, p->ainew.temp);
+
+ p->ainew.from_tile = 0;
+ p->ainew.to_tile = 0;
+
+ return;
+ }
+ } else if (p->ainew.tbt == AI_TRUCK) {
+ bool found = false;
+ int max_cargo = 0;
+ int i;
+ // TODO: in max_cargo, also check other cargo (beside [0])
+ // First we check if the from_ic produces cargo that this ic accepts
+ if (DEREF_INDUSTRY(p->ainew.from_ic)->produced_cargo[0] != 0xFF && DEREF_INDUSTRY(p->ainew.from_ic)->total_production[0] != 0) {
+ for (i=0;i<3;i++) {
+ if (DEREF_INDUSTRY(p->ainew.temp)->accepts_cargo[i] == 0xFF) break;
+ if (DEREF_INDUSTRY(p->ainew.from_ic)->produced_cargo[0] == DEREF_INDUSTRY(p->ainew.temp)->accepts_cargo[i]) {
+ // Found a compatbiel industry
+ max_cargo = DEREF_INDUSTRY(p->ainew.from_ic)->total_production[0] - DEREF_INDUSTRY(p->ainew.from_ic)->total_transported[0];
+ found = true;
+ p->ainew.from_deliver = true;
+ p->ainew.to_deliver = false;
+ break;
+ }
+ }
+ }
+ if (!found && DEREF_INDUSTRY(p->ainew.temp)->produced_cargo[0] != 0xFF && DEREF_INDUSTRY(p->ainew.temp)->total_production[0] != 0) {
+ // If not check if the current ic produces cargo that the from_ic accepts
+ for (i=0;i<3;i++) {
+ if (DEREF_INDUSTRY(p->ainew.from_ic)->accepts_cargo[i] == 0xFF) break;
+ if (DEREF_INDUSTRY(p->ainew.temp)->produced_cargo[0] == DEREF_INDUSTRY(p->ainew.from_ic)->accepts_cargo[i]) {
+ // Found a compatbiel industry
+ found = true;
+ max_cargo = DEREF_INDUSTRY(p->ainew.temp)->total_production[0] - DEREF_INDUSTRY(p->ainew.from_ic)->total_transported[0];
+ p->ainew.from_deliver = false;
+ p->ainew.to_deliver = true;
+ break;
+ }
+ }
+ }
+ if (found) {
+ // Yeah, they are compatible!!!
+ // Check the length against the amount of goods
+ if (GetTileDist(DEREF_INDUSTRY(p->ainew.from_ic)->xy, DEREF_INDUSTRY(p->ainew.temp)->xy) > AI_LOCATEROUTE_TRUCK_MIN_DISTANCE &&
+ GetTileDist(DEREF_INDUSTRY(p->ainew.from_ic)->xy, DEREF_INDUSTRY(p->ainew.temp)->xy) <= max_cargo * AI_LOCATEROUTE_TRUCK_CARGO_DISTANCE) {
+ p->ainew.to_ic = p->ainew.temp;
+ if (p->ainew.from_deliver) {
+ p->ainew.cargo = DEREF_INDUSTRY(p->ainew.from_ic)->produced_cargo[0];
+ } else {
+ p->ainew.cargo = DEREF_INDUSTRY(p->ainew.temp)->produced_cargo[0];
+ }
+ p->ainew.state = AI_STATE_FIND_STATION;
+
+ DEBUG(ai,1)("[AiNew - LocateRoute] Found truck-route of %d tiles long (from %d to %d)",GetTileDist(DEREF_INDUSTRY(p->ainew.from_ic)->xy, DEREF_INDUSTRY(p->ainew.temp)->xy), p->ainew.from_ic, p->ainew.temp);
+
+ p->ainew.from_tile = 0;
+ p->ainew.to_tile = 0;
+
+ return;
+ }
+ }
+ }
+ }
+
+ // It was not a valid city
+ // increase the temp with one, and return. We will come back later here
+ // to try again
+ p->ainew.temp++;
+ if (p->ainew.to_type == AI_CITY) {
+ if (p->ainew.temp >= _total_towns) p->ainew.temp = 0;
+ } else {
+ if (p->ainew.temp >= _total_industries) p->ainew.temp = 0;
+ }
+
+ // Don't do an attempt if we are trying the same id as the last time...
+ if (p->ainew.last_id == p->ainew.temp) return;
+ p->ainew.last_id = p->ainew.temp;
+}
+
+// Check if there are not more then a certain amount of vehicles pointed to a certain
+// station. This to prevent 10 busses going to one station, which gives... problems ;)
+static bool AiNew_CheckVehicleStation(Player *p, Station *st) {
+ int count = 0;
+ Vehicle *v;
+ uint16 *sched;
+ uint16 ord;
+
+ // Also check if we don't have already a lot of busses to this city...
+ FOR_ALL_VEHICLES(v) {
+ if (v->owner == _current_player) {
+ sched = v->schedule_ptr;
+ while ((ord=*sched++) != 0) {
+ if ((ord & OT_MASK) == OT_GOTO_STATION && DEREF_STATION(ord >> 8) == st) {
+ // This vehicle has this city in his list
+ count++;
+ }
+ };
+ }
+ }
+
+ if (count > AI_CHECK_MAX_VEHICLE_PER_STATION) return false;
+ return true;
+}
+
+extern const byte _roadveh_speed[88];
+extern const byte _roadveh_capacity[88];
+
+// This function finds a good spot for a station
+static void AiNew_State_FindStation(Player *p) {
+ TileIndex tile;
+ Station *st;
+ int i, count = 0;
+ TileIndex new_tile = 0;
+ byte direction = 0;
+ Town *town = NULL;
+ Industry *industry = NULL;
+ assert(p->ainew.state == AI_STATE_FIND_STATION);
+
+ if (p->ainew.from_tile == 0) {
+ // First we scan for a station in the from-city
+ if (p->ainew.from_type == AI_CITY) {
+ town = DEREF_TOWN(p->ainew.from_ic);
+ tile = town->xy;
+ } else {
+ industry = DEREF_INDUSTRY(p->ainew.from_ic);
+ tile = industry->xy;
+ }
+ } else if (p->ainew.to_tile == 0) {
+ // Second we scan for a station in the to-city
+ if (p->ainew.to_type == AI_CITY) {
+ town = DEREF_TOWN(p->ainew.to_ic);
+ tile = town->xy;
+ } else {
+ industry = DEREF_INDUSTRY(p->ainew.to_ic);
+ tile = industry->xy;
+ }
+ } else {
+ // Unsupported request
+ // Go to FIND_PATH
+ p->ainew.temp = -1;
+ p->ainew.state = AI_STATE_FIND_PATH;
+ return;
+ }
+
+ // First, we are going to look at the stations that already exist inside the city
+ // If there is enough cargo left in the station, we take that station
+ // If that is not possible, and there are more then 2 stations in the city, abort
+ i = AiNew_PickVehicle(p);
+ // Euhmz, this should not happen _EVER_
+ // Quit finding a route...
+ if (i == -1) { p->ainew.state = AI_STATE_NOTHING; return; }
+
+ FOR_ALL_STATIONS(st) {
+ if (st->xy != 0) {
+ if (st->owner == _current_player) {
+ if (p->ainew.tbt == AI_BUS && (FACIL_BUS_STOP & st->facilities) == FACIL_BUS_STOP) {
+ if (st->town == town) {
+ // Check how much cargo there is left in the station
+ if ((st->goods[p->ainew.cargo].waiting_acceptance & 0xFFF) > _roadveh_capacity[i-ROAD_ENGINES_INDEX] * AI_STATION_REUSE_MULTIPLER) {
+ if (AiNew_CheckVehicleStation(p, st)) {
+ // We did found a station that was good enough!
+ new_tile = st->xy;
+ // Cheap way to get the direction of the station...
+ // Bus stations save it as 0x47 .. 0x4A, so decrease it with 0x47, and tada!
+ direction = _map5[st->xy] - 0x47;
+ break;
+ }
+ }
+ count++;
+ }
+ }
+ }
+ }
+ }
+ // We are going to add a new station...
+ if (new_tile == 0) count++;
+ // No more then 2 stations allowed in a city
+ // This is because only the best 2 stations of one cargo do get any cargo
+ if (count > 2) {
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+
+ if (new_tile == 0 && p->ainew.tbt == AI_BUS) {
+ uint x, y, i = 0;
+ int r;
+ uint best;
+ uint accepts[NUM_CARGO];
+ TileIndex found_spot[AI_FINDSTATION_TILE_RANGE*AI_FINDSTATION_TILE_RANGE*4];
+ uint found_best[AI_FINDSTATION_TILE_RANGE*AI_FINDSTATION_TILE_RANGE*4];
+ // To find a good spot we scan a range from the center, a get the point
+ // where we get the most cargo and where it is buildable.
+ // TODO: also check for station of myself and make sure we are not
+ // taking eachothers passangers away (bad result when it does not)
+ for (x = GET_TILE_X(tile) - AI_FINDSTATION_TILE_RANGE; x <= GET_TILE_X(tile) + AI_FINDSTATION_TILE_RANGE; x++) {
+ for (y = GET_TILE_Y(tile) - AI_FINDSTATION_TILE_RANGE; y <= GET_TILE_Y(tile) + AI_FINDSTATION_TILE_RANGE; y++) {
+ new_tile = TILE_XY(x,y);
+ if (IS_TILETYPE(new_tile, MP_CLEAR) || IS_TILETYPE(new_tile, MP_TREES)) {
+ // This tile we can build on!
+ // Check acceptance
+ GetAcceptanceAroundTiles(accepts, new_tile, 1, 1);
+ // >> 3 == 0 means no cargo
+ if (accepts[p->ainew.cargo] >> 3 == 0) continue;
+ // See if we can build the station
+ r = AiNew_Build_Station(p, p->ainew.tbt, new_tile, 0, 0, 0, DC_QUERY_COST);
+ if (r == CMD_ERROR) continue;
+ // We can build it, so add it to found_spot
+ found_spot[i] = new_tile;
+ found_best[i++] = accepts[p->ainew.cargo];
+ }
+ }
+ }
+
+ // If i is still zero, we did not found anything :(
+ if (i == 0) {
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+
+ // Go through all the found_best and check which has the highest value
+ best = 0;
+ new_tile = 0;
+
+ for (x=0;x<i;x++) {
+ if (found_best[x] > best ||
+ (found_best[x] == best && GetTileDist(tile, new_tile) > GetTileDist(tile, found_spot[x]))) {
+ new_tile = found_spot[x];
+ best = found_best[x];
+ }
+ }
+
+ // See how much it is going to cost us...
+ r = AiNew_Build_Station(p, p->ainew.tbt, new_tile, 0, 0, 0, DC_QUERY_COST);
+ p->ainew.new_cost += r;
+
+ direction = AI_PATHFINDER_NO_DIRECTION;
+ } else if (new_tile == 0 && p->ainew.tbt == AI_TRUCK) {
+ // Truck station locater works differently.. a station can be on any place
+ // as long as it is in range. So we give back code AI_STATION_RANGE
+ // so the pathfinder routine can work it out!
+ new_tile = AI_STATION_RANGE;
+ direction = AI_PATHFINDER_NO_DIRECTION;
+ }
+
+ if (p->ainew.from_tile == 0) {
+ p->ainew.from_tile = new_tile;
+ p->ainew.from_direction = direction;
+ // Now we found thisone, go in for to_tile
+ return;
+ } else if (p->ainew.to_tile == 0) {
+ p->ainew.to_tile = new_tile;
+ p->ainew.to_direction = direction;
+ // K, done placing stations!
+ p->ainew.temp = -1;
+ p->ainew.state = AI_STATE_FIND_PATH;
+ return;
+ }
+}
+
+// We try to find a path between 2 points
+static void AiNew_State_FindPath(Player *p) {
+ int r;
+ assert(p->ainew.state == AI_STATE_FIND_PATH);
+
+ // First time, init some data
+ if (p->ainew.temp == -1) {
+ // Init path_info
+ if (p->ainew.from_tile == AI_STATION_RANGE) {
+ // For truck routes we take a range around the industry
+ p->ainew.path_info.start_tile_tl = DEREF_INDUSTRY(p->ainew.from_ic)->xy - TILE_XY(1,1);
+ p->ainew.path_info.start_tile_br = DEREF_INDUSTRY(p->ainew.from_ic)->xy + TILE_XY(DEREF_INDUSTRY(p->ainew.from_ic)->width, DEREF_INDUSTRY(p->ainew.from_ic)->height) + TILE_XY(1,1);
+ p->ainew.path_info.start_direction = p->ainew.from_direction;
+ } else {
+ p->ainew.path_info.start_tile_tl = p->ainew.from_tile;
+ p->ainew.path_info.start_tile_br = p->ainew.from_tile;
+ p->ainew.path_info.start_direction = p->ainew.from_direction;
+ }
+
+ if (p->ainew.to_tile == AI_STATION_RANGE) {
+ p->ainew.path_info.end_tile_tl = DEREF_INDUSTRY(p->ainew.to_ic)->xy - TILE_XY(1,1);
+ p->ainew.path_info.end_tile_br = DEREF_INDUSTRY(p->ainew.to_ic)->xy + TILE_XY(DEREF_INDUSTRY(p->ainew.to_ic)->width, DEREF_INDUSTRY(p->ainew.to_ic)->height) + TILE_XY(1,1);
+ p->ainew.path_info.end_direction = p->ainew.to_direction;
+ } else {
+ p->ainew.path_info.end_tile_tl = p->ainew.to_tile;
+ p->ainew.path_info.end_tile_br = p->ainew.to_tile;
+ p->ainew.path_info.end_direction = p->ainew.to_direction;
+ }
+
+ if (p->ainew.tbt == AI_TRAIN)
+ p->ainew.path_info.rail_or_road = true;
+ else
+ p->ainew.path_info.rail_or_road = false;
+
+ // First, clean the pathfinder with our new begin and endpoints
+ clean_AyStar_AiPathFinder(p->ainew.pathfinder, &p->ainew.path_info);
+
+ p->ainew.temp = 0;
+ }
+
+ // Start the pathfinder
+ r = p->ainew.pathfinder->main(p->ainew.pathfinder);
+ // If it return: no match, stop it...
+ if (r == AYSTAR_NO_PATH) {
+ DEBUG(ai,1)("[AiNew] PathFinder found no route!");
+ // Start all over again...
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+ if (r == AYSTAR_FOUND_END_NODE) {
+ // We found the end-point
+ p->ainew.temp = -1;
+ p->ainew.state = AI_STATE_FIND_DEPOT;
+ return;
+ }
+ // In any other case, we are still busy finding the route...
+}
+
+// This function tries to locate a good place for a depot!
+static void AiNew_State_FindDepot(Player *p) {
+ // To place the depot, we walk through the route, and if we find a lovely spot (MP_CLEAR, MP_TREES), we place it there..
+ // Simple, easy, works!
+ // To make the depot stand in the middle of the route, we start from the center..
+ // But first we walk through the route see if we can find a depot that is ours
+ // this keeps things nice ;)
+ int g, i, j, r;
+ TileIndex tile;
+ assert(p->ainew.state == AI_STATE_FIND_DEPOT);
+
+ p->ainew.depot_tile = 0;
+
+ for (i=2;i<p->ainew.path_info.route_length-2;i++) {
+ tile = p->ainew.path_info.route[i];
+ for (j=0;j<lengthof(_tileoffs_by_dir);j++) {
+ if (IS_TILETYPE(tile + _tileoffs_by_dir[j], MP_STREET)) {
+ // Its a street, test if it is a depot
+ if (_map5[tile + _tileoffs_by_dir[j]] & 0x20) {
+ // We found a depot, is it ours? (TELL ME!!!)
+ if (_map_owner[tile + _tileoffs_by_dir[j]] == _current_player) {
+ // Now, is it pointing to the right direction.........
+ if ((_map5[tile + _tileoffs_by_dir[j]] & 3) == (j ^ 2)) {
+ // Yeah!!!
+ p->ainew.depot_tile = tile + _tileoffs_by_dir[j];
+ p->ainew.depot_direction = j ^ 2; // Reverse direction
+ p->ainew.state = AI_STATE_VERIFY_ROUTE;
+ return;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // This routine let depot finding start in the middle, and work his way to the stations
+ // It makes depot placing nicer :)
+ i = p->ainew.path_info.route_length / 2;
+ g = 1;
+ while (i > 1 && i < p->ainew.path_info.route_length - 2) {
+ i += g;
+ g *= -1;
+ (g < 0?g--:g++);
+
+ if (p->ainew.path_info.route_extra[i] != 0 || p->ainew.path_info.route_extra[i+1] != 0) {
+ // Bridge or tunnel.. we can't place a depot there
+ continue;
+ }
+
+ tile = p->ainew.path_info.route[i];
+
+ for (j=0;j<lengthof(_tileoffs_by_dir);j++) {
+ // It may not be placed on the road/rail itself
+ // And because it is not build yet, we can't see it on the tile..
+ // So check the surrounding tiles :)
+ if (tile + _tileoffs_by_dir[j] == p->ainew.path_info.route[i-1] ||
+ tile + _tileoffs_by_dir[j] == p->ainew.path_info.route[i+1]) continue;
+ // Not around a bridge?
+ if (p->ainew.path_info.route_extra[i] != 0) continue;
+ if (IS_TILETYPE(tile, MP_TUNNELBRIDGE)) continue;
+ // Is the terrain clear?
+ if (IS_TILETYPE(tile + _tileoffs_by_dir[j], MP_CLEAR) ||
+ IS_TILETYPE(tile + _tileoffs_by_dir[j], MP_TREES)) {
+ TileInfo ti;
+ FindLandscapeHeightByTile(&ti, tile);
+ // If the current tile is on a slope (tileh != 0) then we do not allow this
+ if (ti.tileh != 0) continue;
+ // Check if everything went okay..
+ r = AiNew_Build_Depot(p, tile + _tileoffs_by_dir[j], j ^ 2, 0);
+ if (r == CMD_ERROR) continue;
+ // Found a spot!
+ p->ainew.new_cost += r;
+ p->ainew.depot_tile = tile + _tileoffs_by_dir[j];
+ p->ainew.depot_direction = j ^ 2; // Reverse direction
+ p->ainew.state = AI_STATE_VERIFY_ROUTE;
+ return;
+ }
+ }
+ }
+
+ // Failed to find a depot?
+ p->ainew.state = AI_STATE_NOTHING;
+}
+
+
+// This function calculates how many vehicles there are needed on this
+// traject.
+// It works pretty simple: get the length, see how much we move around
+// and hussle that, and you know how many vehicles there are needed.
+// It returns the cost for the vehicles
+static int AiNew_HowManyVehicles(Player *p) {
+ if (p->ainew.tbt == AI_BUS) {
+ // For bus-routes we look at the time before we are back in the station
+ int i, length, tiles_a_day;
+ int amount;
+ i = AiNew_PickVehicle(p);
+ if (i == -1) return 0;
+ // Passenger run.. how long is the route?
+ length = p->ainew.path_info.route_length;
+ // Calculating tiles a day a vehicle moves is not easy.. this is how it must be done!
+ // ROAD_ENGINES_INDEX is because the first roadveh engine is ROAD_ENGINES_INDEX, and _roadveh_speed starts from 0
+ tiles_a_day = _roadveh_speed[i-ROAD_ENGINES_INDEX] * 74 / 256 / 16;
+ // We want a vehicle in a station once a month at least, so, calculate it!
+ // (the * 2 is because we have 2 stations ;))
+ amount = ((int)(((float)length / (float)tiles_a_day / 30 * 2))) * 2;
+ if (amount == 0) amount = 1;
+ return amount;
+ } else if (p->ainew.tbt == AI_TRUCK) {
+ // For truck-routes we look at the cargo
+ int i, length, amount, tiles_a_day;
+ int max_cargo;
+ i = AiNew_PickVehicle(p);
+ if (i == -1) return 0;
+ // Passenger run.. how long is the route?
+ length = p->ainew.path_info.route_length;
+ // Calculating tiles a day a vehicle moves is not easy.. this is how it must be done!
+ // ROAD_ENGINES_INDEX is because the first roadveh engine is ROAD_ENGINES_INDEX, and _roadveh_speed starts from 0
+ tiles_a_day = _roadveh_speed[i-ROAD_ENGINES_INDEX] * 74 / 256 / 16;
+ if (p->ainew.from_deliver)
+ max_cargo = DEREF_INDUSTRY(p->ainew.from_ic)->total_production[0];
+ else
+ max_cargo = DEREF_INDUSTRY(p->ainew.to_ic)->total_production[0];
+
+ // This is because moving 60% is more then we can dream of!
+ max_cargo *= 0.6;
+ // We want all the cargo to be gone in a month.. so, we know the cargo it delivers
+ // we know what the vehicle takes with him, and we know the time it takes him
+ // to get back here.. now let's do some math!
+ amount = (int)(((float)length / (float)tiles_a_day / 30 * 2) * ((float)max_cargo / (float)_roadveh_capacity[i-ROAD_ENGINES_INDEX]));
+ amount += 1;
+ return amount;
+ } else {
+ // Currently not supported
+ return 0;
+ }
+}
+
+
+// This function checks:
+// - If the route went okay
+// - Calculates the amount of money needed to build the route
+// - Calculates how much vehicles needed for the route
+static void AiNew_State_VerifyRoute(Player *p) {
+ int res, i;
+ assert(p->ainew.state == AI_STATE_VERIFY_ROUTE);
+
+ // Let's calculate the cost of the path..
+ // new_cost already contains the cost of the stations
+ p->ainew.path_info.position = -1;
+
+ do {
+ p->ainew.path_info.position++;
+ p->ainew.new_cost += AiNew_Build_RoutePart(p, &p->ainew.path_info, DC_QUERY_COST);
+ } while (p->ainew.path_info.position != -2);
+
+ // Now we know the price of build station + path. Now check how many vehicles
+ // we need and what the price for that will be
+ res = AiNew_HowManyVehicles(p);
+ // If res == 0, no vehicle was found, or an other problem did occour
+ if (res == 0) {
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+ p->ainew.amount_veh = res;
+ p->ainew.cur_veh = 0;
+
+ // Check how much it it going to cost us..
+ for (i=0;i<res;i++) {
+ p->ainew.new_cost += AiNew_Build_Vehicle(p, 0, DC_QUERY_COST);
+ }
+
+ // Now we know how much the route is going to cost us
+ // Check if we have enough money for it!
+ if (p->ainew.new_cost > p->player_money - AI_MINIMUM_MONEY) {
+ // Too bad..
+ DEBUG(ai,1)("[AiNew] Can't pay for this route (%d)", p->ainew.new_cost);
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+
+ // Now we can build the route, check the direction of the stations!
+ if (p->ainew.from_direction == AI_PATHFINDER_NO_DIRECTION) {
+ p->ainew.from_direction = AiNew_GetDirection(p->ainew.path_info.route[p->ainew.path_info.route_length-1], p->ainew.path_info.route[p->ainew.path_info.route_length-2]);
+ }
+ if (p->ainew.to_direction == AI_PATHFINDER_NO_DIRECTION) {
+ p->ainew.to_direction = AiNew_GetDirection(p->ainew.path_info.route[0], p->ainew.path_info.route[1]);
+ }
+ if (p->ainew.from_tile == AI_STATION_RANGE)
+ p->ainew.from_tile = p->ainew.path_info.route[p->ainew.path_info.route_length-1];
+ if (p->ainew.to_tile == AI_STATION_RANGE)
+ p->ainew.to_tile = p->ainew.path_info.route[0];
+
+ p->ainew.state = AI_STATE_BUILD_STATION;
+ p->ainew.temp = 0;
+
+ DEBUG(ai,1)("[AiNew] The route is set and buildable.. going to build it!");
+}
+
+// Build the stations
+static void AiNew_State_BuildStation(Player *p) {
+ int res = 0;
+ assert(p->ainew.state == AI_STATE_BUILD_STATION);
+ if (p->ainew.temp == 0) {
+ if (!IS_TILETYPE(p->ainew.from_tile, MP_STATION))
+ res = AiNew_Build_Station(p, p->ainew.tbt, p->ainew.from_tile, 0, 0, p->ainew.from_direction, DC_EXEC);
+ }
+ else {
+ if (!IS_TILETYPE(p->ainew.to_tile, MP_STATION))
+ res = AiNew_Build_Station(p, p->ainew.tbt, p->ainew.to_tile, 0, 0, p->ainew.to_direction, DC_EXEC);
+ p->ainew.state = AI_STATE_BUILD_PATH;
+ }
+ if (res == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildStation] Strange but true... station can not be build!");
+ p->ainew.state = AI_STATE_NOTHING;
+ // If the first station _was_ build, destroy it
+ if (p->ainew.temp != 0)
+ DoCommandByTile(p->ainew.from_tile, 0, 0, DC_EXEC, CMD_LANDSCAPE_CLEAR);
+ return;
+ }
+ p->ainew.temp++;
+}
+
+// Build the path
+static void AiNew_State_BuildPath(Player *p) {
+ assert(p->ainew.state == AI_STATE_BUILD_PATH);
+ // p->ainew.temp is set to -1 when this function is called for the first time
+ if (p->ainew.temp == -1) {
+ DEBUG(ai,1)("[AiNew] Starting to build the path..");
+ // Init the counter
+ p->ainew.counter = (4 - _opt.diff.competitor_speed) * AI_BUILDPATH_PAUSE + 1;
+ // Set the position to the startingplace (-1 because in a minute we do ++)
+ p->ainew.path_info.position = -1;
+ // And don't do this again
+ p->ainew.temp = 0;
+ }
+ // Building goes very fast on normal rate, so we are going to slow it down..
+ // By let the counter count from AI_BUILDPATH_PAUSE to 0, we have a nice way :)
+ if (--p->ainew.counter != 0) return;
+ p->ainew.counter = (4 - _opt.diff.competitor_speed) * AI_BUILDPATH_PAUSE + 1;
+
+ // Increase the building position
+ p->ainew.path_info.position++;
+ // Build route
+ AiNew_Build_RoutePart(p, &p->ainew.path_info, DC_EXEC);
+ if (p->ainew.path_info.position == -2) {
+ // This means we are done building!
+
+ if (p->ainew.tbt == AI_TRUCK && !_patches.roadveh_queue) {
+ static const byte _roadbits_by_dir[4] = {2,1,8,4};
+ // If they not queue, they have to go up and down to try again at a station...
+ // We don't want that, so try building some road left or right of the station
+ short dir1, dir2, dir3;
+ TileIndex tile;
+ int i, r;
+ for (i=0;i<2;i++) {
+ if (i == 0) {
+ tile = p->ainew.from_tile + _tileoffs_by_dir[p->ainew.from_direction];
+ dir1 = p->ainew.from_direction - 1;
+ if (dir1 < 0) dir1 = 3;
+ dir2 = p->ainew.from_direction + 1;
+ if (dir2 > 3) dir2 = 0;
+ dir3 = p->ainew.from_direction;
+ } else {
+ tile = p->ainew.to_tile + _tileoffs_by_dir[p->ainew.to_direction];
+ dir1 = p->ainew.to_direction - 1;
+ if (dir1 < 0) dir1 = 3;
+ dir2 = p->ainew.to_direction + 1;
+ if (dir2 > 3) dir2 = 0;
+ dir3 = p->ainew.to_direction;
+ }
+
+ DoCommandByTile(tile, _roadbits_by_dir[dir1], 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ DoCommandByTile(tile, _roadbits_by_dir[dir2], 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ DoCommandByTile(tile, _roadbits_by_dir[dir3^2], 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+
+ dir1 = _tileoffs_by_dir[dir1];
+ dir2 = _tileoffs_by_dir[dir2];
+ dir3 = _tileoffs_by_dir[dir3];
+ r = CMD_ERROR;
+ if (IS_TILETYPE(tile+dir1, MP_CLEAR) || IS_TILETYPE(tile+dir1, MP_TREES))
+ r = DoCommandByTile(tile+dir1, AiNew_GetRoadDirection(tile, tile+dir1, tile+dir1+dir1), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ if (r != CMD_ERROR)
+ if (IS_TILETYPE(tile+dir1+dir1, MP_CLEAR) || IS_TILETYPE(tile+dir1+dir1, MP_TREES))
+ DoCommandByTile(tile+dir1+dir1, AiNew_GetRoadDirection(tile+dir1, tile+dir1+dir1, tile+dir1+dir1+dir1), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+
+ r = CMD_ERROR;
+ if (IS_TILETYPE(tile+dir2, MP_CLEAR) || IS_TILETYPE(tile+dir2, MP_TREES))
+ DoCommandByTile(tile+dir2, AiNew_GetRoadDirection(tile, tile+dir2, tile+dir2+dir2), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ if (r != CMD_ERROR)
+ if (IS_TILETYPE(tile+dir2+dir2, MP_CLEAR) || IS_TILETYPE(tile+dir2+dir2, MP_TREES))
+ DoCommandByTile(tile+dir2+dir2, AiNew_GetRoadDirection(tile+dir2, tile+dir2+dir2, tile+dir2+dir2+dir2), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+
+ r = CMD_ERROR;
+ if (IS_TILETYPE(tile+dir3, MP_CLEAR) || IS_TILETYPE(tile+dir3, MP_TREES))
+ DoCommandByTile(tile+dir3, AiNew_GetRoadDirection(tile, tile+dir3, tile+dir3+dir3), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ if (r != CMD_ERROR)
+ if (IS_TILETYPE(tile+dir3+dir3, MP_CLEAR) || IS_TILETYPE(tile+dir3+dir3, MP_TREES))
+ DoCommandByTile(tile+dir3+dir3, AiNew_GetRoadDirection(tile+dir3, tile+dir3+dir3, tile+dir3+dir3+dir3), 0, DC_EXEC | DC_NO_WATER, CMD_BUILD_ROAD);
+ }
+ }
+
+
+ DEBUG(ai,1)("[AiNew] Done building the path (cost: %d)", p->ainew.new_cost);
+ p->ainew.state = AI_STATE_BUILD_DEPOT;
+ }
+}
+
+// Builds the depot
+static void AiNew_State_BuildDepot(Player *p) {
+ int res = 0;
+ assert(p->ainew.state == AI_STATE_BUILD_DEPOT);
+
+ if (IS_TILETYPE(p->ainew.depot_tile, MP_STREET) && _map5[p->ainew.depot_tile] & 0x20) {
+ if (_map_owner[p->ainew.depot_tile] == _current_player) {
+ // The depot is already builded!
+ p->ainew.state = AI_STATE_BUILD_VEHICLE;
+ return;
+ } else {
+ // There is a depot, but not of our team! :(
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+ }
+
+ // There is a bus on the tile we want to build road on... idle till he is gone! (BAD PERSON! :p)
+ if (!EnsureNoVehicle(p->ainew.depot_tile + _tileoffs_by_dir[p->ainew.depot_direction]))
+ return;
+
+ res = AiNew_Build_Depot(p, p->ainew.depot_tile, p->ainew.depot_direction, DC_EXEC);
+ if (res == CMD_ERROR) {
+ DEBUG(ai,0)("[AiNew - BuildDepot] Strange but true... depot can not be build!");
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+
+ p->ainew.state = AI_STATE_BUILD_VEHICLE;
+ p->ainew.idle = 1;
+ p->ainew.veh_main_id = (VehicleID)-1;
+}
+
+// Build vehicles
+static void AiNew_State_BuildVehicle(Player *p) {
+ int res;
+ assert(p->ainew.state == AI_STATE_BUILD_VEHICLE);
+
+ // Check if we need to build a vehicle
+ if (p->ainew.amount_veh == 0) {
+ // Nope, we are done!
+ // This means: we are all done! The route is open.. go back to NOTHING
+ // He will idle some time and it will all start over again.. :)
+ p->ainew.state = AI_STATE_ACTION_DONE;
+ return;
+ }
+ if (--p->ainew.idle != 0) return;
+ // It is realistic that the AI can only build 1 vehicle a day..
+ // This makes sure of that!
+ p->ainew.idle = AI_BUILD_VEHICLE_TIME_BETWEEN;
+
+ // Build the vehicle
+ res = AiNew_Build_Vehicle(p, p->ainew.depot_tile, DC_EXEC);
+ if (res == CMD_ERROR) {
+ // This happens when the AI can't build any more vehicles!
+ p->ainew.state = AI_STATE_NOTHING;
+ return;
+ }
+ // Increase the current counter
+ p->ainew.cur_veh++;
+ // Decrease the total counter
+ p->ainew.amount_veh--;
+ // Get the new ID
+ if (p->ainew.tbt == AI_TRAIN) {
+ } else {
+ p->ainew.veh_id = _new_roadveh_id;
+ }
+ // Go give some orders!
+ p->ainew.state = AI_STATE_GIVE_ORDERS;
+}
+
+// Put the stations in the order list
+static void AiNew_State_GiveOrders(Player *p) {
+ int order, flags;
+ assert(p->ainew.state == AI_STATE_GIVE_ORDERS);
+
+ if (p->ainew.veh_main_id != (VehicleID)-1) {
+ DoCommandByTile(0, p->ainew.veh_id + (p->ainew.veh_main_id << 16), 0, DC_EXEC, CMD_CLONE_ORDER);
+
+ // Skip the first order if it is a second vehicle
+ // This to make vehicles go different ways..
+ if (p->ainew.veh_id & 1)
+ DoCommandByTile(0, p->ainew.veh_id, 0, DC_EXEC, CMD_SKIP_ORDER);
+ p->ainew.state = AI_STATE_START_VEHICLE;
+ return;
+ } else {
+ p->ainew.veh_main_id = p->ainew.veh_id;
+ }
+
+ // When more then 1 vehicle, we send them to different directions
+ order = 0;
+ flags = (_map2[p->ainew.from_tile] << 8) | OT_GOTO_STATION;
+ if (p->ainew.tbt == AI_TRUCK && p->ainew.from_deliver)
+ flags |= OF_FULL_LOAD;
+ DoCommandByTile(0, p->ainew.veh_id + (order << 16), flags, DC_EXEC, CMD_INSERT_ORDER);
+
+ order = 1;
+ flags = (_map2[p->ainew.to_tile] << 8) | OT_GOTO_STATION;
+ if (p->ainew.tbt == AI_TRUCK && p->ainew.to_deliver)
+ flags |= OF_FULL_LOAD;
+ DoCommandByTile(0, p->ainew.veh_id + (order << 16), flags, DC_EXEC, CMD_INSERT_ORDER);
+
+ // Very handy for AI, goto depot.. but yeah, it needs to be activated ;)
+ if (_patches.gotodepot) {
+ order = 2;
+ flags = (GetDepotByTile(p->ainew.depot_tile) << 8) | OT_GOTO_DEPOT | OF_UNLOAD;
+ DoCommandByTile(0, p->ainew.veh_id + (order << 16), flags, DC_EXEC, CMD_INSERT_ORDER);
+ }
+
+ // Start the engines!
+ p->ainew.state = AI_STATE_START_VEHICLE;
+}
+
+// Start the vehicle
+static void AiNew_State_StartVehicle(Player *p) {
+ assert(p->ainew.state == AI_STATE_START_VEHICLE);
+
+ // 3, 2, 1... go! (give START_STOP command ;))
+ DoCommandByTile(0, p->ainew.veh_id, 0, DC_EXEC, CMD_START_STOP_ROADVEH);
+ // Try to build an other vehicle (that function will stop building when needed)
+ p->ainew.state = AI_STATE_BUILD_VEHICLE;
+}
+
+// Repays money
+static void AiNew_State_RepayMoney(Player *p) {
+ int i;
+ for (i=0;i<AI_LOAN_REPAY;i++)
+ DoCommandByTile(0, _current_player, 0, DC_EXEC, CMD_DECREASE_LOAN);
+ p->ainew.state = AI_STATE_ACTION_DONE;
+}
+
+// Using the technique simular to the original AI
+// Keeps things logical
+// It really should be in the same order as the AI_STATE's are!
+static AiNew_StateFunction* const _ainew_state[] = {
+ NULL,
+ AiNew_State_FirstTime,
+ AiNew_State_Nothing,
+ AiNew_State_WakeUp,
+ AiNew_State_LocateRoute,
+ AiNew_State_FindStation,
+ AiNew_State_FindPath,
+ AiNew_State_FindDepot,
+ AiNew_State_VerifyRoute,
+ AiNew_State_BuildStation,
+ AiNew_State_BuildPath,
+ AiNew_State_BuildDepot,
+ AiNew_State_BuildVehicle,
+ AiNew_State_GiveOrders,
+ AiNew_State_StartVehicle,
+ AiNew_State_RepayMoney,
+ AiNew_State_ActionDone,
+ NULL,
+};
+
+static void AiNew_OnTick(Player *p) {
+ if (_ainew_state[p->ainew.state] != NULL)
+ _ainew_state[p->ainew.state](p);
+}
+
+void AiNewDoGameLoop(Player *p) {
+ // If it is a human player, it is not an AI, so bubye!
+ if (IS_HUMAN_PLAYER(_current_player))
+ return;
+
+ if (p->ainew.state == AI_STATE_STARTUP) {
+ // The AI just got alive!
+ p->ainew.state = AI_STATE_FIRST_TIME;
+ p->ainew.tick = 0;
+
+ // Only startup the AI
+ return;
+ }
+
+ // We keep a ticker. We use it for competitor_speed
+ p->ainew.tick++;
+
+ // See what the speed is
+ switch (_opt.diff.competitor_speed) {
+ case 0: // Very slow
+ if (!(p->ainew.tick&8)) return;
+ break;
+ case 1: // Slow
+ if (!(p->ainew.tick&4)) return;
+ break;
+ case 2:
+ if (!(p->ainew.tick&2)) return;
+ break;
+ case 3:
+ if (!(p->ainew.tick&1)) return;
+ break;
+ case 4: // Very fast
+ default: // Cool, a new speed setting.. ;) VERY fast ;)
+ break;
+ }
+
+ // If we come here, we can do a tick.. do so!
+ AiNew_OnTick(p);
+}
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;
+}
diff --git a/ai_shared.c b/ai_shared.c new file mode 100644 index 000000000..192651c82 --- /dev/null +++ b/ai_shared.c @@ -0,0 +1,82 @@ +#include "stdafx.h"
+#include "ttd.h"
+#include "player.h"
+#include "ai.h"
+
+int AiNew_GetRailDirection(uint tile_a, uint tile_b, uint tile_c) {
+ // 0 = vert
+ // 1 = horz
+ // 2 = dig up-left
+ // 3 = dig down-right
+ // 4 = dig down-left
+ // 5 = dig up-right
+
+ int x1, x2, x3;
+ int y1, y2, y3;
+
+ x1 = GET_TILE_X(tile_a);
+ x2 = GET_TILE_X(tile_b);
+ x3 = GET_TILE_X(tile_c);
+
+ y1 = GET_TILE_Y(tile_a);
+ y2 = GET_TILE_Y(tile_b);
+ y3 = GET_TILE_Y(tile_c);
+
+ if (y1 == y2 && y2 == y3) return 0;
+ if (x1 == x2 && x2 == x3) return 1;
+ if (y2 > y1) {
+ if (x2 > x3) return 2;
+ else return 4;
+ }
+ if (x2 > x1) {
+ if (y2 > y3) return 2;
+ else return 5;
+ }
+ if (y1 > y2) {
+ if (x2 > x3) return 5;
+ else return 3;
+ }
+ if (x1 > x2) {
+ if (y2 > y3) return 4;
+ else return 3;
+ }
+
+ return 0;
+}
+
+int AiNew_GetRoadDirection(uint tile_a, uint tile_b, uint tile_c) {
+ int x1, x2, x3;
+ int y1, y2, y3;
+ int r;
+
+ x1 = GET_TILE_X(tile_a);
+ x2 = GET_TILE_X(tile_b);
+ x3 = GET_TILE_X(tile_c);
+
+ y1 = GET_TILE_Y(tile_a);
+ y2 = GET_TILE_Y(tile_b);
+ y3 = GET_TILE_Y(tile_c);
+
+ r = 0;
+
+ if (x1 < x2) r += 8;
+ if (y1 < y2) r += 1;
+ if (x1 > x2) r += 2;
+ if (y1 > y2) r += 4;
+
+ if (x2 < x3) r += 2;
+ if (y2 < y3) r += 4;
+ if (x2 > x3) r += 8;
+ if (y2 > y3) r += 1;
+
+ return r;
+}
+
+// Get's the direction between 2 tiles seen from tile_a
+int AiNew_GetDirection(uint tile_a, uint tile_b) {
+ if (GET_TILE_Y(tile_a) < GET_TILE_Y(tile_b)) return 1;
+ if (GET_TILE_Y(tile_a) > GET_TILE_Y(tile_b)) return 3;
+ if (GET_TILE_X(tile_a) < GET_TILE_X(tile_b)) return 2;
+ return 0;
+}
+
diff --git a/aircraft_cmd.c b/aircraft_cmd.c index a9fad4326..15e5a7640 100644 --- a/aircraft_cmd.c +++ b/aircraft_cmd.c @@ -272,7 +272,8 @@ int32 CmdBuildAircraft(int x, int y, uint32 flags, uint32 p1, uint32 p2) *(v->schedule_ptr = _ptr_to_next_order++) = 0; // the AI doesn't click on a tile to build airplanes, so the below code will // never work. Therefore just assume the AI's planes always come from Hangar0 - v->u.air.pos = (_is_ai_player) ? 0:MAX_ELEMENTS; + // On hold for NewAI + v->u.air.pos = (!_patches.ainew_active && _is_ai_player) ? 0:MAX_ELEMENTS; /* When we click on hangar we know the tile (it is in var 'tile')it is on. By that we know its position in the array of depots the airport has.....we can search diff --git a/aystar.c b/aystar.c new file mode 100644 index 000000000..cd7c40214 --- /dev/null +++ b/aystar.c @@ -0,0 +1,271 @@ +/*
+ * This file has the core function for AyStar
+ * AyStar is a fast pathfinding routine and is used for things like
+ * AI_pathfinding and Train_pathfinding.
+ * For more information about AyStar (A* Algorithm), you can look at
+ * http://en.wikipedia.org/wiki/A-star_search_algorithm
+ */
+
+/*
+ * Friendly reminder:
+ * Call (AyStar).free() when you are done with Aystar. It reserves a lot of memory
+ * And when not free'd, it can cause system-crashes.
+ * Also remember that when you stop an algorithm before it is finished, your
+ * should call clear() yourself!
+ */
+
+#include "stdafx.h"
+#include "ttd.h"
+#include "aystar.h"
+// This looks in the Hash if a node exists in ClosedList
+// If so, it returns the PathNode, else NULL
+PathNode *AyStarMain_ClosedList_IsInList(AyStar *aystar, AyStarNode *node) {
+ return (PathNode*)Hash_Get(&aystar->ClosedListHash, node->tile, node->direction);
+}
+
+// This adds a node to the ClosedList
+// It makes a copy of the data
+void AyStarMain_ClosedList_Add(AyStar *aystar, PathNode *node) {
+ // Add a node to the ClosedList
+ PathNode *new_node = malloc(sizeof(PathNode));
+ *new_node = *node;
+ Hash_Set(&aystar->ClosedListHash, node->node.tile, node->node.direction, new_node);
+}
+
+// Checks if a node is in the OpenList
+// If so, it returns the OpenListNode, else NULL
+OpenListNode *AyStarMain_OpenList_IsInList(AyStar *aystar, AyStarNode *node) {
+ return (OpenListNode*)Hash_Get(&aystar->OpenListHash, node->tile, node->direction);
+}
+
+// Gets the best node from OpenList
+// returns the best node, or NULL of none is found
+// Also it deletes the node from the OpenList
+OpenListNode *AyStarMain_OpenList_Pop(AyStar *aystar) {
+ // Return the item the Queue returns.. the best next OpenList item.
+ OpenListNode* res = (OpenListNode*)aystar->OpenListQueue.pop(&aystar->OpenListQueue);
+ if (res != NULL)
+ Hash_Delete(&aystar->OpenListHash, res->path.node.tile, res->path.node.direction);
+
+ return res;
+}
+
+// Adds a node to the OpenList
+// It makes a copy of node, and puts the pointer of parent in the struct
+void AyStarMain_OpenList_Add(AyStar *aystar, PathNode *parent, AyStarNode *node, int f, int g, int userdata) {
+ // Add a new Node to the OpenList
+ OpenListNode* new_node = malloc(sizeof(OpenListNode));
+ new_node->g = g;
+ new_node->path.parent = parent;
+ new_node->path.node = *node;
+ Hash_Set(&aystar->OpenListHash, node->tile, node->direction, new_node);
+
+ // Add it to the queue
+ aystar->OpenListQueue.push(&aystar->OpenListQueue, new_node, f);
+}
+
+/*
+ * Checks one tile and calculate his f-value
+ * return values:
+ * AYSTAR_DONE : indicates we are done
+ */
+int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent) {
+ int new_f, new_g, new_h;
+ PathNode *closedlist_parent;
+ OpenListNode *check;
+
+ // Check the new node against the ClosedList
+ if (AyStarMain_ClosedList_IsInList(aystar, current) != NULL) return AYSTAR_DONE;
+
+ // Calculate the G-value for this node
+ new_g = aystar->CalculateG(aystar, current, parent);
+ // If the value was INVALID_NODE, we don't do anything with this node
+ if (new_g == AYSTAR_INVALID_NODE) return AYSTAR_DONE;
+
+ // There should not be given any other error-code..
+ assert(new_g >= 0);
+ // Add the parent g-value to the new g-value
+ new_g += parent->g;
+ if (aystar->max_path_cost != 0 && (uint)new_g > aystar->max_path_cost) return AYSTAR_DONE;
+
+ // Calculate the h-value
+ new_h = aystar->CalculateH(aystar, current, parent);
+ // There should not be given any error-code..
+ assert(new_h >= 0);
+
+ // The f-value if g + h
+ new_f = new_g + new_h;
+
+ // Get the pointer to the parent in the ClosedList (the currentone is to a copy of the one in the OpenList)
+ closedlist_parent = AyStarMain_ClosedList_IsInList(aystar, &parent->path.node);
+
+ // Check if this item is already in the OpenList
+ if ((check = AyStarMain_OpenList_IsInList(aystar, current)) != NULL) {
+ int i;
+ // Yes, check if this g value is lower..
+ if (new_g > check->g) return AYSTAR_DONE;
+ aystar->OpenListQueue.del(&aystar->OpenListQueue, check, 0);
+ // It is lower, so change it to this item
+ check->g = new_g;
+ check->path.parent = closedlist_parent;
+ /* Copy user data, will probably have changed */
+ for (i=0;i<lengthof(current->user_data);i++)
+ check->path.node.user_data[i] = current->user_data[i];
+ // Readd him in the OpenListQueue
+ 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);
+ }
+
+ return AYSTAR_DONE;
+}
+
+/*
+ * This function is the core of AyStar. It handles one item and checks
+ * his neighbour items. If they are valid, they are added to be checked too.
+ * return values:
+ * AYSTAR_EMPTY_OPENLIST : indicates all items are tested, and no path
+ * has been found.
+ * AYSTAR_LIMIT_REACHED : Indicates that the max_nodes limit has been
+ * reached.
+ * AYSTAR_FOUND_END_NODE : indicates we found the end. Path_found now is true, and in path is the path found.
+ * AYSTAR_STILL_BUSY : indicates we have done this tile, did not found the path yet, and have items left to try.
+ */
+int AyStarMain_Loop(AyStar *aystar) {
+ int i, r;
+
+ // Get the best node from OpenList
+ OpenListNode *current = AyStarMain_OpenList_Pop(aystar);
+ // If empty, drop an error
+ if (current == NULL) return AYSTAR_EMPTY_OPENLIST;
+
+ // Check for end node and if found, return that code
+ if (aystar->EndNodeCheck(aystar, current) == AYSTAR_FOUND_END_NODE) {
+ if (aystar->FoundEndNode != NULL)
+ aystar->FoundEndNode(aystar, current);
+ free(current);
+ return AYSTAR_FOUND_END_NODE;
+ }
+
+ // Add the node to the ClosedList
+ AyStarMain_ClosedList_Add(aystar, ¤t->path);
+
+ // Load the neighbours
+ aystar->GetNeighbours(aystar, current);
+
+ // Go through all neighbours
+ for (i=0;i<aystar->num_neighbours;i++) {
+ // Check and add them to the OpenList if needed
+ r = aystar->checktile(aystar, &aystar->neighbours[i], current);
+ }
+
+ // Free the node
+ free(current);
+
+ if (aystar->max_search_nodes != 0 && Hash_Size(&aystar->ClosedListHash) >= aystar->max_search_nodes)
+ /* We've expanded enough nodes */
+ return AYSTAR_LIMIT_REACHED;
+ else
+ // Return that we are still busy
+ return AYSTAR_STILL_BUSY;
+}
+
+/*
+ * This function frees the memory it allocated
+ */
+void AyStarMain_Free(AyStar *aystar) {
+ aystar->OpenListQueue.free(&aystar->OpenListQueue, false);
+ /* 2nd argument above is false, below is true, to free the values only
+ * once */
+ delete_Hash(&aystar->OpenListHash, true);
+ delete_Hash(&aystar->ClosedListHash, true);
+#ifdef AYSTAR_DEBUG
+ printf("[AyStar] Memory free'd\n");
+#endif
+}
+
+/*
+ * This function make the memory go back to zero
+ * This function should be called when you are using the same instance again.
+ */
+void AyStarMain_Clear(AyStar *aystar) {
+ // Clean the Queue, but not the elements within. That will be done by
+ // the hash.
+ aystar->OpenListQueue.clear(&aystar->OpenListQueue, false);
+ // Clean the hashes
+ clear_Hash(&aystar->OpenListHash, true);
+ clear_Hash(&aystar->ClosedListHash, true);
+
+#ifdef AYSTAR_DEBUG
+ printf("[AyStar] Cleared AyStar\n");
+#endif
+}
+
+/*
+ * This is the function you call to run AyStar.
+ * return values:
+ * AYSTAR_FOUND_END_NODE : indicates we found an end node.
+ * AYSTAR_NO_PATH : indicates that there was no path found.
+ * AYSTAR_STILL_BUSY : indicates we have done some checked, that we did not found the path yet, and that we still have items left to try.
+ * When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY)
+ * aystar->clear() is called. Note that when you stop the algorithm halfway,
+ * you should still call clear() yourself!
+ */
+int AyStarMain_Main(AyStar *aystar) {
+ int r, i = 0;
+ // Loop through the OpenList
+ // Quit if result is no AYSTAR_STILL_BUSY or is more then loops_per_tick
+ while ((r = aystar->loop(aystar)) == AYSTAR_STILL_BUSY && (aystar->loops_per_tick == 0 || ++i < aystar->loops_per_tick)) { }
+#ifdef AYSTAR_DEBUG
+ if (r == AYSTAR_FOUND_END_NODE)
+ printf("[AyStar] Found path!\n");
+ else if (r == AYSTAR_EMPTY_OPENLIST)
+ printf("[AyStar] OpenList run dry, no path found\n");
+ else if (r == AYSTAR_LIMIT_REACHED)
+ printf("[AyStar] Exceeded search_nodes, no path found\n");
+#endif
+ if (r != AYSTAR_STILL_BUSY)
+ /* We're done, clean up */
+ aystar->clear(aystar);
+
+ // Check result-value
+ if (r == AYSTAR_FOUND_END_NODE) return AYSTAR_FOUND_END_NODE;
+ // Check if we have some left in the OpenList
+ if (r == AYSTAR_EMPTY_OPENLIST || r == AYSTAR_LIMIT_REACHED) return AYSTAR_NO_PATH;
+
+ // Return we are still busy
+ return AYSTAR_STILL_BUSY;
+}
+
+/*
+ * Adds a node from where to start an algorithm. Multiple nodes can be added
+ * 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
+ */
+void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node) {
+#ifdef AYSTAR_DEBUG
+ printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n", GET_TILE_X(start_node->tile), GET_TILE_Y(start_node->tile), start_node->direction);
+#endif
+ AyStarMain_OpenList_Add(aystar, NULL, start_node, 0, 0, 0);
+}
+
+void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets) {
+ // Allocated the Hash for the OpenList and ClosedList
+ init_Hash(&aystar->OpenListHash, hash, num_buckets);
+ init_Hash(&aystar->ClosedListHash, hash, num_buckets);
+
+ // Set up our sorting queue
+ // BinaryHeap allocates a block of 1024 nodes
+ // When thatone gets full it reserves an otherone, till this number
+ // That is why it can stay this high
+ init_BinaryHeap(&aystar->OpenListQueue, 102400);
+
+ aystar->addstart = AyStarMain_AddStartNode;
+ aystar->main = AyStarMain_Main;
+ aystar->loop = AyStarMain_Loop;
+ aystar->free = AyStarMain_Free;
+ aystar->clear = AyStarMain_Clear;
+ aystar->checktile = AyStarMain_CheckTile;
+}
diff --git a/aystar.h b/aystar.h new file mode 100644 index 000000000..bb2cad15d --- /dev/null +++ b/aystar.h @@ -0,0 +1,169 @@ +/* + * This file has the header for AyStar + * AyStar is a fast pathfinding routine and is used for things like + * AI_pathfinding and Train_pathfinding. + * For more information about AyStar (A* Algorithm), you can look at + * http://en.wikipedia.org/wiki/A-star_search_algorithm + */ + +#ifndef AYSTAR_H +#define AYSTAR_H + +#include "queue.h" + +//#define AYSTAR_DEBUG +enum { + AYSTAR_FOUND_END_NODE, + AYSTAR_EMPTY_OPENLIST, + AYSTAR_STILL_BUSY, + AYSTAR_NO_PATH, + AYSTAR_LIMIT_REACHED, + AYSTAR_DONE +}; + +enum{ + AYSTAR_INVALID_NODE = -1, +}; + +typedef struct AyStarNode AyStarNode; +struct AyStarNode { + uint tile; + uint direction; + uint user_data[2]; +}; + +// The resulting path has nodes looking like this. +typedef struct PathNode PathNode; +struct PathNode { + AyStarNode node; + // The parent of this item + PathNode *parent; +}; + +// For internal use only +// We do not save the h-value, because it is only needed to calculate the f-value. +// h-value should _always_ be the distance left to the end-tile. +typedef struct OpenListNode OpenListNode; +struct OpenListNode { + int g; + PathNode path; +}; + +typedef struct AyStar AyStar; +/* + * This function is called to check if the end-tile is found + * return values can be: + * AYSTAR_FOUND_END_NODE : indicates this is the end tile + * AYSTAR_DONE : indicates this is not the end tile (or direction was wrong) + */ +typedef int32 AyStar_EndNodeCheck(AyStar *aystar, OpenListNode *current); + +/* + * This function is called to calculate the G-value for AyStar Algorithm. + * return values can be: + * AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable) + * Any value >= 0 : the g-value for this tile + */ +typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent); + +/* + * This function is called to calculate the H-value for AyStar Algorithm. + * Mostly, this must result the distance (Manhattan way) between the + * current point and the end point + * return values can be: + * Any value >= 0 : the h-value for this tile + */ +typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent); + +/* + * This function request the tiles around the current tile and put them in tiles_around + * tiles_around is never resetted, so if you are not using directions, just leave it alone. + * Warning: never add more tiles_around than memory allocated for it. + */ +typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current); + +/* + * If the End Node is found, this function is called. + * It can do, for example, calculate the route and put that in an array + */ +typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current); + +// For internal use, see aystar.c +typedef void AyStar_AddStartNode(AyStar *aystar, AyStarNode* start_node); +typedef int AyStar_Main(AyStar *aystar); +typedef int AyStar_Loop(AyStar *aystar); +typedef int AyStar_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent); +typedef void AyStar_Free(AyStar *aystar); +typedef void AyStar_Clear(AyStar *aystar); + +struct AyStar { +/* These fields should be filled before initting the AyStar, but not changed + * afterwards (except for user_data and user_path)! (free and init again to change them) */ + + /* These should point to the application specific routines that do the + * actual work */ + AyStar_CalculateG* CalculateG; + AyStar_CalculateH* CalculateH; + AyStar_GetNeighbours* GetNeighbours; + AyStar_EndNodeCheck* EndNodeCheck; + AyStar_FoundEndNode* FoundEndNode; + + /* These are completely untouched by AyStar, they can be accesed by + * the application specific routines to input and output data. + * user_path should typically contain data about the resulting path + * afterwards, user_target should typically contain information about + * what where looking for, and user_data can contain just about + * everything */ + void *user_path; + void *user_target; + uint user_data[10]; + + /* How many loops are there called before AyStarMain_Main gives + * control back to the caller. 0 = until done */ + byte loops_per_tick; + /* If the g-value goes over this number, it stops searching + * 0 = infinite */ + uint max_path_cost; + /* The maximum amount of nodes that will be expanded, 0 = infinite */ + uint max_search_nodes; + + /* These should be filled with the neighbours of a tile by + * GetNeighbours */ + AyStarNode neighbours[12]; + byte num_neighbours; + + /* These will contain the methods for manipulating the AyStar. Only + * main() should be called externally */ + AyStar_AddStartNode* addstart; + AyStar_Main* main; + AyStar_Loop* loop; + AyStar_Free* free; + AyStar_Clear* clear; + AyStar_CheckTile* checktile; + + /* These will contain the open and closed lists */ + + /* The actual closed list */ + Hash ClosedListHash; + /* The open queue */ + Queue OpenListQueue; + /* An extra hash to speed up the process of looking up an element in + * the open list */ + Hash OpenListHash; +}; + + +void AyStarMain_AddStartNode(AyStar *aystar, AyStarNode *start_node); +int AyStarMain_Main(AyStar *aystar); +int AyStarMain_Loop(AyStar *aystar); +int AyStarMain_CheckTile(AyStar *aystar, AyStarNode *current, OpenListNode *parent); +void AyStarMain_Free(AyStar *aystar); +void AyStarMain_Clear(AyStar *aystar); + +/* Initialize an AyStar. You should fill all appropriate fields before + * callling init_AyStar (see the declaration of AyStar for which fields are + * internal */ +void init_AyStar(AyStar* aystar, Hash_HashProc hash, uint num_buckets); + + +#endif diff --git a/lang/english.txt b/lang/english.txt index d22e649c0..e5f3fdfe3 100644 --- a/lang/english.txt +++ b/lang/english.txt @@ -991,6 +991,8 @@ STR_CONFIG_PATCHES_AI_BUILDS_ROADVEH :{LTBLUE}Disable road vehicles for computer STR_CONFIG_PATCHES_AI_BUILDS_AIRCRAFT :{LTBLUE}Disable aircraft for computer: {ORANGE}{STRING} STR_CONFIG_PATCHES_AI_BUILDS_SHIPS :{LTBLUE}Disable ships for computer: {ORANGE}{STRING} +STR_CONFIG_PATCHES_AINEW_ACTIVE :{LTBLUE}Enable new AI (alpha): {ORANGE}{STRING} + STR_CONFIG_PATCHES_SERVINT_TRAINS :{LTBLUE}Default service interval for trains: {ORANGE}{STRING} days STR_CONFIG_PATCHES_SERVINT_TRAINS_DISABLED :{LTBLUE}Default service interval for trains: {ORANGE}disabled STR_CONFIG_PATCHES_SERVINT_ROADVEH :{LTBLUE}Default service interval for road vehicles: {ORANGE}{STRING} days @@ -1134,6 +1136,8 @@ STR_RAIL_SELECT_TYPE_OF_CARGO_FOR :{BLACK}Select type of cargo for train to car STR_RAIL_REFIT_TO_CARRY_HIGHLIGHTED :{BLACK}Refit train to carry highlighted cargo type STR_RAIL_CAN_T_REFIT_VEHICLE :{WHITE}Can't refit train... +TEMP_AI_IN_PROGRESS :{WHITE}Welcome to this new AI, in progress. You can expect problems. When you do, make a screenshot and post it at the forum. Enjoy! +TEMP_AI_ACTIVATED :{WHITE}Warning: this new AI is still alpha! Currently, only trucks and busses work! ############ network gui strings diff --git a/misc_cmd.c b/misc_cmd.c index 59bed3fbc..5015d37bf 100644 --- a/misc_cmd.c +++ b/misc_cmd.c @@ -93,9 +93,12 @@ int32 CmdDecreaseLoan(int x, int y, uint32 flags, uint32 p1, uint32 p2) size = p->current_loan; // p2 is true while CTRL is pressed (repay all possible loan, or max money you have) - if (!p2) - size = min(size, IS_HUMAN_PLAYER((byte)p1) ? 10000 : 50000); - else { // only repay in chunks of 10K + if (!p2) { + if (_patches.ainew_active) + size = min(size, 10000); + else + size = min(size, IS_HUMAN_PLAYER((byte)p1) ? 10000 : 50000); + } else { // only repay in chunks of 10K size = min(size, p->player_money); size = max(size, 10000); size -= size % 10000; @@ -1,6 +1,8 @@ #ifndef PLAYER_H #define PLAYER_H +#include "aystar.h" + typedef struct PlayerEconomyEntry { int32 income; int32 expenses; @@ -62,6 +64,74 @@ typedef struct PlayerAI { byte banned_val[16]; } PlayerAI; +typedef struct Ai_PathFinderInfo { + TileIndex start_tile_tl; // tl = top-left + TileIndex start_tile_br; // br = bottom-right + TileIndex end_tile_tl; // tl = top-left + TileIndex end_tile_br; // br = bottom-right + byte start_direction; // 0 to 3 or AI_PATHFINDER_NO_DIRECTION + byte end_direction; // 0 to 3 or AI_PATHFINDER_NO_DIRECTION + + TileIndex route[500]; + byte route_extra[500]; // Some extra information about the route like bridge/tunnel + int route_length; + int position; // Current position in the build-path, needed to build the path + + bool rail_or_road; // true = rail, false = road +} Ai_PathFinderInfo; + +typedef struct PlayerAiNew { + uint8 state; + uint tick; + uint idle; + + int temp; // A value used in more then one function, but it just temporary + // The use is pretty simple: with this we can 'think' about stuff + // in more then one tick, and more then one AI. A static will not + // do, because they are not saved. This way, the AI is almost human ;) + int counter; // For the same reason as temp, we have counter. It can count how + // long we are trying something, and just abort if it takes too long + + // Pathfinder stuff + Ai_PathFinderInfo path_info; + AyStar *pathfinder; + + // Route stuff + + byte cargo; + byte tbt; // train/bus/truck 0/1/2 AI_TRAIN/AI_BUS/AI_TRUCK + int new_cost; + + byte action; + + uint last_id; // here is stored the last id of the searched city/industry + + TileIndex from_tile; + TileIndex to_tile; + + byte from_direction; + byte to_direction; + + bool from_deliver; // True if this is the station that GIVES cargo + bool to_deliver; + + TileIndex depot_tile; + byte depot_direction; + + byte amount_veh; // How many vehicles we are going to build in this route + byte cur_veh; // How many vehicles did we bought? + VehicleID veh_id; // Used when bought a vehicle + VehicleID veh_main_id; // The ID of the first vehicle, for shared copy + + int from_ic; // ic = industry/city. This is the ID of them + byte from_type; // AI_NO_TYPE/AI_CITY/AI_INDUSTRY + int to_ic; + byte to_type; + +} PlayerAiNew; + + + typedef struct Player { uint32 name_2; uint16 name_1; @@ -99,6 +169,7 @@ typedef struct Player { bool is_active; byte is_ai; PlayerAI ai; + PlayerAiNew ainew; int64 yearly_expenses[3][13]; PlayerEconomyEntry cur_economy; @@ -8,6 +8,7 @@ #include "news.h" #include "saveload.h" #include "command.h" +#include "ai.h" extern void StartupEconomy(); @@ -543,13 +544,16 @@ void OnTick_Players() void RunOtherPlayersLoop() { Player *p; - + _is_ai_player = true; FOR_ALL_PLAYERS(p) { if (p->is_active) { _current_player = p->index; - AiDoGameLoop(p); + if (_patches.ainew_active) + AiNewDoGameLoop(p); + else + AiDoGameLoop(p); } } diff --git a/queue.c b/queue.c new file mode 100644 index 000000000..9256736ab --- /dev/null +++ b/queue.c @@ -0,0 +1,659 @@ +#include "stdafx.h" +#include "ttd.h" +#include "queue.h" + +void Stack_Clear(Queue* q, bool free_values) +{ + uint i; + if (free_values) + for (i=0;i<q->stack.size;i++) + free(q->stack.elements[i]); + q->stack.size = 0; +} + +void Stack_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + free(q->stack.elements); + if (q->freeq) + free(q); +} + +bool Stack_Push(Queue* q, void* item, int priority) { + if (q->stack.size == q->stack.max_size) + return false; + q->stack.elements[q->stack.size++] = item; + return true; +} + +void* Stack_Pop(Queue* q) { + void* result; + if (q->stack.size == 0) + return NULL; + result = q->stack.elements[--q->stack.size]; + + return result; +} + +bool Stack_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +Queue* init_stack(Queue* q, uint max_size) { + q->push = Stack_Push; + q->pop = Stack_Pop; + q->del = Stack_Delete; + q->clear = Stack_Clear; + q->free = Stack_Free; + q->stack.max_size = max_size; + q->stack.size = 0; + q->stack.elements = malloc(max_size * sizeof(void*)); + q->freeq = false; + return q; +} + +Queue* new_Stack(uint max_size) +{ + Queue* q = malloc(sizeof(Queue)); + init_stack(q, max_size); + q->freeq = true; + return q; +} + +/* + * Fifo + */ + +void Fifo_Clear(Queue* q, bool free_values) +{ + uint head, tail; + if (free_values) { + head = q->fifo.head; + tail = q->fifo.tail; /* cache for speed */ + while (head != tail) { + free(q->fifo.elements[tail]); + tail = (tail + 1) % q->fifo.max_size; + } + } + q->fifo.head = q->fifo.tail = 0; +} + +void Fifo_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + free(q->fifo.elements); + if (q->freeq) + free(q); +} + +bool Fifo_Push(Queue* q, void* item, int priority) { + uint next = (q->fifo.head + 1) % q->fifo.max_size; + if (next == q->fifo.tail) + return false; + q->fifo.elements[q->fifo.head] = item; + + + q->fifo.head = next; + return true; +} + +void* Fifo_Pop(Queue* q) { + void* result; + if (q->fifo.head == q->fifo.tail) + return NULL; + result = q->fifo.elements[q->fifo.tail]; + + + q->fifo.tail = (q->fifo.tail + 1) % q->fifo.max_size; + return result; +} + +bool Fifo_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +Queue* init_fifo(Queue* q, uint max_size) { + q->push = Fifo_Push; + q->pop = Fifo_Pop; + q->del = Fifo_Delete; + q->clear = Fifo_Clear; + q->free = Fifo_Free; + q->fifo.max_size = max_size; + q->fifo.head = 0; + q->fifo.tail = 0; + q->fifo.elements = malloc(max_size * sizeof(void*)); + q->freeq = false; + return q; +} + +Queue* new_Fifo(uint max_size) +{ + Queue* q = malloc(sizeof(Queue)); + init_fifo(q, max_size); + q->freeq = true; + return q; +} + + +/* + * Insertion Sorter + */ + +void InsSort_Clear(Queue* q, bool free_values) { + InsSortNode* node = q->inssort.first; + InsSortNode* prev; + while (node != NULL) { + if (free_values) + free(node->item); + prev = node; + node = node->next; + free(prev); + + } + q->inssort.first = NULL; +} + +void InsSort_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + if (q->freeq) + free(q); +} + +bool InsSort_Push(Queue* q, void* item, int priority) { + InsSortNode* newnode = malloc(sizeof(InsSortNode)); + if (newnode == NULL) return false; + newnode->item = item; + newnode->priority = priority; + if (q->inssort.first == NULL || q->inssort.first->priority >= priority) { + newnode->next = q->inssort.first; + q->inssort.first = newnode; + } else { + InsSortNode* node = q->inssort.first; + while( node != NULL ) { + if (node->next == NULL || node->next->priority >= priority) { + newnode->next = node->next; + node->next = newnode; + break; + } + node = node->next; + } + } + return true; +} + +void* InsSort_Pop(Queue* q) { + InsSortNode* node = q->inssort.first; + void* result; + if (node == NULL) + return NULL; + result = node->item; + q->inssort.first = q->inssort.first->next; + if (q->inssort.first) + assert(q->inssort.first->priority >= node->priority); + free(node); + return result; +} + +bool InsSort_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +void init_InsSort(Queue* q) { + q->push = InsSort_Push; + q->pop = InsSort_Pop; + q->del = InsSort_Delete; + q->clear = InsSort_Clear; + q->free = InsSort_Free; + q->inssort.first = NULL; + q->freeq = false; +} + +Queue* new_InsSort() { + Queue* q = malloc(sizeof(Queue)); + init_InsSort(q); + q->freeq = true; + return q; +} + + +/* + * Binary Heap + * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm + */ + +#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS) +#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE-1) + +// To make our life easy, we make the next define +// Because Binary Heaps works with array from 1 to n, +// and C with array from 0 to n-1, and we don't like typing +// q->binaryheap.elements[i-1] every time, we use this define. +#define BIN_HEAP_ARR(i) q->binaryheap.elements[((i)-1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i)-1) & BINARY_HEAP_BLOCKSIZE_MASK] + +void BinaryHeap_Clear(Queue* q, bool free_values) +{ + /* Free all items if needed and free all but the first blocks of + * memory */ + uint i,j; + for (i=0;i<q->binaryheap.blocks;i++) { + if (q->binaryheap.elements[i] == NULL) { + /* No more allocated blocks */ + break; + } + /* For every allocated block */ + if (free_values) + for (j=0;j<(1<<BINARY_HEAP_BLOCKSIZE_BITS);j++) { + /* For every element in the block */ + if ((q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i + && (q->binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) + break; /* We're past the last element */ + free(q->binaryheap.elements[i][j].item); + } + if (i != 0) { + /* Leave the first block of memory alone */ + free(q->binaryheap.elements[i]); + q->binaryheap.elements[i] = NULL; + } + } + q->binaryheap.size = 0; + q->binaryheap.blocks = 1; +} + +void BinaryHeap_Free(Queue* q, bool free_values) +{ + uint i; + q->clear(q, free_values); + for (i=0;i<q->binaryheap.blocks;i++) { + if (q->binaryheap.elements[i] == NULL) + break; + free(q->binaryheap.elements[i]); + } + if (q->freeq) + free(q); +} + +bool BinaryHeap_Push(Queue* q, void* item, int priority) { + #ifdef QUEUE_DEBUG + printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->binaryheap.size); + #endif + if (q->binaryheap.size == q->binaryheap.max_size) + return false; + assert(q->binaryheap.size < q->binaryheap.max_size); + + if (q->binaryheap.elements[q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) { + /* The currently allocated blocks are full, allocate a new one */ + assert((q->binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0); + q->binaryheap.elements[q->binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode)); + q->binaryheap.blocks++; +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Increasing size of elements to %d nodes\n",q->binaryheap.blocks * BINARY_HEAP_BLOCKSIZE); +#endif + } + + // Add the item at the end of the array + BIN_HEAP_ARR(q->binaryheap.size+1).priority = priority; + BIN_HEAP_ARR(q->binaryheap.size+1).item = item; + q->binaryheap.size++; + + // Now we are going to check where it belongs. As long as the parent is + // bigger, we switch with the parent + { + int i, j; + BinaryHeapNode temp; + i = q->binaryheap.size; + while (i > 1) { + // Get the parent of this object (divide by 2) + j = i / 2; + // Is the parent bigger then the current, switch them + if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) { + temp = BIN_HEAP_ARR(j); + BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); + BIN_HEAP_ARR(i) = temp; + i = j; + } else { + // It is not, we're done! + break; + } + } + } + + return true; +} + +bool BinaryHeap_Delete(Queue* q, void* item, int priority) +{ + #ifdef QUEUE_DEBUG + printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->binaryheap.size); + #endif + uint i = 0; + // First, we try to find the item.. + do { + if (BIN_HEAP_ARR(i+1).item == item) break; + i++; + } while (i < q->binaryheap.size); + // We did not find the item, so we return false + if (i == q->binaryheap.size) return false; + + // Now we put the last item over the current item while decreasing the size of the elements + q->binaryheap.size--; + BIN_HEAP_ARR(i+1) = BIN_HEAP_ARR(q->binaryheap.size+1); + + // Now the only thing we have to do, is resort it.. + // On place i there is the item to be sorted.. let's start there + { + uint j; + BinaryHeapNode temp; + // Because of the fast that Binary Heap uses array from 1 to n, we need to increase + // i with 1 + i++; + + for (;;) { + j = i; + // Check if we have 2 childs + if (2*j+1 <= q->binaryheap.size) { + // Is this child smaller then the parent? + if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) {i = 2*j; } + // Yes, we _need_ to use i here, not j, because we want to have the smallest child + // This way we get that straight away! + if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2*j+1).priority) { i = 2*j+1; } + // Do we have one child? + } else if (2*j <= q->binaryheap.size) { + if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) { i = 2*j; } + } + + // One of our childs is smaller then we are, switch + if (i != j) { + temp = BIN_HEAP_ARR(j); + BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); + BIN_HEAP_ARR(i) = temp; + } else { + // None of our childs is smaller, so we stay here.. stop :) + break; + } + } + } + + return true; +} + +void* BinaryHeap_Pop(Queue* q) { + #ifdef QUEUE_DEBUG + printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->binaryheap.size); + #endif + void* result; + if (q->binaryheap.size == 0) + return NULL; + + // The best item is always on top, so give that as result + result = BIN_HEAP_ARR(1).item; + // And now we should get ride of this item... + BinaryHeap_Delete(q,BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority); + + return result; +} + +void init_BinaryHeap(Queue* q, uint max_size) +{ + assert(q); + q->push = BinaryHeap_Push; + q->pop = BinaryHeap_Pop; + q->del = BinaryHeap_Delete; + q->clear = BinaryHeap_Clear; + q->free = BinaryHeap_Free; + q->binaryheap.max_size = max_size; + q->binaryheap.size = 0; + // We malloc memory in block of BINARY_HEAP_BLOCKSIZE + // It autosizes when it runs out of memory + q->binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE) + 1); + q->binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode)); + q->binaryheap.blocks = 1; + q->freeq = false; +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Initial size of elements is %d nodes\n",(1024)); +#endif +} + +Queue* new_BinaryHeap(uint max_size) { + Queue* q = malloc(sizeof(Queue)); + init_BinaryHeap(q, max_size); + q->freeq = true; + return q; +} + +// Because we don't want anyone else to bother with our defines +#undef BIN_HEAP_ARR + +/* + * Hash + */ + +void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets) { + /* Allocate space for the Hash, the buckets and the bucket flags */ + int i; + assert(h); + #ifdef HASH_DEBUG + debug("Allocated hash: %p", h); + #endif + h->hash = hash; + h->size = 0; + h->num_buckets = num_buckets; + h->buckets = malloc(num_buckets * (sizeof(HashNode) + sizeof(bool))); + #ifdef HASH_DEBUG + debug("Buckets = %p", h->buckets); + #endif + h->buckets_in_use = (bool*)(h->buckets + num_buckets); + h->freeh = false; + for (i=0;i<num_buckets;i++) + h->buckets_in_use[i] = false; +} + +Hash* new_Hash(Hash_HashProc* hash, int num_buckets) { + Hash* h = malloc(sizeof(Hash)); + init_Hash(h, hash, num_buckets); + h->freeh = true; + return h; +} + +void delete_Hash(Hash* h, bool free_values) { + uint i; + /* Iterate all buckets */ + for (i=0;i<h->num_buckets;i++) + { + if (h->buckets_in_use[i]) { + HashNode* node; + /* Free the first value */ + if (free_values) + free(h->buckets[i].value); + node = h->buckets[i].next; + while (node != NULL) { + HashNode* prev = node; + node = node->next; + /* Free the value */ + if (free_values) + free(prev->value); + /* Free the node */ + free(prev); + } + } + } + free(h->buckets); + /* No need to free buckets_in_use, it is always allocated in one + * malloc with buckets */ + #ifdef HASH_DEBUG + debug("Freeing Hash: %p", h); + #endif + if (h->freeh) + free(h); +} + +void clear_Hash(Hash* h, bool free_values) +{ + uint i; + HashNode* node; + /* Iterate all buckets */ + for (i=0;i<h->num_buckets;i++) + { + if (h->buckets_in_use[i]) { + h->buckets_in_use[i] = false; + /* Free the first value */ + if (free_values) + free(h->buckets[i].value); + node = h->buckets[i].next; + while (node != NULL) { + HashNode* prev = node; + node = node->next; + if (free_values) + free(prev->value); + free(prev); + } + } + } + h->size = 0; +} + +/* Finds the node that that saves this key pair. If it is not + * found, returns NULL. If it is found, *prev is set to the + * node before the one found, or if the node found was the first in the bucket + * to NULL. If it is not found, *prev is set to the last HashNode in the + * bucket, or NULL if it is empty. prev can also be NULL, in which case it is + * not used for output. + */ +HashNode* Hash_FindNode(Hash* h, uint key1, uint key2, HashNode** prev_out) { + uint hash = h->hash(key1, key2); + HashNode* result = NULL; + #ifdef HASH_DEBUG + debug("Looking for %u, %u", key1, key2); + #endif + /* Check if the bucket is empty */ + if (!h->buckets_in_use[hash]) { + if (prev_out) + *prev_out = NULL; + result = NULL; + /* Check the first node specially */ + } else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) { + /* Save the value */ + result = h->buckets + hash; + if (prev_out) + *prev_out = NULL; + #ifdef HASH_DEBUG + debug("Found in first node: %p", result); + #endif + /* Check all other nodes */ + } else { + HashNode* prev = h->buckets + hash; + HashNode* node = prev->next; + while (node != NULL) { + if (node->key1 == key1 && node->key2 == key2) { + /* Found it */ + result = node; + #ifdef HASH_DEBUG + debug("Found in other node: %p", result); + #endif + break; + } + prev = node; + node = node->next; + } + if (prev_out) + *prev_out = prev; + } + #ifdef HASH_DEBUG + if (result == NULL) + debug("Not found"); + #endif + return result; +} + +void* Hash_Delete(Hash* h, uint key1, uint key2) { + void* result; + HashNode* prev; /* Used as output var for below function call */ + HashNode* node = Hash_FindNode(h, key1, key2, &prev); + + if (node == NULL) { + /* not found */ + result = NULL; + } else if (prev == NULL) { + /* It is in the first node, we can't free that one, so we free + * the next one instead (if there is any)*/ + /* Save the value */ + result = node->value; + if (node->next != NULL) { + HashNode* next = node->next; + /* Copy the second to the first */ + *node = *next; + /* Free the second */ + #ifndef NOFREE + free(next); + #endif + } else { + /* This was the last in this bucket */ + /* Mark it as empty */ + uint hash = h->hash(key1, key2); + h->buckets_in_use[hash] = false; + } + } else { + /* It is in another node */ + /* Save the value */ + result = node->value; + /* Link previous and next nodes */ + prev->next = node->next; + /* Free the node */ + #ifndef NOFREE + free(node); + #endif + } + if (result != NULL) + h->size--; + return result; +} + + +void* Hash_Set(Hash* h, uint key1, uint key2, void* value) { + HashNode* prev; + HashNode* node = Hash_FindNode(h, key1, key2, &prev); + void* result = NULL; + if (node != NULL) { + /* Found it */ + result = node->value; + node->value = value; + return result; + } + /* It is not yet present, let's add it */ + if (prev == NULL) { + /* The bucket is still empty */ + uint hash = h->hash(key1, key2); + h->buckets_in_use[hash] = true; + node = h->buckets + hash; + } else { + /* Add it after prev */ + node = malloc(sizeof(HashNode)); + prev->next = node; + } + node->next = NULL; + node->key1 = key1; + node->key2 = key2; + node->value = value; + h->size++; + return NULL; +} + +void* Hash_Get(Hash* h, uint key1, uint key2) { + HashNode* node = Hash_FindNode(h, key1, key2, NULL); + #ifdef HASH_DEBUG + debug("Found node: %p", node); + #endif + if (node == NULL) { + /* Node not found */ + return NULL; + } else { + return node->value; + } +} + +uint Hash_Size(Hash* h) { + return h->size; +} diff --git a/queue.h b/queue.h new file mode 100644 index 000000000..8394aa61a --- /dev/null +++ b/queue.h @@ -0,0 +1,202 @@ +#ifndef QUEUE_H
+#define QUEUE_H
+
+//#define NOFREE
+//#define QUEUE_DEBUG
+//#define HASH_DEBUG
+
+
+typedef struct Queue Queue;
+typedef bool Queue_PushProc(Queue* q, void* item, int priority);
+typedef void* Queue_PopProc(Queue* q);
+typedef bool Queue_DeleteProc(Queue* q, void* item, int priority);
+typedef void Queue_ClearProc(Queue* q, bool free_values);
+typedef void Queue_FreeProc(Queue* q, bool free_values);
+
+typedef struct InsSortNode InsSortNode;
+struct InsSortNode {
+ void* item;
+ int priority;
+ InsSortNode* next;
+};
+typedef struct BinaryHeapNode BinaryHeapNode;
+ struct BinaryHeapNode {
+ void* item;
+ int priority;
+};
+
+
+struct Queue{
+ /*
+ * Pushes an element into the queue, at the appropriate place for the queue.
+ * Requires the queue pointer to be of an appropriate type, of course.
+ */
+ Queue_PushProc* push;
+ /*
+ * Pops the first element from the queue. What exactly is the first element,
+ * is defined by the exact type of queue.
+ */
+ Queue_PopProc* pop;
+ /*
+ * Deletes the item from the queue. priority should be specified if
+ * known, which speeds up the deleting for some queue's. Should be -1
+ * if not known.
+ */
+ Queue_DeleteProc* del;
+
+ /* Clears the queue, by removing all values from it. It's state is
+ * effectively reset. If free_items is true, each of the items cleared
+ * in this way are free()'d.
+ */
+ Queue_ClearProc* clear;
+ /* Frees the queue, by reclaiming all memory allocated by it. After
+ * this it is no longer usable. If free_items is true, any remaining
+ * items are free()'d too.
+ */
+ Queue_FreeProc* free;
+
+ union {
+ struct {
+ uint max_size;
+ uint size;
+ void** elements;
+ } stack;
+ struct {
+ uint max_size;
+ uint head; /* The index where the last element should be inserted */
+ uint tail; /* The index where the next element should be read */
+ void** elements;
+ } fifo;
+ struct {
+ InsSortNode* first;
+ } inssort;
+ struct {
+ uint max_size;
+ uint size;
+ uint blocks; /* The amount of blocks for which space is reserved in elements */
+ BinaryHeapNode** elements;
+ } binaryheap;
+ };
+ /* If true, this struct will be free'd when the
+ * Queue is deleted. */
+ bool freeq;
+};
+
+/* Initializes a stack and allocates internal memory. */
+void init_Stack(Queue* q, uint max_size);
+
+/* Allocate a new stack with a maximum of max_size elements. */
+Queue* new_Stack(uint max_size);
+
+/*
+ * Fifo
+ */
+
+/* Initializes a fifo and allocates internal memory for maximum of max_size
+ * elements */
+void init_Fifo(Queue* q, uint max_size);
+
+/* Allocate a new fifo and initializes it with a maximum of max_size elements. */
+Queue* new_Fifo(uint max_size);
+
+Queue* new_Fifo_in_buffer(uint max_size, void* buffer);
+
+int build_Fifo(void* buffer, uint size);
+
+/*
+ * Insertion Sorter
+ */
+
+/* Initializes a inssort and allocates internal memory. There is no maximum
+ * size */
+void init_InsSort(Queue* q);
+
+/* Allocate a new fifo and initializes it. There is no maximum size */
+Queue* new_InsSort();
+
+/*
+ * Binary Heap
+ * For information, see:
+ * http://www.policyalmanac.org/games/binaryHeaps.htm
+ */
+
+/* The amount of elements that will be malloc'd at a time */
+#define BINARY_HEAP_BLOCKSIZE_BITS 10
+
+/* Initializes a binary heap and allocates internal memory for maximum of
+ * max_size elements */
+void init_BinaryHeap(Queue* q, uint max_size);
+
+/* Allocate a new binary heap and initializes it with a maximum of max_size
+ * elements. */
+Queue* new_BinaryHeap(uint max_size);
+
+/*
+ * Hash
+ */
+typedef struct HashNode HashNode;
+struct HashNode {
+ uint key1;
+ uint key2;
+ void* value;
+ HashNode* next;
+};
+/* Generates a hash code from the given key pair. You should make sure that
+ * the resulting range is clearly defined.
+ */
+typedef uint Hash_HashProc(uint key1, uint key2);
+typedef struct Hash {
+ /* The hash function used */
+ Hash_HashProc* hash;
+ /* The amount of items in the hash */
+ uint size;
+ /* The number of buckets allocated */
+ uint num_buckets;
+ /* A pointer to an array of num_buckets buckets. */
+ HashNode* buckets;
+ /* A pointer to an array of numbuckets booleans, which will be true if
+ * there are any Nodes in the bucket */
+ bool* buckets_in_use;
+ /* If true, buckets will be freed in delete_hash */
+ bool freeb;
+ /* If true, the pointer to this struct will be freed in delete_hash */
+ bool freeh;
+} Hash;
+
+/* Call these function to manipulate a hash */
+
+/* Deletes the value with the specified key pair from the hash and returns
+ * that value. Returns NULL when the value was not present. The value returned
+ * is _not_ free()'d! */
+void* Hash_Delete(Hash* h, uint key1, uint key2);
+/* Sets the value associated with the given key pair to the given value.
+ * Returns the old value if the value was replaced, NULL when it was not yet present. */
+void* Hash_Set(Hash* h, uint key1, uint key2, void* value);
+/* Gets the value associated with the given key pair, or NULL when it is not
+ * present. */
+void* Hash_Get(Hash* h, uint key1, uint key2);
+
+/* Call these function to create/destroy a hash */
+
+/* Builds a new hash, with num_buckets buckets. Make sure that hash() always
+ * returns a hash less than num_buckets! Call delete_hash after use */
+Hash* new_Hash(Hash_HashProc* hash, int num_buckets);
+/* Builds a new hash in an existing struct. Make sure that hash() always
+ * returns a hash less than num_buckets! Call delete_hash after use */
+void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets);
+/*
+ * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash
+ * & friends. If free is true, it will call free() on all the values that
+ * are left in the hash.
+ */
+void delete_Hash(Hash* h, bool free_values);
+/*
+ * Cleans the hash, but keeps the memory allocated
+ */
+void clear_Hash(Hash* h, bool free_values);
+/*
+ * Gets the current size of the Hash
+ */
+uint Hash_Size(Hash* h);
+
+#endif /* QUEUE_H */
diff --git a/rail_cmd.c b/rail_cmd.c index bb8736c67..567e0c973 100644 --- a/rail_cmd.c +++ b/rail_cmd.c @@ -203,7 +203,7 @@ static const byte _valid_tileh_slopes[4][15] = { } }; -static uint GetRailFoundation(uint tileh, uint bits) +uint GetRailFoundation(uint tileh, uint bits) { int i; @@ -351,7 +351,7 @@ need_clear:; cost += ret; // the AI is not allowed to used foundationed tiles. - if (ret && (_is_ai_player || !_patches.build_on_slopes)) + if (ret && (!_patches.build_on_slopes || (!_patches.ainew_active && _is_ai_player))) return_cmd_error(STR_1000_LAND_SLOPED_IN_WRONG_DIRECTION); if (flags & DC_EXEC && need_clear) { @@ -628,7 +628,7 @@ int32 CmdBuildTrainDepot(int x, int y, uint32 flags, uint32 p1, uint32 p2) tileh = GetTileSlope(tile, NULL); if (tileh != 0) { - if (_is_ai_player || !_patches.build_on_slopes || (tileh & 0x10 || !((0x4C >> p2) & tileh) )) + if ((!_patches.ainew_active && _is_ai_player) || !_patches.build_on_slopes || (tileh & 0x10 || !((0x4C >> p2) & tileh) )) return_cmd_error(STR_0007_FLAT_LAND_REQUIRED); } diff --git a/road_cmd.c b/road_cmd.c index 441e1dff8..e782430e0 100644 --- a/road_cmd.c +++ b/road_cmd.c @@ -16,7 +16,7 @@ static bool _road_special_gettrackstatus; void RoadVehEnterDepot(Vehicle *v); -static bool HasTileRoadAt(uint tile, int i) +bool HasTileRoadAt(uint tile, int i) { int mask; byte b; @@ -424,8 +424,7 @@ do_clear:; cost = CheckRoadSlope(ti.tileh, &pieces, existing); if (cost == CMD_ERROR) return_cmd_error(STR_1800_LAND_SLOPED_IN_WRONG_DIRECTION); - // the AI is not allowed to used foundationed tiles. - if (cost && (_is_ai_player || !_patches.build_on_slopes)) + if (cost && (!_patches.build_on_slopes || (!_patches.ainew_active && _is_ai_player))) return CMD_ERROR; if (!(ti.type == MP_STREET && (ti.map5 & 0xF0) == 0)) { @@ -600,7 +599,7 @@ int32 CmdBuildRoadDepot(int x, int y, uint32 flags, uint32 p1, uint32 p2) return CMD_ERROR; if (ti.tileh != 0) { - if (_is_ai_player || !_patches.build_on_slopes || (ti.tileh & 0x10 || !((0x4C >> p1) & ti.tileh) )) + if (!_patches.build_on_slopes || (ti.tileh & 0x10 || !((0x4C >> p1) & ti.tileh) )) return_cmd_error(STR_0007_FLAT_LAND_REQUIRED); } @@ -696,7 +695,7 @@ typedef struct DrawRoadSeqStruct { #include "table/road_land.h" -static uint GetRoadFoundation(uint tileh, uint bits) { +uint GetRoadFoundation(uint tileh, uint bits) { int i; // normal level sloped building if ((~_valid_tileh_slopes_road[1][tileh] & bits) == 0) diff --git a/settings.c b/settings.c index 8e5ef88aa..d281c37cb 100644 --- a/settings.c +++ b/settings.c @@ -874,6 +874,8 @@ static const SettingDesc patch_settings[] = { {"wait_oneway_signal", SDT_UINT8, (void*)15, (void*)offsetof(Patches, wait_oneway_signal)}, {"wait_twoway_signal", SDT_UINT8, (void*)41, (void*)offsetof(Patches, wait_twoway_signal)}, + + {"ainew_active", SDT_BOOL, (void*)false, (void*)offsetof(Patches, ainew_active)}, {"drag_signals_density", SDT_UINT8, (void*)4, (void*)offsetof(Patches, drag_signals_density)}, diff --git a/settings_gui.c b/settings_gui.c index 48eaa5b83..e8334808c 100644 --- a/settings_gui.c +++ b/settings_gui.c @@ -670,6 +670,14 @@ int32 v_PositionMainToolbar(int32 p1) return 0; } +int32 AiNew_PatchActive_Warning(int32 p1) +{ + if (p1 == 1) + ShowErrorMessage(-1, TEMP_AI_ACTIVATED, 0, 0); + + return 0; +} + typedef int32 PatchButtonClick(int32); static PatchButtonClick * const _patch_button_proc[] = { &v_PositionMainToolbar, @@ -773,6 +781,8 @@ static const PatchEntry _patches_economy[] = { }; static const PatchEntry _patches_ai[] = { + {PE_BOOL, 0, STR_CONFIG_PATCHES_AINEW_ACTIVE, &_patches.ainew_active, 0, 1, 1, &AiNew_PatchActive_Warning}, + {PE_BOOL, 0, STR_CONFIG_PATCHES_AI_BUILDS_TRAINS, &_patches.ai_disable_veh_train}, {PE_BOOL, 0, STR_CONFIG_PATCHES_AI_BUILDS_ROADVEH, &_patches.ai_disable_veh_roadveh}, {PE_BOOL, 0, STR_CONFIG_PATCHES_AI_BUILDS_AIRCRAFT, &_patches.ai_disable_veh_aircraft}, diff --git a/station_cmd.c b/station_cmd.c index 6019957de..c5528d906 100644 --- a/station_cmd.c +++ b/station_cmd.c @@ -577,7 +577,7 @@ int32 CheckFlatLandBelow(uint tile, uint w, uint h, uint flags, uint invalid_dir tileh = GetTileSlope(tile_cur, &z); // steep slopes are completely prohibited - if (tileh & 0x10 || ((_is_ai_player || !_patches.build_on_slopes) && tileh != 0)) { + if (tileh & 0x10 || (((!_patches.ainew_active && _is_ai_player) || !_patches.build_on_slopes) && tileh != 0)) { _error_message = STR_0007_FLAT_LAND_REQUIRED; return CMD_ERROR; } @@ -782,8 +782,8 @@ int32 CmdBuildRailroadStation(int x_org, int y_org, uint32 flags, uint32 p1, uin return_cmd_error(STR_3009_TOO_CLOSE_TO_ANOTHER_STATION); if (st->train_tile != 0) { - // check if we want to expanding an already existing station? Only human players can do this. - if (_is_ai_player || !_patches.join_stations || !CanExpandRailroadStation(st, finalvalues, direction)) + // check if we want to expanding an already existing station? + if ((!_patches.ainew_active && _is_ai_player) || !_patches.join_stations || !CanExpandRailroadStation(st, finalvalues, direction)) return_cmd_error(STR_3005_TOO_CLOSE_TO_ANOTHER_RAILROAD); } @@ -20,6 +20,7 @@ #include "hal.h" #include "airport.h" #include "saveload.h" +#include "ai.h" #include <stdarg.h> @@ -429,6 +430,7 @@ void SetDebugString(const char *s) _debug_spritecache_level = v; _debug_misc_level = v; _debug_grf_level = v; + _debug_ai_level = v; } // individual levels @@ -445,6 +447,7 @@ void SetDebugString(const char *s) if IS_LVL("misc") p = &_debug_misc_level; else if IS_LVL("spritecache") p = &_debug_spritecache_level; else if IS_LVL("grf") p = &_debug_grf_level; + else if IS_LVL("ai") p = &_debug_ai_level; else { ShowInfoF("Unknown debug level '%.*s'", s-t, t); return; diff --git a/tunnelbridge_cmd.c b/tunnelbridge_cmd.c index 92bafbe65..5326c161a 100644 --- a/tunnelbridge_cmd.c +++ b/tunnelbridge_cmd.c @@ -239,9 +239,9 @@ int32 CmdBuildBridge(int x, int y, uint32 flags, uint32 p1, uint32 p2) terraformcost = CheckBridgeSlope(direction, ti_start.tileh, true); // true - bridge-start-tile, false - bridge-end-tile - // the AI and towns are not allowed to use bridges on slopes. + // towns are not allowed to use bridges on slopes. if (terraformcost == CMD_ERROR || - (terraformcost && (_is_ai_player || _current_player == OWNER_TOWN || !_patches.build_on_slopes))) + (terraformcost && ((!_patches.ainew_active && _is_ai_player) || _current_player == OWNER_TOWN || !_patches.build_on_slopes))) return_cmd_error(STR_1000_LAND_SLOPED_IN_WRONG_DIRECTION); cost += terraformcost; @@ -253,9 +253,9 @@ int32 CmdBuildBridge(int x, int y, uint32 flags, uint32 p1, uint32 p2) terraformcost = CheckBridgeSlope(direction, ti_end.tileh, false); // false - end tile slope check - // the AI and towns are not allowed to use bridges on slopes. + // towns are not allowed to use bridges on slopes. if (terraformcost == CMD_ERROR || - (terraformcost && (_is_ai_player || _current_player == OWNER_TOWN || !_patches.build_on_slopes))) + (terraformcost && ((!_patches.ainew_active && _is_ai_player) || _current_player == OWNER_TOWN || !_patches.build_on_slopes))) return_cmd_error(STR_1000_LAND_SLOPED_IN_WRONG_DIRECTION); cost += terraformcost; @@ -377,10 +377,10 @@ not_valid_below:; It's unnecessary to execute this command every time for every bridge. So it is done only and cost is computed in "bridge_gui.c". For AI, Towns this has to be of course calculated */ - if (!(flags & DC_QUERY_COST)) { + if (!(flags & DC_QUERY_COST)) { bridge_len += 2; // begin and end tiles/ramps - if (_current_player < MAX_PLAYERS && IS_HUMAN_PLAYER(_current_player)) + if (_current_player < MAX_PLAYERS && !(_is_ai_player && !_patches.ainew_active)) bridge_len = CalcBridgeLenCostFactor(bridge_len); cost += ((bridge_len * _price.build_bridge) * _bridge_type_price_mod[bridge_type]) >> 8; @@ -887,7 +887,7 @@ int32 DoConvertTunnelBridgeRail(uint tile, uint totype, bool exec) // fast routine for getting the height of a middle bridge tile. 'tile' MUST be a middle bridge tile. -static uint GetBridgeHeight(const TileInfo *ti) +uint GetBridgeHeight(const TileInfo *ti) { uint delta; TileInfo ti_end; @@ -966,7 +966,7 @@ static void DrawBridgePillars(TileInfo *ti, int x, int y, int z) } } -static uint GetBridgeFoundation(uint tileh, byte direction) { +uint GetBridgeFoundation(uint tileh, byte direction) { int i; // normal level sloped building (7, 11, 13, 14) if (BRIDGE_FULL_LEVELED_FOUNDATION & (1 << tileh)) diff --git a/variables.h b/variables.h index bbb0ded43..2073979e9 100644 --- a/variables.h +++ b/variables.h @@ -155,6 +155,7 @@ typedef struct Patches { byte wait_twoway_signal; //waitingtime in days before a twoway signal byte drag_signals_density; // many signals density + bool ainew_active; // Is the new AI active? } Patches; VARDEF Patches _patches; @@ -225,7 +226,7 @@ VARDEF uint32 _network_detected_serverport; // UDP Broadcast detected server-por VARDEF uint32 _sync_seed_1, _sync_seed_2; -VARDEF bool _is_ai_player; // current player is an AI player? +VARDEF bool _is_ai_player; // current player is an AI player? - Can be removed if new AI is done VARDEF bool _do_autosave; VARDEF int _autosave_ctr; @@ -431,6 +432,7 @@ VARDEF bool _ignore_wrong_grf; VARDEF int _debug_spritecache_level; VARDEF int _debug_misc_level; VARDEF int _debug_grf_level; +VARDEF int _debug_ai_level; void CDECL debug(const char *s, ...); #ifdef NO_DEBUG_MESSAGES |