/*****************************************************************************
The Dark Mod GPL Source Code

This file is part of the The Dark Mod Source Code, originally based
on the Doom 3 GPL Source Code as published in 2011.

The Dark Mod 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 3 of the License,
or (at your option) any later version. For details, see LICENSE.TXT.

Project: The Dark Mod (http://www.thedarkmod.com/)

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

#include "precompiled.h"
#pragma hdrstop



#include "AAS_local.h"
#include "../Game_local.h"		// for print and error

#include "../DarkModGlobals.h"
#include "../MultiStateMover.h"
#include "../MultiStateMoverPosition.h"
#include "../TimerManager.h"

#define CACHETYPE_AREA				1
#define CACHETYPE_PORTAL			2

//stgatilov #4755: should be large enough for EAS initialization
//if cache is not large enough, then EAS setup becomes much slower
//P.S. Shadowhide WIP needs at least 6 MB
#define MAX_ROUTING_CACHE_MEMORY	(20*1024*1024)

#define LEDGE_TRAVELTIME_PENALTY	250

/*
============
idRoutingCache::idRoutingCache
============
*/
idRoutingCache::idRoutingCache( int size ) {
	areaNum = 0;
	cluster = 0;
	next = prev = NULL;
	time_next = time_prev = NULL;
	travelFlags = 0;
	startTravelTime = 0;
	type = 0;
	this->size = size;
	reachabilities = new byte[size];
	memset( reachabilities, 0, size * sizeof( reachabilities[0] ) );
	travelTimes = new unsigned short[size];
	memset( travelTimes, 0, size * sizeof( travelTimes[0] ) );
}

/*
============
idRoutingCache::~idRoutingCache
============
*/
idRoutingCache::~idRoutingCache( void ) {
	delete [] reachabilities;
	delete [] travelTimes;
}

/*
============
idRoutingCache::Size
============
*/
int idRoutingCache::Size( void ) const {
	return sizeof( idRoutingCache ) + size * sizeof( reachabilities[0] ) + size * sizeof( travelTimes[0] );
}

/*
============
idAASLocal::AreaTravelTime
============
*/
unsigned short idAASLocal::AreaTravelTime( int areaNum, const idVec3 &start, const idVec3 &end ) const {
	float dist;

	dist = ( end - start ).Length();

	if ( file->GetArea( areaNum ).travelFlags & TFL_CROUCH ) {
		dist *= 100.0f / 100.0f;
	} else if ( file->GetArea( areaNum ).travelFlags & TFL_WATER ) {
		dist *= 100.0f / 150.0f;
	} else {
		dist *= 100.0f / 300.0f;
	}
	if ( dist < 1.0f ) {
		return 1;
	}
	return (unsigned short) idMath::FtoiRound( dist );
}

/*
============
idAASLocal::CalculateAreaTravelTimes
============
*/
void idAASLocal::CalculateAreaTravelTimes(void) {
	int n, i, j, numReach, numRevReach, t, maxt;
	byte *bytePtr;
	idReachability *reach, *rev_reach;

	// get total memory for all area travel times
	numAreaTravelTimes = 0;
	for ( n = 0; n < file->GetNumAreas(); n++ ) {

		if ( !(file->GetArea( n ).flags & (AREA_REACHABLE_WALK|AREA_REACHABLE_FLY)) ) {
			continue;
		}

		numReach = 0;
		for ( reach = file->GetArea( n ).reach; reach; reach = reach->next ) {
			numReach++;
		}

		numRevReach = 0;
		for ( rev_reach = file->GetArea( n ).rev_reach; rev_reach; rev_reach = rev_reach->rev_next ) {
			numRevReach++;
		}
		numAreaTravelTimes += numReach * numRevReach;
	}

	areaTravelTimes = (unsigned short *) Mem_Alloc( numAreaTravelTimes * sizeof( unsigned short ) );
	bytePtr = (byte *) areaTravelTimes;

	for ( n = 0; n < file->GetNumAreas(); n++ ) {

		if ( !(file->GetArea( n ).flags & (AREA_REACHABLE_WALK|AREA_REACHABLE_FLY)) ) {
			continue;
		}

		// for each reachability that starts in this area calculate the travel time
		// towards all the reachabilities that lead towards this area
		for ( maxt = i = 0, reach = file->GetArea( n ).reach; reach; reach = reach->next, i++ ) {
			assert( i < MAX_REACH_PER_AREA );
			if ( i >= MAX_REACH_PER_AREA ) {
				gameLocal.Error( "i >= MAX_REACH_PER_AREA" );
			}
			reach->number = i;
			reach->disableCount = 0;
			reach->areaTravelTimes = (unsigned short *) bytePtr;
			for ( j = 0, rev_reach = file->GetArea( n ).rev_reach; rev_reach; rev_reach = rev_reach->rev_next, j++ ) {
				t = AreaTravelTime( n, reach->start, rev_reach->end );
				reach->areaTravelTimes[j] = t;
				if ( t > maxt ) {
					maxt = t;
				}
			}
			bytePtr += j * sizeof( unsigned short );
		}

		// if this area is a portal
		if ( file->GetArea( n ).cluster < 0 ) {
			// set the maximum travel time through this portal
			file->SetPortalMaxTravelTime( -file->GetArea( n ).cluster, maxt );
		}
	}

    assert(((ptrdiff_t)bytePtr - (ptrdiff_t)areaTravelTimes) <= static_cast<ptrdiff_t>(numAreaTravelTimes * sizeof(unsigned short)));
}

/*
============
idAASLocal::DeleteAreaTravelTimes
============
*/
void idAASLocal::DeleteAreaTravelTimes( void ) {
	Mem_Free( areaTravelTimes );
	areaTravelTimes = NULL;
	numAreaTravelTimes = 0;
}

