Newsgroups: comp.os.msdos.djgpp
From: Matt Reiferson <MReiferson AT aol DOT com>
Subject: A* Algorithm Problems SIGSEGV
Content-Type: multipart/alternative; boundary="------------46003C0AF10F5A060574AABD"
Reply-To: MReiferson AT aol DOT com
Organization: DeltaSoft
Message-ID: <ED2A6G.2x9@nonexistent.com>
Mime-Version: 1.0
Date: Wed, 9 Jul 1997 17:02:14 GMT
Lines: 1085
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk


--------------46003C0AF10F5A060574AABD
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

This A* Pathfinding algorithm I am planning to use in a Warcraft II type
game, the problem is, it doesn't work.......Sometimes I will be able to
find the paths but sometimes it gives me SIGSEGV crash
messages.....NOTE, this program that follows is just a program that
allows you to place blockades, a start and an end position to find the
fastest route from one point to another around those obstacles, it uses
allegro for the graphics, and a specialized version of MikMod, because
of this you will be unable to recompile the code without removing the
#include <mikmod.h>.....The line that is faulty (claimed by symify is
highlighted RED) Here is the symify output:

Shutting down Allegro
Exiting due to signal SIGSEGV
General Protection Fault at eip=000019d0
eax=fffe6485 ebx=00000000 ecx=00000003 edx=000000b7 esi=00000009
edi=00000001
ebp=001297df esp=001297df
program=C:\DJGPP\SOURCE\PROJECTS\ASTAR\ASTAR.EXE
cs: sel=00af  base=82e15000  limit=0015ffff
ds: sel=00b7  base=82e15000  limit=0015ffff
es: sel=00b7  base=82e15000  limit=0015ffff
fs: sel=00c7  base=00000000  limit=ffffffff
gs: sel=00c7  base=00000000  limit=ffffffff
ss: sel=00b7  base=82e15000  limit=0015ffff

Call frame traceback EIPs:
  0x000019d0   _CheckCLOSED+16, line 302 of mypath.c
  0x00001900   _GenerateSucc+104, line 240 of mypath.c
  0x00001791   _GenerateSuccessors+49, line 163 of mypath.c
  0x0000171f   _FindPath+151, line 121 of mypath.c
  0x00001fd9   _main+997, line 437 of mypath.c
  0x00013b72   ___crt1_startup+138

And here is the source code:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <math.h>
#include <string.h>
#include <sys/farptr.h>
#include <sys/segments.h>
#include <sys/movedata.h>
#include <mikmod.h>
#include <allegro.h>
#include <time.h>

#define COLS 20
#define ROWS 15
#define TOTAL_TILES ROWS*COLS
#define TILESIZE 1

int TileMap[TOTAL_TILES];
int FINISHED=0;

typedef int boolean;

struct NODE {
    long f,h;
    int g,tmpg;
    int x,y;
    int NodeNum;
    struct NODE *Parent;
    struct NODE *Child[8];       /* a node may have upto 8+(NULL)
children. */
    struct NODE *NextNode;       /* for filing purposes */
};

struct NODE *OPEN;
struct NODE *CLOSED;

struct STACK {
    struct NODE *NodePtr;
    struct STACK *NextStackPtr;
};

struct STACK *Stack;

unsigned _stklen = 1048567;

boolean FreeTile(int x, int y);
int TileNum(int x, int y);
struct NODE *FindPath(long sx,long sy,long dx,long dy);
struct NODE *ReturnBestNode(void);
void GenerateSuccessors(struct NODE *BestNode,long dx,long dy);
void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long
dy);
struct NODE *CheckOPEN(int tilenum);
struct NODE *CheckCLOSED(int tilenum);
void Insert(struct NODE *Successor);
void PropagateDown(struct NODE *Old);
void Push(struct NODE *Node);
struct NODE *Pop(void);

int TileNum(int x, int y)
{
  return ((y*20)+x);
}

boolean FreeTile(int x, int y)
{             //  returns 1 if tile is free(nothing on it).
       //  Note: if TileMap[equation]==0 it means free so just !(not)
it.
  return (!TileMap[(y*20)+x]);
}

