codemp/game/ai_wpnav.c

Go to the documentation of this file.

#include "g_local.h"
#include "q_shared.h"
#include "botlib.h"
#include "ai_main.h"

float gWPRenderTime = 0;
float gDeactivated = 0;
float gBotEdit = 0;
int gWPRenderedFrame = 0;

#include "../namespace_begin.h"
wpobject_t *gWPArray[MAX_WPARRAY_SIZE];
int gWPNum = 0;
#include "../namespace_end.h"

int gLastPrintedIndex = -1;

#ifndef _XBOX
nodeobject_t nodetable[MAX_NODETABLE_SIZE];
int nodenum; //so we can connect broken trails
#endif

int gLevelFlags = 0;

char *GetFlagStr( int flags )
{
        char *flagstr;
        int i;

        flagstr = (char *)B_TempAlloc(128);
        i = 0;

        if (!flags)
        {
                strcpy(flagstr, "none\0");
                goto fend;
        }

        if (flags & WPFLAG_JUMP)
        {
                flagstr[i] = 'j';
                i++;
        }

        if (flags & WPFLAG_DUCK)
        {
                flagstr[i] = 'd';
                i++;
        }

        if (flags & WPFLAG_SNIPEORCAMPSTAND)
        {
                flagstr[i] = 'c';
                i++;
        }

        if (flags & WPFLAG_WAITFORFUNC)
        {
                flagstr[i] = 'f';
                i++;
        }

        if (flags & WPFLAG_SNIPEORCAMP)
        {
                flagstr[i] = 's';
                i++;
        }

        if (flags & WPFLAG_ONEWAY_FWD)
        {
                flagstr[i] = 'x';
                i++;
        }

        if (flags & WPFLAG_ONEWAY_BACK)
        {
                flagstr[i] = 'y';
                i++;
        }

        if (flags & WPFLAG_GOALPOINT)
        {
                flagstr[i] = 'g';
                i++;
        }

        if (flags & WPFLAG_NOVIS)
        {
                flagstr[i] = 'n';
                i++;
        }

        if (flags & WPFLAG_NOMOVEFUNC)
        {
                flagstr[i] = 'm';
                i++;
        }

        if (flags & WPFLAG_RED_FLAG)
        {
                if (i)
                {
                        flagstr[i] = ' ';
                        i++;
                }
                flagstr[i] = 'r';
                i++;
                flagstr[i] = 'e';
                i++;
                flagstr[i] = 'd';
                i++;
                flagstr[i] = ' ';
                i++;
                flagstr[i] = 'f';
                i++;
                flagstr[i] = 'l';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = 'g';
                i++;
        }

        if (flags & WPFLAG_BLUE_FLAG)
        {
                if (i)
                {
                        flagstr[i] = ' ';
                        i++;
                }
                flagstr[i] = 'b';
                i++;
                flagstr[i] = 'l';
                i++;
                flagstr[i] = 'u';
                i++;
                flagstr[i] = 'e';
                i++;
                flagstr[i] = ' ';
                i++;
                flagstr[i] = 'f';
                i++;
                flagstr[i] = 'l';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = 'g';
                i++;
        }

        if (flags & WPFLAG_SIEGE_IMPERIALOBJ)
        {
                if (i)
                {
                        flagstr[i] = ' ';
                        i++;
                }
                flagstr[i] = 's';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = 'g';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = '_';
                i++;
                flagstr[i] = 'i';
                i++;
                flagstr[i] = 'm';
                i++;
                flagstr[i] = 'p';
                i++;
        }

        if (flags & WPFLAG_SIEGE_REBELOBJ)
        {
                if (i)
                {
                        flagstr[i] = ' ';
                        i++;
                }
                flagstr[i] = 's';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = 'g';
                i++;
                flagstr[i] = 'a';
                i++;
                flagstr[i] = '_';
                i++;
                flagstr[i] = 'r';
                i++;
                flagstr[i] = 'e';
                i++;
                flagstr[i] = 'b';
                i++;
        }

        flagstr[i] = '\0';

        if (i == 0)
        {
                strcpy(flagstr, "unknown\0");
        }

fend:
        return flagstr;
}

void G_TestLine(vec3_t start, vec3_t end, int color, int time)
{
        gentity_t *te;

        te = G_TempEntity( start, EV_TESTLINE );
        VectorCopy(start, te->s.origin);
        VectorCopy(end, te->s.origin2);
        te->s.time2 = time;
        te->s.weapon = color;
        te->r.svFlags |= SVF_BROADCAST;
}

void BotWaypointRender(void)
{
        int i, n;
        int inc_checker;
        int bestindex;
        int gotbestindex;
        float bestdist;
        float checkdist;
        gentity_t *plum;
        gentity_t *viewent;
        char *flagstr;
        vec3_t a;

        if (!gBotEdit)
        {
                return;
        }

        bestindex = 0;

        if (gWPRenderTime > level.time)
        {
                goto checkprint;
        }

        gWPRenderTime = level.time + 100;

        i = gWPRenderedFrame;
        inc_checker = gWPRenderedFrame;

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse)
                {
                        plum = G_TempEntity( gWPArray[i]->origin, EV_SCOREPLUM );
                        plum->r.svFlags |= SVF_BROADCAST;
                        plum->s.time = i;
                        
                        n = 0;

                        while (n < gWPArray[i]->neighbornum)
                        {
                                if (gWPArray[i]->neighbors[n].forceJumpTo && gWPArray[gWPArray[i]->neighbors[n].num])
                                {
                                        G_TestLine(gWPArray[i]->origin, gWPArray[gWPArray[i]->neighbors[n].num]->origin, 0x0000ff, 5000);
                                }
                                n++;
                        }

                        gWPRenderedFrame++;
                }
                else
                {
                        gWPRenderedFrame = 0;
                        break;
                }

                if ((i - inc_checker) > 4)
                {
                        break; //don't render too many at once
                }
                i++;
        }

        if (i >= gWPNum)
        {
                gWPRenderTime = level.time + 1500; //wait a bit after we finish doing the whole trail
                gWPRenderedFrame = 0;
        }

