/*
	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.
*/

//=====================================================================================================================
/// @brief		This temporary unoptimised path network is used to build up the path network at the start of the
///				level. Once the network is built then all this data in here is discarded. This class does a lot of
///				the hard work of actually building the network up.
//=====================================================================================================================

#include "Precompiled.h"
#include "AI/BuildPathNetwork.h"
#include "AI/BuildPathNode.h"
#include "AI/BuildPathSubsector.h"
#include "Doom/DoomLevel.h"
#include "Doom/DoomThing.h"
#include "Doom/DoomGLSubsectorV2.h"

using namespace Game;

//=====================================================================================================================
/// @brief		Creates the temporary path network. Begins building the network immediately.
/// @param		level - level the path network is for
//=====================================================================================================================

BuildPathNetwork::BuildPathNetwork( const DoomLevel & level ) : m_level(&level)
{
	// Build a list of path nodes and subsectors firstly:
	
	BuildNodeList();
	BuildSubsectorList();
	
	// Assign nodes to the subsectors they are in
	
	AssignNodesToSubsectors();
	
	// Need to flood fill all subsectors without nodes and assign them nodes:
	
	std::list<BuildPathSubsector*> subsectors; 
	
	for ( unsigned i = 0 ; i < m_subsectors.size() ; ++i )
	{
		subsectors.push_back(m_subsectors[i]);
	}
	
	// Continue flood filling until there are no changes:
	
	while ( FloodFillSubsectors(subsectors) ){;}
	
	// If path information is missing and some subsectors do not have nodes, then generate them:
	
	GenerateMissingNodes();
	
	// Connect up all nodes
	
	BuildNodeConnectivity();
	
	// Set node numbers
	
	AssignNodeNumbers();
}

//=====================================================================================================================
/// @brief		Destroys the temporary path network
//=====================================================================================================================

BuildPathNetwork::~BuildPathNetwork()
{
	// Destroy all nodes:
	
	for ( unsigned i = 0 ; i < m_nodes.size() ; ++i ) delete m_nodes[i];
	
	// Destroy all subsectors:
	
	for ( unsigned i = 0 ; i < m_subsectors.size() ; ++i ) delete m_subsectors[i];
}

//=====================================================================================================================
/// @brief		Creates a list of nodes by looking at the doom level. We use the armor helmet pickup to denote a path 
///				node.
//=====================================================================================================================

void BuildPathNetwork::BuildNodeList()
{
	// Find the number of helmets pickups in the level:
	
	unsigned num_things = m_level->GetThingCount();
	
	// Store all of the helmet pickups here:
	
	std::list<DoomThing> armor_pickups;
	
	// Run through all things in the level:
	
	for ( unsigned i = 0 ; i < num_things ; ++i )
	{
		// Get this thing:
		
		const DoomThing & thing = m_level->GetThing(i);
		
		// See if it is an armor bonus or helmet:
		
		if ( thing.m_type == (unsigned short)(DoomThing::TT_ARMOR_BONUS) )
		{
			// Armor helmet: this is a path node. Add to the armor pickup list
			
			armor_pickups.push_back(thing);
		}
	}
	
	// Now allocate enough space in our nodes array for all the nodes:
	
	m_nodes.resize(armor_pickups.size());
	
	// Create all of the path nodes:
	
	unsigned node_num = 0;
	
	{	
		std::list<DoomThing>::iterator i = armor_pickups.begin();
		std::list<DoomThing>::iterator e = armor_pickups.end();
		
		while ( i != e )
		{
			// Get this thing
			
			DoomThing & thing = * i; i++;
			
			// Save to nodes list:
		
			m_nodes[node_num] = new BuildPathNode( Vec2f(thing.m_x,thing.m_z) , * m_level );
			
			// Next node
			
			node_num++;
		}
	}
}

//=====================================================================================================================
/// @brief		Builds a list of subsectors by looking at the doom level.
//=====================================================================================================================

void BuildPathNetwork::BuildSubsectorList()
{
	// Get the number of subsectors
	
	unsigned num_subsectors = m_level->GetSubsectorCount();

	// We know how many subsectors there are
	
	m_subsectors.resize(num_subsectors);
	
	// Build the list:
	
	for ( unsigned i = 0 ; i < num_subsectors ; ++i )
	{
		// Make this subsector
		
		m_subsectors[i] = new BuildPathSubsector(*m_level,m_level->GetSubsector(i));
	}
}

//=====================================================================================================================
/// @brief		Assigns nodes to subsectors. Prunes the node list also for uneeded nodes.
//=====================================================================================================================

