.:: Bots United ::.
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)
-   -   what's your pathwalking algorithm (http://forums.bots-united.com/showthread.php?t=129)

Pierre-Marie Baty 01-01-2004 20:18
what's your pathwalking algorithm
 
Hi guys

I was wondering... what's your pathwalking algorithm like ? I mean, right after the pathfinder returned a path, be it a linked list or an array of waypoints, how do you put your bots into movement ? How do you detect if a path fails (the bot falled down a pit or whatever), or if it's time to head up to the next waypoint ? Do you allow your bot to "skip" waypoints in the path ? Where do you make it look at ?

I'm currently asking all these things because I wonder if it wouldn't be more natural to make the bot walk directly towards the furthest visible "waypoint" each time instead of making it follow the whole series. Or if not walk, at least look at. Lots of things like that.

What do you think ?

stefanhendriks 01-01-2004 20:36
Re: what's your pathwalking algorithm
 
Since my nodes are close to each other, i force the bots to walk to each of them. This to ensure the path is valid, because i cannot tell if 2 nodes out of reach actually are reachable (even though they are 'visible' with 1 tracehull).

I let my bots just face body to the waypoint and run to it. Whenever something blocks it (due the bot falls in a pit i could not somehow detect , or due false connecting nodes) the bot will get stuck, when that is true i begin doing some checks.

I do never skip waypoints.

Perhaps checking if the distance to waypoint grows instead of getting smaller can make things neater, but it also is dangerous, like when going on a 180 degree corner, you should do a traceline thingy for this, but even then it is not water proof.

FYI, i have posted the relevant path_walk function of RB BUILD 2049