checkprint:

        if (!bot_wp_info.value)
        {
                return;
        }

        viewent = &g_entities[0]; //only show info to the first client

        if (!viewent || !viewent->client)
        { //client isn't in the game yet?
                return;
        }

        bestdist = 256; //max distance for showing point info
        gotbestindex = 0;

        i = 0;

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse)
                {
                        VectorSubtract(viewent->client->ps.origin, gWPArray[i]->origin, a);

                        checkdist = VectorLength(a);

                        if (checkdist < bestdist)
                        {
                                bestdist = checkdist;
                                bestindex = i;
                                gotbestindex = 1;
                        }
                }
                i++;
        }

        if (gotbestindex && bestindex != gLastPrintedIndex)
        {
                flagstr = GetFlagStr(gWPArray[bestindex]->flags);
                gLastPrintedIndex = bestindex;
                G_Printf(S_COLOR_YELLOW "Waypoint %i\nFlags - %i (%s) (w%f)\nOrigin - (%i %i %i)\n", (int)(gWPArray[bestindex]->index), (int)(gWPArray[bestindex]->flags), flagstr, gWPArray[bestindex]->weight, (int)(gWPArray[bestindex]->origin[0]), (int)(gWPArray[bestindex]->origin[1]), (int)(gWPArray[bestindex]->origin[2]));
                //GetFlagStr allocates 128 bytes for this, if it's changed then obviously this must be as well
                B_TempFree(128); //flagstr

                plum = G_TempEntity( gWPArray[bestindex]->origin, EV_SCOREPLUM );
                plum->r.svFlags |= SVF_BROADCAST;
                plum->s.time = bestindex; //render it once
        }
        else if (!gotbestindex)
        {
                gLastPrintedIndex = -1;
        }
}

void TransferWPData(int from, int to)
{
        if (!gWPArray[to])
        {
                gWPArray[to] = (wpobject_t *)B_Alloc(sizeof(wpobject_t));
        }

        if (!gWPArray[to])
        {
                G_Printf(S_COLOR_RED "FATAL ERROR: Could not allocated memory for waypoint\n");
        }

        gWPArray[to]->flags = gWPArray[from]->flags;
        gWPArray[to]->weight = gWPArray[from]->weight;
        gWPArray[to]->associated_entity = gWPArray[from]->associated_entity;
        gWPArray[to]->disttonext = gWPArray[from]->disttonext;
        gWPArray[to]->forceJumpTo = gWPArray[from]->forceJumpTo;
        gWPArray[to]->index = to;
        gWPArray[to]->inuse = gWPArray[from]->inuse;
        VectorCopy(gWPArray[from]->origin, gWPArray[to]->origin);
}

void CreateNewWP(vec3_t origin, int flags)
{
        if (gWPNum >= MAX_WPARRAY_SIZE)
        {
                if (!g_RMG.integer)
                {
                        G_Printf(S_COLOR_YELLOW "Warning: Waypoint limit hit (%i)\n", MAX_WPARRAY_SIZE);
                }
                return;
        }

        if (!gWPArray[gWPNum])
        {
                gWPArray[gWPNum] = (wpobject_t *)B_Alloc(sizeof(wpobject_t));
        }

        if (!gWPArray[gWPNum])
        {
                G_Printf(S_COLOR_RED "ERROR: Could not allocated memory for waypoint\n");
        }

        gWPArray[gWPNum]->flags = flags;
        gWPArray[gWPNum]->weight = 0; //calculated elsewhere
        gWPArray[gWPNum]->associated_entity = ENTITYNUM_NONE; //set elsewhere
        gWPArray[gWPNum]->forceJumpTo = 0;
        gWPArray[gWPNum]->disttonext = 0; //calculated elsewhere
        gWPArray[gWPNum]->index = gWPNum;
        gWPArray[gWPNum]->inuse = 1;
        VectorCopy(origin, gWPArray[gWPNum]->origin);
        gWPNum++;
}

void CreateNewWP_FromObject(wpobject_t *wp)
{
        int i;

        if (gWPNum >= MAX_WPARRAY_SIZE)
        {
                return;
        }

        if (!gWPArray[gWPNum])
        {
                gWPArray[gWPNum] = (wpobject_t *)B_Alloc(sizeof(wpobject_t));
        }

        if (!gWPArray[gWPNum])
        {
                G_Printf(S_COLOR_RED "ERROR: Could not allocated memory for waypoint\n");
        }

        gWPArray[gWPNum]->flags = wp->flags;
        gWPArray[gWPNum]->weight = wp->weight;
        gWPArray[gWPNum]->associated_entity = wp->associated_entity;
        gWPArray[gWPNum]->disttonext = wp->disttonext;
        gWPArray[gWPNum]->forceJumpTo = wp->forceJumpTo;
        gWPArray[gWPNum]->index = gWPNum;
        gWPArray[gWPNum]->inuse = 1;
        VectorCopy(wp->origin, gWPArray[gWPNum]->origin);
        gWPArray[gWPNum]->neighbornum = wp->neighbornum;

        i = wp->neighbornum;

        while (i >= 0)
        {
                gWPArray[gWPNum]->neighbors[i].num = wp->neighbors[i].num;
                gWPArray[gWPNum]->neighbors[i].forceJumpTo = wp->neighbors[i].forceJumpTo;

                i--;
        }

        if (gWPArray[gWPNum]->flags & WPFLAG_RED_FLAG)
        {
                flagRed = gWPArray[gWPNum];
                oFlagRed = flagRed;
        }
        else if (gWPArray[gWPNum]->flags & WPFLAG_BLUE_FLAG)
        {
                flagBlue = gWPArray[gWPNum];
                oFlagBlue = flagBlue;
        }

        gWPNum++;
}

