3D Astar Pathing

Title: Using A* for 3D Pathing in Q2
Difficulty: Fairly Difficult
By: Maj.Bitch
Email: peblair@frontier.net
Date: 09-26-99
Note: Please give credit where credit is due.
======================================================

I spent quite a bit of time searching the web for stuff to
bootstrap me into the 3D pathing realm but I didn't find
much. There were some good things but, as always, in the
end I had to figure it out myself. Wasn't too difficult
but took some time. So, for all the other coders out there
I've decided to put together a tutorial in implementing the
A* (pronounced A-Star) algorithm for path routing in Q2.

Okay, I'm gonna spend some time upfront talking about this
algorithm for it was developed in the 60's and has been the
subject of quite a bit of research in the computer science
fields and has proven to be the premier routing algorithm
of its kind. After reading this tutorial, you'll see why.

NOTE: If you don't know linked lists, then I'll tell you upfront
that most, if not all, of this tutorial won't make any sense to
you...

What does the A* algorithm do?

The A* algorithm does a bunch of stuff to find the shortest path
from start to destination by conducting a pre-determined search
on neighboring locations (nodes) and accumulating a cost for
each node along the way. The path with the least total cost from
start to destination is determined to be the shortest (and best)
path to take. The implementation uses a Stack (for temp storage
of past nodes for backtracking) and an OPEN list (for temp storage
of nodes not yet searched) and a CLOSED list (for temp storage of
nodes already search so you don't go over them again and again).
The Stack and OPEN/CLOSED lists are Linked Lists created dynamically
as the search for the shortest path moves merrily along. In the end,
a linked list (in reverse order) is returned which contains the path
from end to start. That right.. End to start because that's the way
it works. So, when the path is returned you have to copy the linked
nodes in reverse order to get the path from start to end. You'll see
why this is as you begin to understand what is happening.

=======================================================================
=======================================================================

What does the data structure look like?

You'll need to have this struct NODE declared.
<c code>
#define NUMCHILDS 6 // I'll explain this later...

struct NODE {
  int   g; // how far we've already gone from start to here
  float h; // heuristic estimate of how far is left
  float f; // is total cost (estimated) from start to finish
  // ANYTHING YOU WANT GOES HERE 
  // DEPENDING ON YOUR IMPLEMENTATION 
  struct NODE *Child[NUMCHILDS];
  struct NODE *PrevNode;
  struct NODE *NextNode;
};
</c code>
So, ALL of the above fields YOU MUST HAVE but you can add other fields
too. For the implementation below, I will add a field called nodenum so
my struct NODE looks like this.
<c code>
struct NODE {
  int   g; // how far we've already gone from start to here
  float h; // heuristic estimate of how far is left
  float f; // is total cost (estimated) from start to finish
  int nodenum; // My own field here...
  struct NODE *Child[NUMCHILDS];
  struct NODE *PrevNode;
  struct NODE *NextNode;
};
</c code>
=======================================================================
=======================================================================

What does my own structure look like?

You can have any kind of structure you want which contains your
own information about the map. For this tutorial, I will use
the following:
<c code>
typedef struct {
  int nodenum;   // index number of this node
  vec3_t origin; // location in [x,y,z]
} node_t;

node_t node;
int numnodes; // Number of node[]
</c code>
Once I know how many nodes I've got (using whatever technique you
want) then, I create my huge node struct array by doing this:
<c code>
   node=(node_t *)malloc(numnodes*sizeof(node_t));
</c code>
So, I've gotten all the information about all the nodes that I need
for pathing. You'll have to figure out what works best for your
own implementation.

I then have a huge array of node[0..numnodes-1] with node[i].nodenum=i;

Note that my huge array of nodes is sequential and I'm using the nodenum
for each node in my struct NODE array for cross reference. You have to
have some way of allowing the A* algorithm to be able to cross reference
your data (no matter how you may want to do it). Here, the NODE field
called nodenum will correspond directly to the node[i].nodenum field.
This way, when the A* algorithm returns the linked list of nodes along
the shortest path, I can cross reference this with my node[i].origin.

Don't get confused by this.. You'll see what I'm talking about later on
down in this tutorial.

What does the A*'s Stack look like?

The A* algorithm uses a Stack like this:
<c code>
struct STACK {
  struct NODE  *NodePtr;
  struct STACK *StackPtr;
};

struct STACK *Stack=NULL;
</c code>
Note that the Stack is merely a linked list of pointers. One pointer on
each link of the Stack connects to a NODE struct and the other links to
the next Stack node in the Stacks linked list..

