Few quetions about astar waypoints pathfinding

[RobsoN]

Hello, I'm new in pathfinding. I basically know how it is working in a netting thing (1block = node), but I have no idea how to implement that into cod2. I want to try easiest method i.e. astar waypoints. I did my pathfinding script but it was really messed up (It required a lot of things to add into script manually). I have few questions about that:
1. What exactly is a node (in cod2 ver)?
2. How can I check on which node entity is?
3. What do I need to add manually into script if i would use astar waypoint algorithm (node origin?, node connections? waypoint origin?, waypoint connections?)

Regards RobsoN.

[Tally]

Hello, I'm new in pathfinding. I basically know how it is working in a netting thing (1block = node), but I have no idea how to implement that into cod2. I want to try easiest method i.e. astar waypoints. I did my pathfinding script but it was really messed up (It required a lot of things to add into script manually). I have few questions about that:
1. What exactly is a node (in cod2 ver)?
2. How can I check on which node entity is?
3. What do I need to add manually into script if i would use astar waypoint algorithm (node origin?, node connections? waypoint origin?, waypoint connections?)

1. a "node" is a point in a map which AI can intersect with. In COD terms it is a spawn_struct which an AI will follow.

2. If I take your meaning correctly, you are asking how to check which node an entity should follow. For that you need an algorithm which determines which node will be best for the AI. So, I will post Pezzalucifer's astarSearch() function from Pezbot:

		////////////////////////////////////////////////////////////
// AStarSearch, performs an astar search
///////////////////////////////////////////////////////////
/*

    The best-established algorithm for the general searching of optimal paths is A* (pronounced “A-star”). 
    This heuristic search ranks each node by an estimate of the best route that goes through that node. The typical formula is expressed as:

    f(n) = g(n) + h(n)

    where: f(n) is the score assigned to node n g(n) is the actual cheapest cost of arriving at n from the start h(n) is the heuristic 
    estimate of the cost to the goal from n 

    priorityqueue Open
    list Closed


    AStarSearch
       s.g = 0  // s is the start node
       s.h = GoalDistEstimate( s )
       s.f = s.g + s.h
       s.parent = null
       push s on Open
       while Open is not empty
          pop node n from Open  // n has the lowest f
          if n is a goal node 
             construct path 
             return success
          for each successor n' of n
             newg = n.g + cost(n,n')
             if n' is in Open or Closed,
              and n'.g < = newg
               skip
             n'.parent = n
             n'.g = newg
             n'.h = GoalDistEstimate( n' )
             n'.f = n'.g + n'.h
             if n' is in Closed
                remove it from Closed
             if n' is not yet in Open
                push n' on Open
          push n onto Closed
       return failure // if no path found 
*/
AStarSearch( startWp, goalWp )
{
    pQOpen = [];
    pQSize = 0;
    closedList = [];
    listSize = 0;
    s = spawnstruct();
    s.g = 0; //start node
    s.h = distance( level.waypoints[startWp].origin, level.waypoints[goalWp].origin );
    s.f = s.g + s.h;
    s.wpIdx = startWp;
    s.parent = spawnstruct();
    s.parent.wpIdx = -1;
  
    //push s on Open
    pQOpen[pQSize] = spawnstruct();
    pQOpen[pQSize] = s; //push s on Open
    pQSize++;

    //while Open is not empty  
    while( !PQIsEmpty(pQOpen, pQSize) )
    {
        //pop node n from Open  // n has the lowest f
        n = pQOpen[0];
        highestPriority = 9999999999;
        bestNode = -1;
        for( i = 0; i < pQSize; i++ )
        {
            if( pQOpen[i].f < highestPriority )
            {
                bestNode = i;
                highestPriority = pQOpen[i].f;
            }
        } 
    
        if( bestNode != -1 )
        {
            n = pQOpen[bestNode];
            //remove node from queue    
            for( i = bestNode; i < pQSize-1; i++ )
                pQOpen[i] = pQOpen[i+1];
            
            pQSize--;
        }
        else
        {
            return -1;
        }
    
        //if n is a goal node; construct path, return success
        if( n.wpIdx == goalWp )
        { 
            x = n;
            for( z = 0; z < 1000; z++ )
            {
                parent = x.parent;
                if( parent.parent.wpIdx == -1 )
                {
                    return x.wpIdx;
                }

                x = parent;
            }

            return -1;      
        }

        //for each successor nc of n
        for( i = 0; i < level.waypoints[n.wpIdx].childCount; i++ )
        {
            //newg = n.g + cost(n,nc)
            newg = n.g + distance( level.waypoints[n.wpIdx].origin, level.waypoints[level.waypoints[n.wpIdx].children[i]].origin );
      
            //if nc is in Open or Closed, and nc.g <= newg then skip
            if( PQExists( pQOpen, level.waypoints[n.wpIdx].children[i], pQSize ) )
            {
                //find nc in open
                nc = spawnstruct();
                for( p = 0; p < pQSize; p++ )
                {
                    if( pQOpen[p].wpIdx == level.waypoints[n.wpIdx].children[i] )
                    {
                        nc = pQOpen[p];
                        break;
                    }
                }
       
                if( nc.g <= newg )
                {
                    continue;
                }
            }
            else if( ListExists( closedList, level.waypoints[n.wpIdx].children[i], listSize ) ) 
            {
                //find nc in closed list
                nc = spawnstruct();
                for( p = 0; p < listSize; p++ )
                {
                    if( closedList[p].wpIdx == level.waypoints[n.wpIdx].children[i] )
                    {
                        nc = closedList[p];
                        break;
                    }
                }
        
                if( nc.g <= newg )
                {
                    continue;
                }
            }
      
            nc = spawnstruct();
            nc.parent = spawnstruct();
            nc.parent = n;
            nc.g = newg;
            nc.h = distance( level.waypoints[level.waypoints[n.wpIdx].children[i]].origin, level.waypoints[goalWp].origin );
            nc.f = nc.g + nc.h;
            nc.wpIdx = level.waypoints[n.wpIdx].children[i];

            //if nc is in Closed,
            if( ListExists( closedList, nc.wpIdx, listSize ) )
            {
                //remove it from Closed
                deleted = false;
                for( p = 0; p < listSize; p++ )
                {
                    if( closedList[p].wpIdx == nc.wpIdx )
                    {
                        for( x = p; x < listSize-1; x++ )
                        {
                            closedList[x] = closedList[x+1];
                        }
                        deleted = true;
                        break;
                    }
                    
                    if( deleted )
                    {
                        break;
                    }
                }
                
                listSize--;
            }
        
            //if nc is not yet in Open, 
            if( !PQExists( pQOpen, nc.wpIdx, pQSize ) )
            {
                //push nc on Open
                pQOpen[pQSize] = spawnstruct();
                pQOpen[pQSize] = nc;
                pQSize++;
            }
        }
      
        //Done with children, push n onto Closed
        if( !ListExists( closedList, n.wpIdx, listSize ) )
        {
            closedList[listSize] = spawnstruct();
            closedList[listSize] = n;
            listSize++;
        }
    }
} 
	

3. To setup your wayfinding, you simply add script_origins to a map. This is the method used by both Meatbot and Pezbot. Each script_origin becomes part of the astar waypoint struct array, and the AI are guided through them using various procedures to determine their paths.

My advice for you is to use either Meatbot or Pezbot as a starting point in your AI pathfinding experiments. I knew nothing at all about pathfinding before I sunk my teeth into Pezbot, but it was blooding interesting. Pezbot in particular has some really cool utility functions to help you develop your code. They save me heaps of time and energy.