void DisplayPath(int x1, int y1, int x2, int y2)
{
  struct NODE *path, *Node;
  int lx=x2,ly=y2;

  path=(struct NODE *)FindPath((long)x1,(long)y1,(long)x2,(long)y2);

  while (path->Parent != NULL)
  {
     path=path->Parent;
     line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);
     lx=path->x;
     ly=path->y;
  }
  line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);

  // Free Nodes up
  Node=OPEN->NextNode;
  while (Node != NULL)
  {
     free(Node);
     Node=Node->NextNode;
  }
  Node=CLOSED->NextNode;
  while (Node != NULL)
  {
     free(Node);
     Node=Node->NextNode;
  }
}

struct NODE *FindPath(long sx,long sy,long dx,long dy)
{
    struct NODE *Node, *BestNode;
    int TileNumDest;

    TileNumDest=TileNum((int)dx,(int)dy);

    OPEN=(struct NODE *)malloc(sizeof( struct NODE ));
    CLOSED=(struct NODE *)malloc(sizeof( struct NODE ));

    Node=(struct NODE *)malloc(sizeof( struct NODE ));
    Node->g=0;
    Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use
sqrt().
    Node->f=Node->g+Node->h;
    Node->NodeNum=TileNum((int)sx,(int)sy);
    Node->x=sx;
    Node->y=sy;
    Node->NextNode=NULL;

    OPEN->NextNode=Node;        /* make Open List point to first node */

    for (;;)
    {
  BestNode=(struct NODE *)ReturnBestNode();
    if (BestNode->NodeNum == TileNumDest)    /* if we've found the end,
break and finish */
       break;
  GenerateSuccessors(BestNode,dx,dy);
    }
    return (BestNode);
}

struct NODE *ReturnBestNode(void)
{
    struct NODE *tmp;

    if (OPEN->NextNode == NULL)
  {
     exit(0);
  }

    /* Pick Node with lowest f, in this case it's the first node in list

    because we sort the OPEN list wrt lowest f. Call it BESTNODE. */

    tmp=OPEN->NextNode;   // point to first node on OPEN
    OPEN->NextNode=tmp->NextNode;    // Make OPEN point to nextnode or
NULL.

    /* Next take BESTNODE (or temp in this case) and put it on CLOSED */

    tmp->NextNode=CLOSED->NextNode;
    CLOSED->NextNode=tmp;

    return(tmp);
}

void GenerateSuccessors(struct NODE *BestNode,long dx,long dy)
{
    long x,y;

      /* Upper-Left  */
    x=(long)BestNode->x-TILESIZE;
    y=(long)BestNode->y-TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Upper       */
    x=(long)BestNode->x;
    y=(long)BestNode->y-TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Upper-Right */
    x=(long)BestNode->x+TILESIZE;
    y=(long)BestNode->y-TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Right       */
    x=(long)BestNode->x+TILESIZE;
    y=(long)BestNode->y;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Lower-Right */
    x=(long)BestNode->x+TILESIZE;
    y=(long)BestNode->y+TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Lower       */
    x=(long)BestNode->x;
    y=(long)BestNode->y+TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Lower-Left  */
    x=(long)BestNode->x-TILESIZE;
    y=(long)BestNode->y+TILESIZE;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);

      /* Left        */
    x=(long)BestNode->x-TILESIZE;
    y=(long)BestNode->y;
    if(x>0 && x<COLS && y>0 && y<ROWS)
       if (FreeTile(x,y))
          GenerateSucc(BestNode,x,y,dx,dy);
}

void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long
dy)
{
    int g,TileNumS,c=0;
    struct NODE *Old,*Successor;

    g=BestNode->g+1;     /* g(Successor)=g(BestNode)+cost of getting
from BestNode to Successor */
    TileNumS=TileNum((int)x,(int)y);  /* identification purposes */

    if ((Old=CheckOPEN(TileNumS)) != NULL) /* if equal to NULL then not
in OPEN list, else it returns the Node in Old */
    {
       for(c=0;c<8;c++)
        if(BestNode->Child[c] == NULL) /* Add Old to the list of
BestNode's Children (or Successors). */
           break;
     BestNode->Child[c]=Old;


     if (g < Old->g)  /* if our new g value is < Old's then reset Old's
parent to point to BestNode */
     {
        Old->Parent=BestNode;
        Old->g=g;
        Old->f=g+Old->h;
     }
    }
    else if ((Old=CheckCLOSED(TileNumS)) != NULL) /* if equal to NULL
then not in OPEN list, else it returns the Node in Old */
    {
       for(c=0;c<8;c++)
        if (BestNode->Child[c] == NULL) /* Add Old to the list of
BestNode's Children (or Successors). */
           break;
       BestNode->Child[c]=Old;

     if (g < Old->g)  /* if our new g value is < Old's then reset Old's
parent to point to BestNode */
       {
        Old->Parent=BestNode;
        Old->g=g;
        Old->f=g+Old->h;
        PropagateDown(Old);       /* Since we changed the g value of
Old, we need
      to propagate this new value downwards, i.e.
      do a Depth-First traversal of the tree! */
      }
    }
    else
    {
     Successor=(struct NODE *)malloc(sizeof( struct NODE ));
     Successor->Parent=BestNode;
     Successor->g=g;
     Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);  // should do sqrt(), but
since we don't really
     Successor->f=g+Successor->h;     // care about the distance but
just which branch looks
     Successor->x=x;                  // better this should suffice.
Anyayz it's faster.
     Successor->y=y;
     Successor->NodeNum=TileNumS;
     Insert(Successor);     /* Insert Successor on OPEN list wrt f */
     for(c=0;c<8;c++)
        if (BestNode->Child[c] == NULL) /* Add Old to the list of
BestNode's Children (or Successors). */
           break;
     BestNode->Child[c]=Successor;
    }
}