/*
============
idAASLocal::SetupRoutingCache
============
*/
void idAASLocal::SetupRoutingCache( void ) {

	// greebo: First, determine the number of areas in the map by adding all reachable areas of all clusters
	areaCacheIndexSize = 0;
	for ( int i = 0; i < file->GetNumClusters(); i++ ) {
		areaCacheIndexSize += file->GetCluster(i).numReachableAreas;
	}

	/**
	 * greebo: Next, we need to allocate the memory for the idRoutingCache* pointers (only the pointers, not the structs!)
	 * Take one pointer array per cluster and add one pointer for each area. The area pointers
	 * are grouped after their clusters.
	 *
	 * The area cache index is then looking like this (divided into two large sections). The first
	 * section serves as "index" for the pointers further down in memory.
	 *
	 * idRoutingCache** cluster0	(pointing to the "area0" pointer below)
	 * idRoutingCache** cluster1	(pointing to the "area3" pointer below)
	 * idRoutingCache** cluster2	(pointing to the "area5" pointer below)
	 * ...
	 *
	 * idRoutingCache* area0		(belonging to Cluster 0)
	 * idRoutingCache* area1		(belonging to Cluster 0)
	 * idRoutingCache* area2		(belonging to Cluster 0)
	 *
	 * idRoutingCache* area3		(belonging to Cluster 1)
	 * idRoutingCache* area4		(belonging to Cluster 1)
	 *
	 * idRoutingCache* area5		(belonging to Cluster 2)
	 * idRoutingCache* area6		(belonging to Cluster 2)
	 * ...
	 *
	 * This whole pointer structure is stored in a dynamically allocated area, hence the type idRoutingCache***
	 */
	areaCacheIndex = (idRoutingCache***) Mem_ClearedAlloc( file->GetNumClusters() * sizeof(idRoutingCache**) +
													areaCacheIndexSize * sizeof(idRoutingCache*) );

	// Now initialise the areaCacheIndex pointers

	// skip the index part, i.e. the first <numClusters> pointers
	byte* bytePtr = ((byte *)areaCacheIndex) + file->GetNumClusters() * sizeof(idRoutingCache**);

	// Initialise the first pointer section (the clusterN pointers), which point to the second (area) section
	for ( int i = 0; i < file->GetNumClusters(); i++ ) {
		// Set the i-th cluster pointer to the first area pointer (corresponding to this cluster)
		areaCacheIndex[i] = (idRoutingCache**) bytePtr;

		// Set the pointer to the next array
		bytePtr += file->GetCluster(i).numReachableAreas * sizeof(idRoutingCache*);
	}

	// At this point, all the area idRoutingCache* pointers are NULL and the index pointers are initialised

	// greebo: Allocate an idRoutingCache pointer for each area in the world and set the pointers to 0
	portalCacheIndexSize = file->GetNumAreas();
	portalCacheIndex = (idRoutingCache**) Mem_ClearedAlloc( portalCacheIndexSize * sizeof(idRoutingCache*) );

	// greebo: Allocate as many idRoutingUpdate structures as there are AREAS in the map, and set everything to 0
	areaUpdate = (idRoutingUpdate*) Mem_ClearedAlloc( file->GetNumAreas() * sizeof(idRoutingUpdate) );

	// greebo: Allocate as many idRoutingUpdate structures as there are PORTALS+1 in the map, and set everything to 0
	portalUpdate = (idRoutingUpdate*) Mem_ClearedAlloc( (file->GetNumPortals()+1) * sizeof(idRoutingUpdate) );

	// greebo: For each area in the map, allocate a traveltime integer and initialise them to 0
	goalAreaTravelTimes = (unsigned short *) Mem_ClearedAlloc( file->GetNumAreas() * sizeof(unsigned short) );

	cacheListStart = cacheListEnd = NULL;
	totalCacheMemory = 0;
}

/*
============
idAASLocal::DeleteClusterCache
============
*/
void idAASLocal::DeleteClusterCache( int clusterNum ) {
	int i;
	idRoutingCache *cache;

	for ( i = 0; i < file->GetCluster( clusterNum ).numReachableAreas; i++ ) {
		for ( cache = areaCacheIndex[clusterNum][i]; cache; cache = areaCacheIndex[clusterNum][i] ) {
			areaCacheIndex[clusterNum][i] = cache->next;
			UnlinkCache( cache );
			delete cache;
		}
	}
}

/*
============
idAASLocal::DeletePortalCache
============
*/
void idAASLocal::DeletePortalCache( void ) {
	int i;
	idRoutingCache *cache;

	for ( i = 0; i < file->GetNumAreas(); i++ ) {
		for ( cache = portalCacheIndex[i]; cache; cache = portalCacheIndex[i] ) {
			portalCacheIndex[i] = cache->next;
			UnlinkCache( cache );
			delete cache;
		}
	}
}

/*
============
idAASLocal::ShutdownRoutingCache
============
*/
void idAASLocal::ShutdownRoutingCache( void ) {
	int i;

	for ( i = 0; i < file->GetNumClusters(); i++ ) {
		DeleteClusterCache( i );
	}

	DeletePortalCache();

	Mem_Free( areaCacheIndex );
	areaCacheIndex = NULL;
	areaCacheIndexSize = 0;
	Mem_Free( portalCacheIndex );
	portalCacheIndex = NULL;
	portalCacheIndexSize = 0;
	Mem_Free( areaUpdate );
	areaUpdate = NULL;
	Mem_Free( portalUpdate );
	portalUpdate = NULL;
	Mem_Free( goalAreaTravelTimes );
	goalAreaTravelTimes = NULL;

	cacheListStart = cacheListEnd = NULL;
	totalCacheMemory = 0;
}

/*
============
idAASLocal::SetupRouting
============
*/
bool idAASLocal::SetupRouting( void ) {
	CalculateAreaTravelTimes();
	SetupRoutingCache();
	return true;
}

/*
============
idAASLocal::ShutdownRouting
============
*/
void idAASLocal::ShutdownRouting( void ) {
	DeleteAreaTravelTimes();
	ShutdownRoutingCache();
}

/*
============
idAASLocal::RoutingStats
============
*/
void idAASLocal::RoutingStats( void ) const {
	idRoutingCache *cache;
	int numAreaCache, numPortalCache;
	int totalAreaCacheMemory, totalPortalCacheMemory;

	numAreaCache = numPortalCache = 0;
	totalAreaCacheMemory = totalPortalCacheMemory = 0;
	for ( cache = cacheListStart; cache; cache = cache->time_next ) {
		if ( cache->type == CACHETYPE_AREA ) {
			numAreaCache++;
			totalAreaCacheMemory += sizeof( idRoutingCache ) + cache->size * (sizeof( unsigned short ) + sizeof( byte ));
		} else {
			numPortalCache++;
			totalPortalCacheMemory += sizeof( idRoutingCache ) + cache->size * (sizeof( unsigned short ) + sizeof( byte ));
		}
	}

	gameLocal.Printf( "%6d area cache (%d KB)\n", numAreaCache, totalAreaCacheMemory >> 10 );
	gameLocal.Printf( "%6d portal cache (%d KB)\n", numPortalCache, totalPortalCacheMemory >> 10 );
	gameLocal.Printf( "%6d total cache (%d KB)\n", numAreaCache + numPortalCache, totalCacheMemory >> 10 );
	gameLocal.Printf( "%6d area travel times (%lld KB)\n", numAreaTravelTimes, int64( numAreaTravelTimes * sizeof( unsigned short ) ) >> 10 );
	gameLocal.Printf( "%6d area cache entries (%lld KB)\n", areaCacheIndexSize, int64( areaCacheIndexSize * sizeof( idRoutingCache * ) ) >> 10 );
	gameLocal.Printf( "%6d portal cache entries (%lld KB)\n", portalCacheIndexSize, int64( portalCacheIndexSize * sizeof( idRoutingCache * ) ) >> 10 );
}

/*
============
idAASLocal::RemoveRoutingCacheUsingArea
============
*/
void idAASLocal::RemoveRoutingCacheUsingArea( int areaNum ) {
	int clusterNum;

	clusterNum = file->GetArea( areaNum ).cluster;
	if ( clusterNum > 0 ) {
		// remove all the cache in the cluster the area is in
		DeleteClusterCache( clusterNum );
	}
	else {
		// if this is a portal remove all cache in both the front and back cluster
		DeleteClusterCache( file->GetPortal( -clusterNum ).clusters[0] );
		DeleteClusterCache( file->GetPortal( -clusterNum ).clusters[1] );
	}
	DeletePortalCache();
}