void RemoveWP(void)
{
        if (gWPNum <= 0)
        {
                return;
        }

        gWPNum--;

        if (!gWPArray[gWPNum] || !gWPArray[gWPNum]->inuse)
        {
                return;
        }

        //B_Free((wpobject_t *)gWPArray[gWPNum]);
        if (gWPArray[gWPNum])
        {
                memset( gWPArray[gWPNum], 0, sizeof(gWPArray[gWPNum]) );
        }

        //gWPArray[gWPNum] = NULL;

        if (gWPArray[gWPNum])
        {
                gWPArray[gWPNum]->inuse = 0;
        }
}

void RemoveAllWP(void)
{
        while(gWPNum) {
                RemoveWP();
        }
}

void RemoveWP_InTrail(int afterindex)
{
        int foundindex;
        int foundanindex;
        int didchange;
        int i;

        foundindex = 0;
        foundanindex = 0;
        didchange = 0;
        i = 0;

        if (afterindex < 0 || afterindex >= gWPNum)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint number %i does not exist\n", afterindex);
                return;
        }

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == afterindex)
                {
                        foundindex = i;
                        foundanindex = 1;
                        break;
                }

                i++;
        }

        if (!foundanindex)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint index %i should exist, but does not (?)\n", afterindex);
                return;
        }

        i = 0;

        while (i <= gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->index == foundindex)
                {
                        //B_Free(gWPArray[i]);

                        //Keep reusing the memory
                        memset( gWPArray[i], 0, sizeof(gWPArray[i]) );

                        //gWPArray[i] = NULL;
                        gWPArray[i]->inuse = 0;
                        didchange = 1;
                }
                else if (gWPArray[i] && didchange)
                {
                        TransferWPData(i, i-1);
                        //B_Free(gWPArray[i]);

                        //Keep reusing the memory
                        memset( gWPArray[i], 0, sizeof(gWPArray[i]) );

                        //gWPArray[i] = NULL;
                        gWPArray[i]->inuse = 0;
                }

                i++;
        }
        gWPNum--;
}

int CreateNewWP_InTrail(vec3_t origin, int flags, int afterindex)
{
        int foundindex;
        int foundanindex;
        int i;

        foundindex = 0;
        foundanindex = 0;
        i = 0;

        if (gWPNum >= MAX_WPARRAY_SIZE)
        {
                if (!g_RMG.integer)
                {
                        G_Printf(S_COLOR_YELLOW "Warning: Waypoint limit hit (%i)\n", MAX_WPARRAY_SIZE);
                }
                return 0;
        }

        if (afterindex < 0 || afterindex >= gWPNum)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint number %i does not exist\n", afterindex);
                return 0;
        }

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == afterindex)
                {
                        foundindex = i;
                        foundanindex = 1;
                        break;
                }

                i++;
        }

        if (!foundanindex)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint index %i should exist, but does not (?)\n", afterindex);
                return 0;
        }

        i = gWPNum;

        while (i >= 0)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index != foundindex)
                {
                        TransferWPData(i, i+1);
                }
                else if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == foundindex)
                {
                        i++;

                        if (!gWPArray[i])
                        {
                                gWPArray[i] = (wpobject_t *)B_Alloc(sizeof(wpobject_t));
                        }

                        gWPArray[i]->flags = flags;
                        gWPArray[i]->weight = 0; //calculated elsewhere
                        gWPArray[i]->associated_entity = ENTITYNUM_NONE; //set elsewhere
                        gWPArray[i]->disttonext = 0; //calculated elsewhere
                        gWPArray[i]->forceJumpTo = 0;
                        gWPArray[i]->index = i;
                        gWPArray[i]->inuse = 1;
                        VectorCopy(origin, gWPArray[i]->origin);
                        gWPNum++;
                        break;
                }

                i--;
        }

        return 1;
}

int CreateNewWP_InsertUnder(vec3_t origin, int flags, int afterindex)
{
        int foundindex;
        int foundanindex;
        int i;

        foundindex = 0;
        foundanindex = 0;
        i = 0;

        if (gWPNum >= MAX_WPARRAY_SIZE)
        {
                if (!g_RMG.integer)
                {
                        G_Printf(S_COLOR_YELLOW "Warning: Waypoint limit hit (%i)\n", MAX_WPARRAY_SIZE);
                }
                return 0;
        }

        if (afterindex < 0 || afterindex >= gWPNum)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint number %i does not exist\n", afterindex);
                return 0;
        }

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == afterindex)
                {
                        foundindex = i;
                        foundanindex = 1;
                        break;
                }

                i++;
        }

        if (!foundanindex)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint index %i should exist, but does not (?)\n", afterindex);
                return 0;
        }

        i = gWPNum;

        while (i >= 0)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index != foundindex)
                {
                        TransferWPData(i, i+1);
                }
                else if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == foundindex)
                {
                        //i++;
                        TransferWPData(i, i+1);

                        if (!gWPArray[i])
                        {
                                gWPArray[i] = (wpobject_t *)B_Alloc(sizeof(wpobject_t));
                        }

                        gWPArray[i]->flags = flags;
                        gWPArray[i]->weight = 0; //calculated elsewhere
                        gWPArray[i]->associated_entity = ENTITYNUM_NONE; //set elsewhere
                        gWPArray[i]->disttonext = 0; //calculated elsewhere
                        gWPArray[i]->forceJumpTo = 0;
                        gWPArray[i]->index = i;
                        gWPArray[i]->inuse = 1;
                        VectorCopy(origin, gWPArray[i]->origin);
                        gWPNum++;
                        break;
                }

                i--;
        }

        return 1;
}