struct NODE *CheckOPEN(int tilenum)
{
    struct NODE *tmp;

    tmp=OPEN->NextNode;
    while (tmp != NULL)
    {
     if (tmp->NodeNum == tilenum)
        return (tmp);
     else
        tmp=tmp->NextNode;
    }
    return (NULL);
}

struct NODE *CheckCLOSED(int tilenum)
{
    struct NODE *tmp;

    tmp=CLOSED->NextNode;

    while (tmp != NULL)
    {
      if (tmp->NodeNum == tilenum)
        return (tmp);
     else
        tmp=tmp->NextNode;
    }
    return (NULL);
}

void Insert(struct NODE *Successor)
{
    struct NODE *tmp1,*tmp2;
    long f;

    if (OPEN->NextNode == NULL)
    {
       OPEN->NextNode=Successor;
       return;
    }

       /* insert into OPEN successor wrt f */

    f=Successor->f;
    tmp1=OPEN;
    tmp2=OPEN->NextNode;

    while ((tmp2 != NULL) && (tmp2->f < f))
    {
       tmp1=tmp2;
       tmp2=tmp2->NextNode;
    }
  Successor->NextNode=tmp2;
  tmp1->NextNode=Successor;
}

void PropagateDown(struct NODE *Old)
{
    int c,g;
    struct NODE *Child, *Father;

    g=Old->g;            // alias.
    for(c=0;c<8;c++)
    {
       if ((Child=Old->Child[c])==NULL)   // create alias for faster
access.
          break;
     if (g+1 < Child->g)
     {
        Child->g=g+1;
        Child->f=Child->g+Child->h;
        Child->Parent=Old;           // reset parent to new path.
        Push(Child);                 // Now the Child's branch need to
be
       }     // checked out. Remember the new cost must be propagated
down.
    }

    while (Stack->NextStackPtr != NULL)
    {
     Father=Pop();
     for(c=0;c<8;c++)
     {
        if ((Child=Father->Child[c])==NULL)       /* we may stop the
propagation 2 ways: either */
           break;
        if (Father->g+1 < Child->g) /* there are no children, or that
the g value of */
        {                           /* the child is equal or better than
the cost we're propagating */
           Child->g=Father->g+1;
           Child->f=Child->g+Child->h;
           Child->Parent=Father;
           Push(Child);
        }
       }
    }
}

void Push(struct NODE *Node)
{
    struct STACK *tmp;

    tmp=(struct STACK *)malloc(sizeof(struct STACK));
    tmp->NodePtr=Node;
    tmp->NextStackPtr=Stack->NextStackPtr;
    Stack->NextStackPtr=tmp;
}

struct NODE *Pop()
{
    struct NODE *tmp;
    struct STACK *tmpSTK;

    tmpSTK=Stack->NextStackPtr;
    tmp=tmpSTK->NodePtr;

    Stack->NextStackPtr=tmpSTK->NextStackPtr;
    free(tmpSTK);
    return (tmp);
}