Code:
// Walk the path Neo
void cNodeMachine::path_walk(cBot *pBot, float moved_distance)
{
        int BotIndex = pBot->iIndex;

        // Check if path is valid
        if (iPath[BotIndex][0] < 0)
        {
                pBot->f_move_speed = 0.0; // do not move
                return; // back out
        }
       
        // If we should wait, we do nothing here
        if (pBot->f_wait_time > gpGlobals->time)   
                return;

        pBot->f_move_speed = pBot->f_max_speed;

        // Walk the path
        int iCurrentNode = iPath[BotIndex][pBot->bot_pathid]; // Node we are heading for
        int iNextNode = iPath[BotIndex][pBot->bot_pathid + 3];
       
        if (iCurrentNode < 0)
        {
        // When f_cover_time is > gpGlobals, we are taking cover
        // so we 'wait'
        if (pBot->f_cover_time > gpGlobals->time)
        {
            if (pBot->pBotEnemy != NULL)
                pBot->vHead = pBot->v_enemy;

            pBot->f_wait_time = RANDOM_FLOAT(1.5, 6.0);
            pBot->f_cover_time = gpGlobals->time;

            if (RANDOM_LONG(0,100) < 50)
                pBot->f_hold_duck = gpGlobals->time + RANDOM_FLOAT(1.0, 4.0);
           
        }
        else
        {
            if (pBot->iPathFlags == PATH_CAMP)
            {
//                UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: I CAMP!!!!!.\n");
                // Camp
                pBot->f_camp_time = gpGlobals->time + RANDOM_FLOAT(10, 30);
                pBot->iPathFlags = PATH_DANGER;
            }
            else
            {
                // Set on camp mode
                if (RANDOM_LONG(0,100) < pBot->ipCampRate)
                    pBot->iPathFlags = PATH_CAMP;

            }

            // reached the end
            pBot->iGoalNode = -1;
            pBot->bot_pathid = -1;               
        }
            return;

        }

        // Near Node       
    bool bNearNode=false;
    bool bReachNode=false;

    Vector vEdict, vNode;
    vEdict=pBot->pEdict->v.origin;
    vNode=Nodes[iCurrentNode].origin;

    // Make same height
    vEdict.z=0;
    vNode.z=0;     

    TraceResult tr;
    Vector vOrigin=pBot->pEdict->v.origin;

    //Using TraceHull to detect de_aztec bridge and other entities.
    //DONT_IGNORE_MONSTERS, we reached it only when there are no other bots standing in our way!
    UTIL_TraceHull(vOrigin, vNode, dont_ignore_monsters, point_hull, pBot->pEdict, &tr);

    // if nothing hit:
    if (tr.flFraction >= 1.0)
        bReachNode=true;
   
    if (pBot->f_strafe_speed < gpGlobals->time)
        pBot->vBody = Nodes[iCurrentNode].origin;

          if (FUNC_IsOnLadder(pBot->pEdict))
        {
                // Set touch radius       
                pBot->f_strafe_speed = 0.0;                                        // we may not strafe
                pBot->f_move_speed = (pBot->f_max_speed/2); // move speed
                //pBot->pEdict->v.button |= IN_DUCK;                        // duck

                // Look at the waypoint we are heading to.
                  pBot->vHead=Nodes[iCurrentNode].origin;
                pBot->vBody=Nodes[iCurrentNode].origin;
               
                // Press forward key to move on ladder
                UTIL_BotPressKey(pBot, IN_FORWARD);               

        if (BotShouldDuck(pBot))
        {
//            UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: Ladder; I should duck.\n");
            UTIL_BotPressKey(pBot, IN_DUCK);
            pBot->f_hold_duck = gpGlobals->time + 0.2;
        }

        if (func_distance(vEdict, vNode) < 25)
            bNearNode=true;
        }
    else
    {
        if (Nodes[iCurrentNode].iNodeBits & BIT_LADDER)
        {
            // Going to a ladder waypoint
            if (func_distance(vEdict, vNode) < 25)
                bNearNode=true;
        }
        else
        {
            if (func_distance(vEdict, vNode) < 40)
                bNearNode=true;
        }

        // If we should duck, duck.
        if (BotShouldDuck(pBot))
        {
            UTIL_BotPressKey(pBot, IN_DUCK);
            pBot->f_hold_duck = gpGlobals->time + 0.2;
        }
           
    }


        if (bNearNode)       
    {
                pBot->bot_pathid++;       
        // Calculate vis table from here
        vis_calculate(iCurrentNode);
    }
       
    // TODO TODO TODO Water Navigation


    // NO ENEMY, CHECK AROUND AREA
    if (pBot->pBotEnemy == NULL)
    {       
        if (iNextNode > -1)
            pBot->vHead = Nodes[iNextNode].origin;
        else
            pBot->vHead = Nodes[iCurrentNode].origin;
    }


       
       
        // Jump over possible gaps, this is when a node is floating..
        /*
        if (node_float(Nodes[iCurrentNode].origin))
        {
                // check if we are going to 'fall'.
                TraceResult tr;
                Vector v_jump, v_source, v_dest;
                edict_t *pEdict = pBot->pEdict;

                // convert current view angle to vectors for TraceLine math...

                v_jump = pEdict->v.v_angle;
                v_jump.x = 0;  // reset pitch to 0 (level horizontally)
                v_jump.z = 0;  // reset roll to 0 (straight up and down)

                UTIL_MakeVectors( v_jump );

                // use center of the body first...

                // check if the bot is going to 'fall'
                v_source = pEdict->v.origin + Vector(0,0,32);
                v_dest = v_source + gpGlobals->v_forward * 45;

                v_dest = v_dest - Vector(0, 0, 90);

                // trace a line forward at duck height...
                UTIL_TraceLine( v_source, v_dest, dont_ignore_monsters,
                pEdict->v.pContainingEntity, &tr);

                //WaypointDrawBeam(listenserver_edict, v_source, v_dest, 15, 0, 255, 255, 255, 255, 5);

                // if trace DID NOT hit something, return FALSE
                if (tr.flFraction >= 1.0 && pBot->f_jump_time < gpGlobals->time)
                {
                        // we are going to fall
                        // JUMP baby
                        UTIL_BotPressKey(pBot, IN_JUMP);
                        pBot->f_jump_time = gpGlobals->time + 0.3;
                        UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: Connected jump i think.\n");
                }
               
        }
        */

    // When longer not stuck for some time we clear stuff
    if (pBot->fNotStuckTime + 2 < gpGlobals->time)
    {
        pBot->iDuckTries=0;
        pBot->iJumpTries=0;
    }

    // When we have to many duck/jump tries, we reset path stuff
    if (pBot->iDuckTries > 7 || pBot->iJumpTries > 7)
    {
        pBot->bot_pathid = -1; // reset path
        return;
    }

        bool bShouldMove=false;
        if (pBot->f_freeze_time+2  < gpGlobals->time
          && pBot->f_stuck_time  < gpGlobals->time
        && pBot->f_camp_time    < gpGlobals->time
        && pBot->f_wait_time    < gpGlobals->time
        && pBot->f_c4_time      < gpGlobals->time
        && pBot->f_jump_time+0.1< gpGlobals->time)
                bShouldMove=true; // according to our timers we should move

        // When not moving (and        we should move):
        // - learn from mistakes
        // - unstuck
        // - go back in path...
        if (moved_distance < 2.0)
        {
                cBot *pBotStuck = search_near_players(pBot);
                bool bPlayersNear = BOOL_search_near_players(pBot);
        pBot->fNotStuckTime=gpGlobals->time;

        // JUMP & DUCK
        if (BotShouldJump(pBot))
        {
            //UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: I should jump.\n");
            UTIL_BotPressKey(pBot, IN_JUMP);
            // stay focussed with body and head to this vector
            pBot->vHead=Nodes[iCurrentNode].origin;
            pBot->vBody=Nodes[iCurrentNode].origin;               
            pBot->iJumpTries++;
        }
        else if (BotShouldDuck(pBot))
        {
            //UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: I should duck.\n");
            UTIL_BotPressKey(pBot, IN_DUCK);
            pBot->f_hold_duck = gpGlobals->time + 0.2;
            pBot->iDuckTries++;
        }
        else
        {
            // check if the connection we want is going up
            // - when going up
            // - when we should move
            // - when no players are close (could be blocked by them, do not learn stupid things)
            if (Nodes[iCurrentNode].origin.z > pBot->pEdict->v.origin.z &&
                bShouldMove &&
                pBotStuck == NULL)
            {
                // check if the next node is floating
                if (node_float(Nodes[iCurrentNode].origin))
                {
                    // it floats, cannot reach
                    // Our previous node in the list sent us here, so disable that connection
                    int iCurrentPathId = pBot->bot_pathid - 1;
                    int iPrevNode = -1;
                    if (iCurrentPathId > -1)
                        iPrevNode = iPath[BotIndex][iCurrentPathId];

                    // Find the neighbour connection, and remove it
                    for (int n=0; n < MAX_NEIGHBOURS; n++)
                        if (Nodes[iPrevNode].iNeighbour[n] == iCurrentNode)
                        {
                            Nodes[iPrevNode].iNeighbour[n] = -1; // disable this connection
                            //UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: Fixed connection ------- #1.\n");
                            // be sure we reset our path stuff
                            pBot->bot_pathid = -1;
                            break; // get out
                        }
                }
                else
                {
                    // When this node is not floating, it could be something we should jump to.
                    // somehow we cannot reach that node, so we fix it here.
                    int iCurrentPathId = pBot->bot_pathid - 1;
                    int iPrevNode = -1;                               
                    if (iCurrentPathId > -1)
                        iPrevNode = iPath[BotIndex][iCurrentPathId];

                    // Find the neighbour connection, and remove it
                    for (int n=0; n < MAX_NEIGHBOURS; n++)
                        if (Nodes[iPrevNode].iNeighbour[n] == iCurrentNode)
                        {
                            Nodes[iPrevNode].iNeighbour[n] = -1; // disable this connection
                            //UTIL_ClientPrintAll(HUD_PRINTNOTIFY, "NodeMachine: Fixed connection ------ #2.\n");
                            // be sure we reset our path stuff                           
                            break; // get out
                        }                                               

//                    pBot->iGoalNode = -1;
                    pBot->bot_pathid = -1;
                }       

            }
            // Any other connections to 'learn'?
            // Check if we are stuck with other players
            if (bPlayersNear && bShouldMove)
            {
                // Depending on how the other bot looks, act
                // pBotStuck -> faces pBot , do same
                // pBotStuck -> cannot see pBot, do opposite                       
                // Check if pBotStuck can see pBot (pBot can see pBotStuck!)                       
                int angle_to_player = 40;
               
                if (pBotStuck != NULL)
                    angle_to_player = FUNC_InFieldOfView(pBot->pEdict, (pBotStuck->pEdict->v.origin - pBot->pEdict->v.origin));
               
                bool bReverse=false;
                if (angle_to_player > 45)
                    bReverse=true;

                // Method: both bots do exactly the same?
                if (RANDOM_LONG(0,100) < 50)
                {
                    pBot->f_strafe_speed = pBot->f_max_speed;
                    if (pBotStuck != NULL)
                        if (bReverse)
                            pBotStuck->f_strafe_speed = pBotStuck->f_max_speed;
                        else
                            pBotStuck->f_strafe_speed = -pBotStuck->f_max_speed;
                }
                else
                {
                    pBot->f_strafe_speed = -pBot->f_max_speed;
                    if (pBotStuck != NULL)
                        if (bReverse)
                            pBotStuck->f_strafe_speed = pBotStuck->f_max_speed;
                        else
                            pBotStuck->f_strafe_speed = -pBotStuck->f_max_speed;
                }

                pBot->f_strafe_time = gpGlobals->time + 1.6;
                pBot->f_goback_time = gpGlobals->time + 0.8;

                if (pBotStuck != NULL)
                {
                    pBotStuck->f_strafe_time = gpGlobals->time + 0.8;
                    pBot->f_stuck_time = gpGlobals->time + 0.2;
                    pBotStuck->f_stuck_time = gpGlobals->time + 0.2;

                    if (bReverse)
                    {
                        pBotStuck->f_goback_time = gpGlobals->time;
                        pBotStuck->f_move_speed = pBotStuck->f_max_speed;
                    }
                    else
                        pBotStuck->f_goback_time = gpGlobals->time + 0.8;

                }
               
                if (RANDOM_LONG(0,100) < 50)
                {
                    UTIL_BotPressKey(pBot, IN_JUMP);
                   
                    if (pBotStuck != NULL)
                        UTIL_BotPressKey(pBotStuck, IN_DUCK);
                   
                }
                else
                {
                    UTIL_BotPressKey(pBot, IN_DUCK);
                   
                    if (pBotStuck != NULL)
                        UTIL_BotPressKey(pBotStuck, IN_JUMP);
                }
            }
            else if (bShouldMove)
            {
                // we are stuck by 'world', we go back one step
                pBot->bot_pathid--;                       
                pBot->f_stuck_time = gpGlobals->time + 0.2;

                // When its not reachable disable goal
              //  if (bReachNode == false)
              //    pBot->iGoalNode = -1;

                if (RANDOM_LONG(0,100) < 50)
                {
                    //pBot->iGoalNode = -1;
                    pBot->bot_pathid = -1;                           
                }
            }
        } // Cannot jump or duck
    } // Moved distance < 2.0
        // check body
        //check_body_infront(pBot);
}
btw, located in NodeMachine.cpp (for your convinience)