void TeleportToWP(gentity_t *pl, int afterindex)
{
        int foundindex;
        int foundanindex;
        int i;

        if (!pl || !pl->client)
        {
                return;
        }

        foundindex = 0;
        foundanindex = 0;
        i = 0;

        if (afterindex < 0 || afterindex >= gWPNum)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint number %i does not exist\n", afterindex);
                return;
        }

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i]->index == afterindex)
                {
                        foundindex = i;
                        foundanindex = 1;
                        break;
                }

                i++;
        }

        if (!foundanindex)
        {
                G_Printf(S_COLOR_YELLOW "Waypoint index %i should exist, but does not (?)\n", afterindex);
                return;
        }

        VectorCopy(gWPArray[foundindex]->origin, pl->client->ps.origin);

        return;
}

void WPFlagsModify(int wpnum, int flags)
{
        if (wpnum < 0 || wpnum >= gWPNum || !gWPArray[wpnum] || !gWPArray[wpnum]->inuse)
        {
                G_Printf(S_COLOR_YELLOW "WPFlagsModify: Waypoint %i does not exist\n", wpnum);
                return;
        }

        gWPArray[wpnum]->flags = flags;
}

static int NotWithinRange(int base, int extent)
{
        if (extent > base && base+5 >= extent)
        {
                return 0;
        }

        if (extent < base && base-5 <= extent)
        {
                return 0;
        }

        return 1;
}

#ifndef _XBOX
int NodeHere(vec3_t spot)
{
        int i;

        i = 0;

        while (i < nodenum)
        {
                if ((int)nodetable[i].origin[0] == (int)spot[0] &&
                        (int)nodetable[i].origin[1] == (int)spot[1])
                {
                        if ((int)nodetable[i].origin[2] == (int)spot[2] ||
                                ((int)nodetable[i].origin[2] < (int)spot[2] && (int)nodetable[i].origin[2]+5 > (int)spot[2]) ||
                                ((int)nodetable[i].origin[2] > (int)spot[2] && (int)nodetable[i].origin[2]-5 < (int)spot[2]))
                        {
                                return 1;
                        }
                }
                i++;
        }

        return 0;
}
#endif

int CanGetToVector(vec3_t org1, vec3_t org2, vec3_t mins, vec3_t maxs)
{
        trace_t tr;

        trap_Trace(&tr, org1, mins, maxs, org2, ENTITYNUM_NONE, MASK_SOLID);

        if (tr.fraction == 1 && !tr.startsolid && !tr.allsolid)
        {
                return 1;
        }

        return 0;
}

