//!
/**
 **************************************************************************************************************************************************************
 * A* path-finding implementation
 **************************************************************************************************************************************************************
 * @file   AStar.h
 * @author Guillaume Blanchard
 **************************************************************************************************************************************************************/
#pragma once

/**************************************************************************************************************************************************************
 * Includes
 **************************************************************************************************************************************************************/

// std
#include <vector>
#include <algorithm>

// BotStrike
#include "BotStrike.h"
#include "BinaryHeap.h"

// noe
#include <noe/noe.h>
#include <noe/singleton.h>
#include <noe/math.h>

namespace BS {

/**************************************************************************************************************************************************************
 * Implementation
 **************************************************************************************************************************************************************/

/**
 * Node structure used by A* algorithm
 */
struct CNode
{
// Member variables

	CNode* Parent;     ///< Parent node
	f32   CostToStart; ///< Cost to go from this node to the start point (G)
	f32   CostToGoal;  ///< Cost to go from this node to the goal (H)
	i32   Flag;        ///< Node's flag (state, etc.)
	i16   X;           ///< X coordinate into the grid space
	i16   Y;           ///< Y coordinate into the grid space
	
	/// Node flag enumeration
	enum FLAG
	{
		FLAG_FREE = 0, ///< Node not yet explored
		FLAG_OPEN,     ///< Node in the open list (explored but not yet checked)
		FLAG_CLOSE,    ///< Node in the close list (explored & checked)
	};

// Member methods

	/**
	 * Reset the node to initiale value
	 */
	void Reset(i32 x, i32 y)
	{
		Parent = NULL;
		CostToStart = 0;
		CostToGoal = 0;
		Flag = FLAG_FREE;
		X = scast<i16>(x);
		Y = scast<i16>(y);
	}

	/**
	 * Compute total node cost
	 * @return		Cost-to-start plus cost-to-goal
	 */
	f32 ComputeCost() const
	{
		return CostToStart + CostToGoal;
	}
};

/**
 * Node pointer wrapper to allow operator overload.
 * Used as binary heap data.
 */
struct CNodePointer
{
// Member variables

	CNode* Addr; ///< Node address.

// Member methods

	CNodePointer(CNode* node = NULL): Addr(node) {} ///< Constructor.

	bool operator < (const CNodePointer& node) const ///< Comparaison operator (don't need to be mathematical < operator)
	{
		return(Addr->CostToGoal < node.Addr->CostToGoal);   
	}
};

//-------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
 * A* algorithm implementation
 */
class CAStar: public noe::Singleton<CAStar>
{
protected: // member types

	typedef f32 (*CostToGoalFunc)(CNode* node); ///< Cost to goal computation function. Used to customize A* algorithm

public: // member methods

	// Constructor
	CAStar();

	// Initialize the A* data structure.
	void Initialize(const BS::CArena* arena);

	// Compare two nodes and check if the first one is bigger than second one.
	static bool IsBigger(const CNode* n1, const CNode* n2);

	// Check if a given coordinate point to a valid cell node
	bool IsValidNode(i32 x, i32 y) const;

	// Get the lowset (cheaper) node from the open list.
	CNode* PickLowestNode();

	// Compute distance-to-goal cost using manathan algorithm [cost = dx + dy]
	static f32 DistanceToGoalManathan(CNode* node);

	// Compute distance-to-goal cost in step unit.
	static f32 DistanceToGoal(CNode* node);
	
	// Compute distance-to-goal cost with some trick to incite bot to go behind its target.
	static f32 DistanceToBehindGoal(CNode* node);

	// Add a node to the open list. Or replace it if new path is cheaper than previous one.
	void AddToOpenList(CNode* node, CNode* parent);

	// Add a node to the close list.
	void AddToCloseList(CNode* node);

	// Process path-finding.
	BOOL FindPath(std::vector<CNode*>& path, i32 startX, i32 startY, i32 targetX, i32 targetY, i32 targetDX, i32 targetDY, i32 dist=0, CostToGoalFunc func=DistanceToBehindGoal);

protected: // member variables

	std::vector<CNode>        m_NodeList;    ///< The nodes pool
	CBinaryHeap<CNodePointer> m_OpenList;    ///< The open list 
	i32                       m_CloseNumber; ///< The close nodes list
	i32                       m_TargetX;     ///< Target position
	i32                       m_TargetY;     ///< Target position
	i32                       m_TargetDX;    ///< Target orientation
	i32                       m_TargetDY;    ///< Target orientation
	const BS::CArena*         m_Arena;       ///< Arena information
	CostToGoalFunc            m_CostToGoal;  ///< Cost to goal computation function
};

/**************************************************************************************************************************************************************/

} // namespace BS