Changeset - r84:ffa541707cbb
[Not reviewed]
master
0 14 9
truelight - 20 years ago 2004-08-20 09:32:32
truelight@openttd.org
(svn r85) -Add: initial commit of new AI (enable in Patch menu)
-Add: generalised A* Algorithm
-Add: generalised queues (Fifo, Stack, InsSort, BinaryHeap)
23 files changed with 3688 insertions and 27 deletions:
0 comments (0 inline, 0 general)
Makefile
Show inline comments
 
@@ -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
ai.h
Show inline comments
 
new file 100644
 
#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
ai_build.c
Show inline comments
 
new file 100644
 
#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;
 
    }
 
}
ai_new.c
Show inline comments
 
new file 100644
 
/*
 
 * 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);
 
}
ai_pathfinder.c
Show inline comments
 
new file 100644
 
#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 = &current->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;
 
}
ai_shared.c
Show inline comments
 
new file 100644
 
#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;
 
}
 
 
aircraft_cmd.c
Show inline comments
 
@@ -272,7 +272,8 @@ int32 CmdBuildAircraft(int x, int y, uin
 
		*(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 
aystar.c
Show inline comments
 
new file 100644
 
/*
 
 * 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, &current->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;
 
}
aystar.h
Show inline comments
 
new file 100644
 
/*
 
 * 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
lang/english.txt
Show inline comments
 
@@ -991,6 +991,8 @@ STR_CONFIG_PATCHES_AI_BUILDS_ROADVEH	:{L
 
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		:{BLA
 
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
 

	
misc_cmd.c
Show inline comments
 
@@ -93,9 +93,12 @@ int32 CmdDecreaseLoan(int x, int y, uint
 
	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;
player.h
Show inline comments
 
#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;
players.c
Show inline comments
 
@@ -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);
 
		}
 
	}
 

	
queue.c
Show inline comments
 
new file 100644
 
#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;
 
}
queue.h
Show inline comments
 
new file 100644
 
#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 */
rail_cmd.c
Show inline comments
 
@@ -203,7 +203,7 @@ static const byte _valid_tileh_slopes[4]
 
	}
 
};
 

	
 
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, u
 

	
 
	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);
 
	}
 

	
road_cmd.c
Show inline comments
 
@@ -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, ui
 
		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)
settings.c
Show inline comments
 
@@ -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)},
 

	
settings_gui.c
Show inline comments
 
@@ -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},
station_cmd.c
Show inline comments
 
@@ -577,7 +577,7 @@ int32 CheckFlatLandBelow(uint tile, uint
 
		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,
 
			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);
 
		}
 

	
ttd.c
Show inline comments
 
@@ -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;
tunnelbridge_cmd.c
Show inline comments
 
@@ -239,9 +239,9 @@ int32 CmdBuildBridge(int x, int y, uint3
 

	
 
	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, uint3
 
	
 
	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 til
 

	
 

	
 
// 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 *
 
	}
 
}
 

	
 
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))
variables.h
Show inline comments
 
@@ -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_serverpo
 

	
 
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
0 comments (0 inline, 0 general)