/* Do no change below values */

static const uint NPF_HASH_SIZE = 1 << NPF_HASH_BITS;

static const uint NPF_HASH_HALFBITS = NPF_HASH_BITS / 2;

static const uint NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1;

/** Meant to be stored in AyStar.targetdata */

struct NPFFindStationOrTileData {

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

	StationID station_index;  ///< station index we're heading for, or INVALID_STATION when we're heading for a tile

	bool reserve_path;        ///< Indicates whether the found path should be reserved

	StationType station_type; ///< The type of station we're heading for

	bool not_articulated;     ///< The (road) vehicle is not articulated

	const Vehicle *v;         ///< The vehicle we are pathfinding for

};

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

struct AyStarUserData {

	Owner owner;

	TransportType type;

	RailTypes railtypes;

	RoadTypes roadtypes;

	uint subtype;

};

/** Indices into AyStarNode.userdata[] */

enum AyStarNodeUserDataType {

	NPF_TRACKDIR_CHOICE = 0, ///< The trackdir chosen to get here

	NPF_NODE_FLAGS,

};

/** Flags for AyStarNode.userdata[NPF_NODE_FLAGS]. Use NPFSetFlag() and NPFGetFlag() to use them. */

enum NPFNodeFlag {

	NPF_FLAG_SEEN_SIGNAL,       ///< Used to mark that a signal was seen on the way, for rail only

	NPF_FLAG_2ND_SIGNAL,        ///< Used to mark that two signals were seen, rail only

	NPF_FLAG_3RD_SIGNAL,        ///< Used to mark that three signals were seen, rail only

	NPF_FLAG_REVERSE,           ///< Used to mark that this node was reached from the second start node, if applicable

	NPF_FLAG_LAST_SIGNAL_RED,   ///< Used to mark that the last signal on this path was red

	NPF_FLAG_LAST_SIGNAL_BLOCK, ///< Used to mark that the last signal on this path was a block signal

	NPF_FLAG_IGNORE_START_TILE, ///< Used to mark that the start tile is invalid, and searching should start from the second tile on

	NPF_FLAG_TARGET_RESERVED,   ///< Used to mark that the possible reservation target is already reserved

	NPF_FLAG_IGNORE_RESERVED,   ///< Used to mark that reserved tiles should be considered impassable

};

/** Meant to be stored in AyStar.userpath */

struct NPFFoundTargetData {

	uint best_bird_dist;    ///< The best heuristic found. Is 0 if the target was found

	uint best_path_dist;    ///< The shortest path. Is UINT_MAX if no path is found

	Trackdir best_trackdir; ///< The trackdir that leads to the shortest path/closest birds dist

	AyStarNode node;        ///< The node within the target the search led us to

	bool res_okay;          ///< True if a path reservation could be made

};

static AyStar _npf_aystar;

/* The cost of each trackdir. A diagonal piece is the full NPF_TILE_LENGTH,

 * the shorter piece is sqrt(2)/2*NPF_TILE_LENGTH =~ 0.7071

 */

#define NPF_STRAIGHT_LENGTH (uint)(NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH)

static const uint _trackdir_length[TRACKDIR_END] = {

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH,

	0, 0,

	NPF_TILE_LENGTH, NPF_TILE_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH, NPF_STRAIGHT_LENGTH

};

/**

 * Returns the current value of the given flag on the given AyStarNode.

 */

static inline bool NPFGetFlag(const AyStarNode *node, NPFNodeFlag flag)

{

	return HasBit(node->user_data[NPF_NODE_FLAGS], flag);

}

/**

 * Sets the given flag on the given AyStarNode to the given value.

 */

static inline void NPFSetFlag(AyStarNode *node, NPFNodeFlag flag, bool value)

{

	SB(node->user_data[NPF_NODE_FLAGS], flag, 1, value);

}

bool CheckIgnoreFirstTile(const PathNode *node)

{

	return (node->parent == nullptr && HasBit(node->node.user_data[NPF_NODE_FLAGS], NPF_FLAG_IGNORE_START_TILE));

}

/**

 * Calculates the minimum distance travelled to get from t0 to t1 when only

 * using tracks (ie, only making 45 degree turns). Returns the distance in the

 * NPF scale, ie the number of full tiles multiplied by NPF_TILE_LENGTH to

 * prevent rounding.

 */

