be_aas_route.c

Go to the documentation of this file.

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena 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.

Quake III Arena 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 Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

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

#include "../game/q_shared.h"
#include "l_utils.h"
#include "l_memory.h"
#include "l_log.h"
#include "l_crc.h"
#include "l_libvar.h"
#include "l_script.h"
#include "l_precomp.h"
#include "l_struct.h"
#include "aasfile.h"
#include "../game/botlib.h"
#include "../game/be_aas.h"
#include "be_aas_funcs.h"
#include "be_interface.h"
#include "be_aas_def.h"

#define ROUTING_DEBUG

//travel time in hundreths of a second = distance * 100 / speed
#define DISTANCEFACTOR_CROUCH       1.3f        //crouch speed = 100
#define DISTANCEFACTOR_SWIM         1       //should be 0.66, swim speed = 150
#define DISTANCEFACTOR_WALK         0.33f   //walk speed = 300

//cache refresh time
#define CACHE_REFRESHTIME       15.0f   //15 seconds refresh time

//maximum number of routing updates each frame
#define MAX_FRAMEROUTINGUPDATES     10


/*

  area routing cache:
  stores the distances within one cluster to a specific goal area
  this goal area is in this same cluster and could be a cluster portal
  for every cluster there's a list with routing cache for every area
  in that cluster (including the portals of that cluster)
  area cache stores aasworld.clusters[?].numreachabilityareas travel times

  portal routing cache:
  stores the distances of all portals to a specific goal area
  this goal area could be in any cluster and could also be a cluster portal
  for every area (aasworld.numareas) the portal cache stores
  aasworld.numportals travel times

*/

#ifdef ROUTING_DEBUG
int numareacacheupdates;
int numportalcacheupdates;
#endif //ROUTING_DEBUG

int routingcachesize;
int max_routingcachesize;