void main()
{
   int x,y,x1,y1,x2,y2,x3,y3,count=0;
   allegro_init();
   install_keyboard();
   install_mouse();
   install_timer();
   set_gfx_mode(GFX_AUTODETECT, 640, 480, 0, 0);

   for(x3=0;x3<=640;x3+=32)
      line(screen,x3,0,x3,480,55);
   for(y3=0;y3<=480;y3+=32)
      line(screen,0,y3,640,y3,55);

   for(y3=0;y3<ROWS;y3++)
      for(x3=0;x3<COLS;x3++)
         TileMap[(y3*20)+x3] = 0;

   while(!FINISHED)       // loop until ESC key hit
   {
      show_mouse(NULL);
      if(mouse_b & 1)
         {
         TileMap[((mouse_y/32)*20)+(mouse_x/32)]=1;
         rectfill(screen,
(mouse_x/32)*32,(mouse_y/32)*32,(mouse_x/32)*32+32,(mouse_y/32)*32+32,55);

         }
    if(key[KEY_X])
       {

circlefill(screen,((mouse_x/32)*32)+16,((mouse_y/32)*32)+16,16,32);

         if(count==0)
       {
            x=(mouse_x/32);
            y=(mouse_y/32);
            count++;
         }
         else if(count==1)
         {
            x1=(mouse_x/32);
            y1=(mouse_y/32);
            count=0;
          DisplayPath(x,y,x1,y1);
         }
       }

    if(key[KEY_ESC])
       FINISHED=1;

      show_mouse(screen);
      rest(300);
   }

   exit(0);
}

---------------------
Matt Reiferson
MReiferson AT aol DOT com
RingMaster: Game Programmers Guild
URL: http://gpg.home.ml.org
WebMaster: The Game Programming MegaSite
URL: http://gpmega.home.ml.org
---------------------
"See You On The Other Side........"
  -Ozzy


--------------46003C0AF10F5A060574AABD
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit

<HTML>
This A* Pathfinding algorithm I am planning to use in a Warcraft II type
game, the problem is, it doesn't work.......Sometimes I will be able to
find the paths but sometimes it gives me SIGSEGV crash messages.....NOTE,
this program that follows is just a program that allows you to place blockades,
a start and an end position to find the fastest route from one point to
another around those obstacles, it uses allegro for the graphics, and a
specialized version of MikMod, because of this you will be unable to recompile
the code without removing the #include &lt;mikmod.h>.....The line that
is faulty (claimed by symify is highlighted RED) Here is the symify output:

<P>Shutting down Allegro
<BR>Exiting due to signal SIGSEGV
<BR>General Protection Fault at eip=000019d0
<BR>eax=fffe6485 ebx=00000000 ecx=00000003 edx=000000b7 esi=00000009 edi=00000001
<BR>ebp=001297df esp=001297df program=C:\DJGPP\SOURCE\PROJECTS\ASTAR\ASTAR.EXE
<BR>cs: sel=00af&nbsp; base=82e15000&nbsp; limit=0015ffff
<BR>ds: sel=00b7&nbsp; base=82e15000&nbsp; limit=0015ffff
<BR>es: sel=00b7&nbsp; base=82e15000&nbsp; limit=0015ffff
<BR>fs: sel=00c7&nbsp; base=00000000&nbsp; limit=ffffffff
<BR>gs: sel=00c7&nbsp; base=00000000&nbsp; limit=ffffffff
<BR>ss: sel=00b7&nbsp; base=82e15000&nbsp; limit=0015ffff
<BR>&nbsp;
<BR>Call frame traceback EIPs:
<BR>&nbsp; 0x000019d0&nbsp;&nbsp; _CheckCLOSED+16, line 302 of mypath.c
<BR>&nbsp; 0x00001900&nbsp;&nbsp; _GenerateSucc+104, line 240 of mypath.c
<BR>&nbsp; 0x00001791&nbsp;&nbsp; _GenerateSuccessors+49, line 163 of mypath.c
<BR>&nbsp; 0x0000171f&nbsp;&nbsp; _FindPath+151, line 121 of mypath.c
<BR>&nbsp; 0x00001fd9&nbsp;&nbsp; _main+997, line 437 of mypath.c
<BR>&nbsp; 0x00013b72&nbsp;&nbsp; ___crt1_startup+138
<BR>&nbsp;
<BR>And here is the source code:

<P>#include &lt;conio.h>
<BR>#include &lt;stdio.h>
<BR>#include &lt;stdlib.h>
<BR>#include &lt;fcntl.h>
<BR>#include &lt;math.h>
<BR>#include &lt;string.h>
<BR>#include &lt;sys/farptr.h>
<BR>#include &lt;sys/segments.h>
<BR>#include &lt;sys/movedata.h>
<BR>#include &lt;mikmod.h>
<BR>#include &lt;allegro.h>
<BR>#include &lt;time.h>