void BuildPathNetwork::AssignNodesToSubsectors()
{
	//-----------------------------------------------------------------------------------------------------------------
	// Run through the list of nodes: assign them to subsectors
	//-----------------------------------------------------------------------------------------------------------------
	
	for ( unsigned i = 0 ; i < m_nodes.size() ; ++i ) 
	{
		// Get this node:
		
		BuildPathNode & node = * ( m_nodes[i] );
		
		// Get which subsector this node is in:
		
		const DoomGLSubsectorV2 * subsector = m_level->GetSubsector(node.GetPosition());
		
		// If the node is not in a subsector then ignore this node
		
		if ( subsector == 0 ) continue;
		
		// Get the subsector number:
		
		unsigned subsector_num = m_level->GetSubsectorNumber(*subsector);
		
		// Make sure ok:
		
		ENSURE( subsector_num < m_level->GetSubsectorCount() , "Invalid subsector number" )
		
		// Now: see if the subsector has already been assigned a path node:
		
		if ( m_subsectors[subsector_num]->HasClosestNode() )
		{
			// Get the distance of the other node to the subsector center:
			
			float other_dist = m_subsectors[subsector_num]->GetCenter().DistanceTo
			(
				m_subsectors[subsector_num]->GetClosestNode()->GetPosition()
			);
			
			// Get our distance to the subsector center:
			
			float our_dist = m_subsectors[subsector_num]->GetCenter().DistanceTo
			(
				node.GetPosition()
			);
			
			// If we are closer to the center of this subsector then we become the new path-node for the subsector
			
			if ( our_dist < other_dist )
			{
				// Unlink the other node from the subsector:
				
				m_subsectors[subsector_num]->GetClosestNode()->SetSubsector(0);
				
				// Assign this node as the closest node to the subsector
				
				m_subsectors[subsector_num]->SetClosestNode(&node);
				
				// Link the node to the subsector:
				
				node.SetSubsector( m_subsectors[subsector_num] );
			}
		}
		else
		{
			// Subsector does not already have a closest node: assign it this one
			
			m_subsectors[subsector_num]->SetClosestNode(&node);
			
			// Link the node to the subsector:
			
			node.SetSubsector( m_subsectors[subsector_num] );
		}
	}
	
	//-----------------------------------------------------------------------------------------------------------------
	// Now build a list of nodes that have subsectors assigned to them:
	//-----------------------------------------------------------------------------------------------------------------
	
	std::list<BuildPathNode*> pruned_nodes;
	
		// Run through all the nodes again:
		
		for ( unsigned i = 0 ; i < m_nodes.size() ; ++i )
		{
			// See if this node has a subsector
			
			if ( m_nodes[i]->GetSubsector() != 0 )
			{
				// Add to the list of pruned nodes:
				
				pruned_nodes.push_back(m_nodes[i]);
			}
			else
			{
				// Delete this node:
				
				delete m_nodes[i];
			}
		}
	
	//-----------------------------------------------------------------------------------------------------------------
	// Now re-make the nodes list so that only the pruned nodes are in it:
	//-----------------------------------------------------------------------------------------------------------------
	
	m_nodes.resize(pruned_nodes.size());
	
	// Popuplate the new nodes list
	
	{
		// Current node number we are on
		
		unsigned node_num = 0;
		
		// Run through the pruned nodes list:
		
		std::list<BuildPathNode*>::iterator i = pruned_nodes.begin();
		std::list<BuildPathNode*>::iterator e = pruned_nodes.end();
		
		while ( i != e )
		{
			// Add to the nodes array
			
			m_nodes[node_num] = *i; i++; node_num++;
		}
	}
}

//=====================================================================================================================
/// @brief		Flood fills subsectors without nodes to assign them with the closest node possible. 
///				This needs to be called until it returns false.
/// @param		subsectors - list of subsectors to assign nodes to. this list is pruned on each
///				iteration of the flood fill algorithm.
/// @returns	True if we should call this again, false otherwise.
//=====================================================================================================================