Pierre-Marie Baty 01-01-2004 20:57
Re: what's your pathwalking algorithm
 
om** what a long function, mine is 5 times shorter !!! :D

the bit to get stuck bots to unstuck each other is well thought anyway :)

BTW thanks, I just realized why I shouldn't let my bots skip navnodes at all. I'll keep optimizing the current method and I'll post my BotWalkPath() function once it'll be correctly debugged.

@$3.1415rin 01-01-2004 21:15
Re: what's your pathwalking algorithm
 
I dont skip waypoints neither ... but you know, the practical things of joebot xp are still very beta ...

Code:
void CBVNP_HLDM_MovePath::evaluate(list<CGoal> *pGoals,CPerceipt* p){
        float fLastDist;
       
        switch(m_iState){
        case 0:{                        // waypoint based moving
                if(!m_CurrWay.m_iCount){
                        // no way to move along
                        m_iCurrWP = -1;

                        // let's camp for a second - hackhack
                        m_pBot->m_pCamp->campO(1);
                        return;
                }
               
                if(m_iCurrWP >-1){        // it's a valid waypoint
                        fLastDist = (g_Map.m_Waypoints[m_iCurrWP].m_VOrigin - m_pBot->m_pPlayer->getOrigin()).length();
                }
                else{        // no waypoint to run to set yet ?
                        if(!m_CurrWay.m_iCount){
                                reset();
                        }
                        else{
                                m_fLastDist = 10000;
                                initPath();
                               
                                m_bSetTarget = true;
                                execute(0);
                        }
                        return;
                }
               
                if(m_fLastDist < fLastDist){        // we are moving away from current waypoint we aim to
                        if(fLastDist > 75.f){
                                m_bSetTarget = true;
                                execute(0);
                                //m_pAction->runTo(g_Map.m_Waypoints[m_iCurrWP].m_VOrigin);
                        }
                        else{
                                if((m_iCurrWP = m_CurrWay.getNext()) != -1){
                                        // so we have a subsequent waypoint to go to
                                        m_fLastVisitedWP = g_pGame->getTime();
                                       
                                        m_bSetTarget = true;
                                        execute(0);
                                        //m_pAction->lookTo(g_Map.m_Waypoints.m_Waypoints[iRun2].m_VOrigin);
#ifdef DEBUGMESSAGES                               
                                        //if(listenserver_edict)UTIL_DrawBeam(listenserver_edict,g_Map.m_Waypoints.m_Waypoints[m_iCurrWP].m_VOrigin,m_pPlayer->getOrigin(),10,10,255,255,255,255,20);
                                        //if(listenserver_edict)UTIL_DrawBeam(listenserver_edict,listenserver_edict->v.origin,m_pPlayer->getOrigin(),10,10,255,255,255,255,20);
#endif
                                       
                                        fLastDist = 10000;
                                }
                                else{
                                        // we are at the end of the path
                                        if(m_bMove2Origin){
                                                m_iState = 1;                // go to direct moving state
                                                m_bSetTarget = true;
                                                m_fLastVisitedWP = g_pGame->getTime();
                                        }
                                        else{
                                                if(m_pDReached){                        // call callback function
                                                        m_pDReached->onReachedDestination(m_pBot->m_pPlayer);
                                                }
                                                reset();
                                        }
                                }
                        }
                }
                /*else{
                        if(m_pBot->m_pPlayer->getVelocity().length() > 100){
                                Vector VAim;
                                switch(m_iState){
                                case 0:{
                                        VAim = g_Map.m_Waypoints[m_iCurrWP].m_VOrigin;
                                          }break;
                                case 1:{
                                        VAim = m_VGoal;
                                          }break;
                                }
                                Vector Cross = CrossProduct(m_pBot->m_pPlayer->getVelocity(),VAim-m_pBot->m_pPlayer->getOrigin());
                                float fError = Cross.length() / m_pBot->m_pPlayer->getVelocity().length();
                                char szTemp[20];
                                sprintf(szTemp,"%f",fError);
                                m_pBot->fakeClientCommand("say",szTemp);
                        }
                }*/
                if(fabs(m_fLastExecution - g_pGame->getTime()) > .5f){
                        m_bSetTarget = true;
                        execute(0);
                }
                m_fLastDist = fLastDist;
                  }
                break;
        case 1:{
                fLastDist = (m_VGoal - m_pBot->m_pPlayer->getOrigin()).length();
                if(m_fLastDist < fLastDist){
                        if(fLastDist > 75){
                                m_bSetTarget = true;
                        }
                        else{
                                // reached location
                                if(m_pDReached){                        // call callback function
                                        m_pDReached->onReachedDestination(m_pBot->m_pPlayer);
                                }
                                reset();
                        }
                }
                execute(0);
                m_fLastDist = fLastDist;
                  }
                break;
        }
       
        return;
}