<P>#define COLS 20
<BR>#define ROWS 15
<BR>#define TOTAL_TILES ROWS*COLS
<BR>#define TILESIZE 1

<P>int TileMap[TOTAL_TILES];
<BR>int FINISHED=0;

<P>typedef int boolean;

<P>struct NODE {
<BR>&nbsp;&nbsp;&nbsp; long f,h;
<BR>&nbsp;&nbsp;&nbsp; int g,tmpg;
<BR>&nbsp;&nbsp;&nbsp; int x,y;
<BR>&nbsp;&nbsp;&nbsp; int NodeNum;
<BR>&nbsp;&nbsp;&nbsp; struct NODE *Parent;
<BR>&nbsp;&nbsp;&nbsp; struct NODE *Child[8];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* a node may have upto 8+(NULL) children. */
<BR>&nbsp;&nbsp;&nbsp; struct NODE *NextNode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* for filing purposes */
<BR>};

<P>struct NODE *OPEN;
<BR>struct NODE *CLOSED;

<P>struct STACK {
<BR>&nbsp;&nbsp;&nbsp; struct NODE *NodePtr;
<BR>&nbsp;&nbsp;&nbsp; struct STACK *NextStackPtr;
<BR>};

<P>struct STACK *Stack;

<P>unsigned _stklen = 1048567;

<P>boolean FreeTile(int x, int y);
<BR>int TileNum(int x, int y);
<BR>struct NODE *FindPath(long sx,long sy,long dx,long dy);
<BR>struct NODE *ReturnBestNode(void);
<BR>void GenerateSuccessors(struct NODE *BestNode,long dx,long dy);
<BR>void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long
dy);
<BR>struct NODE *CheckOPEN(int tilenum);
<BR>struct NODE *CheckCLOSED(int tilenum);
<BR>void Insert(struct NODE *Successor);
<BR>void PropagateDown(struct NODE *Old);
<BR>void Push(struct NODE *Node);
<BR>struct NODE *Pop(void);

<P>int TileNum(int x, int y)
<BR>{
<BR>&nbsp; return ((y*20)+x);
<BR>}

<P>boolean FreeTile(int x, int y)
<BR>{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
//&nbsp; returns 1 if tile is free(nothing on it).
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //&nbsp; Note: if TileMap[equation]==0
it means free so just !(not) it.
<BR>&nbsp; return (!TileMap[(y*20)+x]);
<BR>}

<P>void DisplayPath(int x1, int y1, int x2, int y2)
<BR>{
<BR>&nbsp; struct NODE *path, *Node;
<BR>&nbsp; int lx=x2,ly=y2;

<P>&nbsp; path=(struct NODE *)FindPath((long)x1,(long)y1,(long)x2,(long)y2);

<P>&nbsp; while (path->Parent != NULL)
<BR>&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; path=path->Parent;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);
<BR>&nbsp;&nbsp;&nbsp;&nbsp; lx=path->x;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; ly=path->y;
<BR>&nbsp; }
<BR>&nbsp; line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);

<P>&nbsp; // Free Nodes up
<BR>&nbsp; Node=OPEN->NextNode;
<BR>&nbsp; while (Node != NULL)
<BR>&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; free(Node);
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Node=Node->NextNode;
<BR>&nbsp; }
<BR>&nbsp; Node=CLOSED->NextNode;
<BR>&nbsp; while (Node != NULL)
<BR>&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; free(Node);
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Node=Node->NextNode;
<BR>&nbsp; }
<BR>}

<P>struct NODE *FindPath(long sx,long sy,long dx,long dy)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *Node, *BestNode;
<BR>&nbsp;&nbsp;&nbsp; int TileNumDest;

<P>&nbsp;&nbsp;&nbsp; TileNumDest=TileNum((int)dx,(int)dy);

<P>&nbsp;&nbsp;&nbsp; OPEN=(struct NODE *)malloc(sizeof( struct NODE ));
<BR>&nbsp;&nbsp;&nbsp; CLOSED=(struct NODE *)malloc(sizeof( struct NODE
));