#if 0
int CanGetToVectorTravel(vec3_t org1, vec3_t org2, vec3_t mins, vec3_t maxs)
{
        trace_t tr;
        vec3_t a, ang, fwd;
        vec3_t midpos, dmid;
        float startheight, midheight, fLen;

        mins[2] = -13;
        maxs[2] = 13;

        trap_Trace(&tr, org1, mins, maxs, org2, ENTITYNUM_NONE, MASK_SOLID);

        if (tr.fraction != 1 || tr.startsolid || tr.allsolid)
        {
                return 0;
        }

        VectorSubtract(org2, org1, a);

        vectoangles(a, ang);

        AngleVectors(ang, fwd, NULL, NULL);

        fLen = VectorLength(a)/2;

        midpos[0] = org1[0] + fwd[0]*fLen;
        midpos[1] = org1[1] + fwd[1]*fLen;
        midpos[2] = org1[2] + fwd[2]*fLen;

        VectorCopy(org1, dmid);
        dmid[2] -= 1024;

        trap_Trace(&tr, midpos, NULL, NULL, dmid, ENTITYNUM_NONE, MASK_SOLID);

        startheight = org1[2] - tr.endpos[2];

        VectorCopy(midpos, dmid);
        dmid[2] -= 1024;

        trap_Trace(&tr, midpos, NULL, NULL, dmid, ENTITYNUM_NONE, MASK_SOLID);

        if (tr.startsolid || tr.allsolid)
        {
                return 1;
        }

        midheight = midpos[2] - tr.endpos[2];

        if (midheight > startheight*2)
        {
                return 0; //too steep of a drop.. can't go on
        }

        return 1;
}
#else
int CanGetToVectorTravel(vec3_t org1, vec3_t moveTo, vec3_t mins, vec3_t maxs)
//int ExampleAnimEntMove(gentity_t *self, vec3_t moveTo, float stepSize)
{
        trace_t tr;
        vec3_t stepTo;
        vec3_t stepSub;
        vec3_t stepGoal;
        vec3_t workingOrg;
        vec3_t lastIncrement;
        vec3_t finalMeasure;
        float stepSize = 0;
        float measureLength = 0;
        int didMove = 0;
        int traceMask = MASK_PLAYERSOLID;
        qboolean initialDone = qfalse;

        VectorCopy(org1, workingOrg);
        VectorCopy(org1, lastIncrement);

        VectorCopy(moveTo, stepTo);
        stepTo[2] = workingOrg[2];

        VectorSubtract(stepTo, workingOrg, stepSub);
        stepSize = VectorLength(stepSub); //make the step size the length of the original positions without Z

        VectorNormalize(stepSub);

        while (!initialDone || didMove)
        {
                initialDone = qtrue;
                didMove = 0;

                stepGoal[0] = workingOrg[0] + stepSub[0]*stepSize;
                stepGoal[1] = workingOrg[1] + stepSub[1]*stepSize;
                stepGoal[2] = workingOrg[2] + stepSub[2]*stepSize;

                trap_Trace(&tr, workingOrg, mins, maxs, stepGoal, ENTITYNUM_NONE, traceMask);

                if (!tr.startsolid && !tr.allsolid && tr.fraction)
                {
                        vec3_t vecSub;
                        VectorSubtract(workingOrg, tr.endpos, vecSub);

                        if (VectorLength(vecSub) > (stepSize/2))
                        {
                                workingOrg[0] = tr.endpos[0];
                                workingOrg[1] = tr.endpos[1];
                                //trap_LinkEntity(self);
                                didMove = 1;
                        }
                }
                
                if (didMove != 1)
                { //stair check
                        vec3_t trFrom;
                        vec3_t trTo;
                        vec3_t trDir;
                        vec3_t vecMeasure;

                        VectorCopy(tr.endpos, trFrom);
                        trFrom[2] += 16;

                        VectorSubtract(/*tr.endpos*/stepGoal, workingOrg, trDir);
                        VectorNormalize(trDir);
                        trTo[0] = tr.endpos[0] + trDir[0]*2;
                        trTo[1] = tr.endpos[1] + trDir[1]*2;
                        trTo[2] = tr.endpos[2] + trDir[2]*2;
                        trTo[2] += 16;

                        VectorSubtract(trFrom, trTo, vecMeasure);

                        if (VectorLength(vecMeasure) > 1)
                        {
                                trap_Trace(&tr, trFrom, mins, maxs, trTo, ENTITYNUM_NONE, traceMask);

                                if (!tr.startsolid && !tr.allsolid && tr.fraction == 1)
                                { //clear trace here, probably up a step
                                        vec3_t trDown;
                                        vec3_t trUp;
                                        VectorCopy(tr.endpos, trUp);
                                        VectorCopy(tr.endpos, trDown);
                                        trDown[2] -= 16;

                                        trap_Trace(&tr, trFrom, mins, maxs, trTo, ENTITYNUM_NONE, traceMask);

                                        if (!tr.startsolid && !tr.allsolid)
                                        { //plop us down on the step after moving up
                                                VectorCopy(tr.endpos, workingOrg);
                                                //trap_LinkEntity(self);
                                                didMove = 1;
                                        }
                                }
                        }
                }

                VectorSubtract(lastIncrement, workingOrg, finalMeasure);
                measureLength = VectorLength(finalMeasure);

                if (!measureLength)
                { //no progress, break out. If last movement was a sucess didMove will equal 1.
                        break;
                }

                stepSize -= measureLength; //subtract the progress distance from the step size so we don't overshoot the mark.
                if (stepSize <= 0)
                {
                        break;
                }

                VectorCopy(workingOrg, lastIncrement);
        }

        return didMove;
}
#endif