//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
#ifdef ROUTING_DEBUG
void AAS_RoutingInfo(void)
{
    botimport.Print(PRT_MESSAGE, "%d area cache updates\n", numareacacheupdates);
    botimport.Print(PRT_MESSAGE, "%d portal cache updates\n", numportalcacheupdates);
    botimport.Print(PRT_MESSAGE, "%d bytes routing cache\n", routingcachesize);
} //end of the function AAS_RoutingInfo
#endif //ROUTING_DEBUG
//===========================================================================
// returns the number of the area in the cluster
// assumes the given area is in the given cluster or a portal of the cluster
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
__inline int AAS_ClusterAreaNum(int cluster, int areanum)
{
    int side, areacluster;

    areacluster = aasworld.areasettings[areanum].cluster;
    if (areacluster > 0) return aasworld.areasettings[areanum].clusterareanum;
    else
    {
/*#ifdef ROUTING_DEBUG
        if (aasworld.portals[-areacluster].frontcluster != cluster &&
                aasworld.portals[-areacluster].backcluster != cluster)
        {
            botimport.Print(PRT_ERROR, "portal %d: does not belong to cluster %d\n"
                                            , -areacluster, cluster);
        } //end if
#endif //ROUTING_DEBUG*/
        side = aasworld.portals[-areacluster].frontcluster != cluster;
        return aasworld.portals[-areacluster].clusterareanum[side];
    } //end else
} //end of the function AAS_ClusterAreaNum
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_InitTravelFlagFromType(void)
{
    int i;

    for (i = 0; i < MAX_TRAVELTYPES; i++)
    {
        aasworld.travelflagfortype[i] = TFL_INVALID;
    } //end for
    aasworld.travelflagfortype[TRAVEL_INVALID] = TFL_INVALID;
    aasworld.travelflagfortype[TRAVEL_WALK] = TFL_WALK;
    aasworld.travelflagfortype[TRAVEL_CROUCH] = TFL_CROUCH;
    aasworld.travelflagfortype[TRAVEL_BARRIERJUMP] = TFL_BARRIERJUMP;
    aasworld.travelflagfortype[TRAVEL_JUMP] = TFL_JUMP;
    aasworld.travelflagfortype[TRAVEL_LADDER] = TFL_LADDER;
    aasworld.travelflagfortype[TRAVEL_WALKOFFLEDGE] = TFL_WALKOFFLEDGE;
    aasworld.travelflagfortype[TRAVEL_SWIM] = TFL_SWIM;
    aasworld.travelflagfortype[TRAVEL_WATERJUMP] = TFL_WATERJUMP;
    aasworld.travelflagfortype[TRAVEL_TELEPORT] = TFL_TELEPORT;
    aasworld.travelflagfortype[TRAVEL_ELEVATOR] = TFL_ELEVATOR;
    aasworld.travelflagfortype[TRAVEL_ROCKETJUMP] = TFL_ROCKETJUMP;
    aasworld.travelflagfortype[TRAVEL_BFGJUMP] = TFL_BFGJUMP;
    aasworld.travelflagfortype[TRAVEL_GRAPPLEHOOK] = TFL_GRAPPLEHOOK;
    aasworld.travelflagfortype[TRAVEL_DOUBLEJUMP] = TFL_DOUBLEJUMP;
    aasworld.travelflagfortype[TRAVEL_RAMPJUMP] = TFL_RAMPJUMP;
    aasworld.travelflagfortype[TRAVEL_STRAFEJUMP] = TFL_STRAFEJUMP;
    aasworld.travelflagfortype[TRAVEL_JUMPPAD] = TFL_JUMPPAD;
    aasworld.travelflagfortype[TRAVEL_FUNCBOB] = TFL_FUNCBOB;
} //end of the function AAS_InitTravelFlagFromType
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
__inline int AAS_TravelFlagForType_inline(int traveltype)
{
    int tfl;

    tfl = 0;
    if (tfl & TRAVELFLAG_NOTTEAM1)
        tfl |= TFL_NOTTEAM1;
    if (tfl & TRAVELFLAG_NOTTEAM2)
        tfl |= TFL_NOTTEAM2;
    traveltype &= TRAVELTYPE_MASK;
    if (traveltype < 0 || traveltype >= MAX_TRAVELTYPES)
        return TFL_INVALID;
    tfl |= aasworld.travelflagfortype[traveltype];
    return tfl;
} //end of the function AAS_TravelFlagForType_inline
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_TravelFlagForType(int traveltype)
{
    return AAS_TravelFlagForType_inline(traveltype);
} //end of the function AAS_TravelFlagForType_inline
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_UnlinkCache(aas_routingcache_t *cache)
{
    if (cache->time_next) cache->time_next->time_prev = cache->time_prev;
    else aasworld.newestcache = cache->time_prev;
    if (cache->time_prev) cache->time_prev->time_next = cache->time_next;
    else aasworld.oldestcache = cache->time_next;
    cache->time_next = NULL;
    cache->time_prev = NULL;
} //end of the function AAS_UnlinkCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_LinkCache(aas_routingcache_t *cache)
{
    if (aasworld.newestcache)
    {
        aasworld.newestcache->time_next = cache;
        cache->time_prev = aasworld.newestcache;
    } //end if
    else
    {
        aasworld.oldestcache = cache;
        cache->time_prev = NULL;
    } //end else
    cache->time_next = NULL;
    aasworld.newestcache = cache;
} //end of the function AAS_LinkCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_FreeRoutingCache(aas_routingcache_t *cache)
{
    AAS_UnlinkCache(cache);
    routingcachesize -= cache->size;
    FreeMemory(cache);
} //end of the function AAS_FreeRoutingCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_RemoveRoutingCacheInCluster( int clusternum )
{
    int i;
    aas_routingcache_t *cache, *nextcache;
    aas_cluster_t *cluster;

    if (!aasworld.clusterareacache)
        return;
    cluster = &aasworld.clusters[clusternum];
    for (i = 0; i < cluster->numareas; i++)
    {
        for (cache = aasworld.clusterareacache[clusternum][i]; cache; cache = nextcache)
        {
            nextcache = cache->next;
            AAS_FreeRoutingCache(cache);
        } //end for
        aasworld.clusterareacache[clusternum][i] = NULL;
    } //end for
} //end of the function AAS_RemoveRoutingCacheInCluster
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_RemoveRoutingCacheUsingArea( int areanum )
{
    int i, clusternum;
    aas_routingcache_t *cache, *nextcache;

    clusternum = aasworld.areasettings[areanum].cluster;
    if (clusternum > 0)
    {
        //remove all the cache in the cluster the area is in
        AAS_RemoveRoutingCacheInCluster( clusternum );
    } //end if
    else
    {
        // if this is a portal remove all cache in both the front and back cluster
        AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].frontcluster );
        AAS_RemoveRoutingCacheInCluster( aasworld.portals[-clusternum].backcluster );
    } //end else
    // remove all portal cache
    for (i = 0; i < aasworld.numareas; i++)
    {
        //refresh portal cache
        for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
        {
            nextcache = cache->next;
            AAS_FreeRoutingCache(cache);
        } //end for
        aasworld.portalcache[i] = NULL;
    } //end for
} //end of the function AAS_RemoveRoutingCacheUsingArea
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_EnableRoutingArea(int areanum, int enable)
{
    int flags;

    if (areanum <= 0 || areanum >= aasworld.numareas)
    {
        if (bot_developer)
        {
            botimport.Print(PRT_ERROR, "AAS_EnableRoutingArea: areanum %d out of range\n", areanum);
        } //end if
        return 0;
    } //end if
    flags = aasworld.areasettings[areanum].areaflags & AREA_DISABLED;
    if (enable < 0)
        return !flags;

    if (enable)
        aasworld.areasettings[areanum].areaflags &= ~AREA_DISABLED;
    else
        aasworld.areasettings[areanum].areaflags |= AREA_DISABLED;
    // if the status of the area changed
    if ( (flags & AREA_DISABLED) != (aasworld.areasettings[areanum].areaflags & AREA_DISABLED) )
    {
        //remove all routing cache involving this area
        AAS_RemoveRoutingCacheUsingArea( areanum );
    } //end if
    return !flags;
} //end of the function AAS_EnableRoutingArea
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
__inline float AAS_RoutingTime(void)
{
    return AAS_Time();
} //end of the function AAS_RoutingTime
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_GetAreaContentsTravelFlags(int areanum)
{
    int contents, tfl;

    contents = aasworld.areasettings[areanum].contents;
    tfl = 0;
    if (contents & AREACONTENTS_WATER)
        tfl |= TFL_WATER;
    else if (contents & AREACONTENTS_SLIME)
        tfl |= TFL_SLIME;
    else if (contents & AREACONTENTS_LAVA)
        tfl |= TFL_LAVA;
    else
        tfl |= TFL_AIR;
    if (contents & AREACONTENTS_DONOTENTER)
        tfl |= TFL_DONOTENTER;
    if (contents & AREACONTENTS_NOTTEAM1)
        tfl |= TFL_NOTTEAM1;
    if (contents & AREACONTENTS_NOTTEAM2)
        tfl |= TFL_NOTTEAM2;
    if (aasworld.areasettings[areanum].areaflags & AREA_BRIDGE)
        tfl |= TFL_BRIDGE;
    return tfl;
} //end of the function AAS_GetAreaContentsTravelFlags
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
__inline int AAS_AreaContentsTravelFlags_inline(int areanum)
{
    return aasworld.areacontentstravelflags[areanum];
} //end of the function AAS_AreaContentsTravelFlags
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_AreaContentsTravelFlags(int areanum)
{
    return aasworld.areacontentstravelflags[areanum];
} //end of the function AAS_AreaContentsTravelFlags
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_InitAreaContentsTravelFlags(void)
{
    int i;

    if (aasworld.areacontentstravelflags) FreeMemory(aasworld.areacontentstravelflags);
    aasworld.areacontentstravelflags = (int *) GetClearedMemory(aasworld.numareas * sizeof(int));
    //
    for (i = 0; i < aasworld.numareas; i++) {
        aasworld.areacontentstravelflags[i] = AAS_GetAreaContentsTravelFlags(i);
    }
} //end of the function AAS_InitAreaContentsTravelFlags
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_CreateReversedReachability(void)
{
    int i, n;
    aas_reversedlink_t *revlink;
    aas_reachability_t *reach;
    aas_areasettings_t *settings;
    char *ptr;
#ifdef DEBUG
    int starttime;

    starttime = Sys_MilliSeconds();
#endif
    //free reversed links that have already been created
    if (aasworld.reversedreachability) FreeMemory(aasworld.reversedreachability);
    //allocate memory for the reversed reachability links
    ptr = (char *) GetClearedMemory(aasworld.numareas * sizeof(aas_reversedreachability_t) +
                            aasworld.reachabilitysize * sizeof(aas_reversedlink_t));
    //
    aasworld.reversedreachability = (aas_reversedreachability_t *) ptr;
    //pointer to the memory for the reversed links
    ptr += aasworld.numareas * sizeof(aas_reversedreachability_t);
    //check all reachabilities of all areas
    for (i = 1; i < aasworld.numareas; i++)
    {
        //settings of the area
        settings = &aasworld.areasettings[i];
        //
        if (settings->numreachableareas >= 128)
            botimport.Print(PRT_WARNING, "area %d has more than 128 reachabilities\n", i);
        //create reversed links for the reachabilities
        for (n = 0; n < settings->numreachableareas && n < 128; n++)
        {
            //reachability link
            reach = &aasworld.reachability[settings->firstreachablearea + n];
            //
            revlink = (aas_reversedlink_t *) ptr;
            ptr += sizeof(aas_reversedlink_t);
            //
            revlink->areanum = i;
            revlink->linknum = settings->firstreachablearea + n;
            revlink->next = aasworld.reversedreachability[reach->areanum].first;
            aasworld.reversedreachability[reach->areanum].first = revlink;
            aasworld.reversedreachability[reach->areanum].numlinks++;
        } //end for
    } //end for
#ifdef DEBUG
    botimport.Print(PRT_MESSAGE, "reversed reachability %d msec\n", Sys_MilliSeconds() - starttime);
#endif
} //end of the function AAS_CreateReversedReachability
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
unsigned short int AAS_AreaTravelTime(int areanum, vec3_t start, vec3_t end)
{
    int intdist;
    float dist;
    vec3_t dir;

    VectorSubtract(start, end, dir);
    dist = VectorLength(dir);
    //if crouch only area
    if (AAS_AreaCrouch(areanum)) dist *= DISTANCEFACTOR_CROUCH;
    //if swim area
    else if (AAS_AreaSwim(areanum)) dist *= DISTANCEFACTOR_SWIM;
    //normal walk area
    else dist *= DISTANCEFACTOR_WALK;
    //
    intdist = (int) dist;
    //make sure the distance isn't zero
    if (intdist <= 0) intdist = 1;
    return intdist;
} //end of the function AAS_AreaTravelTime
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_CalculateAreaTravelTimes(void)
{
    int i, l, n, size;
    char *ptr;
    vec3_t end;
    aas_reversedreachability_t *revreach;
    aas_reversedlink_t *revlink;
    aas_reachability_t *reach;
    aas_areasettings_t *settings;
    int starttime;

    starttime = Sys_MilliSeconds();
    //if there are still area travel times, free the memory
    if (aasworld.areatraveltimes) FreeMemory(aasworld.areatraveltimes);
    //get the total size of all the area travel times
    size = aasworld.numareas * sizeof(unsigned short **);
    for (i = 0; i < aasworld.numareas; i++)
    {
        revreach = &aasworld.reversedreachability[i];
        //settings of the area
        settings = &aasworld.areasettings[i];
        //
        size += settings->numreachableareas * sizeof(unsigned short *);
        //
        size += settings->numreachableareas * revreach->numlinks * sizeof(unsigned short);
    } //end for
    //allocate memory for the area travel times
    ptr = (char *) GetClearedMemory(size);
    aasworld.areatraveltimes = (unsigned short ***) ptr;
    ptr += aasworld.numareas * sizeof(unsigned short **);
    //calcluate the travel times for all the areas
    for (i = 0; i < aasworld.numareas; i++)
    {
        //reversed reachabilities of this area
        revreach = &aasworld.reversedreachability[i];
        //settings of the area
        settings = &aasworld.areasettings[i];
        //
        aasworld.areatraveltimes[i] = (unsigned short **) ptr;
        ptr += settings->numreachableareas * sizeof(unsigned short *);
        //
        for (l = 0; l < settings->numreachableareas; l++)
        {
            aasworld.areatraveltimes[i][l] = (unsigned short *) ptr;
            ptr += revreach->numlinks * sizeof(unsigned short);
            //reachability link
            reach = &aasworld.reachability[settings->firstreachablearea + l];
            //
            for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
            {
                VectorCopy(aasworld.reachability[revlink->linknum].end, end);
                //
                aasworld.areatraveltimes[i][l][n] = AAS_AreaTravelTime(i, end, reach->start);
            } //end for
        } //end for
    } //end for
#ifdef DEBUG
    botimport.Print(PRT_MESSAGE, "area travel times %d msec\n", Sys_MilliSeconds() - starttime);
#endif
} //end of the function AAS_CalculateAreaTravelTimes
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_PortalMaxTravelTime(int portalnum)
{
    int l, n, t, maxt;
    aas_portal_t *portal;
    aas_reversedreachability_t *revreach;
    aas_reversedlink_t *revlink;
    aas_areasettings_t *settings;

    portal = &aasworld.portals[portalnum];
    //reversed reachabilities of this portal area
    revreach = &aasworld.reversedreachability[portal->areanum];
    //settings of the portal area
    settings = &aasworld.areasettings[portal->areanum];
    //
    maxt = 0;
    for (l = 0; l < settings->numreachableareas; l++)
    {
        for (n = 0, revlink = revreach->first; revlink; revlink = revlink->next, n++)
        {
            t = aasworld.areatraveltimes[portal->areanum][l][n];
            if (t > maxt)
            {
                maxt = t;
            } //end if
        } //end for
    } //end for
    return maxt;
} //end of the function AAS_PortalMaxTravelTime
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_InitPortalMaxTravelTimes(void)
{
    int i;

    if (aasworld.portalmaxtraveltimes) FreeMemory(aasworld.portalmaxtraveltimes);

    aasworld.portalmaxtraveltimes = (int *) GetClearedMemory(aasworld.numportals * sizeof(int));

    for (i = 0; i < aasworld.numportals; i++)
    {
        aasworld.portalmaxtraveltimes[i] = AAS_PortalMaxTravelTime(i);
        //botimport.Print(PRT_MESSAGE, "portal %d max tt = %d\n", i, aasworld.portalmaxtraveltimes[i]);
    } //end for
} //end of the function AAS_InitPortalMaxTravelTimes
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
/*
int AAS_FreeOldestCache(void)
{
    int i, j, bestcluster, bestarea, freed;
    float besttime;
    aas_routingcache_t *cache, *bestcache;

    freed = qfalse;
    besttime = 999999999;
    bestcache = NULL;
    bestcluster = 0;
    bestarea = 0;
    //refresh cluster cache
    for (i = 0; i < aasworld.numclusters; i++)
    {
        for (j = 0; j < aasworld.clusters[i].numareas; j++)
        {
            for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
            {
                //never remove cache leading towards a portal
                if (aasworld.areasettings[cache->areanum].cluster < 0) continue;
                //if this cache is older than the cache we found so far
                if (cache->time < besttime)
                {
                    bestcache = cache;
                    bestcluster = i;
                    bestarea = j;
                    besttime = cache->time;
                } //end if
            } //end for
        } //end for
    } //end for
    if (bestcache)
    {
        cache = bestcache;
        if (cache->prev) cache->prev->next = cache->next;
        else aasworld.clusterareacache[bestcluster][bestarea] = cache->next;
        if (cache->next) cache->next->prev = cache->prev;
        AAS_FreeRoutingCache(cache);
        freed = qtrue;
    } //end if
    besttime = 999999999;
    bestcache = NULL;
    bestarea = 0;
    for (i = 0; i < aasworld.numareas; i++)
    {
        //refresh portal cache
        for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
        {
            if (cache->time < besttime)
            {
                bestcache = cache;
                bestarea = i;
                besttime = cache->time;
            } //end if
        } //end for
    } //end for
    if (bestcache)
    {
        cache = bestcache;
        if (cache->prev) cache->prev->next = cache->next;
        else aasworld.portalcache[bestarea] = cache->next;
        if (cache->next) cache->next->prev = cache->prev;
        AAS_FreeRoutingCache(cache);
        freed = qtrue;
    } //end if
    return freed;
} //end of the function AAS_FreeOldestCache
*/
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_FreeOldestCache(void)
{
    int clusterareanum;
    aas_routingcache_t *cache;

    for (cache = aasworld.oldestcache; cache; cache = cache->time_next) {
        // never free area cache leading towards a portal
        if (cache->type == CACHETYPE_AREA && aasworld.areasettings[cache->areanum].cluster < 0) {
            continue;
        }
        break;
    }
    if (cache) {
        // unlink the cache
        if (cache->type == CACHETYPE_AREA) {
            //number of the area in the cluster
            clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
            // unlink from cluster area cache
            if (cache->prev) cache->prev->next = cache->next;
            else aasworld.clusterareacache[cache->cluster][clusterareanum] = cache->next;
            if (cache->next) cache->next->prev = cache->prev;
        }
        else {
            // unlink from portal cache
            if (cache->prev) cache->prev->next = cache->next;
            else aasworld.portalcache[cache->areanum] = cache->next;
            if (cache->next) cache->next->prev = cache->prev;
        }
        AAS_FreeRoutingCache(cache);
        return qtrue;
    }
    return qfalse;
} //end of the function AAS_FreeOldestCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
aas_routingcache_t *AAS_AllocRoutingCache(int numtraveltimes)
{
    aas_routingcache_t *cache;
    int size;

    //
    size = sizeof(aas_routingcache_t)
                        + numtraveltimes * sizeof(unsigned short int)
                        + numtraveltimes * sizeof(unsigned char);
    //
    routingcachesize += size;
    //
    cache = (aas_routingcache_t *) GetClearedMemory(size);
    cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t)
                                + numtraveltimes * sizeof(unsigned short int);
    cache->size = size;
    return cache;
} //end of the function AAS_AllocRoutingCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_FreeAllClusterAreaCache(void)
{
    int i, j;
    aas_routingcache_t *cache, *nextcache;
    aas_cluster_t *cluster;

    //free all cluster cache if existing
    if (!aasworld.clusterareacache) return;
    //free caches
    for (i = 0; i < aasworld.numclusters; i++)
    {
        cluster = &aasworld.clusters[i];
        for (j = 0; j < cluster->numareas; j++)
        {
            for (cache = aasworld.clusterareacache[i][j]; cache; cache = nextcache)
            {
                nextcache = cache->next;
                AAS_FreeRoutingCache(cache);
            } //end for
            aasworld.clusterareacache[i][j] = NULL;
        } //end for
    } //end for
    //free the cluster cache array
    FreeMemory(aasworld.clusterareacache);
    aasworld.clusterareacache = NULL;
} //end of the function AAS_FreeAllClusterAreaCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_InitClusterAreaCache(void)
{
    int i, size;
    char *ptr;

    //
    for (size = 0, i = 0; i < aasworld.numclusters; i++)
    {
        size += aasworld.clusters[i].numareas;
    } //end for
    //two dimensional array with pointers for every cluster to routing cache
    //for every area in that cluster
    ptr = (char *) GetClearedMemory(
                aasworld.numclusters * sizeof(aas_routingcache_t **) +
                size * sizeof(aas_routingcache_t *));
    aasworld.clusterareacache = (aas_routingcache_t ***) ptr;
    ptr += aasworld.numclusters * sizeof(aas_routingcache_t **);
    for (i = 0; i < aasworld.numclusters; i++)
    {
        aasworld.clusterareacache[i] = (aas_routingcache_t **) ptr;
        ptr += aasworld.clusters[i].numareas * sizeof(aas_routingcache_t *);
    } //end for
} //end of the function AAS_InitClusterAreaCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_FreeAllPortalCache(void)
{
    int i;
    aas_routingcache_t *cache, *nextcache;

    //free all portal cache if existing
    if (!aasworld.portalcache) return;
    //free portal caches
    for (i = 0; i < aasworld.numareas; i++)
    {
        for (cache = aasworld.portalcache[i]; cache; cache = nextcache)
        {
            nextcache = cache->next;
            AAS_FreeRoutingCache(cache);
        } //end for
        aasworld.portalcache[i] = NULL;
    } //end for
    FreeMemory(aasworld.portalcache);
    aasworld.portalcache = NULL;
} //end of the function AAS_FreeAllPortalCache
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitPortalCache(void)
{
    //
    aasworld.portalcache = (aas_routingcache_t **) GetClearedMemory(
                                aasworld.numareas * sizeof(aas_routingcache_t *));
} //end of the function AAS_InitPortalCache
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitRoutingUpdate(void)
{
    int i, maxreachabilityareas;

    //free routing update fields if already existing
    if (aasworld.areaupdate) FreeMemory(aasworld.areaupdate);
    //
    maxreachabilityareas = 0;
    for (i = 0; i < aasworld.numclusters; i++)
    {
        if (aasworld.clusters[i].numreachabilityareas > maxreachabilityareas)
        {
            maxreachabilityareas = aasworld.clusters[i].numreachabilityareas;
        } //end if
    } //end for
    //allocate memory for the routing update fields
    aasworld.areaupdate = (aas_routingupdate_t *) GetClearedMemory(
                                    maxreachabilityareas * sizeof(aas_routingupdate_t));
    //
    if (aasworld.portalupdate) FreeMemory(aasworld.portalupdate);
    //allocate memory for the portal update fields
    aasworld.portalupdate = (aas_routingupdate_t *) GetClearedMemory(
                                    (aasworld.numportals+1) * sizeof(aas_routingupdate_t));
} //end of the function AAS_InitRoutingUpdate
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void AAS_CreateAllRoutingCache(void)
{
    int i, j, t;

    aasworld.initialized = qtrue;
    botimport.Print(PRT_MESSAGE, "AAS_CreateAllRoutingCache\n");
    for (i = 1; i < aasworld.numareas; i++)
    {
        if (!AAS_AreaReachability(i)) continue;
        for (j = 1; j < aasworld.numareas; j++)
        {
            if (i == j) continue;
            if (!AAS_AreaReachability(j)) continue;
            t = AAS_AreaTravelTimeToGoalArea(i, aasworld.areas[i].center, j, TFL_DEFAULT);
            //Log_Write("traveltime from %d to %d is %d", i, j, t);
        } //end for
    } //end for
    aasworld.initialized = qfalse;
} //end of the function AAS_CreateAllRoutingCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================