<P>&nbsp;&nbsp;&nbsp; Node=(struct NODE *)malloc(sizeof( struct NODE ));
<BR>&nbsp;&nbsp;&nbsp; Node->g=0;
<BR>&nbsp;&nbsp;&nbsp; Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);&nbsp; //
should really use sqrt().
<BR>&nbsp;&nbsp;&nbsp; Node->f=Node->g+Node->h;
<BR>&nbsp;&nbsp;&nbsp; Node->NodeNum=TileNum((int)sx,(int)sy);
<BR>&nbsp;&nbsp;&nbsp; Node->x=sx;
<BR>&nbsp;&nbsp;&nbsp; Node->y=sy;
<BR>&nbsp;&nbsp;&nbsp; Node->NextNode=NULL;

<P>&nbsp;&nbsp;&nbsp; OPEN->NextNode=Node;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* make Open List point to first node */
<BR>&nbsp;&nbsp;&nbsp; for (;;)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp; BestNode=(struct NODE *)ReturnBestNode();
<BR>&nbsp;&nbsp;&nbsp; if (BestNode->NodeNum == TileNumDest)&nbsp;&nbsp;&nbsp;
/* if we've found the end, break and finish */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp; GenerateSuccessors(BestNode,dx,dy);
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; return (BestNode);
<BR>}

<P>struct NODE *ReturnBestNode(void)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *tmp;

<P>&nbsp;&nbsp;&nbsp; if (OPEN->NextNode == NULL)
<BR>&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; exit(0);
<BR>&nbsp; }

<P>&nbsp;&nbsp;&nbsp; /* Pick Node with lowest f, in this case it's the
first node in list
<BR>&nbsp;&nbsp;&nbsp; because we sort the OPEN list wrt lowest f. Call
it BESTNODE. */

<P>&nbsp;&nbsp;&nbsp; tmp=OPEN->NextNode;&nbsp;&nbsp; // point to first
node on OPEN
<BR>&nbsp;&nbsp;&nbsp; OPEN->NextNode=tmp->NextNode;&nbsp;&nbsp;&nbsp;
// Make OPEN point to nextnode or NULL.

<P>&nbsp;&nbsp;&nbsp; /* Next take BESTNODE (or temp in this case) and
put it on CLOSED */

<P>&nbsp;&nbsp;&nbsp; tmp->NextNode=CLOSED->NextNode;
<BR>&nbsp;&nbsp;&nbsp; CLOSED->NextNode=tmp;

<P>&nbsp;&nbsp;&nbsp; return(tmp);
<BR>}

<P>void GenerateSuccessors(struct NODE *BestNode,long dx,long dy)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; long x,y;

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Upper-Left&nbsp; */
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Upper&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
*/
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Upper-Right */
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Right&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
*/
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Lower-Right */
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Lower&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
*/
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Lower-Left&nbsp; */
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y+TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* Left&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
*/
<BR>&nbsp;&nbsp;&nbsp; x=(long)BestNode->x-TILESIZE;
<BR>&nbsp;&nbsp;&nbsp; y=(long)BestNode->y;
<BR>&nbsp;&nbsp;&nbsp; if(x>0 &amp;&amp; x&lt;COLS &amp;&amp; y>0 &amp;&amp;
y&lt;ROWS)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (FreeTile(x,y))
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GenerateSucc(BestNode,x,y,dx,dy);
<BR>}

<P>void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long
dy)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; int g,TileNumS,c=0;
<BR>&nbsp;&nbsp;&nbsp; struct NODE *Old,*Successor;

<P>&nbsp;&nbsp;&nbsp; g=BestNode->g+1;&nbsp;&nbsp;&nbsp;&nbsp; /* g(Successor)=g(BestNode)+cost
of getting from BestNode to Successor */
<BR>&nbsp;&nbsp;&nbsp; TileNumS=TileNum((int)x,(int)y);&nbsp; /* identification
purposes */

