Few quetions about astar waypoints pathfinding [Archive]

Tally

23rd February 2014, 19:32

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.