#ifdef ASURA_USE_NEW_NAV_STUFF

//////////////////////////////////////////////////////////////////////////////
//
// Asura_Nav_Types.h
//
// Copyright (C) 2009 Rebellion. All Rights Reserved.
//
//////////////////////////////////////////////////////////////////////////////

#ifdef ASURA_USE_PRAGMA_ONCE
#pragma once
#endif

#ifndef __ASURA_NAV_TYPES_H__
#define __ASURA_NAV_TYPES_H__ 1

// I N C L U D E S ///////////////////////////////////////////////////////////

// asura
#include "Core/Asura_LinkList.h"
#include "Core/Asura_Maths.h"

// F O R W A R D   D E C L A R A T I O N S ///////////////////////////////////

struct Asura_AI_NavConnection;
class Asura_AI_NavVertex;
struct Asura_AStarData;
class Asura_ResizingMempool;

//////////////////////////////////////////////////////////////////////////////
//
// Types used in Asura_Navigation.
//
//////////////////////////////////////////////////////////////////////////////

namespace Asura_Navigation
{
	void Initialise();
	void Shutdown();

	// Standard test parameters for the majority of the Asura_Navigation functions.
    class TestParams
    {
	public:
        TestParams();
		virtual ~TestParams() {}

		// Returns whether this is a valid waypoint for the given test parameters.
		virtual bool IsValidWaypoint( const Asura_AI_NavVertex& xWP ) const;
		// Returns whether this is a valid link for the given test parameters.
		virtual bool IsValidLink( const Asura_AI_NavConnection& xLink ) const;

        u_int          m_uPathfinderFlags;
		float		   m_fActorRadius;
		float		   m_fActorHeight;
		// Whether to reject waypoints that do not have any links.
		bool           m_bRejectIsolatedWPs;
        // Whether to reject waypoints that are not orientated the same as us.
        bool           m_bRejectNonalignedWPs;
		// Whether we can default to a linear search after a tree search has failed if we have to search the waypoints.
		bool           m_bAllowLinearSearch;
        Asura_Vector_3 m_xNormal;
        u_short        m_usZone;
    };
	extern const TestParams s_xStandardTParams;

	// Parameters for the 'at position' test.
    struct APParams
    {
        APParams();

		// Only test the maximum sphere (radius is largest of coplanar and perpendicular offsets).
		bool		   m_bSphericalTestOnly;
        // The allowed offset parallel to the local XZ plane at the destination.
        float          m_fMaxCoplanarOffset;
        // The allowed offset in the local Y direction at the destination.
        float          m_fMaxPerpendicularOffset;
		// Whether to orientate the test BB using the provided normal.
		bool           m_bUseNormal;
		// Surface normal at the test position.
        Asura_Vector_3 m_xNormal;
    };
	extern const APParams s_xStandardAPParams;

	// Standard path point for use in the A* and Path stuff.
	struct PathPoint
	{
		enum ConstructionFlags
		{
			// Point was generated directly from a waypoint.
			WAYPOINT_POINT = 0x01
		};

		void Initialise();

		// The WPID that this path point is within, if any.
		u_short		   m_usWPID;
		// The index of the WP link corresponding to the path segment this path point is on, if any.
		u_char		   m_ucLinkIndex;
		// Some flags are used during construction by the various algorithms.
		// After construction this member can be used for whatever projects require.
		u_char		   m_ucFlags;
		// The position of the path point. (Note: not necessarily the position of the associated WP.)
		Asura_Vector_3 m_xPosition;
	};

	// Data to store an in-progress A* search.
	struct AStarData
	{
		// Used to pre-allocate A* storage for the various nav handlers.
		static void InitialiseAStarStorage( const u_int uNumWPs );
		static void ShudownAStarStorage( const u_int uNumWPs );

		// Used to fetch and return A* data for an A* search.
		static AStarData* AllocateAStarData( const u_int uNumWPs );
		static void       DeallocateAStarData( AStarData* pxASD );