=======================================================================
=======================================================================

What does the Stack do?

The A* algorithm uses the stack to keep track of past nodes for the following
reason. The A* slowly creeps along going from node to node (location to location)
in the direction of the shortest path. Say the A* algorithm slowly works its way
down a long and narrow hallway which turns out to be a dead-end. The A* algorithm
didn't know this at first because it just creeps in the direction of the shortest
path. So when it gets to the dead-end it has to slowly work its way backward
to find an alternative side-route and creep that way to see where that leads. If
that also is a dead-end then it has to again work backward until it finds another
possible path to head down. The Stack is used to keep track of these backtracking
nodes so it can get out of trouble if the path it is creeping down turns out to
not lead anywhere.

There are 2 routines for using the Stack. These are:
<c code>
//=========================================
// Push Node to front of the linked list
//=========================================
void Push(struct NODE *Node) {
struct STACK *STK;

  STK=(struct STACK *)malloc(sizeof(struct STACK));
  STK->StackPtr=Stack; // NULL at start
  STK->NodePtr=Node;   // Tie the Node
  Stack=STK;           // Set to start of Stack
}

//=========================================
// Pop Node from front of the linked list
//=========================================
struct NODE *Pop(void) {
struct NODE *tNode;
struct STACK *STK;

  STK=Stack;             // Start of Stack
  tNode=Stack->NodePtr;  // Grab this Node.
  Stack=Stack->StackPtr; // Move Stack Pointer
  free(STK);             // Free this node

  return (tNode);
}
</c code>
Note that the A* algorithm keeps pushing past nodes onto the front of
the Stack and popping nodes from the front of the Stack. It does this
for a simple reason. If it has to backtrack, the last node it visited
should be the next node on the Stack. This way, the order of nodes
visited down any particular path is maintained. When the A* algorithm
has to backtrack, it simply pops the last node it just pushed onto the
Stack. I have rebuilt these 2 routines and they are rock-solid stable.
You can mess with them if you like but do so at your own risk.. I do
recommend that you spend at least a few minutes understanding how NODES
are pushed onto the Stack and popped from the Stack just so you'll have
a feel for what is happening there..

You can put these routines anywhere you want so long as they are made
accessible to the main A* routines..

=======================================================================
=======================================================================

What about the OPEN and CLOSED Lists?

You'll need to have the following declarations made global to your A*
routines:
<c code>
struct NODE *OPEN=NULL;   // Start of OPEN List

struct NODE *CLOSED=NULL; // Start of CLOSED List
</c code>
The OPEN list is a linked list of NODES indicating which Nodes have not
been visited yet. Once a particular NODE has been visited, it is then
immediately removed from the OPEN linked list and placed onto the CLOSED
linked list. This way, the A* routines don't keep searching from the
same nodes over and over again...

So, every time the A* algorithm creeps over to another NODE along its
search path, it'll check to see if this particular NODE is on the OPEN
list (to be searched) or the CLOSED list (already searched).

This routine is used to check both lists (rebuilt):
<c code>
//=====================================================
// Check the desired OPEN/CLOSED LIST for NodeNum..
//=====================================================
struct NODE *CheckLIST(struct NODE *LIST, int NodeNum) {
struct NODE *tNode;

  tNode=LIST->NextNode; // Start of OPEN or CLOSED

  while (tNode)
    if (tNode->nodenum == NodeNum) { // My test!!
      return (tNode); } // Found it!
    else
      tNode=tNode->NextNode;

  return NULL; // NodeNum NOT on LIST.
}
</c code>
When you want to check if a NODE with the nodenum (NodeNumS) is on the
OPEN list then you pass into the CheckList routine OPEN. Likewise,
if you want to see if the NodeNum node is on the CLOSED list then you
pass in the CLOSED list. Easy enough. You'll see this routine in use
a little later on..

Since my struct NODES cross-reference my node[i] locations, I am
testing for the existence of the node on either list by checking if
any NODES on the list have the same NodeNum. If they do then I found
it on the list. If not, then NULL is returned..

NOTE: If I was going to use a vec3_t in my struct NODE instead of an
index number of some type, I'd have a new field called something like
vec3_t origin; added into my struct NODE and my CheckList() routine would
then become the following:
<c code>
//=====================================================
struct NODE *CheckLIST(struct NODE *LIST, vec3_t location) {
struct NODE *tNode;
vec3_t vtmp;