static uint NPFDistanceTrack(TileIndex t0, TileIndex t1)

{

	const uint dx = Delta(TileX(t0), TileX(t1));

	const uint dy = Delta(TileY(t0), TileY(t1));

	/* OPTIMISATION:

	 * Original: diagTracks = max(dx, dy) - min(dx,dy);

	 * Proof:

	 * (dx+dy) - straightTracks  == (min + max) - straightTracks = min + max - 2 * min = max - min */

	const uint diagTracks = dx + dy - straightTracks; // The number of diagonal (full tile length) tracks.

	/* Don't factor out NPF_TILE_LENGTH below, this will round values and lose

	 * precision */

	return diagTracks * NPF_TILE_LENGTH + straightTracks * NPF_TILE_LENGTH * STRAIGHT_TRACK_LENGTH;

}

/**

 * Calculates a hash value for use in the NPF.

 * @param key1 The TileIndex of the tile to hash

 * @param key2 The Trackdir of the track on the tile.

 *

 * @todo Think of a better hash.

 */

static uint NPFHash(uint key1, uint key2)

{

	/* TODO: think of a better hash? */

	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;

	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;

	assert(IsValidTrackdir((Trackdir)key2));

	assert(IsValidTile(key1));

	return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;

}

static int32 NPFCalcZero(AyStar *as, AyStarNode *current, OpenListNode *parent)

{

	return 0;

}

/* Calculates the heuristic to the target station or tile. For train stations, it

 * takes into account the direction of approach.

 */

static int32 NPFCalcStationOrTileHeuristic(AyStar *as, AyStarNode *current, OpenListNode *parent)

{

	NPFFindStationOrTileData *fstd = (NPFFindStationOrTileData*)as->user_target;

	NPFFoundTargetData *ftd = (NPFFoundTargetData*)as->user_path;

	TileIndex from = current->tile;

	TileIndex to = fstd->dest_coords;

	uint dist;

	AyStarUserData *user = (AyStarUserData *)as->user_data;

	/* aim for the closest station tile */

	if (fstd->station_index != INVALID_STATION) {

		to = CalcClosestStationTile(fstd->station_index, from, fstd->station_type);

	}

	if (user->type == TRANSPORT_ROAD) {

		/* Since roads only have diagonal pieces, we use manhattan distance here */

		dist = DistanceManhattan(from, to) * NPF_TILE_LENGTH;

	} else {

		/* Ships and trains can also go diagonal, so the minimum distance is shorter */

		dist = NPFDistanceTrack(from, to);

	}

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

	if (dist < ftd->best_bird_dist) {

		ftd->best_bird_dist = dist;

		ftd->best_trackdir = (Trackdir)current->user_data[NPF_TRACKDIR_CHOICE];

	}

	return dist;

}

/* Fills AyStarNode.user_data[NPF_TRACKDIRCHOICE] with the chosen direction to

 * get here, either getting it from the current choice or from the parent's

 * choice */

static void NPFFillTrackdirChoice(AyStarNode *current, OpenListNode *parent)

{

	if (parent->path.parent == nullptr) {

		Trackdir trackdir = current->direction;

		/* This is a first order decision, so we'd better save the

		 * direction we chose */

		current->user_data[NPF_TRACKDIR_CHOICE] = trackdir;

		DEBUG(npf, 6, "Saving trackdir: 0x%X", trackdir);

	} else {

		/* We've already made the decision, so just save our parent's decision */

		current->user_data[NPF_TRACKDIR_CHOICE] = parent->path.node.user_data[NPF_TRACKDIR_CHOICE];

	}

}

/* Will return the cost of the tunnel. If it is an entry, it will return the

 * cost of that tile. If the tile is an exit, it will return the tunnel length

 * including the exit tile. Requires that this is a Tunnel tile */

static uint NPFTunnelCost(AyStarNode *current)

{

	DiagDirection exitdir = TrackdirToExitdir(current->direction);

	TileIndex tile = current->tile;

	if (GetTunnelBridgeDirection(tile) == ReverseDiagDir(exitdir)) {

		/* We just popped out if this tunnel, since were

		 * facing the tunnel exit */