		struct AStarNode
		{
			float      m_fCostToHere;
			float      m_fCostToGoal;
			u_int      m_uIndex;
			AStarNode* m_pxParent;
		};
		struct OpenClosedElement
		{
			bool m_bOpen;
			bool m_bClosed;
		};
		struct OpenListElement
		{
			float m_fTotalCost;
			u_int m_uIndex;
		};

		AStarData();
		AStarData( const AStarData& xRHS );
		~AStarData();

		u_int      GetCapacity() const { return m_uArraySize; }
		void	   AddNodeToOpenList( AStarNode* pxNode );
		AStarNode* GetOpenListNode();
		AStarData& operator=( const AStarData& xRHS );

		AStarNode*			m_pxNodeList;
		OpenClosedElement*	m_pxOpenClosedVector;
		// The open list is implemented as a min-heap.
		OpenListElement*	m_pxOpenList;
		int					m_iNumOpenListEntries;

	private:
		bool Initialise( const u_int uNumNodes );
		void BeginSearch( const u_int uNumNodes );
		void EndSearch();

	private:
		u_int m_uArraySize;
		bool  m_bInUse;

		// A list of AStarData structures that have been initialised to whatever size.
		static Asura_LinkList< AStarData > s_xAStarDataList;
	};

	// Base search functor.
	class SearchFunctor
	{
	public:
		enum Status
		{
			STATUS_IN_ERROR,
			STATUS_OK,
			STATUS_WORKING
		};

	public:
		virtual ~SearchFunctor() {}
		virtual Status Search() = 0;
		virtual Status BeginIterativeSearch() = 0;
		virtual Status IterateSearch() = 0;

		void SetInputBuffer( const Asura_AI_NavVertex* pxWPs, u_int uNumWPs ) { m_pxWPs = pxWPs; m_uNumWPs = uNumWPs; }

	protected:
		// Returns whether all the search's data is set up ok.
		virtual bool VerifyInputData();

		void GetInputBuffer( const Asura_AI_NavVertex*& pxWPs, u_int& uNumWPs ) { pxWPs = m_pxWPs; uNumWPs = m_uNumWPs; }

	private:
		const Asura_AI_NavVertex* m_pxWPs;
		u_int                     m_uNumWPs;
	};

	// Base A* functor.
	class AStarFunctor : public SearchFunctor
	{
	public:
		AStarFunctor();

		// Performs an A* search, outputting the path points to the supplied buffer.
		virtual Status Search();
		virtual Status BeginIterativeSearch();
		virtual Status IterateSearch();
		// Removes redundant waypoints if required and performs string-pulling.
		virtual bool PostSearchProcessing();

		void SetTestParams( const TestParams& xTestParams ) { m_pxTestParams = &xTestParams; }
		void SetOutputBuffer( Asura_LinkList< PathPoint >* pxPathPoints ) { m_pxPathPoints = pxPathPoints; }
		void SetShouldRefinePath( bool bVal ) { m_bRefinePath = bVal; }

		#ifdef ASURA_TOOLS
		const AStarData& GetAStarData() const { return *m_pxAStarData; }
		#endif

	protected:
		// Returns whether all the search's data is set up ok.
		virtual bool VerifyInputData();
		// Returns the waypoint ID the search should start from.
		virtual u_int GetStartWPID() = 0;
		// Returns the estimated cost to the goal from the waypoint.
		virtual float EstimateCostToGoal( const u_int uWPID, const Asura_AI_NavVertex& xWP ) = 0;
		// Returns whether to ignore the link or not.
		virtual bool ShouldIgnoreLink( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
									   const Asura_AI_NavConnection& xLink,
									   const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );
		// Returns the cost associated with travelling this link.
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP ) = 0;
		// Returns whether this waypoint is the goal or not.
		virtual bool GoalAchieved( const u_int uWPID, const Asura_AI_NavVertex& xWP ) = 0;

		// Set the link indices of the path points.
		bool SetLinkIndices();
		// Adds path positions at the start and destination.
		bool AddStartAndDestPositions();
		// Removes redundant waypoints from the path by casting rays in waypoint space.
		virtual bool RefinePath();
		// Adds extra points the core path following algorithm can better use.
		virtual bool AnnotatePath();