/*
============
idAASLocal::DisableArea
============
*/
void idAASLocal::DisableArea( int areaNum ) {
	assert( areaNum > 0 && areaNum < file->GetNumAreas() );

	if ( file->GetArea( areaNum ).travelFlags & TFL_INVALID ) {
		return;
	}

	file->SetAreaTravelFlag( areaNum, TFL_INVALID );

	RemoveRoutingCacheUsingArea( areaNum );
}

/*
============
idAASLocal::EnableArea
============
*/
void idAASLocal::EnableArea( int areaNum ) {
	assert( areaNum > 0 && areaNum < file->GetNumAreas() );

	if ( !( file->GetArea( areaNum ).travelFlags & TFL_INVALID ) ) {
		return;
	}

	file->RemoveAreaTravelFlag( areaNum, TFL_INVALID );

	RemoveRoutingCacheUsingArea( areaNum );
}

/*
============
idAASLocal::SetAreaState_r
============
*/
bool idAASLocal::SetAreaState_r( int nodeNum, const idBounds &bounds, const int areaContents, bool disabled ) {
	int res;
	const aasNode_t *node;
	bool foundClusterPortal = false;

	while( nodeNum != 0 ) {
		if ( nodeNum < 0 ) {
			// if this area is a cluster portal
			if ( file->GetArea( -nodeNum ).contents & areaContents ) {
				if ( disabled ) {
					DisableArea( -nodeNum );
				} else {
					EnableArea( -nodeNum );
				}
				foundClusterPortal |= true;
			}
			break;
		}
		node = &file->GetNode( nodeNum );
		res = bounds.PlaneSide( file->GetPlane( node->planeNum ) );
		if ( res == PLANESIDE_BACK ) {
			nodeNum = node->children[1];
		}
		else if ( res == PLANESIDE_FRONT ) {
			nodeNum = node->children[0];
		}
		else {
			foundClusterPortal |= SetAreaState_r( node->children[1], bounds, areaContents, disabled );
			nodeNum = node->children[0];
		}
	}

	return foundClusterPortal;
}

/*
============
idAASLocal::SetAreaState
============
*/
bool idAASLocal::SetAreaState( const idBounds &bounds, const int areaContents, bool disabled ) {
	idBounds expBounds;

	if ( !file ) {
		return false;
	}

	expBounds[0] = bounds[0] - file->GetSettings().boundingBoxes[0][1];
	expBounds[1] = bounds[1] - file->GetSettings().boundingBoxes[0][0];

	// find all areas within or touching the bounds with the given contents and disable/enable them for routing
	return SetAreaState_r( 1, expBounds, areaContents, disabled );
}

/*
============
idAASLocal::GetBoundsAreas_r
============
*/
void idAASLocal::GetBoundsAreas_r( int nodeNum, const idBounds &bounds, idList<int> &areas ) const {
	int res;
	const aasNode_t *node;

	while( nodeNum != 0 ) {
		if ( nodeNum < 0 ) {
			areas.Append( -nodeNum );
			break;
		}
		node = &file->GetNode( nodeNum );
		res = bounds.PlaneSide( file->GetPlane( node->planeNum ) );
		if ( res == PLANESIDE_BACK ) {
			nodeNum = node->children[1];
		}
		else if ( res == PLANESIDE_FRONT ) {
			nodeNum = node->children[0];
		}
		else {
			GetBoundsAreas_r( node->children[1], bounds, areas );
			nodeNum = node->children[0];
		}
	}
}

/*
============
idAASLocal::SetObstacleState
============
*/
void idAASLocal::SetObstacleState( const idRoutingObstacle *obstacle, bool enable ) {
	int i;
	const aasArea_t *area;
	idReachability *reach, *rev_reach;
	bool inside;

	for ( i = 0; i < obstacle->areas.Num(); i++ ) {

		RemoveRoutingCacheUsingArea( obstacle->areas[i] );

		area = &file->GetArea( obstacle->areas[i] );

		for ( rev_reach = area->rev_reach; rev_reach; rev_reach = rev_reach->rev_next ) {

		
			/** SZ: I'm commenting this out as it prevents disabling obstacles from making areas
			* Accessible again
			*/
			/*
			if ( rev_reach->travelType & TFL_INVALID ) {
				continue;
			}
			*/

			inside = false;

			if ( obstacle->bounds.ContainsPoint( rev_reach->end ) ) {
				inside = true;
			}
			else {
				for ( reach = area->reach; reach; reach = reach->next ) {
					if ( obstacle->bounds.LineIntersection( rev_reach->end, reach->start ) ) {
						inside = true;
						break;
					}
				}
			}

			// SZ: I'm commenting out the original Doom3 code below because it is broken 
			// It appears as if the if ( enable ) line is supposed to be if ( !enable)
			// Enable refers to the obstacle being on or off, not to the reachability being
			// enabled or disabled. If the obstacle is enabled, then the reachability is
			// disabled.  This appears to have thus been a semantic error by Id.
			if ( inside ) {
				//if ( enable ) {
				if (!enable) {
					rev_reach->disableCount--;
					if ( rev_reach->disableCount <= 0 ) {
						rev_reach->travelType &= ~TFL_INVALID;
						rev_reach->disableCount = 0;
					}
				}
				else {
					rev_reach->travelType |= TFL_INVALID;
					rev_reach->disableCount++;
				}
			}
		}
	}
}

/*
============
idAASLocal::AddObstacle
============
*/
aasHandle_t idAASLocal::AddObstacle( const idBounds &bounds ) {
	idRoutingObstacle *obstacle;

	if ( !file ) {
		return -1;
	}

	obstacle = new idRoutingObstacle;
	obstacle->bounds[0] = bounds[0] - file->GetSettings().boundingBoxes[0][1];
	obstacle->bounds[1] = bounds[1] - file->GetSettings().boundingBoxes[0][0];
	GetBoundsAreas_r( 1, obstacle->bounds, obstacle->areas );
	SetObstacleState( obstacle, true );

	obstacleList.Append( obstacle );
	return obstacleList.Num() - 1;
}

/*
============
idAASLocal::RemoveObstacle
============
*/
void idAASLocal::RemoveObstacle( const aasHandle_t handle ) {
	if ( !file ) {
		return;
	}
	if ( ( handle >= 0 ) && ( handle < obstacleList.Num() ) ) {
		SetObstacleState( obstacleList[handle], false );

		delete obstacleList[handle];
		obstacleList.RemoveIndex( handle );
	}
}

/*
============
idAASLocal::RemoveAllObstacles
============
*/
void idAASLocal::RemoveAllObstacles( void ) {
	int i;

	if ( !file ) {
		return;
	}

	for ( i = 0; i < obstacleList.Num(); i++ ) {
		SetObstacleState( obstacleList[i], false );
		delete obstacleList[i];
	}
	obstacleList.Clear();
}

/*
============
idAASLocal::LinkCache

  link the cache in the cache list sorted from oldest to newest cache
============
*/
void idAASLocal::LinkCache( idRoutingCache *cache ) const {

	// if the cache is already linked
	if ( cache->time_next || cache->time_prev || cacheListStart == cache ) {
		UnlinkCache( cache );
	}

	totalCacheMemory += cache->Size();

	// add cache to the end of the list
	cache->time_next = NULL;
	cache->time_prev = cacheListEnd;
	if ( cacheListEnd ) {
		cacheListEnd->time_next = cache;
	}
	cacheListEnd = cache;
	if ( !cacheListStart ) {
		cacheListStart = cache;
	}
}

