.:: Bots United ::.  
filebase forums discord server github wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Bot Coding
General Bot Coding See what a pain it is to get those little mechs shooting around

Reply
 
Thread Tools
what's your pathwalking algorithm
Old
  (#1)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default what's your pathwalking algorithm - 01-01-2004

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 ?



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#2)
stefanhendriks
RealBot Author
 
stefanhendriks's Avatar
 
Status: Offline
Posts: 3,088
Join Date: Nov 2003
Location: Netherlands
Default Re: what's your pathwalking algorithm - 01-01-2004

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)


Author of RealBot, "Arrakis" and "Dune 2 - The Maker" | co-Founder of Bots-United | Fundynamic | Blog | E-Mail me
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#3)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default Re: what's your pathwalking algorithm - 01-01-2004

om** what a long function, mine is 5 times shorter !!!

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.



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#4)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: what's your pathwalking algorithm - 01-01-2004

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();
}


  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#5)
Phreak
Guest
 
Status:
Posts: n/a
Default Re: what's your pathwalking algorithm - 02-01-2004

I just want to say, WOAH. You thought about this a hell of a lot more than I did. Nice...


Phreak

Last edited by Phreak; 02-01-2004 at 13:03..
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#6)
koraX
Member
 
koraX's Avatar
 
Status: Offline
Posts: 145
Join Date: Jan 2004
Location: Slovak Republic
Default Re: what's your pathwalking algorithm - 05-01-2004

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


kXBot
koraX's utils
- see my homepage for other projects (OpenGL CSG Editor, FAT16 Sim, NNetwork Sim, ...)

Last edited by koraX; 05-01-2004 at 20:06..
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#7)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: what's your pathwalking algorithm - 05-01-2004

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 )


  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#8)
koraX
Member
 
koraX's Avatar
 
Status: Offline
Posts: 145
Join Date: Jan 2004
Location: Slovak Republic
Default Re: what's your pathwalking algorithm - 05-01-2004

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


kXBot
koraX's utils
- see my homepage for other projects (OpenGL CSG Editor, FAT16 Sim, NNetwork Sim, ...)

Last edited by koraX; 05-01-2004 at 21:58..
  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#9)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: what's your pathwalking algorithm - 06-01-2004

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 ....


  
Reply With Quote
Re: what's your pathwalking algorithm
Old
  (#10)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default Re: what's your pathwalking algorithm - 06-01-2004

darn, I gotta have a look in the config panel of this forum to see if we can attach .cpp and .dsp files



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com