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

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

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

// BotStrike
#include "BotStrike.h"

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

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

/**
 * Node structure used by A* algorithm
 */
struct Node
{
	Node* 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,
		FLAG_OPEN,
		FLAG_CLOSE,
	};

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


//-------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
 * A* algorithm implementation
 */
class A_Star: public noe::Singleton<A_Star>
{
public:

	/**
	 * Constructor
	 */
	A_Star(): m_TargetX(0), m_TargetY(0), m_TargetDX(0), m_TargetDY(0), m_CloseNumber(0), m_Arena(NULL) {}

	/**
	 *
	 */
	void Initialize(const BS::CArena* arena)
	{
		m_TargetX = 0;
		m_TargetY = 0;
		m_TargetDX = 0;
		m_TargetDY = 0;
		m_CloseNumber = 0;
		m_Arena = arena;
		
		m_OpenList.clear();
		m_NodeList.resize(m_Arena->width * m_Arena->height);
		loop(y, m_Arena->height)
			loop(x, m_Arena->width)
				m_NodeList[y * m_Arena->width + x].Reset(x, y);
	}

	/**
	 *
	 */
	static bool IsBigger(const Node* n1, const Node* n2)
	{
		return n1->ComputeCost() > n2->ComputeCost();
	}

	/**
	 *
	 */
	bool IsValidNode(i32 x, i32 y) const
	{
		return !(x < 0 || y < 0 || x >= m_Arena->width || y >= m_Arena->height);
	}

	/**
	 *
	 */
	Node* PickLowestNode()
	{
		std::sort(m_OpenList.begin(), m_OpenList.end(), IsBigger);
		Node* node = m_OpenList.back();
		m_OpenList.pop_back();
		return node;
	}

	/**
	 *
	 */
	f32 DistanceToGoalManathan(Node* node) const
	{
		return scast<f32>(abs(node->X - m_TargetX) + abs(node->Y - m_TargetY));
	}

	/**
	 *
	 */
	f32 DistanceToGoal(Node* node) const
	{
		return scast<f32>(noe::Max(abs(node->X - m_TargetX), abs(node->Y - m_TargetY)));
	}

	/**
	 *
	 */
	f32 DistanceToBehindGoal(Node* node) const
	{
		i32 dist = abs(node->X - m_TargetX) + abs(node->Y - m_TargetY);
		
		// try to get behind ennemy
		i32 dx = node->X - m_TargetX;
		i32 dy = node->Y - m_TargetY;
		if((dx > 0 && m_TargetDX < 0) || (dx < 0 && m_TargetDX > 0))
			dist *= 2;
		if((dy > 0 && m_TargetDY > 0) || (dy < 0 && m_TargetDY < 0))
			dist /= 2;
		if((dx > 0 && m_TargetDX < 0) || (dx < 0 && m_TargetDX > 0))
			dist *= 2;
		if((dy > 0 && m_TargetDY > 0) || (dy < 0 && m_TargetDY < 0))
			dist /= 2;

		return scast<f32>(dist);
	}

	/**
	 *
	 */
	void AddToOpenList(Node* node, Node* parent)
	{
		if(node->Flag == Node::FLAG_FREE)
		{
			node->Parent = parent;
			node->CostToStart = parent ? parent->CostToStart + 10.f : 0.f;
			node->CostToGoal = 10.f * DistanceToBehindGoal(node);
			node->Flag = Node::FLAG_OPEN;
			m_OpenList.push_back(node);
		}
		else if(node->Flag == Node::FLAG_OPEN)
		{
			f32 cost = parent ? parent->CostToStart + 10.f : 0.f;
			if(cost < node->CostToStart)
			{
				node->Parent = parent;
				node->CostToStart = cost;
			}
		}
		// else if(node->Flag == Node::FLAG_CLOSE) // do nothing
	}

	/**
	 *
	 */
	void AddToCloseList(Node* node)
	{
		if(node->Flag != Node::FLAG_CLOSE)
		{
			node->Flag = Node::FLAG_CLOSE;
			m_CloseNumber++;
		}
	}

	/**
	 *
	 */
	BOOL FindPath(i32 startX, i32 startY, i32 targetX, i32 targetY, i32 targetDX, i32 targetDY, i32 dist, std::vector<Node*>& path)
	{
		static int dir[8][2] = { {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0} };

		m_TargetX = targetX;
		m_TargetY = targetY;
		m_TargetDX = targetDX;
		m_TargetDY = targetDY;

		i32 x = startX;
		i32 y = startY;
		
		Node* node = &m_NodeList[y * m_Arena->width + x];
		AddToOpenList(node, NULL);

		for( ;; )
		{
			if(m_OpenList.size() == 0)
				return FALSE;

			node = PickLowestNode();

			if(DistanceToGoal(node) < dist)
				break;
		
			loop(i, 8)
			{
				x = node->X + dir[i][0];
				y = node->Y + dir[i][1];
				if(IsValidNode(x, y))
				{
					if((m_Arena->cell(x, y) & BS::ECell::Box)
					|| (m_Arena->cell(x, y) & BS::ECell::Blue)
					|| (m_Arena->cell(x, y) & BS::ECell::Red)
					|| (m_Arena->cell(x, y) & BS::ECell::Grenade))
						continue;

					Node* next = &m_NodeList[y * m_Arena->width + x];
					AddToOpenList(next, node);
				}
			}

			AddToCloseList(node);

			if(m_OpenList.size() + m_CloseNumber >= m_NodeList.size())
				return FALSE;
		}

		while(node->Parent != NULL)
		{
			path.push_back(node);
			node = node->Parent;
		}
		
		return TRUE;
	}

protected:

	std::vector<Node>  m_NodeList;  ///< The nodes pool
	std::vector<Node*> m_OpenList;  ///< The open list (must be sorted!)
	i32                m_CloseNumber; ///< The close nodes list
	i32                m_TargetX;
	i32                m_TargetY;
	i32                m_TargetDX;
	i32                m_TargetDY;
	const BS::CArena*  m_Arena;
};

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