start_node.node.user_data[0] = 0;

	// Now we add all the starting tiles

	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {

		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {

			start_node.node.tile = TILE_XY(x, y);

		}

	}

	return result;

}

	// Now we add all the starting tiles

	for (x = TileX(PathFinderInfo->start_tile_tl); x <= TileX(PathFinderInfo->start_tile_br); x++) {

		for (y = TileY(PathFinderInfo->start_tile_tl); y <= TileY(PathFinderInfo->start_tile_br); y++) {

			if (!(IsTileType(TILE_XY(x, y), MP_CLEAR) || IsTileType(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);

		}

	}

}

// The h-value, simple calculation

static int32 AyStar_AiPathFinder_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)

	return res;

}

// Adds a node to the OpenList

//  It makes a copy of node, and puts the pointer of parent in the struct

{

	// 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;

		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

	}

	return AYSTAR_DONE;

}

/*

/*

 * 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

 */

#ifdef AYSTAR_DEBUG

	printf("[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n",

		TileX(start_node->tile), TileY(start_node->tile), start_node->direction);

#endif

}

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

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

	/* An extra hash to speed up the process of looking up an element in

	 * the open list */

	Hash OpenListHash;

};

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

}

/* Determine the cost of this node, for road tracks */

int32 NPFRoadPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {

	TileIndex tile = current->tile;

	int32 cost = 0;

	/* Determine base length */

	switch (GetTileType(tile)) {

		case MP_TUNNELBRIDGE:

			if ((_map5[tile] & 0xF0)==0) {

				cost = NPFTunnelCost(current);

				break;

/* Determine the cost of this node, for railway tracks */

int32 NPFRailPathCost(AyStar* as, AyStarNode* current, OpenListNode* parent) {

	TileIndex tile = current->tile;

	byte trackdir = current->direction;

	int32 cost = 0;

	OpenListNode new_node;

	/* Determine base length */

	switch (GetTileType(tile)) {

		case MP_TUNNELBRIDGE:

			if ((_map5[tile] & 0xF0)==0) {

	/* Check for turns */

	if (current->direction != _next_trackdir[parent->path.node.direction])

		cost += _patches.npf_rail_curve_penalty;

	//TODO, with realistic acceleration, also the amount of straight track between

	//      curves should be taken into account, as this affects the speed limit.

	/* Check for occupied track */

	//TODO

	NPFMarkTile(tile);

	DEBUG(npf, 4)("Calculating G for: (%d, %d). Result: %d", TileX(current->tile), TileY(current->tile), cost);

	return cost;

}

/* Will find any depot */

int32 NPFFindDepot(AyStar* as, OpenListNode *current) {

	TileIndex tile = current->path.node.tile;

	if (IsTileDepotType(tile, as->user_data[NPF_TYPE]))

		return AYSTAR_FOUND_END_NODE;

	else

		return AYSTAR_DONE;

}

			/* Find out the exit direction first */

			if (IsRoadStationTile(src_tile))

				exitdir = GetRoadStationDir(src_tile);

			else /* Train or road depot. Direction is stored the same for both, in map5 */

				exitdir = GetDepotDirection(src_tile, type);

				/* We are headed inwards. We can only reverse here, so we'll not

				 * consider this direction, but jump ahead to the reverse direction.

				 * It would be nicer to return one neighbour here (the reverse

				 * trackdir of the one we are considering now) and then considering

				 * that one to return the tracks outside of the depot. But, because

				 * the code layout is cleaner this way, we will just pretend we are

	aystar->num_neighbours = i;

}

/*

 * Plan a route to the specified target (which is checked by target_proc),

 * from start1 and if not NULL, from start2 as well. The type of transport we

 * When we are looking for one specific target (optionally multiple tiles), we

 * should use a good heuristic to perform aystar search. When we search for

 * multiple targets that are spread around, we should perform a breadth first

 * search by specifiying CalcZero as our heuristic.

 */

	int r;

	NPFFoundTargetData result;

	/* Initialize procs */

	_npf_aystar.CalculateH = heuristic_proc;

	_npf_aystar.EndNodeCheck = target_proc;

	else

		assert(0);

	/* Initialize Start Node(s) */

	start1->user_data[NPF_TRACKDIR_CHOICE] = 0xff;

	start1->user_data[NPF_NODE_FLAGS] = 0;

	if (start2) {

		start2->user_data[NPF_TRACKDIR_CHOICE] = 0xff;

		start2->user_data[NPF_NODE_FLAGS] = 0;

		NPFSetFlag(start2, NPF_FLAG_REVERSE, true);

	}

	/* Initialize result */

	result.best_bird_dist = (uint)-1;

	result.best_path_dist = (uint)-1;

	result.best_trackdir = 0xff;

NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner) {

	AyStarNode start1;

	AyStarNode start2;

	start1.tile = tile1;

	start2.tile = tile2;

	start1.direction = trackdir1;

	start2.direction = trackdir2;

}

NPFFoundTargetData NPFRouteToStationOrTile(TileIndex tile, byte trackdir, NPFFindStationOrTileData* target, TransportType type, Owner owner) {

	/* We set this in case the target is also the start tile, we will just

	 * return a not found then */

}

NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner) {

}

NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner) {

	/* Okay, what we're gonna do. First, we look at all depots, calculate

	 * the manhatten distance to get to each depot. We then sort them by

	 * distance. We start by trying to plan a route to the closest, then

		/* Initialize Start Node */

		/* We set this in case the target is also the start tile, we will just

		 * return a not found then */

		start.user_data[NPF_TRACKDIR_CHOICE] = 0xff;

		start.user_data[NPF_NODE_FLAGS] = 0;

		/* Initialize result */

		result.best_bird_dist = (uint)-1;

		result.best_path_dist = (uint)-1;

		result.best_trackdir = 0xff;

	/* Do no change below values */

	NPF_HASH_SIZE = 1 << NPF_HASH_BITS,

	NPF_HASH_HALFBITS = NPF_HASH_BITS / 2,

	NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1

};

typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */

	TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */

	int station_index; /* station index we're heading for, or -1 when we're heading for a tile */

} NPFFindStationOrTileData;

enum { /* Indices into AyStar.userdata[] */

 * direction was taken (NPFGetBit(result.node, NPF_FLAG_REVERSE)) */

NPFFoundTargetData NPFRouteToStationOrTileTwoWay(TileIndex tile1, byte trackdir1, TileIndex tile2, byte trackdir2, NPFFindStationOrTileData* target, TransportType type, Owner owner);

/* Will search a route to the closest depot. */

/* Search using breadth first. Good for little track choice and inaccurate

NPFFoundTargetData NPFRouteToDepotBreadthFirst(TileIndex tile, byte trackdir, TransportType type, Owner owner);

/* Search by trying each depot in order of Manhattan Distance. Good for lots

 * of choices and accurate heuristics, such as water. */

NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, TransportType type, Owner owner);

void NPFFillWithOrderData(NPFFindStationOrTileData* fstd, Vehicle* v);

	{"npf_rail_station_penalty",    SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_station_penalty,     NULL},

	{"npf_rail_slope_penalty",      SDT_UINT32, (void*)(1 * NPF_TILE_LENGTH),   &_patches.npf_rail_slope_penalty,       NULL},

	/* This penalty is applied when a train makes a turn. Its value of 1 makes

	 * sure that it has a minimal impact on the pathfinding, only when two

	 * paths have equal length it will make a difference */

	{"npf_rail_curve_penalty",      SDT_UINT32, (void*)(1),                     &_patches.npf_rail_curve_penalty,       NULL},

	{"npf_buoy_penalty",            SDT_UINT32, (void*)(2 * NPF_TILE_LENGTH),   &_patches.npf_buoy_penalty,             NULL},

	/* This penalty is applied when a ship makes a turn. It is bigger than the

	 * rail curve penalty, since ships (realisticly) have more trouble with

	 * making turns */

	{"npf_water_curve_penalty",     SDT_UINT32, (void*)(NPF_TILE_LENGTH / 4),   &_patches.npf_water_curve_penalty,      NULL},

}