void CBVNP_HLDM_MovePath::execute(CGoal *pGoal){
        //if(listenserver_edict)UTIL_DrawBeam(listenserver_edict,Vector(0,0,0),m_pBot->m_pPlayer->getOrigin(),10,10,0,0,255,255,20);
        if(m_bSetTarget ||
                m_iState ||                // set move direction each think frame when moving without waypoints.
                m_fLastExecution != m_pBot->m_fCalledBV){                // last time this move behaviour wasnt called, so set the move target again
                switch(m_iState){
                case 0:{
                        if(m_iCurrWP != -1){
                                m_pBot->m_pAction->runTo(g_Map.m_Waypoints[m_iCurrWP].m_VOrigin);
                                m_bSetTarget = false;
#ifdef DEBUGMESSAGES
                                //if(listenserver_edict)UTIL_DrawBeam(listenserver_edict,g_Map.m_Waypoints.m_Waypoints[m_iCurrWP].m_VOrigin,m_pBot->m_pPlayer->getOrigin(),10,10,255,255,255,255,20);
#endif
                        }
                        else{
                                reset();
                        }
                          }break;
                case 1:{
                        m_pBot->m_pAction->runTo(m_VGoal);
                          }break;
                }
        }
        m_fLastExecution = g_pGame->getTime();
}

