/*!
	@project Rune
	@file RuPathEngine_Base.h

	Copyright (c) 2004-2005 All rights reserved

	@author John Tang
	@date 2005/12/21
*/

#ifndef _RUPATHENGINE_BASE_H_
#define _RUPATHENGINE_BASE_H_

#include "../Collision/RuCollision_Base.h"

#pragma unmanaged

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

enum RuPathNodeLinkType
{
	ruPATHNODELINKTYPE_NONE					= 0,					//!< The link is invalid
	ruPATHNODELINKTYPE_FIXED				= 1,					//!< The link is a fixed block-to-block
	ruPATHNODELINKTYPE_RELOCATABLE			= 2,					//!< The link is a generic first ID match

	ruPATHNODELINKTYPE_FORCE_DWORD			= 0x7FFFFFFF
};

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

inline INT32 RuPathEngine_MakeGraphKey(INT32 x, INT32 z)
{
	return ((x & 0x000001FF) << 9) | (z & 0x000001FF);
}

inline INT32 RuPathEngine_MakeNodeKey(INT32 graphKey, INT32 nodeID)
{
	return (graphKey << 14) | (nodeID & 0x00003FFF);
}

inline INT32 RuPathEngine_GraphKeyFromNodeKey(INT32 nodeKey)
{
	return (nodeKey >> 14) & 0x0003FFFF;
}

inline INT32 RuPathEngine_NodeIDFromNodeKey(INT32 nodeKey)
{
	return nodeKey & 0x00003FFF;
}

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

class CRuPathNode
{
protected:
	CRuVector3								m_position;
	CRuArrayList<INT32>						m_neighbors;
	CRuArrayList<REAL>						m_neighborCosts;

public:
											CRuPathNode();
											CRuPathNode(const CRuVector3 &position);

	INT32									InsertNeighbor(INT32 neighborID, REAL neighborCost);
	BOOL									ClearAllNeighbors();

	void									SerializeTo(IRuStream *stream);
	void									SerializeFrom(IRuStream *stream);

	const CRuVector3&						Position() const { return m_position; }
	const CRuArrayList<INT32>&				Neighbors() const;
	const CRuArrayList<REAL>&				NeighborCosts() const;
};

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

class CRuPathNodePartition
{
private:
	struct PathNodeDesc
	{
		INT32								m_nodeID;					//!< Node index
		CRuPathNode*						m_pathNode;					//!< Path node data

											PathNodeDesc(INT32 nodeID = 0, CRuPathNode *pathNode = NULL)
											:	m_nodeID(nodeID),
												m_pathNode(pathNode)
											{
											}
	};

	static INT32							s_partitionDensity;

	CRuAABB									m_partitionBounds;
	CRuArrayList<PathNodeDesc>				m_pathNodes;
	CRuPathNodePartition*					m_children[4];

public:
											CRuPathNodePartition(const CRuAABB &bounds);
											~CRuPathNodePartition();

	BOOL									IsLeaf() const { return m_children[0] == NULL; }
	
	const CRuAABB&							Bounds() const { return m_partitionBounds; }
	CRuAABB&								Bounds() { return m_partitionBounds; }

	// Tree-building
	BOOL									InsertPathNode(INT32 nodeID, CRuPathNode *pathNode);
	BOOL									DeletePathNode(INT32 nodeID);

	// Spatial queries
	void									Enumerate(const CRuSphere &bounds, CRuArrayList<INT32> &pathNodesOut);

protected:
	BOOL									DeletePathNodeImpl(INT32 nodeID);
	void									ShiftNodeIDFrom(INT32 nodeID);
	void									Subdivide(INT32 targetDensity);
};

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

#pragma managed

#endif