/*
============
idAASLocal::UnlinkCache
============
*/
void idAASLocal::UnlinkCache( idRoutingCache *cache ) const {

	totalCacheMemory -= cache->Size();

	// unlink the cache
	if ( cache->time_next ) {
		cache->time_next->time_prev = cache->time_prev;
	} else {
		cacheListEnd = cache->time_prev;
	}
	if ( cache->time_prev ) {
		cache->time_prev->time_next = cache->time_next;
	} else {
		cacheListStart = cache->time_next;
	}
	cache->time_next = cache->time_prev = NULL;
}

/*
============
idAASLocal::DeleteOldestCache
============
*/
void idAASLocal::DeleteOldestCache( void ) const {
	idRoutingCache *cache;

	assert( cacheListStart );

	// unlink the oldest cache
	cache = cacheListStart;
	UnlinkCache( cache );

	// unlink the oldest cache from the area or portal cache index
	if ( cache->next ) {
		cache->next->prev = cache->prev;
	}
	if ( cache->prev ) {
		cache->prev->next = cache->next;
	}
	else if ( cache->type == CACHETYPE_AREA ) {
		areaCacheIndex[cache->cluster][ClusterAreaNum( cache->cluster, cache->areaNum )] = cache->next;
	}
	else if ( cache->type == CACHETYPE_PORTAL ) {
		portalCacheIndex[cache->areaNum] = cache->next;
	}

	delete cache;
}

/*
============
idAASLocal::GetAreaReachability
============
*/
idReachability *idAASLocal::GetAreaReachability( int areaNum, int reachabilityNum ) const {
	idReachability *reach;

	for ( reach = file->GetArea( areaNum ).reach; reach; reach = reach->next ) {
		if ( --reachabilityNum < 0 ) {
			return reach;
		}
	}
	return NULL;
}

/*
============
idAASLocal::ClusterAreaNum
============
*/
ID_INLINE int idAASLocal::ClusterAreaNum( int clusterNum, int areaNum ) const {
	int side, areaCluster;

	areaCluster = file->GetArea( areaNum ).cluster;
	if ( areaCluster > 0 ) {
		return file->GetArea( areaNum ).clusterAreaNum;
	}
	else {
		side = file->GetPortal( -areaCluster ).clusters[0] != clusterNum;
		return file->GetPortal( -areaCluster ).clusterAreaNum[side];
	}
}

/*
============
idAASLocal::UpdateAreaRoutingCache
============
*/
void idAASLocal::UpdateAreaRoutingCache( idRoutingCache *areaCache ) const {
	// number of reachability areas within this cluster
	int numReachableAreas = file->GetCluster(areaCache->cluster).numReachableAreas;

	// number of the start area within the cluster
	int clusterAreaNum = ClusterAreaNum(areaCache->cluster, areaCache->areaNum);

	if (clusterAreaNum >= numReachableAreas) {
		return; // cluster area is not a reachable area
	}

	areaCache->travelTimes[clusterAreaNum] = areaCache->startTravelTime;
	int badTravelFlags = ~areaCache->travelFlags;

	unsigned short startAreaTravelTimes[MAX_REACH_PER_AREA];
	memset( startAreaTravelTimes, 0, sizeof( startAreaTravelTimes ) );

	// initialize first update
	idRoutingUpdate* curUpdate = &areaUpdate[clusterAreaNum];

	curUpdate->areaNum = areaCache->areaNum;
	curUpdate->areaTravelTimes = startAreaTravelTimes;
	curUpdate->tmpTravelTime = areaCache->startTravelTime;
	curUpdate->next = NULL;
	curUpdate->prev = NULL;

	idRoutingUpdate* updateListStart = curUpdate;
	idRoutingUpdate* updateListEnd = curUpdate;

	// while there are updates in the list
	while( updateListStart ) {

		curUpdate = updateListStart;
		if ( curUpdate->next ) {
			curUpdate->next->prev = NULL;
		}
		else {
			updateListEnd = NULL;
		}
		updateListStart = curUpdate->next;

		curUpdate->isInList = false;

		idReachability* reach;
		int i;
		for ( i = 0, reach = file->GetArea( curUpdate->areaNum ).rev_reach; reach; reach = reach->rev_next, i++ ) {

			// if the reachability uses an undesired travel type
			if ( reach->travelType & badTravelFlags ) {
				continue;
			}

			// next area the reversed reachability leads to
			int nextAreaNum = reach->fromAreaNum;
			const aasArea_t* nextArea = &file->GetArea( nextAreaNum );

			// if traveling through the next area requires an undesired travel flag
			if ( nextArea->travelFlags & badTravelFlags ) {
				continue;
			}

			// get the cluster number of the area
			int cluster = nextArea->cluster;
			// don't leave the cluster, however do flood into cluster portals
			if ( cluster > 0 && cluster != areaCache->cluster ) {
				continue;
			}

			// get the number of the area in the cluster
			clusterAreaNum = ClusterAreaNum( areaCache->cluster, nextAreaNum );
			if ( clusterAreaNum >= numReachableAreas ) {
				continue;	// should never happen
			}

			assert( clusterAreaNum < areaCache->size );

			// time already travelled plus the traveltime through the current area
			// plus the travel time of the reachability towards the next area
			unsigned short t = curUpdate->tmpTravelTime + curUpdate->areaTravelTimes[i] + reach->travelTime;

			if ( !areaCache->travelTimes[clusterAreaNum] || t < areaCache->travelTimes[clusterAreaNum] ) {

				areaCache->travelTimes[clusterAreaNum] = t;
				areaCache->reachabilities[clusterAreaNum] = reach->number; // reversed reachability used to get into this area
				idRoutingUpdate* nextUpdate = &areaUpdate[clusterAreaNum];
				nextUpdate->areaNum = nextAreaNum;
				nextUpdate->tmpTravelTime = t;
				nextUpdate->areaTravelTimes = reach->areaTravelTimes;

				// if we are not allowed to fly
				if ( badTravelFlags & TFL_FLY ) {
					// avoid areas near ledges
					if ( file->GetArea( nextAreaNum ).flags & AREA_LEDGE ) {
						nextUpdate->tmpTravelTime += LEDGE_TRAVELTIME_PENALTY;
					}
				}

				if ( !nextUpdate->isInList ) {
					nextUpdate->next = NULL;
					nextUpdate->prev = updateListEnd;
					if ( updateListEnd ) {
						updateListEnd->next = nextUpdate;
					}
					else {
						updateListStart = nextUpdate;
					}
					updateListEnd = nextUpdate;
					nextUpdate->isInList = true;
				}
			}
		}
	}
}