void CBVNP_HLDM_MovePath::getResult(AStarBase *p,CCallback_onReachedDestination *pDReached){
        if(p){
                p->getResult(m_CurrWay);
                m_iTargetWP = p->getDestination();
        }
        else
                m_iTargetWP = -1;

        m_iState = 0;
       
        m_iCurrWP = -1;
       
        m_pDReached = pDReached;
       
        // check if we should run there without taking the waypoints
        if((m_VGoal-m_pBot->m_pPlayer->getOrigin()).length() < 250.f
                &&m_bMove2Origin){
                m_iState = 1;
        }
        else{
                if(!m_CurrWay.m_iCount
                        && !m_bMove2Origin){
                        m_pBot->m_LGoals.finishedMove();
                }
        }
}

void CBVNP_HLDM_MovePath::initPath(void){
        // simplest method would be
        // m_iCurrWP = m_CurrWay[0];
        // but we wanna check which would be the best first waypoint

        if(m_CurrWay.m_iCount <= 2){
                m_iCurrWP = m_CurrWay.m_piIndices[0];
        }
        else{
                Vector V1,
                        V2,
                        VNow = m_pBot->m_pPlayer->getOrigin() + m_pBot->m_pPlayer->getVelocity() * .3f;

                float fLength0,fLength1;

                V1 = g_Map.m_Waypoints[m_CurrWay.m_piIndices[0]].m_VOrigin - VNow;
                fLength0 = V1.length();
                V2 = g_Map.m_Waypoints[m_CurrWay.m_piIndices[1]].m_VOrigin - g_Map.m_Waypoints[m_CurrWay.m_piIndices[0]].m_VOrigin;
                fLength1 = (g_Map.m_Waypoints[m_CurrWay.m_piIndices[1]].m_VOrigin - VNow).length();

                if(fLength1 < fLength0                                // check if second waypoint is already nearer
                        ||DotProduct(V1,V2) < .0f){                // check if we would have to go back
                        m_iCurrWP = m_CurrWay.m_piIndices[1];
                }
                else{
                        m_iCurrWP = m_CurrWay.m_piIndices[0];
                }
        }

        // check direct move to
        if(m_bMove2Origin
                && m_CurrWay.m_iCount >= 2){
                Vector VN,
                        VNN;

                while(m_CurrWay.m_iCount >= 2){
                        VN = (g_Map.m_Waypoints[m_CurrWay.m_piIndices[m_CurrWay.m_iCount - 1]].m_VOrigin - m_VGoal).normalize();
                        VNN = (g_Map.m_Waypoints[m_CurrWay.m_piIndices[m_CurrWay.m_iCount - 1]].m_VOrigin - g_Map.m_Waypoints[m_CurrWay.m_piIndices[m_CurrWay.m_iCount - 2]].m_VOrigin).normalize();
                        if(DotProduct(VNN,VN) < 0.f){
                                m_CurrWay.m_iCount --;
                        }
                        break;
                }
        }
}