typedef struct TrainFindDepotData {

	uint best_length;

	uint tile;

	byte owner;

} TrainFindDepotData;

static bool TrainFindDepotEnumProc(uint tile, TrainFindDepotData *tfdd, int track, uint length, byte *state)

{

	if (IsTileType(tile, MP_RAILWAY) && _map_owner[tile] == tfdd->owner) {

		if ((_map5[tile] & ~0x3) == 0xC0) {

	uint tile = v->tile;

	assert(!(v->vehstatus & VS_CRASHED));

	tfdd.owner = v->owner;

	tfdd.best_length = (uint)-1;

	if (IsTileDepotType(tile, TRANSPORT_RAIL)){

		tfdd.tile = tile;

		tfdd.best_length = 0;

		return tfdd;

	}

	if (v->u.rail.track == 0x40) { tile = GetVehicleOutOfTunnelTile(v); }

	if (_patches.new_pathfinding_all) {

		NPFFoundTargetData ftd;

		byte trackdir = GetVehicleTrackdir(v);

		assert (trackdir != 0xFF);

		if (ftd.best_bird_dist == 0) {

			/* Found target */

			tfdd.tile = ftd.node.tile;

			/* Our caller expects a number of tiles, so we just approximate that

			* number by this. It might not be completely what we want, but it will

			* work for now :-) We can possibly change this when the old pathfinder

			* is removed. */

		}

	} else if (!_patches.new_depot_finding) {

		// search in all directions

		for(i=0; i!=4; i++)

			NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL);

	} else {

		// search in the forward direction first.

		i = v->direction >> 1;

		if (!(v->direction & 1) && v->u.rail.track != _state_dir_table[i]) { i = (i - 1) & 3; }

		NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL);

		if (tfdd.best_length == (uint)-1){

			// search in backwards direction

			i = (v->direction^4) >> 1;

			if (!(v->direction & 1) && v->u.rail.track != _state_dir_table[i]) { i = (i - 1) & 3; }

			NewTrainPathfind(tile, i, (TPFEnumProc*)TrainFindDepotEnumProc, &tfdd, NULL);

		}

	}

	if (flags & DC_EXEC) {

		v->dest_tile = tfdd.tile;

		v->current_order.type = OT_GOTO_DEPOT;

		v->current_order.flags = OF_NON_STOP | OF_FULL_LOAD;

		v->current_order.station = GetDepotByTile(tfdd.tile)->index;

		InvalidateWindowWidget(WC_VEHICLE_VIEW, v->index, STATUS_BAR);

	}

	return 0;

}