/*
============
idAASLocal::GetAreaRoutingCache
============
*/
idRoutingCache *idAASLocal::GetAreaRoutingCache( int clusterNum, int areaNum, int travelFlags ) const {
	int clusterAreaNum;
	idRoutingCache *cache, *clusterCache;

	// number of the area in the cluster
	clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );
	// pointer to the cache for the area in the cluster
	clusterCache = areaCacheIndex[clusterNum][clusterAreaNum];
	// check if cache without undesired travel flags already exists
	for ( cache = clusterCache; cache; cache = cache->next ) {
		if ( cache->travelFlags == travelFlags ) {
			break;
		}
	}
	// if no cache found
	if ( !cache ) {
		cache = new idRoutingCache( file->GetCluster( clusterNum ).numReachableAreas );
		cache->type = CACHETYPE_AREA;
		cache->cluster = clusterNum;
		cache->areaNum = areaNum;
		cache->startTravelTime = 1;
		cache->travelFlags = travelFlags;
		cache->prev = NULL;
		cache->next = clusterCache;
		if ( clusterCache ) {
			clusterCache->prev = cache;
		}
		areaCacheIndex[clusterNum][clusterAreaNum] = cache;
		UpdateAreaRoutingCache( cache );
	}
	LinkCache( cache );
	return cache;
}

/*
============
idAASLocal::UpdatePortalRoutingCache
============
*/
void idAASLocal::UpdatePortalRoutingCache( idRoutingCache *portalCache ) const {
	int i, portalNum, clusterAreaNum;
	unsigned short t;
	const aasPortal_t *portal;
	const aasCluster_t *cluster;
	idRoutingCache *cache;
	idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;

	curUpdate = &portalUpdate[ file->GetNumPortals() ];
	curUpdate->cluster = portalCache->cluster;
	curUpdate->areaNum = portalCache->areaNum;
	curUpdate->tmpTravelTime = portalCache->startTravelTime;

	//put the area to start with in the current read list
	curUpdate->next = NULL;
	curUpdate->prev = NULL;
	updateListStart = curUpdate;
	updateListEnd = curUpdate;

	// while there are updates in the current list
	while( updateListStart ) {

		curUpdate = updateListStart;
		// remove the current update from the list
		if ( curUpdate->next ) {
			curUpdate->next->prev = NULL;
		}
		else {
			updateListEnd = NULL;
		}
		updateListStart = curUpdate->next;
		// current update is removed from the list
		curUpdate->isInList = false;

		cluster = &file->GetCluster( curUpdate->cluster );
		cache = GetAreaRoutingCache( curUpdate->cluster, curUpdate->areaNum, portalCache->travelFlags );

		// take all portals of the cluster
		for ( i = 0; i < cluster->numPortals; i++ ) {
			portalNum = file->GetPortalIndex( cluster->firstPortal + i );
			assert( portalNum < portalCache->size );
			portal = &file->GetPortal( portalNum );

#if 0		// grayman - print portal data for debugging
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     ----------------------------------\r");
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     | data for portal %d of cluster %d\r",portalNum,curUpdate->cluster);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     |                 areaNum %d\r",portal->areaNum);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     |        clusterNum front %d\r",portal->clusters[0]);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     |         clusterNum back %d\r",portal->clusters[1]);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     | #areas in front cluster %d\r",portal->clusterAreaNum[0]);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     |  #areas in back cluster %d\r",portal->clusterAreaNum[1]);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     |       maxAreaTravelTime %d\r",portal->maxAreaTravelTime);
			DM_LOG(LC_AI, LT_DEBUG)LOGSTRING("     ----------------------------------\r");
#endif
			clusterAreaNum = ClusterAreaNum( curUpdate->cluster, portal->areaNum );
			if ( clusterAreaNum >= cluster->numReachableAreas ) {
				continue;
			}

			t = cache->travelTimes[clusterAreaNum];
			if ( t == 0 )
			{
				continue;
			}

			t += curUpdate->tmpTravelTime;

			if ( !portalCache->travelTimes[portalNum] || ( t < portalCache->travelTimes[portalNum] ) )
			{
				portalCache->travelTimes[portalNum] = t;
				portalCache->reachabilities[portalNum] = cache->reachabilities[clusterAreaNum];
				nextUpdate = &portalUpdate[portalNum];
				if ( portal->clusters[0] == curUpdate->cluster ) {
					nextUpdate->cluster = portal->clusters[1];
				}
				else {
					nextUpdate->cluster = portal->clusters[0];
				}
				nextUpdate->areaNum = portal->areaNum;
				// add travel time through the actual portal area for the next update
				nextUpdate->tmpTravelTime = t + portal->maxAreaTravelTime;

				if ( !nextUpdate->isInList ) {

					nextUpdate->next = NULL;
					nextUpdate->prev = updateListEnd;
					if ( updateListEnd ) {
						updateListEnd->next = nextUpdate;
					}
					else {
						updateListStart = nextUpdate;
					}
					updateListEnd = nextUpdate;
					nextUpdate->isInList = true;
				}
			}
		}
	}
}

/*
============
idAASLocal::GetPortalRoutingCache
============
*/
idRoutingCache *idAASLocal::GetPortalRoutingCache( int clusterNum, int areaNum, int travelFlags ) const {
	idRoutingCache *cache;

	// check if cache without undesired travel flags already exists
	for ( cache = portalCacheIndex[areaNum]; cache; cache = cache->next ) {
		if ( cache->travelFlags == travelFlags ) {
			break;
		}
	}
	// if no cache found
	if ( !cache ) {
		cache = new idRoutingCache( file->GetNumPortals() );
		cache->type = CACHETYPE_PORTAL;
		cache->cluster = clusterNum;
		cache->areaNum = areaNum;
		cache->startTravelTime = 1;
		cache->travelFlags = travelFlags;
		cache->prev = NULL;
		cache->next = portalCacheIndex[areaNum];
		if ( portalCacheIndex[areaNum] ) {
			portalCacheIndex[areaNum]->prev = cache;
		}
		portalCacheIndex[areaNum] = cache;
		UpdatePortalRoutingCache( cache );
	}
	LinkCache( cache );
	return cache;
}

