be_ai_move.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_ai_move.c
 *
 * desc:        bot movement AI
 *
 * $Archive: /MissionPack/code/botlib/be_ai_move.c $
 *
 *****************************************************************************/

#include "../game/q_shared.h"
#include "l_memory.h"
#include "l_libvar.h"
#include "l_utils.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 "../game/be_ea.h"
#include "../game/be_ai_goal.h"
#include "../game/be_ai_move.h"


//#define DEBUG_AI_MOVE
//#define DEBUG_ELEVATOR
//#define DEBUG_GRAPPLE

// bk001204 - redundant bot_avoidspot_t, see ../game/be_ai_move.h

//movement state
//NOTE: the moveflags MFL_ONGROUND, MFL_TELEPORTED, MFL_WATERJUMP and
//      MFL_GRAPPLEPULL must be set outside the movement code
typedef struct bot_movestate_s
{
    //input vars (all set outside the movement code)
    vec3_t origin;                              //origin of the bot
    vec3_t velocity;                            //velocity of the bot
    vec3_t viewoffset;                          //view offset
    int entitynum;                              //entity number of the bot
    int client;                                 //client number of the bot
    float thinktime;                            //time the bot thinks
    int presencetype;                           //presencetype of the bot
    vec3_t viewangles;                          //view angles of the bot
    //state vars
    int areanum;                                //area the bot is in
    int lastareanum;                            //last area the bot was in
    int lastgoalareanum;                        //last goal area number
    int lastreachnum;                           //last reachability number
    vec3_t lastorigin;                          //origin previous cycle
    int reachareanum;                           //area number of the reachabilty
    int moveflags;                              //movement flags
    int jumpreach;                              //set when jumped
    float grapplevisible_time;                  //last time the grapple was visible
    float lastgrappledist;                      //last distance to the grapple end
    float reachability_time;                    //time to use current reachability
    int avoidreach[MAX_AVOIDREACH];             //reachabilities to avoid
    float avoidreachtimes[MAX_AVOIDREACH];      //times to avoid the reachabilities
    int avoidreachtries[MAX_AVOIDREACH];        //number of tries before avoiding
    //
    bot_avoidspot_t avoidspots[MAX_AVOIDSPOTS]; //spots to avoid
    int numavoidspots;
} bot_movestate_t;

//used to avoid reachability links for some time after being used
#define AVOIDREACH
#define AVOIDREACH_TIME         6       //avoid links for 6 seconds after use
#define AVOIDREACH_TRIES        4
//prediction times
#define PREDICTIONTIME_JUMP 3       //in seconds
#define PREDICTIONTIME_MOVE 2       //in seconds
//weapon indexes for weapon jumping
#define WEAPONINDEX_ROCKET_LAUNCHER     5
#define WEAPONINDEX_BFG                 9

#define MODELTYPE_FUNC_PLAT     1
#define MODELTYPE_FUNC_BOB      2
#define MODELTYPE_FUNC_DOOR     3
#define MODELTYPE_FUNC_STATIC   4

libvar_t *sv_maxstep;
libvar_t *sv_maxbarrier;
libvar_t *sv_gravity;
libvar_t *weapindex_rocketlauncher;
libvar_t *weapindex_bfg10k;
libvar_t *weapindex_grapple;
libvar_t *entitytypemissile;
libvar_t *offhandgrapple;
libvar_t *cmd_grappleoff;
libvar_t *cmd_grappleon;
//type of model, func_plat or func_bobbing
int modeltypes[MAX_MODELS];

bot_movestate_t *botmovestates[MAX_CLIENTS+1];

