be_aas_reach.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_reach.c
 *
 * desc:        reachability calculations
 *
 * $Archive: /MissionPack/code/botlib/be_aas_reach.c $
 *
 *****************************************************************************/

#include "../game/q_shared.h"
#include "l_log.h"
#include "l_memory.h"
#include "l_script.h"
#include "l_libvar.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_aas_def.h"

extern int Sys_MilliSeconds(void);


extern botlib_import_t botimport;

//#define REACH_DEBUG

//NOTE: all travel times are in hundreth of a second
//maximum number of reachability links
#define AAS_MAX_REACHABILITYSIZE            65536
//number of areas reachability is calculated for each frame
#define REACHABILITYAREASPERCYCLE           15
//number of units reachability points are placed inside the areas
#define INSIDEUNITS                         2
#define INSIDEUNITS_WALKEND                 5
#define INSIDEUNITS_WALKSTART               0.1
#define INSIDEUNITS_WATERJUMP               15
//area flag used for weapon jumping
#define AREA_WEAPONJUMP                     8192    //valid area to weapon jump to
//number of reachabilities of each type
int reach_swim;         //swim
int reach_equalfloor;   //walk on floors with equal height
int reach_step;         //step up
int reach_walk;         //walk of step
int reach_barrier;      //jump up to a barrier
int reach_waterjump;    //jump out of water
int reach_walkoffledge; //walk of a ledge
int reach_jump;         //jump
int reach_ladder;       //climb or descent a ladder
int reach_teleport;     //teleport
int reach_elevator;     //use an elevator
int reach_funcbob;      //use a func bob
int reach_grapple;      //grapple hook
int reach_doublejump;   //double jump
int reach_rampjump;     //ramp jump
int reach_strafejump;   //strafe jump (just normal jump but further)
int reach_rocketjump;   //rocket jump
int reach_bfgjump;      //bfg jump
int reach_jumppad;      //jump pads
//if true grapple reachabilities are skipped
int calcgrapplereach;
//linked reachability
typedef struct aas_lreachability_s
{
    int areanum;                    //number of the reachable area
    int facenum;                    //number of the face towards the other area
    int edgenum;                    //number of the edge towards the other area
    vec3_t start;                   //start point of inter area movement
    vec3_t end;                     //end point of inter area movement
    int traveltype;                 //type of travel required to get to the area
    unsigned short int traveltime;  //travel time of the inter area movement
    //
    struct aas_lreachability_s *next;
} aas_lreachability_t;
//temporary reachabilities
aas_lreachability_t *reachabilityheap;  //heap with reachabilities
aas_lreachability_t *nextreachability;  //next free reachability from the heap
aas_lreachability_t **areareachability; //reachability links for every area
int numlreachabilities;