/*
============
idAASLocal::RouteToGoalArea
============
*/
bool idAASLocal::RouteToGoalArea( int areaNum, const idVec3 origin, int goalAreaNum, 
								  int travelFlags, int &travelTime, idReachability **reach, 
								  CFrobDoor** firstDoor, idActor* actor ) const
{
#ifdef TIMING_BUILD
	if (actor != NULL)
	{
		START_SCOPED_TIMING(actor->actorRouteToGoalTimer, scopedRouteToGoalTimer);
	}
#endif

	
	// Set the default return values
	travelTime = 0;
	*reach = NULL;

	if (firstDoor != NULL)
	{
		*firstDoor = NULL;
	}

	if ( !file ) {
		return false;
	}

	if ( areaNum == goalAreaNum ) {
		return true;
	}

	if ( areaNum <= 0 || areaNum >= file->GetNumAreas() ) {
		gameLocal.Printf( "RouteToGoalArea: areaNum %d out of range\n", areaNum );
		return false;
	}

	if ( goalAreaNum <= 0 || goalAreaNum >= file->GetNumAreas() ) {
		gameLocal.Printf( "RouteToGoalArea: goalAreaNum %d out of range\n", goalAreaNum );
		return false;
	}

	while( totalCacheMemory > MAX_ROUTING_CACHE_MEMORY ) {
		DeleteOldestCache();
	}

	int clusterNum = file->GetArea( areaNum ).cluster;
	int goalClusterNum = file->GetArea( goalAreaNum ).cluster;

	idRoutingCache* portalCache = NULL;
	const aasPortal_t* portal = NULL;

	// if the source area is a cluster portal, read directly from the portal cache
	if ( clusterNum < 0 ) {
		// if the goal area is a portal
		if ( goalClusterNum < 0 ) {
			// just assume the goal area is part of the front cluster
			portal = &file->GetPortal( -goalClusterNum );
			goalClusterNum = portal->clusters[0];
		}
		// get the portal routing cache
		portalCache = GetPortalRoutingCache( goalClusterNum, goalAreaNum, travelFlags );
		*reach = GetAreaReachability( areaNum, portalCache->reachabilities[-clusterNum] );
		travelTime = portalCache->travelTimes[-clusterNum] + AreaTravelTime( areaNum, origin, (*reach)->start );
		return true;
	}

	unsigned short int bestTime = 0;
	idReachability* bestReach = NULL;

	// check if the goal area is a portal of the source area cluster
	if ( goalClusterNum < 0 ) {
		portal = &file->GetPortal( -goalClusterNum );
		if ( portal->clusters[0] == clusterNum || portal->clusters[1] == clusterNum) {
			goalClusterNum = clusterNum;
		}
	}

	int clusterAreaNum = 0;
	idRoutingCache* clusterCache = NULL;

	// if both areas are in the same cluster
	if ( clusterNum > 0 && goalClusterNum > 0 && clusterNum == goalClusterNum ) {
		clusterCache = GetAreaRoutingCache( clusterNum, goalAreaNum, travelFlags );
		clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );

		if ( clusterCache->travelTimes[clusterAreaNum] ) {
			bestReach = GetAreaReachability( areaNum, clusterCache->reachabilities[clusterAreaNum] );
			bestTime = clusterCache->travelTimes[clusterAreaNum] + AreaTravelTime( areaNum, origin, bestReach->start );
		}
		else {
			clusterCache = NULL;
		}
	}

	clusterNum = file->GetArea( areaNum ).cluster;
	goalClusterNum = file->GetArea( goalAreaNum ).cluster;

	// if the goal area is a portal
	if ( goalClusterNum < 0 ) {
		// just assume the goal area is part of the front cluster
		portal = &file->GetPortal( -goalClusterNum );
		goalClusterNum = portal->clusters[0];
	}
	// get the portal routing cache
	portalCache = GetPortalRoutingCache( goalClusterNum, goalAreaNum, travelFlags );

	// the cluster the area is in
	const aasCluster_t* cluster = &file->GetCluster( clusterNum );
	// current area inside the current cluster
	clusterAreaNum = ClusterAreaNum( clusterNum, areaNum );
	// if the area is not a reachable area
	if ( clusterAreaNum >= cluster->numReachableAreas)
	{
		return false;
	}

	int bestPortalAreaNum = 0;
	// find the portal of the source area cluster leading towards the goal area

	for ( int i = 0 ; i < cluster->numPortals ; i++ )
	{
		int portalNum = file->GetPortalIndex( cluster->firstPortal + i );

		// if the goal area isn't reachable from the portal
		if ( !portalCache->travelTimes[portalNum] )
		{
			continue;
		}

		portal = &file->GetPortal( portalNum );
		int portalAreaNum = portal->areaNum;

		// angua: area is forbidden (e.g. locked door)
		if (actor != NULL && gameLocal.m_AreaManager.AreaIsForbidden(portalAreaNum, static_cast<idAI*>(actor)))
		{
			continue;
		}

		// grayman #4412 - Check for FLYING + DOORS and skip
		// a portal exit if it has a closed door or partially open door that the
		// flying AI can't fit through.

		if (actor != NULL)
		{
			if ( actor->IsType(idAI::Type) )
			{
				idAI* ai = static_cast<idAI*>(actor);
				if ( ai->GetMoveType() == MOVETYPE_FLY )
				{
					// check if there is a door in the path
					aasArea_t pa = file->GetArea(portalAreaNum);
					if ( pa.travelFlags & TFL_DOOR )
					{
						CFrobDoor* portalDoor = GetDoor(portalAreaNum);
						if ( portalDoor != NULL )
						{
							if ( portalDoor->IsOpen() )
							{
								if ( !ai->FitsThrough(portalDoor) )
								{
									continue; // can't fit through the open door
								}
							}
							else
							{
								continue; // can't go through the closed door
							}
						}
					}
				}
			}
		}

		// get the cache of the portal area
		idRoutingCache* areaCache = GetAreaRoutingCache( clusterNum, portal->areaNum, travelFlags );
		// if the portal is not reachable from this area
		if ( !areaCache->travelTimes[clusterAreaNum] ) {
			continue;
		}

		idReachability* r = GetAreaReachability( areaNum, areaCache->reachabilities[clusterAreaNum] );

		if ( clusterCache ) {
			// if the next reachability from the portal leads back into the cluster
			idReachability* nextr = GetAreaReachability( portal->areaNum, portalCache->reachabilities[portalNum] );
			if ( file->GetArea( nextr->toAreaNum ).cluster < 0 || file->GetArea( nextr->toAreaNum ).cluster == clusterNum ) {
				continue;
			}
		}

		// the total travel time is the travel time from the portal area to the goal area
		// plus the travel time from the source area towards the portal area
		unsigned short int t = portalCache->travelTimes[portalNum] + areaCache->travelTimes[clusterAreaNum];

		// NOTE:	Should add the exact travel time through the portal area.
		//			However, we add the largest travel time through the portal area.
		//			We cannot directly calculate the exact travel time through the portal area
		//			because the reachability used to travel into the portal area is not known.
		t += portal->maxAreaTravelTime;

		// if the time is better than the one already found
		if ( !bestTime || t < bestTime ) {
			bestPortalAreaNum = portalAreaNum;
			bestReach = r;
			bestTime = t;
		}
	}

	if (bestPortalAreaNum > 0)
	{
		// angua: check if there is a door in the path
		aasArea_t portalArea = file->GetArea(bestPortalAreaNum);
		if (portalArea.travelFlags & TFL_DOOR)
		{
			CFrobDoor* door = GetDoor(bestPortalAreaNum);
			if (door != NULL && firstDoor != NULL)
			{
				*firstDoor = door;
			}
		}
	}
	
	if ( !bestReach )
	{
		return false;
	}

	*reach = bestReach;
	travelTime = bestTime;

	return true;
}

/*
============
idAASLocal::TravelTimeToGoalArea
============
*/
int idAASLocal::TravelTimeToGoalArea( int areaNum, const idVec3 &origin, int goalAreaNum, int travelFlags, idActor* actor ) const {
	int travelTime;
	idReachability *reach;

	if ( !file ) {
		return 0;
	}

	if ( !RouteToGoalArea( areaNum, origin, goalAreaNum, travelFlags, travelTime, &reach, NULL, actor ) ) {
		return 0;
	}
	return travelTime;
}