bool BuildPathNetwork::FloodFillSubsectors( std::list<BuildPathSubsector*> & subsectors )
{
	// If this is true then there has been a change in subsector node assignmnet
	
	bool found_change = false;

	// Run through the list of subsectors:
	
	std::list<BuildPathSubsector*>::iterator i = subsectors.begin();
	std::list<BuildPathSubsector*>::iterator e = subsectors.end();
	
	while ( i != e )
	{
		// Get this subsector:
		
		BuildPathSubsector & subsector = **i;
		
		// See if it is assigned a node already:
		
		if ( subsector.HasClosestNode() )
		{
			// The subsector has a closest node: remove it from the list
			
			i = subsectors.erase(i);
		}
		else
		{
			//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
			// No closest node for this subsector: run through all the subsectors we can reach from here
			// and see if they have nodes. Assign the closest node to this subsectors center to this
			// subsector. 
			//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
			
			const std::vector<const DoomGLSubsectorV2*> & adajcent_subsectors = subsector.GetConnectedSubsectors();
			
			// Run through all the connected subsectors:
			
			for ( unsigned n = 0 ; n < adajcent_subsectors.size() ; ++n )
			{
				// Get the temporary node network version of the subsector:
				
				BuildPathSubsector & adjacent_subsector = * ( m_subsectors[ m_level->GetSubsectorNumber( * ( adajcent_subsectors[n] ) ) ] );
				
				// See if it has any node if it's own: only flood fill also if the other subsector is able to reach this one
				
				if ( adjacent_subsector.HasClosestNode() && adjacent_subsector.CanTraverseTo( subsector.GetDoomSubsector() ) )
				{
					// Ok: see if we have a node already:
					
					if ( subsector.HasClosestNode() )
					{
						// Get the distance of our current node to our center
						
						float cur_dist = subsector.GetClosestNode()->GetPosition().DistanceTo(subsector.GetCenter());
						
						// Get the distance of the other subsector's node to our center
						
						float new_dist = adjacent_subsector.GetClosestNode()->GetPosition().DistanceTo(subsector.GetCenter());
						
						// See if the adjacent subsectors node is closer to our center than our current node:
						
						if ( new_dist < cur_dist )
						{
							// Use the node of the adjacent subsector:
							
							subsector.SetClosestNode(adjacent_subsector.GetClosestNode());
							
							// There was a change
							
							found_change = true;
						}
					}
					else
					{
						// We don't have a closest node: assign the connected subsectors node to us
						
						subsector.SetClosestNode(adjacent_subsector.GetClosestNode());
						
						// There was a change:
						
						found_change = true;												
					}
				}
			}
			
			// If we do not have a node assigned to us then just move on in the list, otherwise remove this subsector from further consideration
			
			if ( subsector.HasClosestNode() )
			{
				i = subsectors.erase(i);
			}
			else
			{
				i++;
			}
		}
	}
	
	// Return if we should continue the flood fill
	
	return found_change;
}

//=====================================================================================================================
/// @brief		Builds nodes for subsectors that do not have nodes after flood filling
/// @remarks	This will generate a node for every single subsector that does not have a node.
///				It is a last ditch attempt to make a level useable for AI in the absense of 
///				proper path nodes in the level file itself, and the nodes generated will not be
///				as efficient as humanly generated nodes.
//=====================================================================================================================

void BuildPathNetwork::GenerateMissingNodes()
{
	// Run through all the subsectors:
	
	for ( unsigned i = 0 ; i < m_subsectors.size() ; ++i )
	{
		// Get this subsector
		
		BuildPathSubsector & subsector = * ( m_subsectors[i] );
		
		// Make sure it has a node:
		
		if ( subsector.HasClosestNode() == false )
		{
			// Need to make a path node for this subsector:
			
			BuildPathNode * new_node = new BuildPathNode(subsector.GetCenter(),*m_level);
			
			// Assign this node to the subsector and visa versa
			
			new_node->SetSubsector(&subsector); subsector.SetClosestNode(new_node);
			
			// Into the list of nodes:
			
			m_nodes.push_back(new_node);
		}
	}
}

//=====================================================================================================================
/// @brief		Connects all nodes that can connect together
/// @pre		All subsectors must have path nodes assigned to them at this stage
//===================================================================================================================== 

void BuildPathNetwork::BuildNodeConnectivity()
{
	// Run through all the subsectors:
	
	for ( unsigned i = 0 ; i < m_subsectors.size() ; ++i )
	{
		// Get this subsector:
		
		BuildPathSubsector & subsector = * ( m_subsectors[i] );
		
		// Make sure ok
		
		ENSURE( subsector.HasClosestNode() , "All subsectors must have path nodes assigned to them at this stage" )
		
		// Get it's adjacent subsectors:
		
		const std::vector<const DoomGLSubsectorV2*> & adjacent_subsectors = subsector.GetConnectedSubsectors();
		
		// Run through all it's adjacent subsectors:
		
		for ( unsigned j = 0 ; j < adjacent_subsectors.size() ; ++j )
		{
			// Get this adjacent subsector:
			
			BuildPathSubsector & adjacent_subsector = * ( m_subsectors[ m_level->GetSubsectorNumber( * ( adjacent_subsectors[j] ) ) ] );
			
			// Make sure ok
			
			ENSURE( adjacent_subsector.HasClosestNode() , "All subsectors must have path nodes assigned to them at this stage" )			
			
			// Connect our node to it's node:
			
			subsector.GetClosestNode()->Connect( * adjacent_subsector.GetClosestNode() );
		}		
	}	
}

//=====================================================================================================================
/// @brief		Assigns node numbers to all nodes
//=====================================================================================================================

void BuildPathNetwork::AssignNodeNumbers()
{
	// Run through all the nodes
	
	for ( unsigned i = 0 ; i < m_nodes.size() ; ++i ) m_nodes[i]->SetNodeNumber(i);
}