/* p1 = vehicle

		byte trackdir, trackdir_rev;

		Vehicle* last = GetLastVehicleInChain(v);

		NPFFillWithOrderData(&fstd, v);

		trackdir = GetVehicleTrackdir(v);

		assert(trackdir != 0xff);

		assert(trackdir_rev != 0xff);

		ftd = NPFRouteToStationOrTileTwoWay(v->tile, trackdir, last->tile, trackdir_rev, &fstd, TRANSPORT_RAIL, v->owner);

		if (ftd.best_bird_dist != 0) {

			/* We didn't find anything, just keep on going straight ahead */

	uint32 npf_rail_firstred_penalty; /* The penalty for when the first signal is red (and it is not an exit or combo signal) */

	uint32 npf_rail_firstred_exit_penalty; /* The penalty for when the first signal is red (and it is an exit or combo signal) */

	uint32 npf_rail_lastred_penalty; /* The penalty for when the last signal is red */

	uint32 npf_rail_station_penalty; /* The penalty for station tiles */

	uint32 npf_rail_slope_penalty; /* The penalty for sloping upwards */

	uint32 npf_rail_curve_penalty; /* The penalty for curves */

	uint32 npf_buoy_penalty; /* The penalty for going over (through) a buoy */

	uint32 npf_water_curve_penalty; /* The penalty for curves */

	bool population_in_label; // Show the population of a town in his label?

} Patches;

VARDEF char _userstring[USERSTRING_LEN];

VARDEF byte _vehicle_design_names;

/* tunnelbridge */

#define MAX_BRIDGES 13

#define NPF_TILE_LENGTH 100

/* Autoreplace vehicle stuff*/

VARDEF byte _autoreplace_array[256];

VARDEF uint16 _player_num_engines[256];

VARDEF byte _railtype_selected_in_replace_gui;