//========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//========================================================================
int BotAllocMoveState(void)
{
    int i;

    for (i = 1; i <= MAX_CLIENTS; i++)
    {
        if (!botmovestates[i])
        {
            botmovestates[i] = GetClearedMemory(sizeof(bot_movestate_t));
            return i;
        } //end if
    } //end for
    return 0;
} //end of the function BotAllocMoveState
//========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//========================================================================
void BotFreeMoveState(int handle)
{
    if (handle <= 0 || handle > MAX_CLIENTS)
    {
        botimport.Print(PRT_FATAL, "move state handle %d out of range\n", handle);
        return;
    } //end if
    if (!botmovestates[handle])
    {
        botimport.Print(PRT_FATAL, "invalid move state %d\n", handle);
        return;
    } //end if
    FreeMemory(botmovestates[handle]);
    botmovestates[handle] = NULL;
} //end of the function BotFreeMoveState
//========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//========================================================================
bot_movestate_t *BotMoveStateFromHandle(int handle)
{
    if (handle <= 0 || handle > MAX_CLIENTS)
    {
        botimport.Print(PRT_FATAL, "move state handle %d out of range\n", handle);
        return NULL;
    } //end if
    if (!botmovestates[handle])
    {
        botimport.Print(PRT_FATAL, "invalid move state %d\n", handle);
        return NULL;
    } //end if
    return botmovestates[handle];
} //end of the function BotMoveStateFromHandle
//========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//========================================================================
void BotInitMoveState(int handle, bot_initmove_t *initmove)
{
    bot_movestate_t *ms;

    ms = BotMoveStateFromHandle(handle);
    if (!ms) return;
    VectorCopy(initmove->origin, ms->origin);
    VectorCopy(initmove->velocity, ms->velocity);
    VectorCopy(initmove->viewoffset, ms->viewoffset);
    ms->entitynum = initmove->entitynum;
    ms->client = initmove->client;
    ms->thinktime = initmove->thinktime;
    ms->presencetype = initmove->presencetype;
    VectorCopy(initmove->viewangles, ms->viewangles);
    //
    ms->moveflags &= ~MFL_ONGROUND;
    if (initmove->or_moveflags & MFL_ONGROUND) ms->moveflags |= MFL_ONGROUND;
    ms->moveflags &= ~MFL_TELEPORTED;   
    if (initmove->or_moveflags & MFL_TELEPORTED) ms->moveflags |= MFL_TELEPORTED;
    ms->moveflags &= ~MFL_WATERJUMP;
    if (initmove->or_moveflags & MFL_WATERJUMP) ms->moveflags |= MFL_WATERJUMP;
    ms->moveflags &= ~MFL_WALK;
    if (initmove->or_moveflags & MFL_WALK) ms->moveflags |= MFL_WALK;
    ms->moveflags &= ~MFL_GRAPPLEPULL;
    if (initmove->or_moveflags & MFL_GRAPPLEPULL) ms->moveflags |= MFL_GRAPPLEPULL;
} //end of the function BotInitMoveState
//========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//========================================================================
float AngleDiff(float ang1, float ang2)
{
    float diff;

    diff = ang1 - ang2;
    if (ang1 > ang2)
    {
        if (diff > 180.0) diff -= 360.0;
    } //end if
    else
    {
        if (diff < -180.0) diff += 360.0;
    } //end else
    return diff;
} //end of the function AngleDiff
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotFuzzyPointReachabilityArea(vec3_t origin)
{
    int firstareanum, j, x, y, z;
    int areas[10], numareas, areanum, bestareanum;
    float dist, bestdist;
    vec3_t points[10], v, end;

    firstareanum = 0;
    areanum = AAS_PointAreaNum(origin);
    if (areanum)
    {
        firstareanum = areanum;
        if (AAS_AreaReachability(areanum)) return areanum;
    } //end if
    VectorCopy(origin, end);
    end[2] += 4;
    numareas = AAS_TraceAreas(origin, end, areas, points, 10);
    for (j = 0; j < numareas; j++)
    {
        if (AAS_AreaReachability(areas[j])) return areas[j];
    } //end for
    bestdist = 999999;
    bestareanum = 0;
    for (z = 1; z >= -1; z -= 1)
    {
        for (x = 1; x >= -1; x -= 1)
        {
            for (y = 1; y >= -1; y -= 1)
            {
                VectorCopy(origin, end);
                end[0] += x * 8;
                end[1] += y * 8;
                end[2] += z * 12;
                numareas = AAS_TraceAreas(origin, end, areas, points, 10);
                for (j = 0; j < numareas; j++)
                {
                    if (AAS_AreaReachability(areas[j]))
                    {
                        VectorSubtract(points[j], origin, v);
                        dist = VectorLength(v);
                        if (dist < bestdist)
                        {
                            bestareanum = areas[j];
                            bestdist = dist;
                        } //end if
                    } //end if
                    if (!firstareanum) firstareanum = areas[j];
                } //end for
            } //end for
        } //end for
        if (bestareanum) return bestareanum;
    } //end for
    return firstareanum;
} //end of the function BotFuzzyPointReachabilityArea
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotReachabilityArea(vec3_t origin, int client)
{
    int modelnum, modeltype, reachnum, areanum;
    aas_reachability_t reach;
    vec3_t org, end, mins, maxs, up = {0, 0, 1};
    bsp_trace_t bsptrace;
    aas_trace_t trace;

    //check if the bot is standing on something
    AAS_PresenceTypeBoundingBox(PRESENCE_CROUCH, mins, maxs);
    VectorMA(origin, -3, up, end);
    bsptrace = AAS_Trace(origin, mins, maxs, end, client, CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
    if (!bsptrace.startsolid && bsptrace.fraction < 1 && bsptrace.ent != ENTITYNUM_NONE)
    {
        //if standing on the world the bot should be in a valid area
        if (bsptrace.ent == ENTITYNUM_WORLD)
        {
            return BotFuzzyPointReachabilityArea(origin);
        } //end if

        modelnum = AAS_EntityModelindex(bsptrace.ent);
        modeltype = modeltypes[modelnum];

        //if standing on a func_plat or func_bobbing then the bot is assumed to be
        //in the area the reachability points to
        if (modeltype == MODELTYPE_FUNC_PLAT || modeltype == MODELTYPE_FUNC_BOB)
        {
            reachnum = AAS_NextModelReachability(0, modelnum);
            if (reachnum)
            {
                AAS_ReachabilityFromNum(reachnum, &reach);
                return reach.areanum;
            } //end if
        } //end else if

        //if the bot is swimming the bot should be in a valid area
        if (AAS_Swimming(origin))
        {
            return BotFuzzyPointReachabilityArea(origin);
        } //end if
        //
        areanum = BotFuzzyPointReachabilityArea(origin);
        //if the bot is in an area with reachabilities
        if (areanum && AAS_AreaReachability(areanum)) return areanum;
        //trace down till the ground is hit because the bot is standing on some other entity
        VectorCopy(origin, org);
        VectorCopy(org, end);
        end[2] -= 800;
        trace = AAS_TraceClientBBox(org, end, PRESENCE_CROUCH, -1);
        if (!trace.startsolid)
        {
            VectorCopy(trace.endpos, org);
        } //end if
        //
        return BotFuzzyPointReachabilityArea(org);
    } //end if
    //
    return BotFuzzyPointReachabilityArea(origin);
} //end of the function BotReachabilityArea
//===========================================================================
// returns the reachability area the bot is in
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
/*
int BotReachabilityArea(vec3_t origin, int testground)
{
    int firstareanum, i, j, x, y, z;
    int areas[10], numareas, areanum, bestareanum;
    float dist, bestdist;
    vec3_t org, end, points[10], v;
    aas_trace_t trace;

    firstareanum = 0;
    for (i = 0; i < 2; i++)
    {
        VectorCopy(origin, org);
        //if test at the ground (used when bot is standing on an entity)
        if (i > 0)
        {
            VectorCopy(origin, end);
            end[2] -= 800;
            trace = AAS_TraceClientBBox(origin, end, PRESENCE_CROUCH, -1);
            if (!trace.startsolid)
            {
                VectorCopy(trace.endpos, org);
            } //end if
        } //end if

        firstareanum = 0;
        areanum = AAS_PointAreaNum(org);
        if (areanum)
        {
            firstareanum = areanum;
            if (AAS_AreaReachability(areanum)) return areanum;
        } //end if
        bestdist = 999999;
        bestareanum = 0;
        for (z = 1; z >= -1; z -= 1)
        {
            for (x = 1; x >= -1; x -= 1)
            {
                for (y = 1; y >= -1; y -= 1)
                {
                    VectorCopy(org, end);
                    end[0] += x * 8;
                    end[1] += y * 8;
                    end[2] += z * 12;
                    numareas = AAS_TraceAreas(org, end, areas, points, 10);
                    for (j = 0; j < numareas; j++)
                    {
                        if (AAS_AreaReachability(areas[j]))
                        {
                            VectorSubtract(points[j], org, v);
                            dist = VectorLength(v);
                            if (dist < bestdist)
                            {
                                bestareanum = areas[j];
                                bestdist = dist;
                            } //end if
                        } //end if
                    } //end for
                } //end for
            } //end for
            if (bestareanum) return bestareanum;
        } //end for
        if (!testground) break;
    } //end for
//#ifdef DEBUG
    //botimport.Print(PRT_MESSAGE, "no reachability area\n");
//#endif //DEBUG
    return firstareanum;
} //end of the function BotReachabilityArea*/
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotOnMover(vec3_t origin, int entnum, aas_reachability_t *reach)
{
    int i, modelnum;
    vec3_t mins, maxs, modelorigin, org, end;
    vec3_t angles = {0, 0, 0};
    vec3_t boxmins = {-16, -16, -8}, boxmaxs = {16, 16, 8};
    bsp_trace_t trace;

    modelnum = reach->facenum & 0x0000FFFF;
    //get some bsp model info
    AAS_BSPModelMinsMaxsOrigin(modelnum, angles, mins, maxs, NULL);
    //
    if (!AAS_OriginOfMoverWithModelNum(modelnum, modelorigin))
    {
        botimport.Print(PRT_MESSAGE, "no entity with model %d\n", modelnum);
        return qfalse;
    } //end if
    //
    for (i = 0; i < 2; i++)
    {
        if (origin[i] > modelorigin[i] + maxs[i] + 16) return qfalse;
        if (origin[i] < modelorigin[i] + mins[i] - 16) return qfalse;
    } //end for
    //
    VectorCopy(origin, org);
    org[2] += 24;
    VectorCopy(origin, end);
    end[2] -= 48;
    //
    trace = AAS_Trace(org, boxmins, boxmaxs, end, entnum, CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
    if (!trace.startsolid && !trace.allsolid)
    {
        //NOTE: the reachability face number is the model number of the elevator
        if (trace.ent != ENTITYNUM_NONE && AAS_EntityModelNum(trace.ent) == modelnum)
        {
            return qtrue;
        } //end if
    } //end if
    return qfalse;
} //end of the function BotOnMover
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int MoverDown(aas_reachability_t *reach)
{
    int modelnum;
    vec3_t mins, maxs, origin;
    vec3_t angles = {0, 0, 0};

    modelnum = reach->facenum & 0x0000FFFF;
    //get some bsp model info
    AAS_BSPModelMinsMaxsOrigin(modelnum, angles, mins, maxs, origin);
    //
    if (!AAS_OriginOfMoverWithModelNum(modelnum, origin))
    {
        botimport.Print(PRT_MESSAGE, "no entity with model %d\n", modelnum);
        return qfalse;
    } //end if
    //if the top of the plat is below the reachability start point
    if (origin[2] + maxs[2] < reach->start[2]) return qtrue;
    return qfalse;
} //end of the function MoverDown
//========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//========================================================================
void BotSetBrushModelTypes(void)
{
    int ent, modelnum;
    char classname[MAX_EPAIRKEY], model[MAX_EPAIRKEY];

    Com_Memset(modeltypes, 0, MAX_MODELS * sizeof(int));
    //
    for (ent = AAS_NextBSPEntity(0); ent; ent = AAS_NextBSPEntity(ent))
    {
        if (!AAS_ValueForBSPEpairKey(ent, "classname", classname, MAX_EPAIRKEY)) continue;
        if (!AAS_ValueForBSPEpairKey(ent, "model", model, MAX_EPAIRKEY)) continue;
        if (model[0]) modelnum = atoi(model+1);
        else modelnum = 0;

        if (modelnum < 0 || modelnum > MAX_MODELS)
        {
            botimport.Print(PRT_MESSAGE, "entity %s model number out of range\n", classname);
            continue;
        } //end if

        if (!Q_stricmp(classname, "func_bobbing"))
            modeltypes[modelnum] = MODELTYPE_FUNC_BOB;
        else if (!Q_stricmp(classname, "func_plat"))
            modeltypes[modelnum] = MODELTYPE_FUNC_PLAT;
        else if (!Q_stricmp(classname, "func_door"))
            modeltypes[modelnum] = MODELTYPE_FUNC_DOOR;
        else if (!Q_stricmp(classname, "func_static"))
            modeltypes[modelnum] = MODELTYPE_FUNC_STATIC;
    } //end for
} //end of the function BotSetBrushModelTypes
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotOnTopOfEntity(bot_movestate_t *ms)
{
    vec3_t mins, maxs, end, up = {0, 0, 1};
    bsp_trace_t trace;

    AAS_PresenceTypeBoundingBox(ms->presencetype, mins, maxs);
    VectorMA(ms->origin, -3, up, end);
    trace = AAS_Trace(ms->origin, mins, maxs, end, ms->entitynum, CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
    if (!trace.startsolid && (trace.ent != ENTITYNUM_WORLD && trace.ent != ENTITYNUM_NONE) )
    {
        return trace.ent;
    } //end if
    return -1;
} //end of the function BotOnTopOfEntity
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotValidTravel(vec3_t origin, aas_reachability_t *reach, int travelflags)
{
    //if the reachability uses an unwanted travel type
    if (AAS_TravelFlagForType(reach->traveltype) & ~travelflags) return qfalse;
    //don't go into areas with bad travel types
    if (AAS_AreaContentsTravelFlags(reach->areanum) & ~travelflags) return qfalse;
    return qtrue;
} //end of the function BotValidTravel
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void BotAddToAvoidReach(bot_movestate_t *ms, int number, float avoidtime)
{
    int i;

    for (i = 0; i < MAX_AVOIDREACH; i++)
    {
        if (ms->avoidreach[i] == number)
        {
            if (ms->avoidreachtimes[i] > AAS_Time()) ms->avoidreachtries[i]++;
            else ms->avoidreachtries[i] = 1;
            ms->avoidreachtimes[i] = AAS_Time() + avoidtime;
            return;
        } //end if
    } //end for
    //add the reachability to the reachabilities to avoid for a while
    for (i = 0; i < MAX_AVOIDREACH; i++)
    {
        if (ms->avoidreachtimes[i] < AAS_Time())
        {
            ms->avoidreach[i] = number;
            ms->avoidreachtimes[i] = AAS_Time() + avoidtime;
            ms->avoidreachtries[i] = 1;
            return;
        } //end if
    } //end for
} //end of the function BotAddToAvoidReach
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
float DistanceFromLineSquared(vec3_t p, vec3_t lp1, vec3_t lp2)
{
    vec3_t proj, dir;
    int j;

    AAS_ProjectPointOntoVector(p, lp1, lp2, proj);
    for (j = 0; j < 3; j++)
        if ((proj[j] > lp1[j] && proj[j] > lp2[j]) ||
            (proj[j] < lp1[j] && proj[j] < lp2[j]))
            break;
    if (j < 3) {
        if (fabs(proj[j] - lp1[j]) < fabs(proj[j] - lp2[j]))
            VectorSubtract(p, lp1, dir);
        else
            VectorSubtract(p, lp2, dir);
        return VectorLengthSquared(dir);
    }
    VectorSubtract(p, proj, dir);
    return VectorLengthSquared(dir);
} //end of the function DistanceFromLineSquared
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
float VectorDistanceSquared(vec3_t p1, vec3_t p2)
{
    vec3_t dir;
    VectorSubtract(p2, p1, dir);
    return VectorLengthSquared(dir);
} //end of the function VectorDistanceSquared
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotAvoidSpots(vec3_t origin, aas_reachability_t *reach, bot_avoidspot_t *avoidspots, int numavoidspots)
{
    int checkbetween, i, type;
    float squareddist, squaredradius;

    switch(reach->traveltype & TRAVELTYPE_MASK)
    {
        case TRAVEL_WALK: checkbetween = qtrue; break;
        case TRAVEL_CROUCH: checkbetween = qtrue; break;
        case TRAVEL_BARRIERJUMP: checkbetween = qtrue; break;
        case TRAVEL_LADDER: checkbetween = qtrue; break;
        case TRAVEL_WALKOFFLEDGE: checkbetween = qfalse; break;
        case TRAVEL_JUMP: checkbetween = qfalse; break;
        case TRAVEL_SWIM: checkbetween = qtrue; break;
        case TRAVEL_WATERJUMP: checkbetween = qtrue; break;
        case TRAVEL_TELEPORT: checkbetween = qfalse; break;
        case TRAVEL_ELEVATOR: checkbetween = qfalse; break;
        case TRAVEL_GRAPPLEHOOK: checkbetween = qfalse; break;
        case TRAVEL_ROCKETJUMP: checkbetween = qfalse; break;
        case TRAVEL_BFGJUMP: checkbetween = qfalse; break;
        case TRAVEL_JUMPPAD: checkbetween = qfalse; break;
        case TRAVEL_FUNCBOB: checkbetween = qfalse; break;
        default: checkbetween = qtrue; break;
    } //end switch

    type = AVOID_CLEAR;
    for (i = 0; i < numavoidspots; i++)
    {
        squaredradius = Square(avoidspots[i].radius);
        squareddist = DistanceFromLineSquared(avoidspots[i].origin, origin, reach->start);
        // if moving towards the avoid spot
        if (squareddist < squaredradius &&
            VectorDistanceSquared(avoidspots[i].origin, origin) > squareddist)
        {
            type = avoidspots[i].type;
        } //end if
        else if (checkbetween) {
            squareddist = DistanceFromLineSquared(avoidspots[i].origin, reach->start, reach->end);
            // if moving towards the avoid spot
            if (squareddist < squaredradius &&
                VectorDistanceSquared(avoidspots[i].origin, reach->start) > squareddist)
            {
                type = avoidspots[i].type;
            } //end if
        } //end if
        else
        {
            VectorDistanceSquared(avoidspots[i].origin, reach->end);
            // if the reachability leads closer to the avoid spot
            if (squareddist < squaredradius && 
                VectorDistanceSquared(avoidspots[i].origin, reach->start) > squareddist)
            {
                type = avoidspots[i].type;
            } //end if
        } //end else
        if (type == AVOID_ALWAYS)
            return type;
    } //end for
    return type;
} //end of the function BotAvoidSpots
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void BotAddAvoidSpot(int movestate, vec3_t origin, float radius, int type)
{
    bot_movestate_t *ms;

    ms = BotMoveStateFromHandle(movestate);
    if (!ms) return;
    if (type == AVOID_CLEAR)
    {
        ms->numavoidspots = 0;
        return;
    } //end if

    if (ms->numavoidspots >= MAX_AVOIDSPOTS)
        return;
    VectorCopy(origin, ms->avoidspots[ms->numavoidspots].origin);
    ms->avoidspots[ms->numavoidspots].radius = radius;
    ms->avoidspots[ms->numavoidspots].type = type;
    ms->numavoidspots++;
} //end of the function BotAddAvoidSpot
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotGetReachabilityToGoal(vec3_t origin, int areanum,
                                      int lastgoalareanum, int lastareanum,
                                      int *avoidreach, float *avoidreachtimes, int *avoidreachtries,
                                      bot_goal_t *goal, int travelflags, int movetravelflags,
                                      struct bot_avoidspot_s *avoidspots, int numavoidspots, int *flags)
{
    int i, t, besttime, bestreachnum, reachnum;
    aas_reachability_t reach;

    //if not in a valid area
    if (!areanum) return 0;
    //
    if (AAS_AreaDoNotEnter(areanum) || AAS_AreaDoNotEnter(goal->areanum))
    {
        travelflags |= TFL_DONOTENTER;
        movetravelflags |= TFL_DONOTENTER;
    } //end if
    //use the routing to find the next area to go to
    besttime = 0;
    bestreachnum = 0;
    //
    for (reachnum = AAS_NextAreaReachability(areanum, 0); reachnum;
        reachnum = AAS_NextAreaReachability(areanum, reachnum))
    {
#ifdef AVOIDREACH
        //check if it isn't an reachability to avoid
        for (i = 0; i < MAX_AVOIDREACH; i++)
        {
            if (avoidreach[i] == reachnum && avoidreachtimes[i] >= AAS_Time()) break;
        } //end for
        if (i != MAX_AVOIDREACH && avoidreachtries[i] > AVOIDREACH_TRIES)
        {
#ifdef DEBUG
            if (bot_developer)
            {
                botimport.Print(PRT_MESSAGE, "avoiding reachability %d\n", avoidreach[i]);
            } //end if
#endif //DEBUG
            continue;
        } //end if
#endif //AVOIDREACH
        //get the reachability from the number
        AAS_ReachabilityFromNum(reachnum, &reach);
        //NOTE: do not go back to the previous area if the goal didn't change
        //NOTE: is this actually avoidance of local routing minima between two areas???
        if (lastgoalareanum == goal->areanum && reach.areanum == lastareanum) continue;
        //if (AAS_AreaContentsTravelFlags(reach.areanum) & ~travelflags) continue;
        //if the travel isn't valid
        if (!BotValidTravel(origin, &reach, movetravelflags)) continue;
        //get the travel time
        t = AAS_AreaTravelTimeToGoalArea(reach.areanum, reach.end, goal->areanum, travelflags);
        //if the goal area isn't reachable from the reachable area
        if (!t) continue;
        //if the bot should not use this reachability to avoid bad spots
        if (BotAvoidSpots(origin, &reach, avoidspots, numavoidspots)) {
            if (flags) {
                *flags |= MOVERESULT_BLOCKEDBYAVOIDSPOT;
            }
            continue;
        }
        //add the travel time towards the area
        t += reach.traveltime;// + AAS_AreaTravelTime(areanum, origin, reach.start);
        //if the travel time is better than the ones already found
        if (!besttime || t < besttime)
        {
            besttime = t;
            bestreachnum = reachnum;
        } //end if
    } //end for
    //
    return bestreachnum;
} //end of the function BotGetReachabilityToGoal
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int BotAddToTarget(vec3_t start, vec3_t end, float maxdist, float *dist, vec3_t target)
{
    vec3_t dir;
    float curdist;

    VectorSubtract(end, start, dir);
    curdist = VectorNormalize(dir);
    if (*dist + curdist < maxdist)
    {
        VectorCopy(end, target);
        *dist += curdist;
        return qfalse;
    } //end if
    else
    {
        VectorMA(start, maxdist - *dist, dir, target);
        *dist = maxdist;
        return qtrue;
    } //end else
} //end of the function BotAddToTarget

int BotMovementViewTarget(int movestate, bot_goal_t *goal, int travelflags, float lookahead, vec3_t target)
{
    aas_reachability_t reach;
    int reachnum, lastareanum;
    bot_movestate_t *ms;
    vec3_t end;
    float dist;

    ms = BotMoveStateFromHandle(movestate);
    if (!ms) return qfalse;
    reachnum = 0;
    //if the bot has no goal or no last reachability
    if (!ms->lastreachnum || !goal) return qfalse;

    reachnum = ms->lastreachnum;
    VectorCopy(ms->origin, end);
    lastareanum = ms->lastareanum;
    dist = 0;
    while(reachnum && dist < lookahead)
    {
        AAS_ReachabilityFromNum(reachnum, &reach);
        if (BotAddToTarget(end, reach.start, lookahead, &dist, target)) return qtrue;
        //never look beyond teleporters
        if ((reach.traveltype & TRAVELTYPE_MASK) == TRAVEL_TELEPORT) return qtrue;
        //never look beyond the weapon jump point
        if ((reach.traveltype & TRAVELTYPE_MASK) == TRAVEL_ROCKETJUMP) return qtrue;
        if ((reach.traveltype & TRAVELTYPE_MASK) == TRAVEL_BFGJUMP) return qtrue;
        //don't add jump pad distances
        if ((reach.traveltype & TRAVELTYPE_MASK) != TRAVEL_JUMPPAD &&
            (reach.traveltype & TRAVELTYPE_MASK) != TRAVEL_ELEVATOR &&
            (reach.traveltype & TRAVELTYPE_MASK) != TRAVEL_FUNCBOB)
        {
            if (BotAddToTarget(reach.start, reach.end, lookahead, &dist, target)) return qtrue;
        } //end if
        reachnum = BotGetReachabilityToGoal(reach.end, reach.areanum,
                        ms->lastgoalareanum, lastareanum,
                            ms->avoidreach, ms->avoidreachtimes, ms->avoidreachtries,
                                    goal, travelflags, travelflags, NULL, 0, NULL);
        VectorCopy(reach.end, end);
        lastareanum = reach.areanum;
        if (lastareanum == goal->areanum)
        {
            BotAddToTarget(reach.end, goal->origin, lookahead, &dist, target);
            return qtrue;
        } //end if
    } //end while
    //
    return qfalse;
} //end of the function BotMovementViewTarget
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotVisible(int ent, vec3_t eye, vec3_t target)
{
    bsp_trace_t trace;

    trace = AAS_Trace(eye, NULL, NULL, target, ent, CONTENTS_SOLID|CONTENTS_PLAYERCLIP);
    if (trace.fraction >= 1) return qtrue;
    return qfalse;
} //end of the function BotVisible
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotPredictVisiblePosition(vec3_t origin, int areanum, bot_goal_t *goal, int travelflags, vec3_t target)
{
    aas_reachability_t reach;
    int reachnum, lastgoalareanum, lastareanum, i;
    int avoidreach[MAX_AVOIDREACH];
    float avoidreachtimes[MAX_AVOIDREACH];
    int avoidreachtries[MAX_AVOIDREACH];
    vec3_t end;

    //if the bot has no goal or no last reachability
    if (!goal) return qfalse;
    //if the areanum is not valid
    if (!areanum) return qfalse;
    //if the goal areanum is not valid
    if (!goal->areanum) return qfalse;

    Com_Memset(avoidreach, 0, MAX_AVOIDREACH * sizeof(int));
    lastgoalareanum = goal->areanum;
    lastareanum = areanum;
    VectorCopy(origin, end);
    //only do 20 hops
    for (i = 0; i < 20 && (areanum != goal->areanum); i++)
    {
        //
        reachnum = BotGetReachabilityToGoal(end, areanum,
                        lastgoalareanum, lastareanum,
                            avoidreach, avoidreachtimes, avoidreachtries,
                                    goal, travelflags, travelflags, NULL, 0, NULL);
        if (!reachnum) return qfalse;
        AAS_ReachabilityFromNum(reachnum, &reach);
        //
        if (BotVisible(goal->entitynum, goal->origin, reach.start))
        {
            VectorCopy(reach.start, target);
            return qtrue;
        } //end if
        //
        if (BotVisible(goal->entitynum, goal->origin, reach.end))
        {
            VectorCopy(reach.end, target);
            return qtrue;
        } //end if
        //
        if (reach.areanum == goal->areanum)
        {
            VectorCopy(reach.end, target);
            return qtrue;
        } //end if
        //
        lastareanum = areanum;
        areanum = reach.areanum;
        VectorCopy(reach.end, end);
        //
    } //end while
    //
    return qfalse;
} //end of the function BotPredictVisiblePosition
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
void MoverBottomCenter(aas_reachability_t *reach, vec3_t bottomcenter)
{
    int modelnum;
    vec3_t mins, maxs, origin, mids;
    vec3_t angles = {0, 0, 0};

    modelnum = reach->facenum & 0x0000FFFF;
    //get some bsp model info
    AAS_BSPModelMinsMaxsOrigin(modelnum, angles, mins, maxs, origin);
    //
    if (!AAS_OriginOfMoverWithModelNum(modelnum, origin))
    {
        botimport.Print(PRT_MESSAGE, "no entity with model %d\n", modelnum);
    } //end if
    //get a point just above the plat in the bottom position
    VectorAdd(mins, maxs, mids);
    VectorMA(origin, 0.5, mids, bottomcenter);
    bottomcenter[2] = reach->start[2];
} //end of the function MoverBottomCenter
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
float BotGapDistance(vec3_t origin, vec3_t hordir, int entnum)
{
    float dist, startz;
    vec3_t start, end;
    aas_trace_t trace;

    //do gap checking
    startz = origin[2];
    //this enables walking down stairs more fluidly
    {
        VectorCopy(origin, start);
        VectorCopy(origin, end);
        end[2] -= 60;
        trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, entnum);
        if (trace.fraction >= 1) return 1;
        startz = trace.endpos[2] + 1;
    }
    //
    for (dist = 8; dist <= 100; dist += 8)
    {
        VectorMA(origin, dist, hordir, start);
        start[2] = startz + 24;
        VectorCopy(start, end);
        end[2] -= 48 + sv_maxbarrier->value;
        trace = AAS_TraceClientBBox(start, end, PRESENCE_CROUCH, entnum);
        //if solid is found the bot can't walk any further and fall into a gap
        if (!trace.startsolid)
        {
            //if it is a gap
            if (trace.endpos[2] < startz - sv_maxstep->value - 8)
            {
                VectorCopy(trace.endpos, end);
                end[2] -= 20;
                if (AAS_PointContents(end) & CONTENTS_WATER) break;
                //if a gap is found slow down
                //botimport.Print(PRT_MESSAGE, "gap at %f\n", dist);
                return dist;
            } //end if
            startz = trace.endpos[2];
        } //end if
    } //end for
    return 0;
} //end of the function BotGapDistance
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotCheckBarrierJump(bot_movestate_t *ms, vec3_t dir, float speed)
{
    vec3_t start, hordir, end;
    aas_trace_t trace;

    VectorCopy(ms->origin, end);
    end[2] += sv_maxbarrier->value;
    //trace right up
    trace = AAS_TraceClientBBox(ms->origin, end, PRESENCE_NORMAL, ms->entitynum);
    //this shouldn't happen... but we check anyway
    if (trace.startsolid) return qfalse;
    //if very low ceiling it isn't possible to jump up to a barrier
    if (trace.endpos[2] - ms->origin[2] < sv_maxstep->value) return qfalse;
    //
    hordir[0] = dir[0];
    hordir[1] = dir[1];
    hordir[2] = 0;
    VectorNormalize(hordir);
    VectorMA(ms->origin, ms->thinktime * speed * 0.5, hordir, end);
    VectorCopy(trace.endpos, start);
    end[2] = trace.endpos[2];
    //trace from previous trace end pos horizontally in the move direction
    trace = AAS_TraceClientBBox(start, end, PRESENCE_NORMAL, ms->entitynum);
    //again this shouldn't happen
    if (trace.startsolid) return qfalse;
    //
    VectorCopy(trace.endpos, start);
    VectorCopy(trace.endpos, end);
    end[2] = ms->origin[2];
    //trace down from the previous trace end pos
    trace = AAS_TraceClientBBox(start, end, PRESENCE_NORMAL, ms->entitynum);
    //if solid
    if (trace.startsolid) return qfalse;
    //if no obstacle at all
    if (trace.fraction >= 1.0) return qfalse;
    //if less than the maximum step height
    if (trace.endpos[2] - ms->origin[2] < sv_maxstep->value) return qfalse;
    //
    EA_Jump(ms->client);
    EA_Move(ms->client, hordir, speed);
    ms->moveflags |= MFL_BARRIERJUMP;
    //there is a barrier
    return qtrue;
} //end of the function BotCheckBarrierJump
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotSwimInDirection(bot_movestate_t *ms, vec3_t dir, float speed, int type)
{
    vec3_t normdir;

    VectorCopy(dir, normdir);
    VectorNormalize(normdir);
    EA_Move(ms->client, normdir, speed);
    return qtrue;
} //end of the function BotSwimInDirection
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotWalkInDirection(bot_movestate_t *ms, vec3_t dir, float speed, int type)
{
    vec3_t hordir, cmdmove, velocity, tmpdir, origin;
    int presencetype, maxframes, cmdframes, stopevent;
    aas_clientmove_t move;
    float dist;

    if (AAS_OnGround(ms->origin, ms->presencetype, ms->entitynum)) ms->moveflags |= MFL_ONGROUND;
    //if the bot is on the ground
    if (ms->moveflags & MFL_ONGROUND)
    {
        //if there is a barrier the bot can jump on
        if (BotCheckBarrierJump(ms, dir, speed)) return qtrue;
        //remove barrier jump flag
        ms->moveflags &= ~MFL_BARRIERJUMP;
        //get the presence type for the movement
        if ((type & MOVE_CROUCH) && !(type & MOVE_JUMP)) presencetype = PRESENCE_CROUCH;
        else presencetype = PRESENCE_NORMAL;
        //horizontal direction
        hordir[0] = dir[0];
        hordir[1] = dir[1];
        hordir[2] = 0;
        VectorNormalize(hordir);
        //if the bot is not supposed to jump
        if (!(type & MOVE_JUMP))
        {
            //if there is a gap, try to jump over it
            if (BotGapDistance(ms->origin, hordir, ms->entitynum) > 0) type |= MOVE_JUMP;
        } //end if
        //get command movement
        VectorScale(hordir, speed, cmdmove);
        VectorCopy(ms->velocity, velocity);
        //
        if (type & MOVE_JUMP)
        {
            //botimport.Print(PRT_MESSAGE, "trying jump\n");
            cmdmove[2] = 400;
            maxframes = PREDICTIONTIME_JUMP / 0.1;
            cmdframes = 1;
            stopevent = SE_HITGROUND|SE_HITGROUNDDAMAGE|
                        SE_ENTERWATER|SE_ENTERSLIME|SE_ENTERLAVA;
        } //end if
        else
        {
            maxframes = 2;
            cmdframes = 2;
            stopevent = SE_HITGROUNDDAMAGE|
                        SE_ENTERWATER|SE_ENTERSLIME|SE_ENTERLAVA;
        } //end else
        //AAS_ClearShownDebugLines();
        //
        VectorCopy(ms->origin, origin);
        origin[2] += 0.5;
        AAS_PredictClientMovement(&move, ms->entitynum, origin, presencetype, qtrue,
                                    velocity, cmdmove, cmdframes, maxframes, 0.1f,
                                    stopevent, 0, qfalse);//qtrue);
        //if prediction time wasn't enough to fully predict the movement
        if (move.frames >= maxframes && (type & MOVE_JUMP))
        {
            //botimport.Print(PRT_MESSAGE, "client %d: max prediction frames\n", ms->client);
            return qfalse;
        } //end if
        //don't enter slime or lava and don't fall from too high
        if (move.stopevent & (SE_ENTERSLIME|SE_ENTERLAVA|SE_HITGROUNDDAMAGE))
        {
            //botimport.Print(PRT_MESSAGE, "client %d: would be hurt ", ms->client);
            //if (move.stopevent & SE_ENTERSLIME) botimport.Print(PRT_MESSAGE, "slime\n");
            //if (move.stopevent & SE_ENTERLAVA) botimport.Print(PRT_MESSAGE, "lava\n");
            //if (move.stopevent & SE_HITGROUNDDAMAGE) botimport.Print(PRT_MESSAGE, "hitground\n");
            return qfalse;
        } //end if
        //if ground was hit
        if (move.stopevent & SE_HITGROUND)
        {
            //check for nearby gap
            VectorNormalize2(move.velocity, tmpdir);
            dist = BotGapDistance(move.endpos, tmpdir, ms->entitynum);
            if (dist > 0) return qfalse;
            //
            dist = BotGapDistance(move.endpos, hordir, ms->entitynum);
            if (dist > 0) return qfalse;
        } //end if
        //get horizontal movement
        tmpdir[0] = move.endpos[0] - ms->origin[0];
        tmpdir[1] = move.endpos[1] - ms->origin[1];
        tmpdir[2] = 0;
        //
        //AAS_DrawCross(move.endpos, 4, LINECOLOR_BLUE);
        //the bot is blocked by something
        if (VectorLength(tmpdir) < speed * ms->thinktime * 0.5) return qfalse;
        //perform the movement
        if (type & MOVE_JUMP) EA_Jump(ms->client);
        if (type & MOVE_CROUCH) EA_Crouch(ms->client);
        EA_Move(ms->client, hordir, speed);
        //movement was succesfull
        return qtrue;
    } //end if
    else
    {
        if (ms->moveflags & MFL_BARRIERJUMP)
        {
            //if near the top or going down
            if (ms->velocity[2] < 50)
            {
                EA_Move(ms->client, dir, speed);
            } //end if
        } //end if
        //FIXME: do air control to avoid hazards
        return qtrue;
    } //end else
} //end of the function BotWalkInDirection
//===========================================================================
//
// Parameter:           -
// Returns:             -
// Changes Globals:     -
//===========================================================================
int BotMoveInDirection(int movestate, vec3_t dir, float speed, int type)
{
    bot_movestate_t *ms;

    ms = BotMoveStateFromHandle(movestate);
    if (!ms) return qfalse;
    //if swimming
    if (AAS_Swimming(ms->origin))
    {
        return BotSwimInDirection(ms, dir, speed, ty