/*
============
idAASLocal::FindNearestGoal
maxTravelCost is optional and defaults to 0, meaning no maximum
============
*/
bool idAASLocal::FindNearestGoal( aasGoal_t &goal, int areaNum, const idVec3 origin, const idVec3 &target, int travelFlags, aasObstacle_t *obstacles, int numObstacles, idAASCallback &callback, unsigned short maxTravelCost ) const {
	int i, j, k, badTravelFlags, nextAreaNum, bestAreaNum;
	unsigned short t, bestTravelTime;
	idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;
	idReachability *reach;
	const aasArea_t *nextArea;
	idVec3 v1, v2, p;
	float targetDist, dist;

	if ( file == NULL || areaNum <= 0 ) {
		goal.areaNum = areaNum;
		goal.origin = origin;
		return false;
	}

	// if the first area is valid goal, just return the origin
	if ( callback.TestArea( this, areaNum ) ) {
		goal.areaNum = areaNum;
		goal.origin = origin;
		return true;
	}

	// setup obstacles
	for ( k = 0; k < numObstacles; k++ ) {
		obstacles[k].expAbsBounds[0] = obstacles[k].absBounds[0] - file->GetSettings().boundingBoxes[0][1];
		obstacles[k].expAbsBounds[1] = obstacles[k].absBounds[1] - file->GetSettings().boundingBoxes[0][0];
	}
	
	badTravelFlags = ~travelFlags;
	SIMDProcessor->Memset( goalAreaTravelTimes, 0, file->GetNumAreas() * sizeof( unsigned short ) );

	targetDist = (target - origin).Length();

	// initialize first update
	curUpdate = &areaUpdate[areaNum];
	curUpdate->areaNum = areaNum;
	curUpdate->tmpTravelTime = 0;
	curUpdate->start = origin;
	curUpdate->next = NULL;
	curUpdate->prev = NULL;
	updateListStart = curUpdate;
	updateListEnd = curUpdate;

	bestTravelTime = 0;
	bestAreaNum = 0;

	// while there are updates in the list
	while ( updateListStart ) {

		curUpdate = updateListStart;
		if ( curUpdate->next ) {
			curUpdate->next->prev = NULL;
		}
		else {
			updateListEnd = NULL;
		}
		updateListStart = curUpdate->next;

		curUpdate->isInList = false;

		// if we already found a closer location
		if ( bestTravelTime && curUpdate->tmpTravelTime >= bestTravelTime ) {
			continue;
		}

		for ( i = 0, reach = file->GetArea( curUpdate->areaNum ).reach; reach; reach = reach->next, i++ ) {

			// if the reachability uses an undesired travel type
			if ( reach->travelType & badTravelFlags ) {
				continue;
			}

			// next area the reversed reachability leads to
			nextAreaNum = reach->toAreaNum;
			nextArea = &file->GetArea( nextAreaNum );

			// if traveling through the next area requires an undesired travel flag
			if ( nextArea->travelFlags & badTravelFlags ) {
				continue;
			}

			t = curUpdate->tmpTravelTime +
					AreaTravelTime( curUpdate->areaNum, curUpdate->start, reach->start ) +
						reach->travelTime;
			
			// Don't travel too far
			if (maxTravelCost && t >= maxTravelCost) {
				continue;
			}
			
			// project target origin onto movement vector through the area
			v1 = reach->end - curUpdate->start;
			v1.Normalize();
			v2 = target - curUpdate->start;
			p = curUpdate->start + (v2 * v1) * v1;

			// get the point on the path closest to the target
			for ( j = 0; j < 3; j++ ) {
				if ( (p[j] > curUpdate->start[j] + 0.1f && p[j] > reach->end[j] + 0.1f) ||
					(p[j] < curUpdate->start[j] - 0.1f && p[j] < reach->end[j] - 0.1f) ) {
					break;
				}
			}
			if ( j >= 3 ) {
				dist = (target - p).Length();
			} else {
				dist = (target - reach->end).Length();
			}

			// avoid moving closer to the target
			if ( dist < targetDist ) {
				t += static_cast<short unsigned int>(( targetDist - dist ) * 10);
			}

			// if we already found a closer location
			if ( bestTravelTime && t >= bestTravelTime ) {
				continue;
			}

			// if this is not the best path towards the next area
			if ( goalAreaTravelTimes[nextAreaNum] && t >= goalAreaTravelTimes[nextAreaNum] ) {
				continue;
			}

			// path may not go through any obstacles
			for ( k = 0; k < numObstacles; k++ ) {
				// if the movement vector intersects the expanded obstacle bounds
				if ( obstacles[k].expAbsBounds.LineIntersection( curUpdate->start, reach->end ) ) {
					break;
				}
			}
			if ( k < numObstacles ) {
				continue;
			}

			goalAreaTravelTimes[nextAreaNum] = t;
			nextUpdate = &areaUpdate[nextAreaNum];
			nextUpdate->areaNum = nextAreaNum;
			nextUpdate->tmpTravelTime = t;
			nextUpdate->start = reach->end;

			// if we are not allowed to fly
			if ( badTravelFlags & TFL_FLY ) {
				// avoid areas near ledges
				if ( file->GetArea( nextAreaNum ).flags & AREA_LEDGE ) {
					nextUpdate->tmpTravelTime += LEDGE_TRAVELTIME_PENALTY;
				}
			}

			if ( !nextUpdate->isInList ) {
				nextUpdate->next = NULL;
				nextUpdate->prev = updateListEnd;
				if ( updateListEnd ) {
					updateListEnd->next = nextUpdate;
				} else {
					updateListStart = nextUpdate;
				}
				updateListEnd = nextUpdate;
				nextUpdate->isInList = true;
			}

			// don't put goal near a ledge
			if ( !( nextArea->flags & AREA_LEDGE ) ) {

				// add travel time through the area
				t += AreaTravelTime( reach->toAreaNum, reach->end, nextArea->center );
	
				if ( !bestTravelTime || t < bestTravelTime ) {
					// if the area is not visible to the target
					if ( callback.TestArea( this, reach->toAreaNum ) ) {
						bestTravelTime = t;
						bestAreaNum = reach->toAreaNum;
					}
				}
			}
		}
	}

	if ( bestAreaNum ) {
		goal.areaNum = bestAreaNum;
		goal.origin = AreaCenter( bestAreaNum );
		return true;
	}

	return false;
}