<P>&nbsp;&nbsp;&nbsp; if ((Old=CheckOPEN(TileNumS)) != NULL) /* if equal
to NULL then not in OPEN list, else it returns the Node in Old */
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for(c=0;c&lt;8;c++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; BestNode->Child[c]=Old;
<BR>&nbsp;

<P>&nbsp;&nbsp;&nbsp;&nbsp; if (g &lt; Old->g)&nbsp; /* if our new g value
is &lt; Old's then reset Old's parent to point to BestNode */
<BR>&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->Parent=BestNode;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->g=g;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->f=g+Old->h;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; else if ((Old=CheckCLOSED(TileNumS)) != NULL) /*
if equal to NULL then not in OPEN list, else it returns the Node in Old
*/
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for(c=0;c&lt;8;c++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BestNode->Child[c]=Old;

<P>&nbsp;&nbsp;&nbsp;&nbsp; if (g &lt; Old->g)&nbsp; /* if our new g value
is &lt; Old's then reset Old's parent to point to BestNode */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->Parent=BestNode;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->g=g;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Old->f=g+Old->h;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; PropagateDown(Old);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* Since we changed the g value of Old, we need
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; to propagate this new value downwards,
i.e.
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; do a Depth-First traversal of the tree!
*/
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; else
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor=(struct NODE *)malloc(sizeof( struct
NODE ));
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->Parent=BestNode;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->g=g;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);&nbsp;
// should do sqrt(), but since we don't really
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->f=g+Successor->h;&nbsp;&nbsp;&nbsp;&nbsp;
// care about the distance but just which branch looks
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->x=x;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
// better this should suffice. Anyayz it's faster.
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->y=y;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Successor->NodeNum=TileNumS;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Insert(Successor);&nbsp;&nbsp;&nbsp;&nbsp;
/* Insert Successor on OPEN list wrt f */
<BR>&nbsp;&nbsp;&nbsp;&nbsp; for(c=0;c&lt;8;c++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; BestNode->Child[c]=Successor;
<BR>&nbsp;&nbsp;&nbsp; }
<BR>}

<P>struct NODE *CheckOPEN(int tilenum)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *tmp;

<P>&nbsp;&nbsp;&nbsp; tmp=OPEN->NextNode;
<BR>&nbsp;&nbsp;&nbsp; while (tmp != NULL)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; if (tmp->NodeNum == tilenum)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (tmp);
<BR>&nbsp;&nbsp;&nbsp;&nbsp; else
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp=tmp->NextNode;
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; return (NULL);
<BR>}

<P>struct NODE *CheckCLOSED(int tilenum)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *tmp;

<P>&nbsp;&nbsp;&nbsp; tmp=CLOSED->NextNode;

<P>&nbsp;&nbsp;&nbsp; while (tmp != NULL)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT COLOR="#FF0000">if (tmp->NodeNum
== tilenum)</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (tmp);
<BR>&nbsp;&nbsp;&nbsp;&nbsp; else
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp=tmp->NextNode;
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; return (NULL);
<BR>}

<P>void Insert(struct NODE *Successor)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *tmp1,*tmp2;
<BR>&nbsp;&nbsp;&nbsp; long f;

<P>&nbsp;&nbsp;&nbsp; if (OPEN->NextNode == NULL)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; OPEN->NextNode=Successor;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return;
<BR>&nbsp;&nbsp;&nbsp; }

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; /* insert into OPEN successor wrt
f */

<P>&nbsp;&nbsp;&nbsp; f=Successor->f;
<BR>&nbsp;&nbsp;&nbsp; tmp1=OPEN;
<BR>&nbsp;&nbsp;&nbsp; tmp2=OPEN->NextNode;

<P>&nbsp;&nbsp;&nbsp; while ((tmp2 != NULL) &amp;&amp; (tmp2->f &lt; f))
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp1=tmp2;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp2=tmp2->NextNode;
<BR>&nbsp;&nbsp;&nbsp; }
<BR>&nbsp; Successor->NextNode=tmp2;
<BR>&nbsp; tmp1->NextNode=Successor;
<BR>}

<P>void PropagateDown(struct NODE *Old)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; int c,g;
<BR>&nbsp;&nbsp;&nbsp; struct NODE *Child, *Father;

<P>&nbsp;&nbsp;&nbsp; g=Old->g;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
// alias.
<BR>&nbsp;&nbsp;&nbsp; for(c=0;c&lt;8;c++)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if ((Child=Old->Child[c])==NULL)&nbsp;&nbsp;
// create alias for faster access.
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp;&nbsp;&nbsp;&nbsp; if (g+1 &lt; Child->g)
<BR>&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->g=g+1;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->f=Child->g+Child->h;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->Parent=Old;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
// reset parent to new path.
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Push(Child);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
// Now the Child's branch need to be
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp; // checked
out. Remember the new cost must be propagated down.
<BR>&nbsp;&nbsp;&nbsp; }