void CBVNP_HLDM_MovePath::reset(void){
        m_CurrWay.reset();
        m_iState = 0;                // we wanna run go waypoints initially
        m_bMove2Origin = false;
        m_iCurrWP = -1;
        m_fLastDist = 10000;
        m_fLastVisitedWP = g_pGame->getTime();
        m_bSetTarget = false;
        m_pDReached = 0;
       
        m_pBot->m_LGoals.finishedMove();
}
huh, that's not just little code neither :)

and for avoid getting stuck it's until now just this, but there are already structures to handle connections which are often not usable, so the pathfinder can take this into account.

Code:
void CBVNP_HLDM_AvoidStuckWP::evaluate(list<CGoal> *pGoals,CPerceipt* p){
        if( (!m_pBot->m_pMovePath->m_CurrWay.m_iCount && m_pBot->m_pMovePath->m_iState == 0) )
                return;
       
        if(m_pBot->m_pMovePath->m_fLastVisitedWP+5 > g_pGame->getTime())
                return;
       
        int iPriority = (g_pGame->getTime() - m_pBot->m_pMovePath->m_fLastVisitedWP)*4 + 50;
       
        pGoals->push_front(CGoal(iPriority,CGoal::GT_MOVE,this,0));
        return;
}

void CBVNP_HLDM_AvoidStuckWP::execute(CGoal *pGoal){
        m_fLastExecution = g_pGame->getTime();
       
        m_pBot->m_pMovePath->reset();
}