//the route cache header
//this header is followed by numportalcache + numareacache aas_routingcache_t
//structures that store routing cache
typedef struct routecacheheader_s
{
    int ident;
    int version;
    int numareas;
    int numclusters;
    int areacrc;
    int clustercrc;
    int numportalcache;
    int numareacache;
} routecacheheader_t;

#define RCID                        (('C'<<24)+('R'<<16)+('E'<<8)+'M')
#define RCVERSION                   2

//void AAS_DecompressVis(byte *in, int numareas, byte *decompressed);
//int AAS_CompressVis(byte *vis, int numareas, byte *dest);

void AAS_WriteRouteCache(void)
{
    int i, j, numportalcache, numareacache, totalsize;
    aas_routingcache_t *cache;
    aas_cluster_t *cluster;
    fileHandle_t fp;
    char filename[MAX_QPATH];
    routecacheheader_t routecacheheader;

    numportalcache = 0;
    for (i = 0; i < aasworld.numareas; i++)
    {
        for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
        {
            numportalcache++;
        } //end for
    } //end for
    numareacache = 0;
    for (i = 0; i < aasworld.numclusters; i++)
    {
        cluster = &aasworld.clusters[i];
        for (j = 0; j < cluster->numareas; j++)
        {
            for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
            {
                numareacache++;
            } //end for
        } //end for
    } //end for
    // open the file for writing
    Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
    botimport.FS_FOpenFile( filename, &fp, FS_WRITE );
    if (!fp)
    {
        AAS_Error("Unable to open file: %s\n", filename);
        return;
    } //end if
    //create the header
    routecacheheader.ident = RCID;
    routecacheheader.version = RCVERSION;
    routecacheheader.numareas = aasworld.numareas;
    routecacheheader.numclusters = aasworld.numclusters;
    routecacheheader.areacrc = CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas );
    routecacheheader.clustercrc = CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters );
    routecacheheader.numportalcache = numportalcache;
    routecacheheader.numareacache = numareacache;
    //write the header
    botimport.FS_Write(&routecacheheader, sizeof(routecacheheader_t), fp);
    //
    totalsize = 0;
    //write all the cache
    for (i = 0; i < aasworld.numareas; i++)
    {
        for (cache = aasworld.portalcache[i]; cache; cache = cache->next)
        {
            botimport.FS_Write(cache, cache->size, fp);
            totalsize += cache->size;
        } //end for
    } //end for
    for (i = 0; i < aasworld.numclusters; i++)
    {
        cluster = &aasworld.clusters[i];
        for (j = 0; j < cluster->numareas; j++)
        {
            for (cache = aasworld.clusterareacache[i][j]; cache; cache = cache->next)
            {
                botimport.FS_Write(cache, cache->size, fp);
                totalsize += cache->size;
            } //end for
        } //end for
    } //end for
    // write the visareas
    /*
    for (i = 0; i < aasworld.numareas; i++)
    {
        if (!aasworld.areavisibility[i]) {
            size = 0;
            botimport.FS_Write(&size, sizeof(int), fp);
            continue;
        }
        AAS_DecompressVis( aasworld.areavisibility[i], aasworld.numareas, aasworld.decompressedvis );
        size = AAS_CompressVis( aasworld.decompressedvis, aasworld.numareas, aasworld.decompressedvis );
        botimport.FS_Write(&size, sizeof(int), fp);
        botimport.FS_Write(aasworld.decompressedvis, size, fp);
    }
    */
    //
    botimport.FS_FCloseFile(fp);
    botimport.Print(PRT_MESSAGE, "\nroute cache written to %s\n", filename);
    botimport.Print(PRT_MESSAGE, "written %d bytes of routing cache\n", totalsize);
} //end of the function AAS_WriteRouteCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
aas_routingcache_t *AAS_ReadCache(fileHandle_t fp)
{
    int size;
    aas_routingcache_t *cache;

    botimport.FS_Read(&size, sizeof(size), fp);
    cache = (aas_routingcache_t *) GetMemory(size);
    cache->size = size;
    botimport.FS_Read((unsigned char *)cache + sizeof(size), size - sizeof(size), fp);
    cache->reachabilities = (unsigned char *) cache + sizeof(aas_routingcache_t) - sizeof(unsigned short) +
        (size - sizeof(aas_routingcache_t) + sizeof(unsigned short)) / 3 * 2;
    return cache;
} //end of the function AAS_ReadCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_ReadRouteCache(void)
{
    int i, clusterareanum;//, size;
    fileHandle_t fp;
    char filename[MAX_QPATH];
    routecacheheader_t routecacheheader;
    aas_routingcache_t *cache;

    Com_sprintf(filename, MAX_QPATH, "maps/%s.rcd", aasworld.mapname);
    botimport.FS_FOpenFile( filename, &fp, FS_READ );
    if (!fp)
    {
        return qfalse;
    } //end if
    botimport.FS_Read(&routecacheheader, sizeof(routecacheheader_t), fp );
    if (routecacheheader.ident != RCID)
    {
        AAS_Error("%s is not a route cache dump\n");
        return qfalse;
    } //end if
    if (routecacheheader.version != RCVERSION)
    {
        AAS_Error("route cache dump has wrong version %d, should be %d", routecacheheader.version, RCVERSION);
        return qfalse;
    } //end if
    if (routecacheheader.numareas != aasworld.numareas)
    {
        //AAS_Error("route cache dump has wrong number of areas\n");
        return qfalse;
    } //end if
    if (routecacheheader.numclusters != aasworld.numclusters)
    {
        //AAS_Error("route cache dump has wrong number of clusters\n");
        return qfalse;
    } //end if
    if (routecacheheader.areacrc !=
        CRC_ProcessString( (unsigned char *)aasworld.areas, sizeof(aas_area_t) * aasworld.numareas ))
    {
        //AAS_Error("route cache dump area CRC incorrect\n");
        return qfalse;
    } //end if
    if (routecacheheader.clustercrc !=
        CRC_ProcessString( (unsigned char *)aasworld.clusters, sizeof(aas_cluster_t) * aasworld.numclusters ))
    {
        //AAS_Error("route cache dump cluster CRC incorrect\n");
        return qfalse;
    } //end if
    //read all the portal cache
    for (i = 0; i < routecacheheader.numportalcache; i++)
    {
        cache = AAS_ReadCache(fp);
        cache->next = aasworld.portalcache[cache->areanum];
        cache->prev = NULL;
        if (aasworld.portalcache[cache->areanum])
            aasworld.portalcache[cache->areanum]->prev = cache;
        aasworld.portalcache[cache->areanum] = cache;
    } //end for
    //read all the cluster area cache
    for (i = 0; i < routecacheheader.numareacache; i++)
    {
        cache = AAS_ReadCache(fp);
        clusterareanum = AAS_ClusterAreaNum(cache->cluster, cache->areanum);
        cache->next = aasworld.clusterareacache[cache->cluster][clusterareanum];
        cache->prev = NULL;
        if (aasworld.clusterareacache[cache->cluster][clusterareanum])
            aasworld.clusterareacache[cache->cluster][clusterareanum]->prev = cache;
        aasworld.clusterareacache[cache->cluster][clusterareanum] = cache;
    } //end for
    // read the visareas
    /*
    aasworld.areavisibility = (byte **) GetClearedMemory(aasworld.numareas * sizeof(byte *));
    aasworld.decompressedvis = (byte *) GetClearedMemory(aasworld.numareas * sizeof(byte));
    for (i = 0; i < aasworld.numareas; i++)
    {
        botimport.FS_Read(&size, sizeof(size), fp );
        if (size) {
            aasworld.areavisibility[i] = (byte *) GetMemory(size);
            botimport.FS_Read(aasworld.areavisibility[i], size, fp );
        }
    }
    */
    //
    botimport.FS_FCloseFile(fp);
    return qtrue;
} //end of the function AAS_ReadRouteCache
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
#define MAX_REACHABILITYPASSAREAS       32

void AAS_InitReachabilityAreas(void)
{
    int i, j, numareas, areas[MAX_REACHABILITYPASSAREAS];
    int numreachareas;
    aas_reachability_t *reach;
    vec3_t start, end;

    if (aasworld.