/*
	Lan Wars.
	Copyright (c) 2009, Darragh Coy.
	All rights reserved.
	Original work(s), source code & author(s) details available at: http://www.darraghcoy.com

	Redistribution and use in source and binary forms, with or without modification, are permitted 
	provided that the following conditions are met:

		* 	Redistributions of source code must retain the above copyright notice, this list of 
			conditions and the following disclaimer.
		* 	Redistributions in binary form must reproduce the above copyright notice, this list of 
			conditions and the following disclaimer in the documentation.
		* 	Neither the name of the author nor the names of contributors may be used to endorse or 
			promote products derived from this software without specific prior written permission.
		* 	The use of any third party libraries, modules or data files provided with the source 
			form of the program must follow and respect the individual licensing terms of these 
			components. You do not have permission to modify or circumvent the licensing terms for 
			provided third party components unless the third party licenses specifically allow this. 
			If you do not agree to the terms of provided third party components then you do not have 
			permission to use them in your derived work(s).
		* 	The terms of this license do not apply to separate (but related) distributions if supplied 
			by the author(s), only to the contents of this source distribution, derived works, and the 
			binaries produced by either modified or unmodified versions of the source code. The terms 
			of this license do not also apply to any third party libraries or components provided with 
			the source distribution. Such third party elements are licensed under their own separate 
			agreements.

	THIS SOFTWARE IS PROVIDED BY DARRAGH COY ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, 
	BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
	ARE DISCLAIMED. IN NO EVENT SHALL DARRAGH COY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
	OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
	OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
	IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef GAME_PATH_NETWORK_H
#define GAME_PATH_NETWORK_H

//=====================================================================================================================
//=====================================================================================================================

namespace Game
{	
	//=================================================================================================================
	//=================================================================================================================
	
	class DoomLevel;
	class BuildPathNetwork;
	class Camera3D;

	//=================================================================================================================
	/// @brief		This class builds a list of inter-connected nodes for the level that can be used for A* path
	///				finding. It also maintains which areas of the map are connected to which nodes which can be used 
	///				to tell the AI what part of the network it is on.
	//=================================================================================================================

	class PathNetwork
	{
		public:
		
			//=========================================================================================================
			// Structures
			//=========================================================================================================
			
				/// This structure represents a path node
				
				struct Node
				{
					/// This is the position of the node's xz coordinates
					
					Vec2f m_position;
					
					/// This is the number of nodes that the node is connected to
					
					unsigned m_num_connected_nodes;
					
					/// This is an array of other nodes that this node is connected to
					
					Node ** m_connected_nodes;
					
					/// This is the square distance to each of the connected nodes
					
					float * m_connected_distances;

					//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
					/// This is an extra cost to add to the G cost to each of the nodes. Used by the AI to add an extra
					/// penalty for lots of monsters following the same route. Makes monsters take different routes and
					/// consequently produces the illusion of squad based behaviour when closing in on all possible
					/// exits to a target.
					//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

					float * m_connected_costs_extra;

					/// If true then the node is either in the open or closed list when using the A* algorithm
					
					bool m_examined;
					
					//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
					/// If m_examined is true: this is true if the node is in the open list: if it is false then the node 
					/// is in the closed list. If m_examined is false then this is unused.
					//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
					
					bool m_in_open_list;
					
					/// Current F cost: which is G + H cost. Only valid if in the open list. Used by the A* algorithm.
					
					float m_f_cost;
					
					/// Current G cost: cost to get from search start to this node, following path to get there. Used by the A* algorithm.
					
					float m_g_cost;
					
					/// Current H cost: estimated cost to goal point from this node. Used by the A* algorithm.
					
					float m_h_cost;
					
					/// This is the previous node before this node in the currently computed path: Used by the A* algorithm to trace back the path.
					
					Node * m_previous_path_node;
				};
			
			//=========================================================================================================
			// Functions
			//=========================================================================================================
		
				//=====================================================================================================	
				/// @brief		Creates the path network
				/// @param		level - level the path network is for
				//=====================================================================================================
				
				PathNetwork( const DoomLevel & level );
				
				//=====================================================================================================	
				/// @brief		Destroys the path network
				//=====================================================================================================
				
				~PathNetwork();

				//=====================================================================================================
				/// @brief		Adds an extra cost to going through the selected position to get to somewhere.
				///				This is used by the AI to implement surrounding team based behaviour.
				///	@param		position - position to add the extra cost for moving through
				/// @param		cost - extra cost to associate with this position.
				//=====================================================================================================

				void AddPathCost( const Vec3f & position , float cost );

				//=====================================================================================================
				/// @brief		Removes an extra cost to going through the selected position to get to somewhere.
				///				This is used by the AI to implement surrounding team based behaviour.
				///	@param		position - position to add the extra cost for moving through
				/// @param		cost - extra cost to remove from this position.
				//=====================================================================================================

				void RemovePathCost( const Vec3f & position , float cost ){ AddPathCost(position,-cost); }
				
				//=====================================================================================================
				/// @brief		Attempts to generate a path between the two given points in the level
				//=====================================================================================================
				
				void GeneratePath( const Vec2f & from , const Vec2f & to );
				
				//=====================================================================================================
				/// @brief		Gets the number of nodes along the path generated by the last call to GeneratePath()
				/// @returns	The number of generated path nodes
				//=====================================================================================================
				
				inline unsigned GetGeneratedPathSize() const { return m_num_generated_path_nodes; }

				//=====================================================================================================
				/// @brief		Returns the n'th node in the path generated by GeneratePath(), with the 1st node along
				///				the path as index 0.
				/// @param		n - index of which node along the path to return
				/// @returns	The n'th node along the path
				/// @pre		The given index must be within the number of nodes within the generated path.
				//=====================================================================================================
				
				inline const Node & GetGeneratedPathNode( unsigned n ) const 
				{ 
					// Make sure this is ok
				
					ENSURE( n < m_num_generated_path_nodes , "The given index must be within the number of nodes within the generated path." )
					
					// Return it:
					
					return * ( m_generated_path[ ( m_num_generated_path_nodes - 1 ) - n ] );
				}
				
				#ifdef USE_DEBUG_CONSOLE
				
					/// Debug only: draws all the path nodes
					
					void DrawPathNodes( Camera3D * c );
					
					/// Debug only: draws a path generated between the two given points in the level
					
					void DrawPath( Camera3D * c , const Vec2f & p1 , const Vec2f & p2 );
				
				#endif
				
		private:
		
			//=========================================================================================================
			// Structs
			//=========================================================================================================
			
				/// This class is used internally by the pathfinding algorithm: it sorts the nodes based on F score.
				
				struct AStarRatedNode
				{
					/// This is a pointer to the actual node itself.
					
					Node * m_node;
					
					//=================================================================================================
					/// @brief		Default constructor. Creates a null node.
					//=================================================================================================
					
					inline AStarRatedNode(){ m_node = 0; }
					
					//=================================================================================================
					/// @brief		Constructor. Creates the rated node
					/// @param		node - node this rated node relates to
					/// @pre		The given node must not be null
					//=================================================================================================
					
					inline AStarRatedNode( Node * node )
					{ 
						// Make sure ok
						
						ENSURE( node != 0 , "The given node must not be null" )
						
						// Save:
					
						m_node = node; 
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. Note that F scored nodes are regarded as being
					///				'greater' so they are first in the priority queue
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator == ( const AStarRatedNode & other ) const 
					{ 
						return m_node->m_f_cost == other.m_node->m_f_cost;
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. Note that F scored nodes are regarded as being
					///				'greater' so they are first in the priority queue
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator != ( const AStarRatedNode & other ) const 
					{ 
						return m_node->m_f_cost != other.m_node->m_f_cost;
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. Note that F scored nodes are regarded as being
					///				'greater' so they are first in the priority queue
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator > ( const AStarRatedNode & other ) const 
					{ 
						return m_node->m_f_cost > other.m_node->m_f_cost;
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. Note that F scored nodes are regarded as being
					///				'greater' so they are first in the priority queue
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator >= ( const AStarRatedNode & other ) const 
					{ 
						return m_node->m_f_cost >= other.m_node->m_f_cost;
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. 
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator < ( const AStarRatedNode & other ) const 
					{ 
						return m_node->m_f_cost < other.m_node->m_f_cost;
					}
					
					//=================================================================================================
					/// @brief		Compares two nodes for equality. 
					/// @param		other - other node to compare with
					/// @returns	Result of the comparison
					//=================================================================================================
					
					inline bool operator <= ( const AStarRatedNode & other ) const 
					{
						return m_node->m_f_cost <= other.m_node->m_f_cost;
					}
				};
		
			//=========================================================================================================
			// Functions
			//=========================================================================================================
				
				/// Populates and creates our internal node list given the network builder object
				
				void CreatePathNetwork( BuildPathNetwork * net );
				
				/// Performs the A* algorithm, searching for the best path between the two given nodes
				
				void Pathfind( Node * start , Node * end );

			//=========================================================================================================
			// Variables
			//=========================================================================================================
			
				/// This holds the number of path nodes
				
				unsigned m_num_nodes;
				
				/// This holds the number of subsectors			
				
				unsigned m_num_subsectors;
			
				/// This array stores which node is closest to which subsector.
				
				Node ** m_subsector_nodes;
				
				/// This is the array of nodes
				
				Node * m_nodes;
				
				/// This array holds the node numbers for nodes that have been examined by the A* algorithm. Used to clear data after search.
				
				Node ** m_examined_nodes;
				
				/// This is the number of nodes that have been examined by the A* algorithm
				
				unsigned m_num_examined_nodes;
				
				/// This array holds all the nodes in the last generated path by A*, starting with the target node and working back to the starting node.
				
				Node ** m_generated_path;
				
				/// This is the number of nodes in the last generated path:
				
				unsigned m_num_generated_path_nodes;
				
				/// This is the open list used by the A* algorithm, sorted by F score. The node with the lowest F score is first in the queue.
				
				Heap<AStarRatedNode> * m_open_list;
				
				/// This is the level used by the path network
				
				const DoomLevel * m_level;
				
				#ifdef USE_DEBUG_CONSOLE
				
					/// Debug only: a list of subsectors that are closest to each node
					
					std::vector< std::list<unsigned> > m_node_subsectors;
					
				#endif
	};
};

#endif