Phreak 02-01-2004 11:53
Re: what's your pathwalking algorithm
 
I just want to say, WOAH. You thought about this a hell of a lot more than I did. Nice...


Phreak

koraX 05-01-2004 18:46
Re: what's your pathwalking algorithm
 
Hmm I'm using A* algorithm for finding paths.
My bots are auto-waypointing, cause my task is to develop an "highly intelligent" 8D bots and navmeshes are cheating IMO because bot's will create them from map file and not from "seeing" and "exploring"

After path is found, it is returned in array (array of pointers to my CWaypoint class). Bot than go to first waypoint in array (actually last waypoint, cause path is upside down in my array) and when he came there, he goes to another waypoint in array.
I have a FIFO stack in bot's "Navigation Cognitive subsystem" and I place there tasks what bot should do (go there, connect this waypoint with this, create waypoint there) and one of task is GOPATH which is : take first waypoint from path, go there and place new GOPATH task into stack where new path does not have waypoint you are going to now. o_O

My bot auto-waypoined de_aztec an created about 800 waypoint (this is early stage of my auto-waypointing technique, I plan to reduce count of waypoints to max 500 (by merging waypoints into larger). With this waypoint count, 'random' A* pathfinding never took more than 15ms (I was checking this by ::GetTickCount() windows API function. It was either 0 or 15, strange :|) I want to ask those who work with A* if this is fast or slow.

The path can't fail (It stands and falls on waypoints). If it fails from whatever reason (example New Round while bot walking along path) my stack in navigation subsystem is 'flushed' so path is forgotten.

-- Jozef Wagner

@$3.1415rin 05-01-2004 20:17
Re: what's your pathwalking algorithm
 
15ms ... on what kind of hardware ?

getTickCount isnt the best choice, since it's normally using a counter which is running at @ 1Mhz I think ... so no good choice. use something like this to read the number of cpu cycles instead. then you need of course to clean the result from effects of your multitasking environment

Code:
_int64 CTime::getTime(){
        _int64 rdtsc_time;
        __asm
        {
                rdtsc
                mov dword ptr [rdtsc_time],eax
                mov dword ptr [rdtsc_time+4],edx
        }
        return rdtsc_time;
}
( btw, thx for william for this :D )

koraX 05-01-2004 20:30
Re: what's your pathwalking algorithm
 
2GB Athlon (1.6 real), 512RAM, 100fps in CS

I thing that 15ms values are due to some background program in my OS, 'cause it is never 14ms or 16ms, only 0 or 15.

I used the function you posted here. Does it return the number of cpu cycles or what ? I get most of time < 100000 but sometimes I get more than milion (always 0 with ::GetTickCount).
When I get 15 with GetTickCount, I get more than 10 milions obviously o_O

thanx for help

@$3.1415rin 05-01-2004 23:47
Re: what's your pathwalking algorithm
 
yes, it returns the number of cpu cycles elapsed from starting the cpu ... you have of course to check your cpu frequency to make sensemaking measurements ...

argh, no attaching of cpp files allowed ....

Pierre-Marie Baty 06-01-2004 00:37
Re: what's your pathwalking algorithm
 
darn, I gotta have a look in the config panel of this forum to see if we can attach .cpp and .dsp files :)


All times are GMT +2. The time now is 13:53.
Page 1 of 2 1 2
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.