  tNode=LIST->NextNode; // Start of OPEN or CLOSED

  while (tNode) {
    VectorSubtract(tNode->origin,location,vtmp);
    if (VectorLength(vtmp) == 0.0) { // New test here!!
      return (tNode); } // Found it!
    else
      tNode=tNode->NextNode; }

  return NULL; // NodeNum NOT on LIST.
}
</c code>
So my new test would have to compare 2 vec3_t vectors. However you want
to make your test, you do it right inside of this routine...

Okay, lets move on..

=======================================================================
=======================================================================

Now, add these helper functions into your AStar.c file.
<c code>
//=========================================
// Free allocated resources for next search
//=========================================
void FreeStack(struct NODE *PathNode) {
struct NODE *tNode;
struct STACK *STK;

  while (PathNode) {
    tNode=PathNode;
    PathNode=PathNode->PrevNode;
    free(tNode); }

  while (CLOSED) {
    tNode=CLOSED;
    CLOSED=CLOSED->NextNode;
    free(tNode); }

  while (OPEN) {
    tNode=OPEN;
    OPEN=OPEN->NextNode;
    free(tNode); }

  while (Stack) {
    STK=Stack;
    Stack=Stack->StackPtr;
    free(STK); }
}

//===============================================
// Propagate Old node's values to Nodes on Stack
//===============================================
void PropagateDown(struct NODE *Old) {
struct NODE *POPNode;
int g,c;

  for (c=0;c < NUMCHILDS;c++)
    if (Old->Child[c])
      if (Old->g+1 < Old->Child[c]->g) {
        Old->Child[c]->g=Old->g+1;
        Old->Child[c]->f=g+Old->h;
        Old->Child[c]->PrevNode=Old;
        Push(Old->Child[c]); } // Push onto Stack

  while (Stack) {
    POPNode=Pop();
    for (c=0;c < NUMCHILDS;c++) {
      if (!POPNode->Child[c]) break; // No more valid Child nodes!
      if (POPNode->g+1 < POPNode->Child[c]->g) {
        POPNode->Child[c]->g=g=POPNode->g+1;
        POPNode->Child[c]->f=g+POPNode->h;
        POPNode->Child[c]->PrevNode=POPNode;
        Push(POPNode->Child[c]); } } } // Push onto Stack
}
</c code>
// We'll need this Macro!!
<c code>
#define vDiff(b,a) sqrt((a[0]*a[0]-b[0]*b[0])+(a[1]*a[1]-b[1]*b[1])+(a[2]*a[2]-b[2]*b[2]))
</c code>
The following routine is the main function which A* will use when it
moves to a new node as it creeps along its search path. The parameters
are a StartNode, which is the Parent Node that A* is searching from!
NodeNumS is the nodenum of the node it is checking out, and NodeNumD
is the nodenum of the final destination (this stays the same throughout).

What happens is that as the A* creeps along, all valid new nodes it finds
in its search pattern (NUMCHILDS) become child nodes of the current node.
So for example, I have a search pattern that is forward, back, left, right,
up and down. Then my NUMCHILDS is 6 because I could have a maximum of 6
valid child nodes (new directions) from any one particular node along the
path. You'll see a good example of a search pattern later on... As the A*
moves merrily along, if, from its current node, only 2 directions are valid
(the rest are in solid or lava/slime or A* already searched that node)
then that current node will only have 2 child nodes associated with it.
Hope this makes sense to you..