//===========================================================================
// returns the surface area of the given face
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
float AAS_FaceArea(aas_face_t *face)
{
    int i, edgenum, side;
    float total;
    vec_t *v;
    vec3_t d1, d2, cross;
    aas_edge_t *edge;

    edgenum = aasworld.edgeindex[face->firstedge];
    side = edgenum < 0;
    edge = &aasworld.edges[abs(edgenum)];
    v = aasworld.vertexes[edge->v[side]];

    total = 0;
    for (i = 1; i < face->numedges - 1; i++)
    {
        edgenum = aasworld.edgeindex[face->firstedge + i];
        side = edgenum < 0;
        edge = &aasworld.edges[abs(edgenum)];
        VectorSubtract(aasworld.vertexes[edge->v[side]], v, d1);
        VectorSubtract(aasworld.vertexes[edge->v[!side]], v, d2);
        CrossProduct(d1, d2, cross);
        total += 0.5 * VectorLength(cross);
    } //end for
    return total;
} //end of the function AAS_FaceArea
//===========================================================================
// returns the volume of an area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
float AAS_AreaVolume(int areanum)
{
    int i, edgenum, facenum, side;
    vec_t d, a, volume;
    vec3_t corner;
    aas_plane_t *plane;
    aas_edge_t *edge;
    aas_face_t *face;
    aas_area_t *area;

    area = &aasworld.areas[areanum];
    facenum = aasworld.faceindex[area->firstface];
    face = &aasworld.faces[abs(facenum)];
    edgenum = aasworld.edgeindex[face->firstedge];
    edge = &aasworld.edges[abs(edgenum)];
    //
    VectorCopy(aasworld.vertexes[edge->v[0]], corner);

    //make tetrahedrons to all other faces
    volume = 0;
    for (i = 0; i < area->numfaces; i++)
    {
        facenum = abs(aasworld.faceindex[area->firstface + i]);
        face = &aasworld.faces[facenum];
        side = face->backarea != areanum;
        plane = &aasworld.planes[face->planenum ^ side];
        d = -(DotProduct (corner, plane->normal) - plane->dist);
        a = AAS_FaceArea(face);
        volume += d * a;
    } //end for

    volume /= 3;
    return volume;
} //end of the function AAS_AreaVolume
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_BestReachableLinkArea(aas_link_t *areas)
{
    aas_link_t *link;

    for (link = areas; link; link = link->next_area)
    {
        if (AAS_AreaGrounded(link->areanum) || AAS_AreaSwim(link->areanum))
        {
            return link->areanum;
        } //end if
    } //end for
    //
    for (link = areas; link; link = link->next_area)
    {
        if (link->areanum) return link->areanum;
        //FIXME: this is a bad idea when the reachability is not yet
        // calculated when the level items are loaded
        if (AAS_AreaReachability(link->areanum))
            return link->areanum;
    } //end for
    return 0;
} //end of the function AAS_BestReachableLinkArea
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_GetJumpPadInfo(int ent, vec3_t areastart, vec3_t absmins, vec3_t absmaxs, vec3_t velocity)
{
    int modelnum, ent2;
    float speed, height, gravity, time, dist, forward;
    vec3_t origin, angles, teststart, ent2origin;
    aas_trace_t trace;
    char model[MAX_EPAIRKEY];
    char target[MAX_EPAIRKEY], targetname[MAX_EPAIRKEY];

    //
    AAS_FloatForBSPEpairKey(ent, "speed", &speed);
    if (!speed) speed = 1000;
    VectorClear(angles);
    //get the mins, maxs and origin of the model
    AAS_ValueForBSPEpairKey(ent, "model", model, MAX_EPAIRKEY);
    if (model[0]) modelnum = atoi(model+1);
    else modelnum = 0;
    AAS_BSPModelMinsMaxsOrigin(modelnum, angles, absmins, absmaxs, origin);
    VectorAdd(origin, absmins, absmins);
    VectorAdd(origin, absmaxs, absmaxs);
    VectorAdd(absmins, absmaxs, origin);
    VectorScale (origin, 0.5, origin);

    //get the start areas
    VectorCopy(origin, teststart);
    teststart[2] += 64;
    trace = AAS_TraceClientBBox(teststart, origin, PRESENCE_CROUCH, -1);
    if (trace.startsolid)
    {
        botimport.Print(PRT_MESSAGE, "trigger_push start solid\n");
        VectorCopy(origin, areastart);
    } //end if
    else
    {
        VectorCopy(trace.endpos, areastart);
    } //end else
    areastart[2] += 0.125;
    //
    //AAS_DrawPermanentCross(origin, 4, 4);
    //get the target entity
    AAS_ValueForBSPEpairKey(ent, "target", target, MAX_EPAIRKEY);
    for (ent2 = AAS_NextBSPEntity(0); ent2; ent2 = AAS_NextBSPEntity(ent2))
    {
        if (!AAS_ValueForBSPEpairKey(ent2, "targetname", targetname, MAX_EPAIRKEY)) continue;
        if (!strcmp(targetname, target)) break;
    } //end for
    if (!ent2)
    {
        botimport.Print(PRT_MESSAGE, "trigger_push without target entity %s\n", target);
        return qfalse;
    } //end if
    AAS_VectorForBSPEpairKey(ent2, "origin", ent2origin);
    //
    height = ent2origin[2] - origin[2];
    gravity = aassettings.phys_gravity;
    time = sqrt( height / ( 0.5 * gravity ) );
    if (!time)
    {
        botimport.Print(PRT_MESSAGE, "trigger_push without time\n");
        return qfalse;
    } //end if
    // set s.origin2 to the push velocity
    VectorSubtract ( ent2origin, origin, velocity);
    dist = VectorNormalize( velocity);
    forward = dist / time;
    //FIXME: why multiply by 1.1
    forward *= 1.1f;
    VectorScale(velocity, forward, velocity);
    velocity[2] = time * gravity;
    return qtrue;
} //end of the function AAS_GetJumpPadInfo
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_BestReachableFromJumpPadArea(vec3_t origin, vec3_t mins, vec3_t maxs)
{
    int area2num, ent, bot_visualizejumppads, bestareanum;
    float volume, bestareavolume;
    vec3_t areastart, cmdmove, bboxmins, bboxmaxs;
    vec3_t absmins, absmaxs, velocity;
    aas_clientmove_t move;
    aas_link_t *areas, *link;
    char classname[MAX_EPAIRKEY];

#ifdef BSPC
    bot_visualizejumppads = 0;
#else
    bot_visualizejumppads = LibVarValue("bot_visualizejumppads", "0");
#endif
    VectorAdd(origin, mins, bboxmins);
    VectorAdd(origin, maxs, bboxmaxs);
    for (ent = AAS_NextBSPEntity(0); ent; ent = AAS_NextBSPEntity(ent))
    {
        if (!AAS_ValueForBSPEpairKey(ent, "classname", classname, MAX_EPAIRKEY)) continue;
        if (strcmp(classname, "trigger_push")) continue;
        //
        if (!AAS_GetJumpPadInfo(ent, areastart, absmins, absmaxs, velocity)) continue;
        //get the areas the jump pad brush is in
        areas = AAS_LinkEntityClientBBox(absmins, absmaxs, -1, PRESENCE_CROUCH);
        for (link = areas; link; link = link->next_area)
        {
            if (AAS_AreaJumpPad(link->areanum)) break;
        } //end for
        if (!link)
        {
            botimport.Print(PRT_MESSAGE, "trigger_push not in any jump pad area\n");
            AAS_UnlinkFromAreas(areas);
            continue;
        } //end if
        //
        //botimport.Print(PRT_MESSAGE, "found a trigger_push with velocity %f %f %f\n", velocity[0], velocity[1], velocity[2]);
        //
        VectorSet(cmdmove, 0, 0, 0);
        Com_Memset(&move, 0, sizeof(aas_clientmove_t));
        area2num = 0;
        AAS_ClientMovementHitBBox(&move, -1, areastart, PRESENCE_NORMAL, qfalse,
                                velocity, cmdmove, 0, 30, 0.1f, bboxmins, bboxmaxs, bot_visualizejumppads);
        if (move.frames < 30)
        {
            bestareanum = 0;
            bestareavolume = 0;
            for (link = areas; link; link = link->next_area)
            {
                if (!AAS_AreaJumpPad(link->areanum)) continue;
                volume = AAS_AreaVolume(link->areanum);
                if (volume >= bestareavolume)
                {
                    bestareanum = link->areanum;
                    bestareavolume = volume;
                } //end if
            } //end if
            AAS_UnlinkFromAreas(areas);
            return bestareanum;
        } //end if
        AAS_UnlinkFromAreas(areas);
    } //end for
    return 0;
} //end of the function AAS_BestReachableFromJumpPadArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_BestReachableArea(vec3_t origin, vec3_t mins, vec3_t maxs, vec3_t goalorigin)
{
    int areanum, i, j, k, l;
    aas_link_t *areas;
    vec3_t absmins, absmaxs;
    //vec3_t bbmins, bbmaxs;
    vec3_t start, end;
    aas_trace_t trace;

    if (!aasworld.loaded)
    {
        botimport.Print(PRT_ERROR, "AAS_BestReachableArea: aas not loaded\n");
        return 0;
    } //end if
    //find a point in an area
    VectorCopy(origin, start);
    areanum = AAS_PointAreaNum(start);
    //while no area found fudge around a little
    for (i = 0; i < 5 && !areanum; i++)
    {
        for (j = 0; j < 5 && !areanum; j++)
        {
            for (k = -1; k <= 1 && !areanum; k++)
            {
                for (l = -1; l <= 1 && !areanum; l++)
                {
                    VectorCopy(origin, start);
                    start[0] += (float) j * 4 * k;
                    start[1] += (float) j * 4 * l;
                    start[2] += (float) i * 4;
                    areanum = AAS_PointAreaNum(start);
                } //end for
            } //end for
        } //end for
    } //end for
    //if an area was found
    if (areanum)
    {
        //drop client bbox down and try again
        VectorCopy(start, end);
        start[2] += 0.25;
        end[2] -= 50;
        trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, -1);
        if (!trace.startsolid)
        {
            areanum = AAS_PointAreaNum(trace.endpos);
            VectorCopy(trace.endpos, goalorigin);
            //FIXME: cannot enable next line right now because the reachability
            // does not have to be calculated when the level items are loaded
            //if the origin is in an area with reachability
            //if (AAS_AreaReachability(areanum)) return areanum;
            if (areanum) return areanum;
        } //end if
        else
        {
            //it can very well happen that the AAS_PointAreaNum function tells that
            //a point is in an area and that starting a AAS_TraceClientBBox from that
            //point will return trace.startsolid qtrue
#if 0
            if (AAS_PointAreaNum(start))
            {
                Log_Write("point %f %f %f in area %d but trace startsolid", start[0], start[1], start[2], areanum);
                AAS_DrawPermanentCross(start, 4, LINECOLOR_RED);
            } //end if
            botimport.Print(PRT_MESSAGE, "AAS_BestReachableArea: start solid\n");
#endif
            VectorCopy(start, goalorigin);
            return areanum;
        } //end else
    } //end if
    //
    //AAS_PresenceTypeBoundingBox(PRESENCE_CROUCH, bbmins, bbmaxs);
    //NOTE: the goal origin does not have to be in the goal area
    // because the bot will have to move towards the item origin anyway
    VectorCopy(origin, goalorigin);
    //
    VectorAdd(origin, mins, absmins);
    VectorAdd(origin, maxs, absmaxs);
    //add bounding box size
    //VectorSubtract(absmins, bbmaxs, absmins);
    //VectorSubtract(absmaxs, bbmins, absmaxs);
    //link an invalid (-1) entity
    areas = AAS_LinkEntityClientBBox(absmins, absmaxs, -1, PRESENCE_CROUCH);
    //get the reachable link arae
    areanum = AAS_BestReachableLinkArea(areas);
    //unlink the invalid entity
    AAS_UnlinkFromAreas(areas);
    //
    return areanum;
} //end of the function AAS_BestReachableArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_SetupReachabilityHeap(void)
{
    int i;

    reachabilityheap = (aas_lreachability_t *) GetClearedMemory(
                        AAS_MAX_REACHABILITYSIZE * sizeof(aas_lreachability_t));
    for (i = 0; i < AAS_MAX_REACHABILITYSIZE-1; i++)
    {
        reachabilityheap[i].next = &reachabilityheap[i+1];
    } //end for
    reachabilityheap[AAS_MAX_REACHABILITYSIZE-1].next = NULL;
    nextreachability = reachabilityheap;
    numlreachabilities = 0;
} //end of the function AAS_InitReachabilityHeap
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_ShutDownReachabilityHeap(void)
{
    FreeMemory(reachabilityheap);
    numlreachabilities = 0;
} //end of the function AAS_ShutDownReachabilityHeap
//===========================================================================
// returns a reachability link
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
aas_lreachability_t *AAS_AllocReachability(void)
{
    aas_lreachability_t *r;

    if (!nextreachability) return NULL;
    //make sure the error message only shows up once
    if (!nextreachability->next) AAS_Error("AAS_MAX_REACHABILITYSIZE");
    //
    r = nextreachability;
    nextreachability = nextreachability->next;
    numlreachabilities++;
    return r;
} //end of the function AAS_AllocReachability
//===========================================================================
// frees a reachability link
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeReachability(aas_lreachability_t *lreach)
{
    Com_Memset(lreach, 0, sizeof(aas_lreachability_t));

    lreach->next = nextreachability;
    nextreachability = lreach;
    numlreachabilities--;
} //end of the function AAS_FreeReachability
//===========================================================================
// returns qtrue if the area has reachability links
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaReachability(int areanum)
{
    if (areanum < 0 || areanum >= aasworld.numareas)
    {
        AAS_Error("AAS_AreaReachability: areanum %d out of range", areanum);
        return 0;
    } //end if
    return aasworld.areasettings[areanum].numreachableareas;
} //end of the function AAS_AreaReachability
//===========================================================================
// returns the surface area of all ground faces together of the area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
float AAS_AreaGroundFaceArea(int areanum)
{
    int i;
    float total;
    aas_area_t *area;
    aas_face_t *face;

    total = 0;
    area = &aasworld.areas[areanum];
    for (i = 0; i < area->numfaces; i++)
    {
        face = &aasworld.faces[abs(aasworld.faceindex[area->firstface + i])];
        if (!(face->faceflags & FACE_GROUND)) continue;
        //
        total += AAS_FaceArea(face);
    } //end for
    return total;
} //end of the function AAS_AreaGroundFaceArea
//===========================================================================
// returns the center of a face
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FaceCenter(int facenum, vec3_t center)
{
    int i;
    float scale;
    aas_face_t *face;
    aas_edge_t *edge;

    face = &aasworld.faces[facenum];

    VectorClear(center);
    for (i = 0; i < face->numedges; i++)
    {
        edge = &aasworld.edges[abs(aasworld.edgeindex[face->firstedge + i])];
        VectorAdd(center, aasworld.vertexes[edge->v[0]], center);
        VectorAdd(center, aasworld.vertexes[edge->v[1]], center);
    } //end for
    scale = 0.5 / face->numedges;
    VectorScale(center, scale, center);
} //end of the function AAS_FaceCenter
//===========================================================================
// returns the maximum distance a player can fall before being damaged
// damage = deltavelocity*deltavelocity  * 0.0001
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_FallDamageDistance(void)
{
    float maxzvelocity, gravity, t;

    maxzvelocity = sqrt(30 * 10000);
    gravity = aassettings.phys_gravity;
    t = maxzvelocity / gravity;
    return 0.5 * gravity * t * t;
} //end of the function AAS_FallDamageDistance
//===========================================================================
// distance = 0.5 * gravity * t * t
// vel = t * gravity
// damage = vel * vel * 0.0001
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
float AAS_FallDelta(float distance)
{
    float t, delta, gravity;

    gravity = aassettings.phys_gravity;
    t = sqrt(fabs(distance) * 2 / gravity);
    delta = t * gravity;
    return delta * delta * 0.0001;
} //end of the function AAS_FallDelta
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
float AAS_MaxJumpHeight(float phys_jumpvel)
{
    float phys_gravity;

    phys_gravity = aassettings.phys_gravity;
    //maximum height a player can jump with the given initial z velocity
    return 0.5 * phys_gravity * (phys_jumpvel / phys_gravity) * (phys_jumpvel / phys_gravity);
} //end of the function MaxJumpHeight
//===========================================================================
// returns true if a player can only crouch in the area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
float AAS_MaxJumpDistance(float phys_jumpvel)
{
    float phys_gravity, phys_maxvelocity, t;

    phys_gravity = aassettings.phys_gravity;
    phys_maxvelocity = aassettings.phys_maxvelocity;
    //time a player takes to fall the height
    t = sqrt(aassettings.rs_maxjumpfallheight / (0.5 * phys_gravity));
   //maximum distance
    return phys_maxvelocity * (t + phys_jumpvel / phys_gravity);
} //end of the function AAS_MaxJumpDistance
//===========================================================================
// returns true if a player can only crouch in the area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaCrouch(int areanum)
{
    if (!(aasworld.areasettings[areanum].presencetype & PRESENCE_NORMAL)) return qtrue;
    else return qfalse;
} //end of the function AAS_AreaCrouch
//===========================================================================
// returns qtrue if it is possible to swim in the area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaSwim(int areanum)
{
    if (aasworld.areasettings[areanum].areaflags & AREA_LIQUID) return qtrue;
    else return qfalse;
} //end of the function AAS_AreaSwim
//===========================================================================
// returns qtrue if the area contains a liquid
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaLiquid(int areanum)
{
    if (aasworld.areasettings[areanum].areaflags & AREA_LIQUID) return qtrue;
    else return qfalse;
} //end of the function AAS_AreaLiquid
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_AreaLava(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_LAVA);
} //end of the function AAS_AreaLava
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int AAS_AreaSlime(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_SLIME);
} //end of the function AAS_AreaSlime
//===========================================================================
// returns qtrue if the area contains ground faces
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaGrounded(int areanum)
{
    return (aasworld.areasettings[areanum].areaflags & AREA_GROUNDED);
} //end of the function AAS_AreaGround
//===========================================================================
// returns true if the area contains ladder faces
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaLadder(int areanum)
{
    return (aasworld.areasettings[areanum].areaflags & AREA_LADDER);
} //end of the function AAS_AreaLadder
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaJumpPad(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_JUMPPAD);
} //end of the function AAS_AreaJumpPad
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaTeleporter(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_TELEPORTER);
} //end of the function AAS_AreaTeleporter
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaClusterPortal(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_CLUSTERPORTAL);
} //end of the function AAS_AreaClusterPortal
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_AreaDoNotEnter(int areanum)
{
    return (aasworld.areasettings[areanum].contents & AREACONTENTS_DONOTENTER);
} //end of the function AAS_AreaDoNotEnter
//===========================================================================
// returns the time it takes perform a barrier jump
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
unsigned short int AAS_BarrierJumpTravelTime(void)
{
    return aassettings.phys_jumpvel / (aassettings.phys_gravity * 0.1);
} //end op the function AAS_BarrierJumpTravelTime
//===========================================================================
// returns true if there already exists a reachability from area1 to area2
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
qboolean AAS_ReachabilityExists(int area1num, int area2num)
{
    aas_lreachability_t *r;

    for (r = areareachability[area1num]; r; r = r->next)
    {
        if (r->areanum == area2num) return qtrue;
    } //end for
    return qfalse;
} //end of the function AAS_ReachabilityExists
//===========================================================================
// returns true if there is a solid just after the end point when going
// from start to end
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_NearbySolidOrGap(vec3_t start, vec3_t end)
{
    vec3_t dir, testpoint;
    int areanum;

    VectorSubtract(end, start, dir);
    dir[2] = 0;
    VectorNormalize(dir);
    VectorMA(end, 48, dir, testpoint);

    areanum = AAS_PointAreaNum(testpoint);
    if (!areanum)
    {
        testpoint[2] += 16;
        areanum = AAS_PointAreaNum(testpoint);
        if (!areanum) return qtrue;
    } //end if
    VectorMA(end, 64, dir, testpoint);
    areanum = AAS_PointAreaNum(testpoint);
    if (areanum)
    {
        if (!AAS_AreaSwim(areanum) && !AAS_AreaGrounded(areanum)) return qtrue;
    } //end if
    return qfalse;
} //end of the function AAS_SolidGapTime
//===========================================================================
// searches for swim reachabilities between adjacent areas
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_Reachability_Swim(int area1num, int area2num)
{
    int i, j, face1num, face2num, side1;
    aas_area_t *area1, *area2;
    aas_areasettings_t *areasettings;
    aas_lreachability_t *lreach;
    aas_face_t *face1;
    aas_plane_t *plane;
    vec3_t start;

    if (!AAS_AreaSwim(area1num) || !AAS_AreaSwim(area2num)) return qfalse;
    //if the second area is crouch only
    if (!(aasworld.areasettings[area2num].presencetype & PRESENCE_NORMAL)) return qfalse;

    area1 = &aasworld.areas[area1num];
    area2 = &aasworld.areas[area2num];

    //if the areas are not near anough
    for (i = 0; i < 3; i++)
    {
        if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
        if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
    } //end for
    //find a shared face and create a reachability link
    for (i = 0; i < area1->numfaces; i++)
    {
        face1num = aasworld.faceindex[area1->firstface + i];
        side1 = face1num < 0;
        face1num = abs(face1num);
        //
        for (j = 0; j < area2->numfaces; j++)
        {
            face2num = abs(aasworld.faceindex[area2->firstface + j]);
            //
            if (face1num == face2num)
            {
                AAS_FaceCenter(face1num, start);
                //
                if (AAS_PointContents(start) & (CONTENTS_LAVA|CONTENTS_SLIME|CONTENTS_WATER))
                {
                    //
                    face1 = &aasworld.faces[face1num];
                    areasettings = &aasworld.areasettings[area1num];
                    //create a new reachability link
                    lreach = AAS_AllocReachability();
                    if (!lreach) return qfalse;
                    lreach->areanum = area2num;
                    lreach->facenum = face1num;
                    lreach->edgenum = 0;
                    VectorCopy(start, lreach->start);
                    plane = &aasworld.planes[face1->planenum ^ side1];
                    VectorMA(lreach->start, -INSIDEUNITS, plane->normal, lreach->end);
                    lreach->traveltype = TRAVEL_SWIM;
                    lreach->traveltime = 1;
                    //if the volume of the area is rather small
                    if (AAS_AreaVolume(area2num) < 800)
                        lreach->traveltime += 200;
                    //if (!(AAS_PointContents(start) & MASK_WATER)) lreach->traveltime += 500;
                    //link the reachability
                    lreach->next = areareachability[area1num];
                    areareachability[area1num] = lreach;
                    reach_swim++;
                    return qtrue;
                } //end if
            } //end if
        } //end for
    } //end for
    return qfalse;
} //end of the function AAS_Reachability_Swim
//===========================================================================
// searches for reachabilities between adjacent areas with equal floor
// heights
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_Reachability_EqualFloorHeight(int area1num, int area2num)
{
    int i, j, edgenum, edgenum1, edgenum2, foundreach, side;
    float height, bestheight, length, bestlength;
    vec3_t dir, start, end, normal, invgravity, gravitydirection = {0, 0, -1};
    vec3_t edgevec;
    aas_area_t *area1, *area2;
    aas_face_t *face1, *face2;
    aas_edge_t *edge;
    aas_plane_t *plane2;
    aas_lreachability_t lr, *lreach;

    if (!AAS_AreaGrounded(area1num) || !AAS_AreaGrounded(area2num)) return qfalse;

    area1 = &aasworld.areas[area1num];
    area2 = &aasworld.areas[area2num];
    //if the areas are not near anough in the x-y direction
    for (i = 0; i < 2; i++)
    {
        if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
        if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
    } //end for
    //if area 2 is too high above area 1
    if (area2->mins[2] > area1->maxs[2]) return qfalse;
    //
    VectorCopy(gravitydirection, invgravity);
    VectorInverse(invgravity);
    //
    bestheight = 99999;
    bestlength = 0;
    foundreach = qfalse;
    Com_Memset(&lr, 0, sizeof(aas_lreachability_t)); //make the compiler happy
    //
    //check if the areas have ground faces with a common edge
    //if existing use the lowest common edge for a reachability link
    for (i = 0; i < area1->numfaces; i++)
    {
        face1 = &aasworld.faces[abs(aasworld.faceindex[area1->firstface + i])];
        if (!(face1->faceflags & FACE_GROUND)) continue;
        //
        for (j = 0; j < area2->numfaces; j++)
        {
            face2 = &aasworld.faces[abs(aasworld.faceindex[area2->firstface + j])];
            if (!(face2->faceflags & FACE_GROUND)) continue;
            //if there is a common edge
            for (edgenum1 = 0; edgenum1 < face1->numedges; edgenum1++)
            {
                for (edgenum2 = 0; edgenum2 < face2->numedges; edgenum2++)
                {
                    if (abs(aasworld.edgeindex[face1->firstedge + edgenum1]) !=
                            abs(aasworld.edgeindex[face2->firstedge + edgenum2]))
                                    continue;
                    edgenum = aasworld.edgeindex[face1->firstedge + edgenum1];
                    side = edgenum < 0;
                    edge = &aasworld.edges[abs(edgenum)];
                    //get the length of the edge
                    VectorSubtract(aasworld.vertexes[edge->v[1]],
                                aasworld.vertexes[edge->v[0]], dir);
                    length = VectorLength(dir);
                    //get the start point
                    VectorAdd(aasworld.vertexes[edge->v[0]],
                                aasworld.vertexes[edge->v[1]], start);
                    VectorScale(start, 0.5, start);
                    VectorCopy(start, end);
                    //get the end point several units inside area2
                    //and the start point several units inside area1
                    //NOTE: normal is pointing into area2 because the
                    //face edges are stored counter clockwise
                    VectorSubtract(aasworld.vertexes[edge->v[side]],
                                aasworld.vertexes[edge->v[!side]], edgevec);
                    plane2 = &aasworld.planes[face2->planenum];
                    CrossProduct(edgevec, plane2->normal, normal);
                    VectorNormalize(normal);
                    //
                    //VectorMA(start, -1, normal, start);
                    VectorMA(end, INSIDEUNITS_WALKEND, normal, end);
                    VectorMA(start, INSIDEUNITS_WALKSTART, normal, start);
                    end[2] += 0.125;
                    //
                    height = DotProduct(invgravity, start);
                    //NOTE: if there's nearby solid or a gap area after this area
                    //disabled this crap
                    //if (AAS_NearbySolidOrGap(start, end)) height += 200;
                    //NOTE: disabled because it disables reachabilities to very small areas
                    //if (AAS_PointAreaNum(end) != area2num) continue;
                    //get the longest lowest edge
                    if (height < bestheight ||
                            (height < bestheight + 1 && length > bestlength))
                    {
                        bestheight = height;
                        bestlength = length;
                        //create a new reachability link
                        lr.areanum = area2num;
                        lr.facenum = 0;
                        lr.edgenum = edgenum;
                        VectorCopy(start, lr.start);
                        VectorCopy(end, lr.end);
                        lr.traveltype = TRAVEL_WALK;
                        lr.traveltime = 1;
                        foundreach = qtrue;
                    } //end if
                } //end for
            } //end for
        } //end for
    } //end for
    if (foundreach)
    {
        //create a new reachability link
        lreach = AAS_AllocReachability();
        if (!lreach) return qfalse;
        lreach->areanum = lr.areanum;
        lreach->facenum = lr.facenum;
        lreach->edgenum = lr.edgenum;
        VectorCopy(lr.start, lreach->start);
        VectorCopy(lr.end, lreach->end);
        lreach->traveltype = lr.traveltype;
        lreach->traveltime = lr.traveltime;
        lreach->next = areareachability[area1num];
        areareachability[area1num] = lreach;
        //if going into a crouch area
        if (!AAS_AreaCrouch(area1num) && AAS_AreaCrouch(area2num))
        {
            lreach->traveltime += aassettings.rs_startcrouch;
        } //end if
        /*
        //NOTE: if there's nearby solid or a gap area after this area
        if (!AAS_NearbySolidOrGap(lreach->start, lreach->end))
        {
            lreach->traveltime += 100;
        } //end if
        */
        //avoid rather small areas
        //if (AAS_AreaGroundFaceArea(lreach->areanum) < 500) lreach->traveltime += 100;
        //
        reach_equalfloor++;
        return qtrue;
    } //end if
    return qfalse;
} //end of the function AAS_Reachability_EqualFloorHeight
//===========================================================================
// searches step, barrier, waterjump and walk off ledge reachabilities
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_Reachability_Step_Barrier_WaterJump_WalkOffLedge(int area1num, int area2num)
{
    int i, j, k, l, edge1num, edge2num, areas[10], numareas;
    int ground_bestarea2groundedgenum, ground_foundreach;
    int water_bestarea2groundedgenum, water_foundreach;
    int side1, area1swim, faceside1, groundface1num;
    float dist, dist1, dist2, diff, invgravitydot, ortdot;
    float x1, x2, x3, x4, y1, y2, y3, y4, tmp, y;
    float length, ground_bestlength, water_bestlength, ground_bestdist, water_bestdist;
    vec3_t v1, v2, v3, v4, tmpv, p1area1, p1area2, p2area1, p2area2;
    vec3_t normal, ort, edgevec, start, end, dir;
    vec3_t ground_beststart, ground_bestend, ground_bestnormal;
    vec3_t water_beststart, water_bestend, water_bestnormal;
    vec3_t invgravity = {0, 0, 1};
    vec3_t testpoint;
    aas_plane_t *plane;
    aas_area_t *area1, *area2;
    aas_face_t *groundface1, *groundface2, *ground_bestface1, *water_bestface1;
    aas_edge_t *edge1, *edge2;
    aas_lreachability_t *lreach;
    aas_trace_t trace;

    //must be able to walk or swim in the first area
    if (!AAS_AreaGrounded(area1num) && !AAS_AreaSwim(area1num)) return qfalse;
    //
    if (!AAS_AreaGrounded(area2num) && !AAS_AreaSwim(area2num)) return qfalse;
    //
    area1 = &aasworld.areas[area1num];
    area2 = &aasworld.areas[area2num];
    //if the first area contains a liquid
    area1swim = AAS_AreaSwim(area1num);
    //if the areas are not near anough in the x-y direction
    for (i = 0; i < 2; i++)
    {
        if (area1->mins[i] > area2->maxs[i] + 10) return qfalse;
        if (area1->maxs[i] < area2->mins[i] - 10) return qfalse;
    } //end for
    //
    ground_foundreach = qfalse;
    ground_bestdist = 99999;
    ground_bestlength = 0;
    ground_bestarea2groundedgenum = 0;
    //
    water_foundreach = qfalse;
    water_bestdist = 99999;
    water_bestlength = 0;
    water_bestarea2groundedgenum = 0;
    //
    for (i = 0; i < area1->numfaces; i++)
    {
        groundface1num = aasworld.faceindex[area1->firstface + i];
        faceside1 = groundface1num < 0;
        groundface1 = &aasworld.faces[abs(groundface1num)];
        //if this isn't a ground face
        if (!(groundface1->faceflags & FACE_GROUND))
        {
            //if we can swim in the first area
            if (area1swim)
            {
                //face plane must be more or less horizontal
                plane = &aasworld.planes[groundface1->planenum ^ (!faceside1)];
                if (DotProduct(plane->normal, invgravity) < 0.7) continue;
            } //end if
            else
            {
                //if we can't swim in the area it must be a ground face
                continue;
            } //end else
        } //end if
        //
        for (k = 0; k < groundface1->numedges; k++)
        {
            edge1num = aasworld.edgeindex[groundface1->firstedge + k];
            side1 = (edge1num < 0);
            //NOTE: for water faces we must take the side area 1 is
            // on into account because the face is shared and doesn't
            // have to be oriented correctly
            if (!(groundface1->faceflags & FACE_GROUND)) side1 = (side1 == faceside1);
            edge1num = abs(edge1num);
            edge1 = &aasworld.edges[edge1num];
            //vertexes of the edge
            VectorCopy(aasworld.vertexes[edge1->v[!side1]], v1);
            VectorCopy(aasworld.vertexes[edge1->v[side1]], v2);
            //get a vertical plane through the edge
            //NOTE: normal is pointing into area 2 because the
            //face edges are stored counter clockwise
            VectorSubtract(v2, v1, edgevec);
            CrossProduct(edgevec, invgravity, normal);
            VectorNormalize(normal);
            dist = DotProduct(normal, v1);
            //check the faces from the second area
            for (j = 0; j < area2->numfaces; j++)
            {
                groundface2 = &aasworld.faces[abs(aasworld.faceindex[area2->firstface + j])];
                //must be a ground face
                if (!(groundface2->faceflags & FACE_GROUND)) continue;
                //check the edges of this ground face
                for (l = 0; l < groundface2->numedges; l++)
                {
                    edge2num = abs(aasworld.edgeindex[groundface2->firstedge + l]);
                    edge2 = &aasworld.edges[edge2num];
                    //vertexes of the edge
                    VectorCopy(aasworld.vertexes[edge2->v[0]], v3);
                    VectorCopy(aasworld.vertexes[edge2->v[1]], v4);
                    //check the distance between the two points and the vertical plane
                    //through the edge of area1
                    diff = DotProduct(normal, v3) - dist;
                    if (diff < -0.1 || diff > 0.1) continue;
                    diff = DotProduct(normal, v4) - dist;
                    if (diff < -0.1 || diff > 0.1) continue;
                    //
                    //project the two ground edges into the step side plane
                    //and calculate the shortest distance between the two
                    //edges if they overlap in the direction orthogonal to
                    //the gravity direction
                    CrossProduct(invgravity, normal, ort);
                    invgravitydot = DotProduct(invgravity, invgravity);
                    ortdot = DotProduct(ort, ort);
                    //projection into the step plane
                    //NOTE: since gravity is vertical this is just the z coordinate
                    y1 = v1[2];//DotProduct(v1, invgravity) / invgravitydot;
                    y2 = v2[2];//DotProduct(v2, invgravity) / invgravitydot;
                    y3 = v3[2];//DotProduct(v3, invgravity) / invgravitydot;
                    y4 = v4[2];//DotProduct(v4, invgravity) / invgravitydot;
                    //
                    x1 = DotProduct(v1, ort)