Few quetions about astar waypoints pathfinding

Quote:

Originally Posted by 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?)

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:

PHP Code:

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