NOTE: If the search pattern I want (you can make your own) is 8 different
directions from the present node then I must have NUMCHILDS = 8. If I want
to have a fancy search that searches in 20 different directions from each
present node then my NUMCHILDS = 20. If the number of searches per current
node does not match your NUMCHILDS value than you'll step off one of your
pointers and kaboom!! This has also been rebuilt..
<c code>
//===========================================
// Successor Nodes all pushed onto OPEN list
//===========================================
void GetSuccessorNodes(struct NODE *StartNode, int NodeNumS, int NodeNumD) {
struct NODE *Old,*Successor;
struct NODE *tNode1,*tNode2;
int g,c;
float h;

  //================================
  // Has NodeNumS been Searched yet?
  //================================
  Old=CheckLIST(OPEN,NodeNumS);
  if (Old) {
    for (c=0;c < NUMCHILDS;c++)
      if (!StartNode->Child[c]) break; // Find first empty Child
    StartNode->Child[((c < NUMCHILDS)?c:(NUMCHILDS-1))]=Old;
    if (StartNode->g+1 < Old->g) {
      Old->g=g=StartNode->g+1;
      Old->f=g+Old->h;
      Old->PrevNode=StartNode; }
     return; }

  //==================================
  // Has NodeNumS been searched yet?
  //==================================
  Old=CheckLIST(CLOSED,NodeNumS);
  if (Old!=NULL) {
    for (c=0;c < NUMCHILDS;c++)
      if (StartNode->Child[c]==NULL) break;
    StartNode->Child[((c < NUMCHILDS)?c:(NUMCHILDS-1))]=Old;
    if (StartNode->g+1 < Old->g) {
      Old->g=g=StartNode->g+1;
      Old->f=g+Old->h;
      Old->PrevNode=StartNode;
      PropagateDown(Old); }
    return; }

  //=======================================
  // It is NOT on the OPEN or CLOSED List!!
  //=======================================
  // Make Successor a Child of StartNode
  //=======================================
  Successor=(struct NODE *)malloc(sizeof(struct NODE));
  Successor->nodenum=NodeNumS;
  Successor->g=g=StartNode->g+1;

// NOTE: the heuristic estimate of the remaining path from this node
// to the destination node is given by the difference between the 2
// vectors.  You can come up with your own estimate..

  Successor->h=h=abs(vDiff(node[NodeNumS].origin,node[NodeNumD].origin));
  Successor->f=g+h;0
  Successor->PrevNode=StartNode;
  Successor->NextNode=NULL;
  for (c=0;c < NUMCHILDS;c++)
    Successor->Child[c]=NULL;

  for (c=0;c < NUMCHILDS;c++)
    if (StartNode->Child[c]==NULL) break; // Find first empty Child[]
  StartNode->Child[((c < NUMCHILDS)?c:(NUMCHILDS-1))]=Successor;

  //=================================
  // Insert Successor into OPEN List
  //=================================
  tNode1=OPEN;
  tNode2=OPEN->NextNode;
  while (tNode2 && (tNode2->f < Successor->f)) {
    tNode1=tNode2;
    tNode2=tNode2->NextNode; }
  Successor->NextNode=tNode2;
  tNode1->NextNode=Successor;
}

</c code>
This next routine returns the nodenum of the node[i]
which contains this particular origin.
<c code>
//=========================================
// What is nodenum of this origin, if any?
//=========================================
int GetNodeNum(vec3_t origin) {
vec3_t vtmp;
float dist;
int i;

  // Search all of my node[i]'s
  for (i=0;i < numnodes;i++) {
    VectorSubtract(node[i].origin,origin,vtmp);
    dist=VectorLengthSqr(vtmp);
    if (dist < 1.0F)
     return node[i].nodenum; }

  return -1;
}
</c code>
NOTE: If the origin does NOT exist in my huge array of node[i]'s then
it returns -1. Else, if it finds that origin in the node array it
returns that node's nodenum. This way, you can go from any origin in
the map and see if it is a valid node (one in your pre-determined node
array) and get its corresponding nodenum..

You'll also need this helper routine. Since all nodes placed onto the
OPEN list are sorted by their f value (estimated distance from start to
destination) with the ones with the shortest paths at the front of the
OPEN list, then the next best node will always be the first node on
the OPEN list. This function retrieves that node from the OPEN list and
places it on the CLOSED list. This has been rebuilt too.
<c code>
//=========================================
// Pull FIRST node from OPEN, put on CLOSED
//=========================================
struct NODE *NextBestNode(void) {
struct NODE *Node;

  Node=OPEN->NextNode;    // Pull from FRONT of OPEN list

  if (!Node) return NULL;

  OPEN->NextNode=OPEN->NextNode->NextNode;

  Node->NextNode=CLOSED->NextNode;
  CLOSED->NextNode=Node; // Put at FRONT of CLOSED list

  return Node; // Return Next Best Node
}
</c code>
=======================================================================
=======================================================================

Okay, we're all done with the helper stuff. Now let's get into the guts
of the A* algorithm itself.