#ifndef _XBOX
int ConnectTrail(int startindex, int endindex, qboolean behindTheScenes)
{
        int foundit;
        int cancontinue;
        int i;
        int failsafe;
        int successnodeindex;
        int insertindex;
        int prenodestart;
        byte extendednodes[MAX_NODETABLE_SIZE]; //for storing checked nodes and not trying to extend them each a bazillion times
        float fvecmeas;
        float baseheight;
        float branchDistance;
        float maxDistFactor = 256;
        vec3_t a;
        vec3_t startplace, starttrace;
        vec3_t mins, maxs;
        vec3_t testspot;
        vec3_t validspotpos;
        trace_t tr;

        if (g_RMG.integer)
        { //this might be temporary. Or not.
                if (!(gWPArray[startindex]->flags & WPFLAG_NEVERONEWAY) &&
                        !(gWPArray[endindex]->flags & WPFLAG_NEVERONEWAY))
                {
                        gWPArray[startindex]->flags |= WPFLAG_ONEWAY_FWD;
                        gWPArray[endindex]->flags |= WPFLAG_ONEWAY_BACK;
                }
                return 0;
        }

        if (!g_RMG.integer)
        {
                branchDistance = TABLE_BRANCH_DISTANCE;
        }
        else
        {
                branchDistance = 512; //be less precise here, terrain is fairly broad, and we don't want to take an hour precalculating
        }

        if (g_RMG.integer)
        {
                maxDistFactor = 700;
        }

        mins[0] = -15;
        mins[1] = -15;
        mins[2] = 0;
        maxs[0] = 15;
        maxs[1] = 15;
        maxs[2] = 0;

        nodenum = 0;
        foundit = 0;

        i = 0;

        successnodeindex = 0;

        while (i < MAX_NODETABLE_SIZE) //clear it out before using it
        {
                nodetable[i].flags = 0;
//              nodetable[i].index = 0;
                nodetable[i].inuse = 0;
                nodetable[i].neighbornum = 0;
                nodetable[i].origin[0] = 0;
                nodetable[i].origin[1] = 0;
                nodetable[i].origin[2] = 0;
                nodetable[i].weight = 0;

                extendednodes[i] = 0;

                i++;
        }

        i = 0;

        if (!behindTheScenes)
        {
                G_Printf(S_COLOR_YELLOW "Point %i is not connected to %i - Repairing...\n", startindex, endindex);
        }

        VectorCopy(gWPArray[startindex]->origin, startplace);

        VectorCopy(startplace, starttrace);

        starttrace[2] -= 4096;

        trap_Trace(&tr, startplace, NULL, NULL, starttrace, ENTITYNUM_NONE, MASK_SOLID);

        baseheight = startplace[2] - tr.endpos[2];

        cancontinue = 1;

        VectorCopy(startplace, nodetable[nodenum].origin);
        nodetable[nodenum].weight = 1;
        nodetable[nodenum].inuse = 1;
//      nodetable[nodenum].index = nodenum;
        nodenum++;

        while (nodenum < MAX_NODETABLE_SIZE && !foundit && cancontinue)
        {
                if (g_RMG.integer)
                { //adjust the branch distance dynamically depending on the distance from the start and end points.
                        vec3_t startDist;
                        vec3_t endDist;
                        float startDistf;
                        float endDistf;

                        VectorSubtract(nodetable[nodenum-1].origin, gWPArray[startindex]->origin, startDist);
                        VectorSubtract(nodetable[nodenum-1].origin, gWPArray[endindex]->origin, endDist);

                        startDistf = VectorLength(startDist);
                        endDistf = VectorLength(endDist);

                        if (startDistf < 64 || endDistf < 64)
                        {
                                branchDistance = 64;
                        }
                        else if (startDistf < 128 || endDistf < 128)
                        {
                                branchDistance = 128;
                        }
                        else if (startDistf < 256 || endDistf < 256)
                        {
                                branchDistance = 256;
                        }
                        else if (startDistf < 512 || endDistf < 512)
                        {
                                branchDistance = 512;
                        }
                        else
                        {
                                branchDistance = 800;
                        }
                }
                cancontinue = 0;
                i = 0;
                prenodestart = nodenum;

                while (i < prenodestart)
                {
                        if (extendednodes[i] != 1)
                        {
                                VectorSubtract(gWPArray[endindex]->origin, nodetable[i].origin, a);
                                fvecmeas = VectorLength(a);

                                if (fvecmeas < 128 && CanGetToVector(gWPArray[endindex]->origin, nodetable[i].origin, mins, maxs))
                                {
                                        foundit = 1;
                                        successnodeindex = i;
                                        break;
                                }

                                VectorCopy(nodetable[i].origin, testspot);
                                testspot[0] += branchDistance;

                                VectorCopy(testspot, starttrace);

                                starttrace[2] -= 4096;

                                trap_Trace(&tr, testspot, NULL, NULL, starttrace, ENTITYNUM_NONE, MASK_SOLID);

                                testspot[2] = tr.endpos[2]+baseheight;

                                if (!NodeHere(testspot) && !tr.startsolid && !tr.allsolid && CanGetToVector(nodetable[i].origin, testspot, mins, maxs))
                                {
                                        VectorCopy(testspot, nodetable[nodenum].origin);
                                        nodetable[nodenum].inuse = 1;
//                                      nodetable[nodenum].index = nodenum;
                                        nodetable[nodenum].weight = nodetable[i].weight+1;
                                        nodetable[nodenum].neighbornum = i;
                                        if ((nodetable[i].origin[2] - nodetable[nodenum].origin[2]) > 50)
                                        { //if there's a big drop, make sure we know we can't just magically fly back up
                                                nodetable[nodenum].flags = WPFLAG_ONEWAY_FWD;
                                        }
                                        nodenum++;
                                        cancontinue = 1;
                                }

                                if (nodenum >= MAX_NODETABLE_SIZE)
                                {
                                        break; //failure
                                }

                                VectorCopy(nodetable[i].origin, testspot);
                                testspot[0] -= branchDistance;

                                VectorCopy(testspot, starttrace);

                                starttrace[2] -= 4096;

                                trap_Trace(&tr, testspot, NULL, NULL, starttrace, ENTITYNUM_NONE, MASK_SOLID);

                                testspot[2] = tr.endpos[2]+baseheight;

                                if (!NodeHere(testspot) && !tr.startsolid && !tr.allsolid && CanGetToVector(nodetable[i].origin, testspot, mins, maxs))
                                {
                                        VectorCopy(testspot, nodetable[nodenum].origin);
                                        nodetable[nodenum].inuse = 1;
//                                      nodetable[nodenum].index = nodenum;
                                        nodetable[nodenum].weight = nodetable[i].weight+1;
                                        nodetable[nodenum].neighbornum = i;
                                        if ((nodetable[i].origin[2] - nodetable[nodenum].origin[2]) > 50)
                                        { //if there's a big drop, make sure we know we can't just magically fly back up
                                                nodetable[nodenum].flags = WPFLAG_ONEWAY_FWD;
                                        }
                                        nodenum++;
                                        cancontinue = 1;
                                }

                                if (nodenum >= MAX_NODETABLE_SIZE)
                                {
                                        break; //failure
                                }

                                VectorCopy(nodetable[i].origin, testspot);
                                testspot[1] += branchDistance;

                                VectorCopy(testspot, starttrace);

                                starttrace[2] -= 4096;

                                trap_Trace(&tr, testspot, NULL, NULL, starttrace, ENTITYNUM_NONE, MASK_SOLID);

                                testspot[2] = tr.endpos[2]+baseheight;

                                if (!NodeHere(testspot) && !tr.startsolid && !tr.allsolid && CanGetToVector(nodetable[i].origin, testspot, mins, maxs))
                                {
                                        VectorCopy(testspot, nodetable[nodenum].origin);
                                        nodetable[nodenum].inuse = 1;
//                                      nodetable[nodenum].index = nodenum;
                                        nodetable[nodenum].weight = nodetable[i].weight+1;
                                        nodetable[nodenum].neighbornum = i;
                                        if ((nodetable[i].origin[2] - nodetable[nodenum].origin[2]) > 50)
                                        { //if there's a big drop, make sure we know we can't just magically fly back up
                                                nodetable[nodenum].flags = WPFLAG_ONEWAY_FWD;
                                        }
                                        nodenum++;
                                        cancontinue = 1;
                                }

                                if (nodenum >= MAX_NODETABLE_SIZE)
                                {
                                        break; //failure
                                }

                                VectorCopy(nodetable[i].origin, testspot);
                                testspot[1] -= branchDistance;

                                VectorCopy(testspot, starttrace);

                                starttrace[2] -= 4096;

                                trap_Trace(&tr, testspot, NULL, NULL, starttrace, ENTITYNUM_NONE, MASK_SOLID);

                                testspot[2] = tr.endpos[2]+baseheight;

                                if (!NodeHere(testspot) && !tr.startsolid && !tr.allsolid && CanGetToVector(nodetable[i].origin, testspot, mins, maxs))
                                {
                                        VectorCopy(testspot, nodetable[nodenum].origin);
                                        nodetable[nodenum].inuse = 1;
//                                      nodetable[nodenum].index = nodenum;
                                        nodetable[nodenum].weight = nodetable[i].weight+1;
                                        nodetable[nodenum].neighbornum = i;
                                        if ((nodetable[i].origin[2] - nodetable[nodenum].origin[2]) > 50)
                                        { //if there's a big drop, make sure we know we can't just magically fly back up
                                                nodetable[nodenum].flags = WPFLAG_ONEWAY_FWD;
                                        }
                                        nodenum++;
                                        cancontinue = 1;
                                }

                                if (nodenum >= MAX_NODETABLE_SIZE)
                                {
                                        break; //failure
                                }

                                extendednodes[i] = 1;
                        }

                        i++;
                }
        }

        if (!foundit)
        {
#ifndef _DEBUG //if debug just always print this.
                if (!behindTheScenes)
#endif
                {
                        G_Printf(S_COLOR_RED "Could not link %i to %i, unreachable by node branching.\n", startindex, endindex);
                }
                gWPArray[startindex]->flags |= WPFLAG_ONEWAY_FWD;
                gWPArray[endindex]->flags |= WPFLAG_ONEWAY_BACK;
                if (!behindTheScenes)
                {
                        G_Printf(S_COLOR_YELLOW "Since points cannot be connected, point %i has been flagged as only-forward and point %i has been flagged as only-backward.\n", startindex, endindex);
                }

                /*while (nodenum >= 0)
                {
                        if (nodetable[nodenum].origin[0] || nodetable[nodenum].origin[1] || nodetable[nodenum].origin[2])
                        {
                                CreateNewWP(nodetable[nodenum].origin, nodetable[nodenum].flags);
                        }

                        nodenum--;
                }*/
                //The above code transfers nodes into the "rendered" waypoint array. Strictly for debugging.

                if (!behindTheScenes)
                { //just use what we have if we're auto-pathing the level
                        return 0;
                }
                else
                {
                        vec3_t endDist;
                        int nCount = 0;
                        int idealNode = -1;
                        float bestDist = 0;
                        float testDist;

                        if (nodenum <= 10)
                        { //not enough to even really bother.
                                return 0;
                        }

                        //Since it failed, find whichever node is closest to the desired end.
                        while (nCount < nodenum)
                        {
                                VectorSubtract(nodetable[nCount].origin, gWPArray[endindex]->origin, endDist);
                                testDist = VectorLength(endDist);
                                if (idealNode == -1)
                                {
                                        idealNode = nCount;
                                        bestDist = testDist;
                                        nCount++;
                                        continue;
                                }

                                if (testDist < bestDist)
                                {
                                        idealNode = nCount;
                                        bestDist = testDist;
                                }

                                nCount++;
                        }

                        if (idealNode == -1)
                        {
                                return 0;
                        }

                        successnodeindex = idealNode;
                }
        }

        i = successnodeindex;
        insertindex = startindex;
        failsafe = 0;
        VectorCopy(gWPArray[startindex]->origin, validspotpos);

        while (failsafe < MAX_NODETABLE_SIZE && i < MAX_NODETABLE_SIZE && i >= 0)
        {
                VectorSubtract(validspotpos, nodetable[i].origin, a);
                if (!nodetable[nodetable[i].neighbornum].inuse || !CanGetToVectorTravel(validspotpos, /*nodetable[nodetable[i].neighbornum].origin*/nodetable[i].origin, mins, maxs) || VectorLength(a) > maxDistFactor || (!CanGetToVectorTravel(validspotpos, gWPArray[endindex]->origin, mins, maxs) && CanGetToVectorTravel(nodetable[i].origin, gWPArray[endindex]->origin, mins, maxs)) )
                {
                        nodetable[i].flags |= WPFLAG_CALCULATED;
                        if (!CreateNewWP_InTrail(nodetable[i].origin, nodetable[i].flags, insertindex))
                        {
                                if (!behindTheScenes)
                                {
                                        G_Printf(S_COLOR_RED "Could not link %i to %i, waypoint limit hit.\n", startindex, endindex);
                                }
                                return 0;
                        }

                        VectorCopy(nodetable[i].origin, validspotpos);
                }

                if (i == 0)
                {
                        break;
                }

                i = nodetable[i].neighbornum;

                failsafe++;
        }

        if (!behindTheScenes)
        {
                G_Printf(S_COLOR_YELLOW "Finished connecting %i to %i.\n", startindex, endindex);
        }

        return 1;
}
#endif