/*
============
idAASLocal::FindClosestTargetToGoal
============
*/
bool idAASLocal::FindGoalClosestToTarget( aasGoal_t &goal, int areaNum, const idVec3 origin, const idVec3 &target, int travelFlags, aasObstacle_t *obstacles, int numObstacles, idAASCallback &callback ) const 
{
	int i, k, badTravelFlags, nextAreaNum, bestAreaNum;
	bool b_haveClosestDistance;
	float closestDistanceToTarget;
	float distanceToTarget;
	idRoutingUpdate *updateListStart, *updateListEnd, *curUpdate, *nextUpdate;
	idReachability *reach;
	const aasArea_t *nextArea;
	float targetDist;

	if ( file == NULL || areaNum <= 0 ) 
	{
		goal.areaNum = areaNum;
		goal.origin = origin;
		return false;
	}

	/*
	// We want closest to target, not closest to us
	// if the first area is valid goal, just return the origin
	if ( callback.TestArea( this, areaNum ) ) 
	{
		goal.areaNum = areaNum;
		goal.origin = origin;
		return true;
	}
	*/

	// setup obstacles
	for ( k = 0; k < numObstacles; k++ ) 
	{
		obstacles[k].expAbsBounds[0] = obstacles[k].absBounds[0] - file->GetSettings().boundingBoxes[0][1];
		obstacles[k].expAbsBounds[1] = obstacles[k].absBounds[1] - file->GetSettings().boundingBoxes[0][0];
	}
	
	badTravelFlags = ~travelFlags;
	SIMDProcessor->Memset( goalAreaTravelTimes, 0, file->GetNumAreas() * sizeof( unsigned short ) );

	targetDist = (target - origin).Length();

	// Clear the area update tmpTravelTime members, as we use those as breadcrumbs
	int numAreas = file->GetNumAreas();
	for (int ai = 0; ai < numAreas; ai ++)
	{
		areaUpdate[ai].tmpTravelTime = 0;
	}


	// initialize first update
	curUpdate = &areaUpdate[areaNum];
	curUpdate->areaNum = areaNum;
	curUpdate->tmpTravelTime = 0;
	curUpdate->start = origin;
	curUpdate->next = NULL;
	curUpdate->prev = NULL;
	updateListStart = curUpdate;
	updateListEnd = curUpdate;

 	closestDistanceToTarget = 0.0;
	b_haveClosestDistance = false;
	bestAreaNum = 0;

	// while there are updates in the list
	while ( updateListStart ) 
	{

		curUpdate = updateListStart;
		if ( curUpdate->next ) 
		{
			curUpdate->next->prev = NULL;
		}
		else 
		{
			updateListEnd = NULL;
		}
		updateListStart = curUpdate->next;

		curUpdate->isInList = false;

		// If we already checked this area, we are done with it
		// We use the tmpTravelTime as a boolean flag to indicate if we have searched an area or not
		if (curUpdate->tmpTravelTime > 1.0)
		{
			continue;
		}
		else
		{
			// We are checking it
			curUpdate->tmpTravelTime = 2;
		}


		// What is the distance to the target
		distanceToTarget = (file->AreaCenter(curUpdate->areaNum) - target).Length();

		// If is closest so far
		if ( !b_haveClosestDistance || distanceToTarget < closestDistanceToTarget) 
		{
			// if the area is not visible to the target
			if ( callback.TestArea( this, curUpdate->areaNum ) ) 
			{
				closestDistanceToTarget = distanceToTarget;
				b_haveClosestDistance = true;
				bestAreaNum = curUpdate->areaNum;
			}
		}

		// if we already found a closer location we are done
		/*
		if 
		(
			( b_haveClosestDistance) && 
			((closestDistanceToTarget * 2.0) <= distanceToTarget)
		)
		{
			continue;
		}
		*/

		for ( i = 0, reach = file->GetArea( curUpdate->areaNum ).reach; reach; reach = reach->next, i++ )
		{
			// if the reachability uses an undesired travel type
			if ( reach->travelType & badTravelFlags ) 
			{
				continue;
			}

			// next area the reversed reachability leads to
			nextAreaNum = reach->toAreaNum;
			nextArea = &file->GetArea( nextAreaNum );

			// if traveling through the next area requires an undesired travel flag
			if ( nextArea->travelFlags & badTravelFlags ) 
			{
				continue;
			}

			// path may not go through any obstacles
			for ( k = 0; k < numObstacles; k++ ) 
			{
				// if the movement vector intersects the expanded obstacle bounds
				if ( obstacles[k].expAbsBounds.LineIntersection( curUpdate->start, reach->end ) ) 
				{
					break;
				}
			}
			if ( k < numObstacles ) 
			{
				continue;
			}

			nextUpdate = &areaUpdate[nextAreaNum];
			nextUpdate->areaNum = nextAreaNum;
			nextUpdate->start = reach->end;
			

			// if we are not allowed to fly
			if ( badTravelFlags & TFL_FLY ) 
			{
				// avoid areas near ledges
				if ( file->GetArea( nextAreaNum ).flags & AREA_LEDGE ) 
				{
					continue;
				}
			}

			if ( !nextUpdate->isInList ) 
			{
				nextUpdate->next = NULL;
				nextUpdate->prev = updateListEnd;
				if ( updateListEnd ) 
				{
					updateListEnd->next = nextUpdate;
				} 
				else 
				{
					updateListStart = nextUpdate;
				}
				updateListEnd = nextUpdate;
				nextUpdate->isInList = true;
	
			}

			/*
			// don't put goal near a ledge
			distanceToTarget = (file->AreaCenter(reach->toAreaNum) - target).Length();
			if ( !( nextArea->flags & AREA_LEDGE ) ) 
			{
				// If is closest so far
				if ( !b_haveClosestDistance || distanceToTarget < closestDistanceToTarget) 
				{
					// if the area is not visible to the target
					if ( callback.TestArea( this, reach->toAreaNum ) ) 
					{
						closestDistanceToTarget = distanceToTarget;
						b_haveClosestDistance = true;
						bestAreaNum = reach->toAreaNum;
					}
				}
			}
			*/
		}
	}

	if ( bestAreaNum ) 
	{
		goal.areaNum = bestAreaNum;
		goal.origin = AreaCenter( bestAreaNum );
		return true;
	}

	return false;
}

void idAASLocal::AddElevator(CMultiStateMover* mover)
{
	elevatorSystem->AddElevator(mover);
}

int idAASLocal::GetClusterSize()
{
	return file->GetNumClusters();
}

// grayman #3857
void idAASLocal::GetPortals(int areaNum, idList<idVec4> &portalList, idBounds searchLimits, idAI* ai) // grayman #4238
{
	int clusterNum = GetClusterNum(areaNum);
	if (clusterNum > 0)
	{
		const aasCluster_t* cluster = &file->GetCluster(clusterNum);
		int numPortals = cluster->numPortals;
		for (int i = 0 ; i < numPortals ; i++)
		{
			int portalNum = file->GetPortalIndex(cluster->firstPortal + i);
			const aasPortal_t* portal = &file->GetPortal(portalNum);
			idVec3 center = AreaCenter(portal->areaNum);

			// To reduce congestion, ignore any spots that are inside the search area.
			if (searchLimits.ContainsPoint(center))
			{
				continue;
			}

			// grayman #4238 - don't use this portal if already occupied

			if ( ai->PointObstructed(center) )
			{
				continue;
			}

			idVec4 spot = idVec4(center.x,center.y,center.z,idMath::INFINITY); // INFINITY = face search area origin
			portalList.Append(spot);
		}
	}
	else // areaNum is inside a portal, so we only have one portal center to add to the list
	{
		idVec3 center = AreaCenter(areaNum);

		if (searchLimits.ContainsPoint(center) || ai->PointObstructed(center)) // grayman #4238
		{
			// ignore this portal
			return;
		}

		idVec4 spot = idVec4(center.x,center.y,center.z,idMath::INFINITY); // INFINITY = face search area origin
		portalList.Append(spot);
	}
}

void idAASLocal::CompileEAS()
{
	elevatorSystem->Compile();
}

int	idAASLocal::GetAreaInCluster(int clusterNum)
{
	if (!file) return -1;

	// Find an area within that cluster
	for (int i = 0; i < file->GetNumAreas(); i++)
	{
		const aasArea_t& area = file->GetArea(i);
		if (area.cluster == clusterNum && (area.flags & AREA_REACHABLE_WALK) != 0)
		{
			return i;
		}
	}

	return -1;
}