Like I mentioned before, you determine the type of search pattern you want
the A* algorithm to conduct from node to node to node.. The total number
of searches it does per node must equal the NUMCHILDS value as discussed
before... Above, my NUMCHILDS was equal to 6. So, I want the A* algorithm
to search 6 different directions from each node along the path like so.
<c code>
//=========================================
//
//           +Z      +Y
//            |     /
//            |   /
//            | /
//    -X -----o----- +X
//           /|
//         /  |
//       /    |
//     -Y    -Z
//
// 0=+x, 1=-x, 2=+y, 3=-y, 4=+z, 5=-z,
//=========================================
void NextNode(int i, vec3_t v) {
int x=32; // 32 units each x direction
int y=32; // 32 units each y direction
int z=24; // 24 units each z direction

  switch (i) {
   case 0: v[0]+=x; break;
   case 1: v[0]-=x; break;
   case 2: v[1]+=y; break;
   case 3: v[1]-=y; break;
   case 4: v[2]+=z; break;
   case 5: v[2]-=z; break;
   } // end switch
}
</c code>
So, for each node, it'll check up,down, left,right, forward,backward
for the next node along the path which brings me closer to the final
destination node.. Remember, you can have A* go 3 forward and 2 back
and 5 up and 3 down etc etc etc. Whatever you think is the best
searching pattern that you want. Set up your NextNode() function
accordingly and your A* will be on its merry way. Be imaginative!!

The above NextNode() routine is called from this routine:
<c code>
//==========================================================
void ComputeSuccessors(struct NODE *PresentNode, int NodeNumD) {
int c,NextNodeNum;
vec3_t vtmp;

  for (c=0;c < NUMCHILDS;c++) {
    VectorCopy(node[PresentNode->nodenum].origin,vtmp);
    NextNode(c,vtmp); // Note: vtmp is changed inside NextNode()
    NextNodeNum=GetNodeNum(vtmp); // location in node[] array?
    if (NextNodeNum == -1) continue;   // vtmp Node is invalid
    GetSuccessorNodes(PresentNode,NextNodeNum,NodeNumD); }
}
</c code>
What is happening here? Well. for the present node where A* is
currently at (still heading for its NodeNumD destination node)
for each possible pattern (NUMCHILDS) you've set for yourself,
you copy the present node location and send that vector into the
NextNode() routine for some "adjustment". It adjusts the vector
location according to your criteria and returns the adjusted
vector. Now, you need to do some OPEN/CLOSED list searching so
you'll need to find out what NodeNum corresponds to a vector
with this particular origin, if it even exists! If your GetNodeNum
routine fails to find that origin in your node[i] array, then
it must be an invalid location and it returns -1. You check to see
if the adjusted location is valid. If it is then you pass it into
the GetSuccessorNodes() routine for searching on OPEN/CLOSED list
or making it a Successor Node (because it is valid) and then putting
it on the OPEN list.. You repeat this for each of the searches in
your search pattern. If ALL directions are valid from the PresentNode
then the PresentNode will have all 6 of its children nodes filled up..

So.... from each PresentNode, A* will search the surrounding area
based on the criteria you've established and generate possible valid
Successor nodes (child nodes of PresentNode) and put them onto the
OPEN list for later searching...

NOTE: that when a node is put onto the OPEN list it is sorted by
its estimated distance from start to destination (f-value)... All
the valid Successors from the present node are placed onto the OPEN
list (if not already there AND not on the CLOSED list) and the above
function NextBestNode() pulls the next best node (first node on the
OPEN list) as the best possible direction to destination from the
current present node. Get that? If not, go over the source a few
times in your mind...

Now comes the MAIN findpath() function for A* (also rebuilt)..

You call this FindPath() function giving it a start and destination
vector and it returns the number of nodes along the path...

I use the following 2 vars.

<c code>
int *Waypoint=NULL; // Integer array of nodenum's along the path
int numpts=0;       // Number of nodes in the path..