int OpposingEnds(int start, int end)
{
        if (!gWPArray[start] || !gWPArray[start]->inuse || !gWPArray[end] || !gWPArray[end]->inuse)
        {
                return 0;
        }

        if ((gWPArray[start]->flags & WPFLAG_ONEWAY_FWD) &&
                (gWPArray[end]->flags & WPFLAG_ONEWAY_BACK))
        {
                return 1;
        }

        return 0;
}

int DoorBlockingSection(int start, int end)
{ //if a door blocks the trail, we'll just have to assume the points on each side are in visibility when it's open
        trace_t tr;
        gentity_t *testdoor;
        int start_trace_index;

        if (!gWPArray[start] || !gWPArray[start]->inuse || !gWPArray[end] || !gWPArray[end]->inuse)
        {
                return 0;
        }

        trap_Trace(&tr, gWPArray[start]->origin, NULL, NULL, gWPArray[end]->origin, ENTITYNUM_NONE, MASK_SOLID);

        if (tr.fraction == 1)
        {
                return 0;
        }

        testdoor = &g_entities[tr.entityNum];

        if (!testdoor)
        {
                return 0;
        }

        if (!strstr(testdoor->classname, "func_"))
        {
                return 0;
        }

        start_trace_index = tr.entityNum;

        trap_Trace(&tr, gWPArray[end]->origin, NULL, NULL, gWPArray[start]->origin, ENTITYNUM_NONE, MASK_SOLID);

        if (tr.fraction == 1)
        {
                return 0;
        }

        if (start_trace_index == tr.entityNum)
        {
                return 1;
        }

        return 0;
}