<P>&nbsp;&nbsp;&nbsp; while (Stack->NextStackPtr != NULL)
<BR>&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp; Father=Pop();
<BR>&nbsp;&nbsp;&nbsp;&nbsp; for(c=0;c&lt;8;c++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if ((Child=Father->Child[c])==NULL)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* we may stop the propagation 2 ways: either */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (Father->g+1 &lt; Child->g)
/* there are no children, or that the g value of */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
/* the child is equal or better than the cost we're propagating */
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->g=Father->g+1;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->f=Child->g+Child->h;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Child->Parent=Father;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Push(Child);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; }
<BR>}

<P>void Push(struct NODE *Node)
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct STACK *tmp;

<P>&nbsp;&nbsp;&nbsp; tmp=(struct STACK *)malloc(sizeof(struct STACK));
<BR>&nbsp;&nbsp;&nbsp; tmp->NodePtr=Node;
<BR>&nbsp;&nbsp;&nbsp; tmp->NextStackPtr=Stack->NextStackPtr;
<BR>&nbsp;&nbsp;&nbsp; Stack->NextStackPtr=tmp;
<BR>}

<P>struct NODE *Pop()
<BR>{
<BR>&nbsp;&nbsp;&nbsp; struct NODE *tmp;
<BR>&nbsp;&nbsp;&nbsp; struct STACK *tmpSTK;

<P>&nbsp;&nbsp;&nbsp; tmpSTK=Stack->NextStackPtr;
<BR>&nbsp;&nbsp;&nbsp; tmp=tmpSTK->NodePtr;

<P>&nbsp;&nbsp;&nbsp; Stack->NextStackPtr=tmpSTK->NextStackPtr;
<BR>&nbsp;&nbsp;&nbsp; free(tmpSTK);
<BR>&nbsp;&nbsp;&nbsp; return (tmp);
<BR>}

<P>void main()
<BR>{
<BR>&nbsp;&nbsp; int x,y,x1,y1,x2,y2,x3,y3,count=0;
<BR>&nbsp;&nbsp; allegro_init();
<BR>&nbsp;&nbsp; install_keyboard();
<BR>&nbsp;&nbsp; install_mouse();
<BR>&nbsp;&nbsp; install_timer();
<BR>&nbsp;&nbsp; set_gfx_mode(GFX_AUTODETECT, 640, 480, 0, 0);

<P>&nbsp;&nbsp; for(x3=0;x3&lt;=640;x3+=32)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; line(screen,x3,0,x3,480,55);
<BR>&nbsp;&nbsp; for(y3=0;y3&lt;=480;y3+=32)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; line(screen,0,y3,640,y3,55);

<P>&nbsp;&nbsp; for(y3=0;y3&lt;ROWS;y3++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for(x3=0;x3&lt;COLS;x3++)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; TileMap[(y3*20)+x3]
= 0;

<P>&nbsp;&nbsp; while(!FINISHED)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //
loop until ESC key hit
<BR>&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; show_mouse(NULL);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(mouse_b &amp; 1)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; TileMap[((mouse_y/32)*20)+(mouse_x/32)]=1;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rectfill(screen, (mouse_x/32)*32,(mouse_y/32)*32,(mouse_x/32)*32+32,(mouse_y/32)*32+32,55);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp; if(key[KEY_X])
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; circlefill(screen,((mouse_x/32)*32)+16,((mouse_y/32)*32)+16,16,32);

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if(count==0)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
x=(mouse_x/32);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
y=(mouse_y/32);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
count++;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else if(count==1)
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
x1=(mouse_x/32);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
y1=(mouse_y/32);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
count=0;
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; DisplayPath(x,y,x1,y1);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }

<P>&nbsp;&nbsp;&nbsp; if(key[KEY_ESC])
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; FINISHED=1;

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; show_mouse(screen);
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rest(300);
<BR>&nbsp;&nbsp; }

<P>&nbsp;&nbsp; exit(0);
<BR>}

<P>---------------------
<BR>Matt Reiferson
<BR>MReiferson AT aol DOT com
<BR>RingMaster: Game Programmers Guild
<BR>URL: <A HREF="http://gpg.home.ml.org">http://gpg.home.ml.org</A>
<BR>WebMaster: The Game Programming MegaSite
<BR>URL: <A HREF="http://gpmega.home.ml.org">http://gpmega.home.ml.org</A>
<BR>---------------------
<BR>"See You On The Other Side........"
<BR>&nbsp; -Ozzy
<BR>&nbsp;</HTML>

--------------46003C0AF10F5A060574AABD--