/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.
Copyright (C) 2006 Robert Beckebans <trebor_7@users.sourceforge.net>

This file is part of XreaL source code.

XreaL source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

XreaL source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with XreaL source code; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

/*****************************************************************************
 * name:		be_aas_routealt.c
 *
 * desc:		AAS
 *
 * $Archive: /MissionPack/code/botlib/be_aas_routealt.c $
 *
 *****************************************************************************/

#include "../common/shared.h"
#include "l_utils.h"
#include "l_memory.h"
#include "l_log.h"
#include "l_script.h"
#include "l_precomp.h"
#include "l_struct.h"
#include "aasfile.h"
#include "../../mod/game/botlib.h"
#include "../../mod/game/be_aas.h"
#include "be_aas_funcs.h"
#include "be_interface.h"
#include "be_aas_def.h"

#define ENABLE_ALTROUTING
//#define ALTROUTE_DEBUG

typedef struct midrangearea_s
{
	int             valid;
	unsigned short  starttime;
	unsigned short  goaltime;
} midrangearea_t;

midrangearea_t *midrangeareas;
int            *clusterareas;
int             numclusterareas;

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_AltRoutingFloodCluster_r(int areanum)
{
	int             i, otherareanum;
	aas_area_t     *area;
	aas_face_t     *face;

	//add the current area to the areas of the current cluster
	clusterareas[numclusterareas] = areanum;
	numclusterareas++;
	//remove the area from the mid range areas
	midrangeareas[areanum].valid = qfalse;
	//flood to other areas through the faces of this area
	area = &aasworld.areas[areanum];
	for(i = 0; i < area->numfaces; i++)
	{
		face = &aasworld.faces[abs(aasworld.faceindex[area->firstface + i])];
		//get the area at the other side of the face
		if(face->frontarea == areanum)
			otherareanum = face->backarea;
		else
			otherareanum = face->frontarea;
		//if there is an area at the other side of this face
		if(!otherareanum)
			continue;
		//if the other area is not a midrange area
		if(!midrangeareas[otherareanum].valid)
			continue;
		//
		AAS_AltRoutingFloodCluster_r(otherareanum);
	}							//end for
}								//end of the function AAS_AltRoutingFloodCluster_r

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AlternativeRouteGoals(vec3_t start, int startareanum, vec3_t goal, int goalareanum, int travelflags,
							  aas_altroutegoal_t * altroutegoals, int maxaltroutegoals, int type)
{
#ifndef ENABLE_ALTROUTING
	return 0;
#else
	int             i, j, bestareanum;
	int             numaltroutegoals, nummidrangeareas;
	int             starttime, goaltime, goaltraveltime;
	float           dist, bestdist;
	vec3_t          mid, dir;

#ifdef ALTROUTE_DEBUG
	int             startmillisecs;

	startmillisecs = Sys_MilliSeconds();
#endif

	if(!startareanum || !goalareanum)
		return 0;
	//travel time towards the goal area
	goaltraveltime = AAS_AreaTravelTimeToGoalArea(startareanum, start, goalareanum, travelflags);
	//clear the midrange areas
	Com_Memset(midrangeareas, 0, aasworld.numareas * sizeof(midrangearea_t));
	numaltroutegoals = 0;
	//
	nummidrangeareas = 0;
	//
	for(i = 1; i < aasworld.numareas; i++)
	{
		//
		if(!(type & ALTROUTEGOAL_ALL))
		{
			if(!(type & ALTROUTEGOAL_CLUSTERPORTALS && (aasworld.areasettings[i].contents & AREACONTENTS_CLUSTERPORTAL)))
			{
				if(!(type & ALTROUTEGOAL_VIEWPORTALS && (aasworld.areasettings[i].contents & AREACONTENTS_VIEWPORTAL)))
				{
					continue;
				}				//end if
			}					//end if
		}						//end if
		//if the area has no reachabilities
		if(!AAS_AreaReachability(i))
			continue;
		//tavel time from the area to the start area
		starttime = AAS_AreaTravelTimeToGoalArea(startareanum, start, i, travelflags);
		if(!starttime)
			continue;
		//if the travel time from the start to the area is greater than the shortest goal travel time
		if(starttime > (float)1.1 * goaltraveltime)
			continue;
		//travel time from the area to the goal area
		goaltime = AAS_AreaTravelTimeToGoalArea(i, NULL, goalareanum, travelflags);
		if(!goaltime)
			continue;
		//if the travel time from the area to the goal is greater than the shortest goal travel time
		if(goaltime > (float)0.8 * goaltraveltime)
			continue;
		//this is a mid range area
		midrangeareas[i].valid = qtrue;
		midrangeareas[i].starttime = starttime;
		midrangeareas[i].goaltime = goaltime;
		Log_Write("%d midrange area %d", nummidrangeareas, i);
		nummidrangeareas++;
	}							//end for
	//
	for(i = 1; i < aasworld.numareas; i++)
	{
		if(!midrangeareas[i].valid)
			continue;
		//get the areas in one cluster
		numclusterareas = 0;
		AAS_AltRoutingFloodCluster_r(i);
		//now we've got a cluster with areas through which an alternative route could go
		//get the 'center' of the cluster
		VectorClear(mid);
		for(j = 0; j < numclusterareas; j++)
		{
			VectorAdd(mid, aasworld.areas[clusterareas[j]].center, mid);
		}						//end for
		VectorScale(mid, 1.0 / numclusterareas, mid);
		//get the area closest to the center of the cluster
		bestdist = 999999;
		bestareanum = 0;
		for(j = 0; j < numclusterareas; j++)
		{
			VectorSubtract(mid, aasworld.areas[clusterareas[j]].center, dir);
			dist = VectorLength(dir);
			if(dist < bestdist)
			{
				bestdist = dist;
				bestareanum = clusterareas[j];
			}					//end if
		}						//end for
		//now we've got an area for an alternative route
		//FIXME: add alternative goal origin
		VectorCopy(aasworld.areas[bestareanum].center, altroutegoals[numaltroutegoals].origin);
		altroutegoals[numaltroutegoals].areanum = bestareanum;
		altroutegoals[numaltroutegoals].starttraveltime = midrangeareas[bestareanum].starttime;
		altroutegoals[numaltroutegoals].goaltraveltime = midrangeareas[bestareanum].goaltime;
		altroutegoals[numaltroutegoals].extratraveltime =
			(midrangeareas[bestareanum].starttime + midrangeareas[bestareanum].goaltime) - goaltraveltime;
		numaltroutegoals++;
		//
#ifdef ALTROUTE_DEBUG
		AAS_ShowAreaPolygons(bestareanum, 1, qtrue);
#endif
		//don't return more than the maximum alternative route goals
		if(numaltroutegoals >= maxaltroutegoals)
			break;
	}							//end for
#ifdef ALTROUTE_DEBUG
	botimport.Print(PRT_MESSAGE, "alternative route goals in %d msec\n", Sys_MilliSeconds() - startmillisecs);
#endif
	return numaltroutegoals;
#endif
}								//end of the function AAS_AlternativeRouteGoals

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitAlternativeRouting(void)
{
#ifdef ENABLE_ALTROUTING
	if(midrangeareas)
		FreeMemory(midrangeareas);
	midrangeareas = (midrangearea_t *) GetMemory(aasworld.numareas * sizeof(midrangearea_t));
	if(clusterareas)
		FreeMemory(clusterareas);
	clusterareas = (int *)GetMemory(aasworld.numareas * sizeof(int));
#endif
}								//end of the function AAS_InitAlternativeRouting

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_ShutdownAlternativeRouting(void)
{
#ifdef ENABLE_ALTROUTING
	if(midrangeareas)
		FreeMemory(midrangeareas);
	midrangeareas = NULL;
	if(clusterareas)
		FreeMemory(clusterareas);
	clusterareas = NULL;
	numclusterareas = 0;
#endif
}								//end of the function AAS_ShutdownAlternativeRouting