#ifndef _XBOX
int RepairPaths(qboolean behindTheScenes)
{
        int i;
        int preAmount = 0;
        int ctRet;
        vec3_t a;
        float maxDistFactor = 400;

        if (!gWPNum)
        {
                return 0;
        }

        if (g_RMG.integer)
        {
                maxDistFactor = 800; //higher tolerance here.
        }

        i = 0;

        preAmount = gWPNum;

        trap_Cvar_Update(&bot_wp_distconnect);
        trap_Cvar_Update(&bot_wp_visconnect);

        while (i < gWPNum)
        {
                if (gWPArray[i] && gWPArray[i]->inuse && gWPArray[i+1] && gWPArray[i+1]->inuse)
                {
                        VectorSubtract(gWPArray[i]->origin, gWPArray[i+1]->origin, a);

                        if (!(gWPArray[i+1]->flags & WPFLAG_NOVIS) &&
                                !(gWPArray[i+1]->flags & WPFLAG_JUMP) && //don't calculate on jump points because they might not always want to be visible (in cases of force jumping)
                                !(gWPArray[i]->flags & WPFLAG_CALCULATED) && //don't calculate it again
                                !OpposingEnds(i, i+1) &&
                                ((bot_wp_distconnect.value && VectorLength(a) > maxDistFactor) || (!OrgVisible(gWPArray[i]->origin, gWPArray[i+1]->origin, ENTITYNUM_NONE) && bot_wp_visconnect.value) ) &&
                                !DoorBlockingSection(i, i+1))
                        {
                                ctRet = ConnectTrail(i, i+1, behindTheScenes);

                                if (gWPNum >= MAX_WPARRAY_SIZE)
                                { //Bad!
                                        gWPNum = MAX_WPARRAY_SIZE;
                                        break;
                                }

                                /*if (!ctRet)
                                {
                                        return 0;
                                }*/ //we still want to write it..
                        }
                }

                i++;
        }

        return 1;
}
#endif

int OrgVisibleCurve(vec3_t org1, vec3_t mins, vec3_t maxs, vec3_t org2, int ignore)
{
        trace_t tr;
        vec3_t evenorg1;

        VectorCopy(org1, evenorg1);
        evenorg1[2] = org2[2];

        trap_Trace(&tr, evenorg1, mins, maxs, org2, ignore, MASK_SOLID);

        if (tr.fraction == 1 && !tr.startsolid && !tr.allsolid)
        {
                trap_Trace(&tr, evenorg1, mins, maxs, org1, ignore, MASK_SOLID);

                if (tr.fraction == 1 && !tr.startsolid && !tr.allsolid)
                {
                        return 1;
                }
        }

        return 0;
}

int CanForceJumpTo(int baseindex, int testingindex, float distance)
{
        float heightdif;
        vec3_t xy_base, xy_test, v, mins, maxs;
        wpobject_t *wpBase = gWPArray[baseindex];
        wpobject_t *wpTest = gWPArray[testingindex];

        mins[0] = -15;
        mins[1] = -15;
        mins[2] = -15; //-1
        maxs[0] = 15;
        maxs[1] = 15;
        maxs[2] = 15; //1

        if (!wpBase || !wpBase->inuse || !wpTest || !wpTest->inuse)
        {
                return 0;
        }

        if (distance > 400)
        {
                return 0;
        }

        VectorCopy(wpBase->origin, xy_base);
        VectorCopy(wpTest->origin, xy_test);

        xy_base[2] = xy_test[2];

        VectorSubtract(xy_base, xy_test, v);

        if (VectorLength(v) > MAX_NEIGHBOR_LINK_DISTANCE)
        {
                return 0;
        }

        if ((