		virtual const Asura_Vector_3& GetStartPosition() const = 0;
		virtual const Asura_Vector_3& GetDestinationPosition() const = 0;
		virtual bool  WaypointIsValidForRemoval( const u_int uWPID, const Asura_AI_NavVertex& xWP ) { return true; }
		virtual bool  LinkIsValidForRemoval( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP ) { return true; }

		const TestParams* GetTestParams() const { return m_pxTestParams; }
		Asura_LinkList< PathPoint >* GetPathPoints() const { return m_pxPathPoints; }
		bool GetShouldRefinePath() const { return m_bRefinePath; }

	private:
		bool AllocateAStarData( const u_int uNumWPs );
		void DeallocateAStarData();

	private:
		const TestParams*			 m_pxTestParams;
		Asura_LinkList< PathPoint >* m_pxPathPoints;
		bool						 m_bRefinePath;
        AStarData*                   m_pxAStarData;
		u_int                        m_uCurrentWPID;

		typedef SearchFunctor PARENT;
	};

	// Standard from -> to path.
	class FromToPathFindFunctor : public AStarFunctor
	{
	public:
		FromToPathFindFunctor();

		void SetFromToPos( const Asura_Vector_3& xFrom, const Asura_Vector_3& xTo, const TestParams& xTestParams = s_xStandardTParams );
		void SetFromToWPIDs( const u_int uFromWPID, const u_int uToWPID );

	protected:
		virtual bool VerifyInputData();
		virtual u_int GetStartWPID() { return m_uFromWPID; }
		virtual float EstimateCostToGoal( const u_int uWPID, const Asura_AI_NavVertex& xWP );
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );
		virtual bool GoalAchieved( const u_int uWPIndex, const Asura_AI_NavVertex& xWP );

		virtual const Asura_Vector_3& GetStartPosition() const { return m_xFromPos; }
		virtual const Asura_Vector_3& GetDestinationPosition() const { return m_xToPos; }

		u_int GetFromWPID() const { return m_uFromWPID; }
		u_int GetToWPID()   const { return m_uToWPID; }

	private:
		Asura_Vector_3 m_xFromPos;
		Asura_Vector_3 m_xToPos;
		u_int m_uFromWPID;
		u_int m_uToWPID;

		typedef AStarFunctor PARENT;
	};

	// From -> to path with a preferred range from a base position.
	class FromToWithRangePathFindFunctor : public FromToPathFindFunctor
	{
	public:
		FromToWithRangePathFindFunctor();

		void SetBasePos( const Asura_Vector_3& xBasePos ) { m_xBasePos = xBasePos; }
		void SetIdealRange( const float fIdealRange ) { m_fIdealRangeSq = fIdealRange * fIdealRange; }

	protected:
		virtual bool VerifyInputData();
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );

	private:
		Asura_Vector_3 m_xBasePos;
		float m_fIdealRangeSq;

		typedef FromToPathFindFunctor PARENT;
	};

	// Away from position path.
	class AwayFromPathFindFunctor : public AStarFunctor
	{
	public:
		AwayFromPathFindFunctor();

		void SetAvoidPosAndDistance( const Asura_Vector_3& xAvoidPos, const float fDistance );
		void SetFromPos( const Asura_Vector_3& xFrom, const TestParams& xTestParams = s_xStandardTParams );
		void SetFromWPID( const u_int usFromWPID );

	protected:
		virtual bool VerifyInputData();
		virtual u_int GetStartWPID() { return m_uFromWPID; }
		virtual float EstimateCostToGoal( const u_int uWPID, const Asura_AI_NavVertex& xWP );
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );
		virtual bool GoalAchieved( const u_int uWPID, const Asura_AI_NavVertex& xWP );

		virtual const Asura_Vector_3& GetStartPosition() const { return m_xFromPos; }
		virtual const Asura_Vector_3& GetDestinationPosition() const;

		u_int GetFromWPID()					const { return m_uFromWPID; }
		const Asura_Vector_3& GetAvoidPos() const { return m_xAvoidPos; }
		float GetDist()						const { return m_fDist; }
		float GetDistSq()					const { return m_fDistSq; }

	private:
		u_int		   m_uFromWPID;
		Asura_Vector_3 m_xFromPos;
		Asura_Vector_3 m_xAvoidPos;
		float		   m_fDist;
		float		   m_fDistSq;

		typedef AStarFunctor PARENT;
	};

	// Away from position in direction path.
	class AwayFromInDirPathFindFunctor : public AwayFromPathFindFunctor
	{
	public:
		AwayFromInDirPathFindFunctor();

		void SetDirection( const Asura_Vector_3& xDirection ) { m_xDirection = xDirection; }

	protected:
		virtual bool VerifyInputData();
		virtual float EstimateCostToGoal( const u_int uWPID, const Asura_AI_NavVertex& xWP ) { return 0.0f; }
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );

		const Asura_Vector_3& GetDirection() const { return m_xDirection; }

	protected:
		Asura_Vector_3 m_xDirection;

		typedef AwayFromPathFindFunctor PARENT;
	};

	// Breadth first search.
	class BreadthFirstFunctor : public SearchFunctor
	{
	public:
		BreadthFirstFunctor();

		virtual Status Search();
		virtual	Status BeginIterativeSearch();
		virtual	Status IterateSearch();

		void SetStartPosition( const Asura_Vector_3& xPos, const TestParams& xTestParams = s_xStandardTParams );
		void SetStartWPID( const u_int uWPID ) { m_uStartWPID = uWPID; }
		void SetRange( const float fRange ) { m_fRange = fRange; }

		#ifdef ASURA_TOOLS
		const AStarData& GetAStarData() const { return *m_pxAStarData; }
		#endif

	protected:
		// Returns whether all the search's data is set up ok.
		virtual bool VerifyInputData();
		// Returns whether to ignore the link or not.
		virtual bool ShouldIgnoreLink( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
									   const Asura_AI_NavConnection& xLink,
									   const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP ) { return false; }
		// Called once for every node the search touches.
		// Returns whether the search should stop or not.
		// This is optional as the search will automatically stop once it has filled a circle of radius = maximum range.
		virtual bool VisitNode( const u_int uWPID, const Asura_AI_NavVertex& xWP ) { return false; }

		u_int GetStartWPID() const { return m_uStartWPID; }
		float GetRange() const { return m_fRange; }

	private:
		void  AddWIPDToOpenList( const u_int uWPID );
		u_int GetOpenListWPID();

	private:
		u_int      m_uStartWPID;
		float      m_fRange;
		u_int      m_uCurrentWPID;
		AStarData* m_pxAStarData;
        u_int      m_uOpenListFront;
        u_int      m_uOpenListBack;

		typedef SearchFunctor PARENT;
	};

	// Searches in a direction to a maximum range.
	// Once at the maximum range it spreads out and round until it has filled a circle of radius = maximum range.
	class InDirectionFunctor : public SearchFunctor
	{
	public:
		InDirectionFunctor();

		virtual Status Search();
		virtual	Status BeginIterativeSearch();
		virtual	Status IterateSearch();

		void SetStartPosition( const Asura_Vector_3& xPos, const TestParams& xTestParams = s_xStandardTParams );
		void SetStartWPID( const u_int uWPID );
		void SetRange( const float fRange ) { m_fRangeSq = fRange * fRange; }
		void SetDirection( const Asura_Vector_3& xDirection ) { m_xDirection = xDirection; }

		#ifdef ASURA_TOOLS
		const AStarData& GetAStarData() const { return *m_pxAStarData; }
		#endif

	protected:
		// Returns whether all the search's data is set up ok.
		virtual bool VerifyInputData();
		// Returns whether to ignore the link or not.
		virtual bool ShouldIgnoreLink( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
									   const Asura_AI_NavConnection& xLink,
									   const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );
		// Returns the cost associated with travelling this link.
		virtual float EstimateTraversalCost( const u_int uSourceWPID, const Asura_AI_NavVertex& xSourceWP,
											 const Asura_AI_NavConnection& xLink,
											 const u_int uTargetWPID, const Asura_AI_NavVertex& xTargetWP );
		// Called once for every node the search touches.
		// Returns whether the search should stop or not.
		// This is optional as the search will automatically stop once it has filled a circle of radius = maximum range.
		virtual bool VisitNode( const u_int uWPID, const Asura_AI_NavVertex& xWP ) { return false; }

		u_int GetStartWPID() const { return m_uStartWPID; }
		const Asura_Vector_3& GetStartPosition() const { return m_xStartPosition; }
		const Asura_Vector_3& GetDirection() const { return m_xDirection; }
		float GetRange() const { return Asura_Maths::Sqrt( m_fRangeSq ); }

	private:
        u_int          m_uStartWPID;
		Asura_Vector_3 m_xStartPosition;
        float          m_fRangeSq;
		Asura_Vector_3 m_xDirection;
        u_int          m_uCurrentWPID;
		AStarData*     m_pxAStarData;
        u_int          m_uOpenListFront;
        u_int          m_uOpenListBack;

		typedef SearchFunctor PARENT;
	};

	class Path
	{
	public:
		enum Status
		{
			STATUS_IN_ERROR,
			STATUS_OK,
			STATUS_WORKING,
			STATUS_PARTIAL_PATH,
			STATUS_NO_PATH_FOUND
		};

	public:
		Path();
		~Path();

		Status FindPath( AStarFunctor& xAStarFunctor );
		// The owner of the A* functor is responsible for keeping it around whilst the asynchronous search is in progress.
		//Status FindPathASync( AStarFunctor& xAStarFunctor );
		void StopWork();

		Status GetStatus() const { return m_eStatus; }
		void ClearPath();
		Asura_LinkList< PathPoint >& GetPathPoints() { return m_xPathPoints; }
		const Asura_ListElt< PathPoint >* GetCurrentPathPoint() const { return m_pxCurrentPointElt; }
		u_int GetPathPointCount() const { return m_xPathPoints.Size(); }
		float GetPathTotalLength() const;
		float GetPathRemainingLength() const;
		// Works from where we think we currently are on the path and updates this during the calculations.
		bool UpdateNearestPositionOnPath( const Asura_Vector_3& xPosition, float fLookAheadDistance,
										  Asura_Vector_3& xPathPosition, bool& bIsDestination, const Asura_Navigation::APParams& xParams = s_xStandardAPParams ) const;
		// Works from where we think we currently are on the path.
		// Note that this does not update where we think we current are on the path,
		// so it can be called any number of times with whatever look ahead distance is necessary.
		//bool CalcNearestPositionOnPath( const Asura_Vector_3& xPosition, float fLookAheadDistance,
		//							 Asura_Vector_3& xPathPosition, bool& bIsDestination ) const;

#ifdef _DEBUG
		Asura_LinkList< PathPoint >& GetOriginalPathPoints() { return m_xOriginalPathPoints; }
		static void RenderPath( const Asura_LinkList< PathPoint >& xPath, u_int uARGB = 0xffffffff );
		static void RenderPathWPs( const Asura_LinkList< PathPoint >& xPath, u_int uARGB = 0xffffffff );
#endif

		static void InitialisePathMempools();
		static void ShutdownPathMempools();

	private:
		static float GetPathLengthAfter( const Asura_ListElt< PathPoint >* pxElt );

		static void* AllocatePathPointNode();
		static void  DeallocatePathPointNode( void* pNode );

	private:
		AStarFunctor* m_pxAStarFunctor;
		Status m_eStatus;
		Asura_LinkList< PathPoint > m_xPathPoints;
		// These two points together define the path segment we're currently on.
		mutable Asura_ListElt< PathPoint >* m_pxCurrentPointElt;
		mutable Asura_ListElt< PathPoint >* m_pxNextPointElt;

#ifdef _DEBUG
		Asura_LinkList< PathPoint > m_xOriginalPathPoints;
#endif

		// Static mempool for global path storage.
		static Asura_ResizingMempool* s_pxPathPointsMempool;
	};
}

//////////////////////////////////////////////////////////////////////////////
//
// 
//
//////////////////////////////////////////////////////////////////////////////

#endif //__ASURA_NAV_TYPES_H__

#endif // #ifdef ASURA_USE_NEW_NAV_STUFF