//=========================================
int FindPath(vec3_t start, vec3_t destination) {
struct NODE *StartNode;
struct NODE *BestNode;
struct NODE *tNode;
int NodeNumD;
int NodeNumS;
int g,c,i;
float h;
vec3_t tstart,tdest;

  VectorCopy(start,tstart);
  VectorCopy(destination,tdest);

  // Get NodeNum of start vector
  NodeNumS=GetNodeNum(tstart);
  if (NodeNumS==-1) return 0; // ERROR

  // Get NodeNum of destination vector
  NodeNumD=GetNodeNum(tdest);
  if (NodeNumD==-1) return 0; // ERROR

  // Allocate OPEN/CLOSED list pointers..
  OPEN=(struct NODE *)malloc(sizeof(struct NODE));
  OPEN->NextNode=NULL;

  CLOSED=(struct NODE *)malloc(sizeof(struct NODE));
  CLOSED->NextNode=NULL;

  //================================================
  // This is our very first NODE!  Our start vector
  //================================================
  StartNode=(struct NODE *)malloc(sizeof(struct NODE));
  StartNode->nodenum=NodeNumS;
  StartNode->g=g=0;
  StartNode->h=h=abs(vDiff(start,destination));
  StartNode->f=g+h;
  for (c=0;c < NUMCHILDS;c++)
    StartNode->Child[c]=NULL;
  StartNode->NextNode=NULL;
  StartNode->PrevNode=NULL;
  //================================================

  OPEN->NextNode=BestNode=StartNode; // First node on OPEN list..

  for (;;) {
    tNode=BestNode; // Save last valid node
    BestNode=(struct NODE *)NextBestNode(); // Get next node from OPEN list
    if (!BestNode) {
      BestNode=tNode; // Last valid node..
      break;}
    if (BestNode->nodenum==NodeNumD) break;// we there yet?
    ComputeSuccessors(BestNode,NodeNumD);} // Search from here..

  //================================================

  if (BestNode==StartNode) {  // Start==End??
    FreeStack(StartNode);
    return 0; }

  BestNode->NextNode=NULL; // Must tie this off!

  // How many nodes we got?
   tNode=BestNode;
  i=0;
  while (tNode) {
    i++; // How many nodes?
    tNode=tNode->PrevNode; }

  if (i <= 2) { // Only nodes are Start and End??
    FreeStack(BestNode);
    return 0; }

  // Let's allocate our own stuff...

  numpts=i;
  Waypoint=(int *)malloc(numpts*sizeof(int));

  // Now, we have to assign the nodenum's along
  // this path in reverse order because that is
  // the way the A* algorithm finishes its search.
  // The last best node it visited was the END!
  // So, we copy them over in reverse.. No biggy..

  tNode=BestNode;
  while (BestNode) {
    Waypoint[--i]=BestNode->nodenum;
    BestNode=BestNode->PrevNode; }

// NOTE: At this point, if our numpts returned is not
// zero, then a path has been found!  To follow this
// path we simply follow node[Waypoint[i]].origin
// because Waypoint array is filled with indexes into
// our node[i] array of valid vectors in the map..
// We did it!!  Now free the stack and exit..

  //================================================

  FreeStack(tNode); // Release ALL resources!!

  return (numpts);
}
</c code>
I've included these helper routines for you.
<c code>
//======================================================
void G_Spawn_Splash(int type, int count, int color, vec3_t start, vec3_t movdir, vec3_t origin) {
  gi.WriteByte(SVC_TEMP_ENTITY);
  gi.WriteByte(type);
  gi.WriteByte(count);
  gi.WritePosition(start);
  gi.WriteDir(movdir);
  gi.WriteByte(color);
  gi.multicast(origin, MULTICAST_PVS);
}

//==================================================
void DrawPath(void) {
int i=0,k;
vec3_t zvec={0,0,0};

  for (k=0;k < numpts;k++) {
    i=Waypoint[k];
//  fprintf(fp,"PathNode[%d]=[%.0f,%.0f,%.0f]\n",i,node[i].origin[0],node[i].origin[1],node[i].origin[2]); 
    G_Spawn_Splash(TE_LASER_SPARKS, 8, 0xe2e5e3e6, node[i].origin, zvec, node[i].origin);
}
}
</c code>
To use these, you have to have a global var like so:
<c code>
int showpath=0;
</c code>
Inside of your ClientThink function near the top put this:
<c code>
  if (showpath) DrawPath();
</c code>
Then, at the bottom of your ClientCommands() in your g_cmds.c file put this:
<c code>
  else
    if (!Q_stricmp(cmd, "drawpath")) {
      VectorCopy(ent->s.origin,start);
      VectorCopy(SOME_DESTINATION_POINT, dest);
      if (FindPath(start,dest)>0)
        showpath=true; }
  else
    if (!Q_stricmp(cmd, "pathOFF"))
      showpath=false;
</c code>
You bind some key to "drawgrid" in your autoexec.cfg file and
come up with a way of getting some destination vector (using
a findradius or something like that). Make a call to FindPath
with your origin and the destination vectors. If FindPath returns
non-zero, then a path exists. You turn on the showpath var for
ClientThink() and the nodes along the path will be displayed!

If you want to turn them off then bind another key to "pathOFF"
and when you hit that key, ClientThink() will stop drawing the
nodes along the path for you. Cool effects too!

Well... That's it for now..

Now, get out there and find a path to the BASTARDS and KILL THEM!

Have Fun!

Maj.Bitch