Mail Archives: djgpp/1997/07/09/20:05:42
--------------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 <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 base=82e15000 limit=0015ffff
<BR>ds: sel=00b7 base=82e15000 limit=0015ffff
<BR>es: sel=00b7 base=82e15000 limit=0015ffff
<BR>fs: sel=00c7 base=00000000 limit=ffffffff
<BR>gs: sel=00c7 base=00000000 limit=ffffffff
<BR>ss: sel=00b7 base=82e15000 limit=0015ffff
<BR>
<BR>Call frame traceback EIPs:
<BR> 0x000019d0 _CheckCLOSED+16, line 302 of mypath.c
<BR> 0x00001900 _GenerateSucc+104, line 240 of mypath.c
<BR> 0x00001791 _GenerateSuccessors+49, line 163 of mypath.c
<BR> 0x0000171f _FindPath+151, line 121 of mypath.c
<BR> 0x00001fd9 _main+997, line 437 of mypath.c
<BR> 0x00013b72 ___crt1_startup+138
<BR>
<BR>And here is the source code:
<P>#include <conio.h>
<BR>#include <stdio.h>
<BR>#include <stdlib.h>
<BR>#include <fcntl.h>
<BR>#include <math.h>
<BR>#include <string.h>
<BR>#include <sys/farptr.h>
<BR>#include <sys/segments.h>
<BR>#include <sys/movedata.h>
<BR>#include <mikmod.h>
<BR>#include <allegro.h>
<BR>#include <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> long f,h;
<BR> int g,tmpg;
<BR> int x,y;
<BR> int NodeNum;
<BR> struct NODE *Parent;
<BR> struct NODE *Child[8];
/* a node may have upto 8+(NULL) children. */
<BR> struct NODE *NextNode;
/* for filing purposes */
<BR>};
<P>struct NODE *OPEN;
<BR>struct NODE *CLOSED;
<P>struct STACK {
<BR> struct NODE *NodePtr;
<BR> 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> return ((y*20)+x);
<BR>}
<P>boolean FreeTile(int x, int y)
<BR>{
// returns 1 if tile is free(nothing on it).
<BR> // Note: if TileMap[equation]==0
it means free so just !(not) it.
<BR> return (!TileMap[(y*20)+x]);
<BR>}
<P>void DisplayPath(int x1, int y1, int x2, int y2)
<BR>{
<BR> struct NODE *path, *Node;
<BR> int lx=x2,ly=y2;
<P> path=(struct NODE *)FindPath((long)x1,(long)y1,(long)x2,(long)y2);
<P> while (path->Parent != NULL)
<BR> {
<BR> path=path->Parent;
<BR> line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);
<BR> lx=path->x;
<BR> ly=path->y;
<BR> }
<BR> line(screen,lx*32+16,ly*32+16,path->x*32+16,path->y*32+16,44);
<P> // Free Nodes up
<BR> Node=OPEN->NextNode;
<BR> while (Node != NULL)
<BR> {
<BR> free(Node);
<BR> Node=Node->NextNode;
<BR> }
<BR> Node=CLOSED->NextNode;
<BR> while (Node != NULL)
<BR> {
<BR> free(Node);
<BR> Node=Node->NextNode;
<BR> }
<BR>}
<P>struct NODE *FindPath(long sx,long sy,long dx,long dy)
<BR>{
<BR> struct NODE *Node, *BestNode;
<BR> int TileNumDest;
<P> TileNumDest=TileNum((int)dx,(int)dy);
<P> OPEN=(struct NODE *)malloc(sizeof( struct NODE ));
<BR> CLOSED=(struct NODE *)malloc(sizeof( struct NODE
));
<P> Node=(struct NODE *)malloc(sizeof( struct NODE ));
<BR> Node->g=0;
<BR> Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy); //
should really use sqrt().
<BR> Node->f=Node->g+Node->h;
<BR> Node->NodeNum=TileNum((int)sx,(int)sy);
<BR> Node->x=sx;
<BR> Node->y=sy;
<BR> Node->NextNode=NULL;
<P> OPEN->NextNode=Node;
/* make Open List point to first node */
<BR> for (;;)
<BR> {
<BR> BestNode=(struct NODE *)ReturnBestNode();
<BR> if (BestNode->NodeNum == TileNumDest)
/* if we've found the end, break and finish */
<BR> break;
<BR> GenerateSuccessors(BestNode,dx,dy);
<BR> }
<BR> return (BestNode);
<BR>}
<P>struct NODE *ReturnBestNode(void)
<BR>{
<BR> struct NODE *tmp;
<P> if (OPEN->NextNode == NULL)
<BR> {
<BR> exit(0);
<BR> }
<P> /* Pick Node with lowest f, in this case it's the
first node in list
<BR> because we sort the OPEN list wrt lowest f. Call
it BESTNODE. */
<P> tmp=OPEN->NextNode; // point to first
node on OPEN
<BR> OPEN->NextNode=tmp->NextNode;
// Make OPEN point to nextnode or NULL.
<P> /* Next take BESTNODE (or temp in this case) and
put it on CLOSED */
<P> tmp->NextNode=CLOSED->NextNode;
<BR> CLOSED->NextNode=tmp;
<P> return(tmp);
<BR>}
<P>void GenerateSuccessors(struct NODE *BestNode,long dx,long dy)
<BR>{
<BR> long x,y;
<P> /* Upper-Left */
<BR> x=(long)BestNode->x-TILESIZE;
<BR> y=(long)BestNode->y-TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Upper
*/
<BR> x=(long)BestNode->x;
<BR> y=(long)BestNode->y-TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Upper-Right */
<BR> x=(long)BestNode->x+TILESIZE;
<BR> y=(long)BestNode->y-TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Right
*/
<BR> x=(long)BestNode->x+TILESIZE;
<BR> y=(long)BestNode->y;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Lower-Right */
<BR> x=(long)BestNode->x+TILESIZE;
<BR> y=(long)BestNode->y+TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Lower
*/
<BR> x=(long)BestNode->x;
<BR> y=(long)BestNode->y+TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Lower-Left */
<BR> x=(long)BestNode->x-TILESIZE;
<BR> y=(long)BestNode->y+TILESIZE;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<P> /* Left
*/
<BR> x=(long)BestNode->x-TILESIZE;
<BR> y=(long)BestNode->y;
<BR> if(x>0 && x<COLS && y>0 &&
y<ROWS)
<BR> if (FreeTile(x,y))
<BR> GenerateSucc(BestNode,x,y,dx,dy);
<BR>}
<P>void GenerateSucc(struct NODE *BestNode,long x, long y, long dx, long
dy)
<BR>{
<BR> int g,TileNumS,c=0;
<BR> struct NODE *Old,*Successor;
<P> g=BestNode->g+1; /* g(Successor)=g(BestNode)+cost
of getting from BestNode to Successor */
<BR> TileNumS=TileNum((int)x,(int)y); /* identification
purposes */
<P> if ((Old=CheckOPEN(TileNumS)) != NULL) /* if equal
to NULL then not in OPEN list, else it returns the Node in Old */
<BR> {
<BR> for(c=0;c<8;c++)
<BR> if(BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR> break;
<BR> BestNode->Child[c]=Old;
<BR>
<P> if (g < Old->g) /* if our new g value
is < Old's then reset Old's parent to point to BestNode */
<BR> {
<BR> Old->Parent=BestNode;
<BR> Old->g=g;
<BR> Old->f=g+Old->h;
<BR> }
<BR> }
<BR> else if ((Old=CheckCLOSED(TileNumS)) != NULL) /*
if equal to NULL then not in OPEN list, else it returns the Node in Old
*/
<BR> {
<BR> for(c=0;c<8;c++)
<BR> if (BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR> break;
<BR> BestNode->Child[c]=Old;
<P> if (g < Old->g) /* if our new g value
is < Old's then reset Old's parent to point to BestNode */
<BR> {
<BR> Old->Parent=BestNode;
<BR> Old->g=g;
<BR> Old->f=g+Old->h;
<BR> PropagateDown(Old);
/* Since we changed the g value of Old, we need
<BR> to propagate this new value downwards,
i.e.
<BR> do a Depth-First traversal of the tree!
*/
<BR> }
<BR> }
<BR> else
<BR> {
<BR> Successor=(struct NODE *)malloc(sizeof( struct
NODE ));
<BR> Successor->Parent=BestNode;
<BR> Successor->g=g;
<BR> Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);
// should do sqrt(), but since we don't really
<BR> Successor->f=g+Successor->h;
// care about the distance but just which branch looks
<BR> Successor->x=x;
// better this should suffice. Anyayz it's faster.
<BR> Successor->y=y;
<BR> Successor->NodeNum=TileNumS;
<BR> Insert(Successor);
/* Insert Successor on OPEN list wrt f */
<BR> for(c=0;c<8;c++)
<BR> if (BestNode->Child[c] ==
NULL) /* Add Old to the list of BestNode's Children (or Successors). */
<BR> break;
<BR> BestNode->Child[c]=Successor;
<BR> }
<BR>}
<P>struct NODE *CheckOPEN(int tilenum)
<BR>{
<BR> struct NODE *tmp;
<P> tmp=OPEN->NextNode;
<BR> while (tmp != NULL)
<BR> {
<BR> if (tmp->NodeNum == tilenum)
<BR> return (tmp);
<BR> else
<BR> tmp=tmp->NextNode;
<BR> }
<BR> return (NULL);
<BR>}
<P>struct NODE *CheckCLOSED(int tilenum)
<BR>{
<BR> struct NODE *tmp;
<P> tmp=CLOSED->NextNode;
<P> while (tmp != NULL)
<BR> {
<BR> <FONT COLOR="#FF0000">if (tmp->NodeNum
== tilenum)</FONT>
<BR> return (tmp);
<BR> else
<BR> tmp=tmp->NextNode;
<BR> }
<BR> return (NULL);
<BR>}
<P>void Insert(struct NODE *Successor)
<BR>{
<BR> struct NODE *tmp1,*tmp2;
<BR> long f;
<P> if (OPEN->NextNode == NULL)
<BR> {
<BR> OPEN->NextNode=Successor;
<BR> return;
<BR> }
<P> /* insert into OPEN successor wrt
f */
<P> f=Successor->f;
<BR> tmp1=OPEN;
<BR> tmp2=OPEN->NextNode;
<P> while ((tmp2 != NULL) && (tmp2->f < f))
<BR> {
<BR> tmp1=tmp2;
<BR> tmp2=tmp2->NextNode;
<BR> }
<BR> Successor->NextNode=tmp2;
<BR> tmp1->NextNode=Successor;
<BR>}
<P>void PropagateDown(struct NODE *Old)
<BR>{
<BR> int c,g;
<BR> struct NODE *Child, *Father;
<P> g=Old->g;
// alias.
<BR> for(c=0;c<8;c++)
<BR> {
<BR> if ((Child=Old->Child[c])==NULL)
// create alias for faster access.
<BR> break;
<BR> if (g+1 < Child->g)
<BR> {
<BR> Child->g=g+1;
<BR> Child->f=Child->g+Child->h;
<BR> Child->Parent=Old;
// reset parent to new path.
<BR> Push(Child);
// Now the Child's branch need to be
<BR> } // checked
out. Remember the new cost must be propagated down.
<BR> }
<P> while (Stack->NextStackPtr != NULL)
<BR> {
<BR> Father=Pop();
<BR> for(c=0;c<8;c++)
<BR> {
<BR> if ((Child=Father->Child[c])==NULL)
/* we may stop the propagation 2 ways: either */
<BR> break;
<BR> if (Father->g+1 < Child->g)
/* there are no children, or that the g value of */
<BR> {
/* the child is equal or better than the cost we're propagating */
<BR> Child->g=Father->g+1;
<BR> Child->f=Child->g+Child->h;
<BR> Child->Parent=Father;
<BR> Push(Child);
<BR> }
<BR> }
<BR> }
<BR>}
<P>void Push(struct NODE *Node)
<BR>{
<BR> struct STACK *tmp;
<P> tmp=(struct STACK *)malloc(sizeof(struct STACK));
<BR> tmp->NodePtr=Node;
<BR> tmp->NextStackPtr=Stack->NextStackPtr;
<BR> Stack->NextStackPtr=tmp;
<BR>}
<P>struct NODE *Pop()
<BR>{
<BR> struct NODE *tmp;
<BR> struct STACK *tmpSTK;
<P> tmpSTK=Stack->NextStackPtr;
<BR> tmp=tmpSTK->NodePtr;
<P> Stack->NextStackPtr=tmpSTK->NextStackPtr;
<BR> free(tmpSTK);
<BR> return (tmp);
<BR>}
<P>void main()
<BR>{
<BR> int x,y,x1,y1,x2,y2,x3,y3,count=0;
<BR> allegro_init();
<BR> install_keyboard();
<BR> install_mouse();
<BR> install_timer();
<BR> set_gfx_mode(GFX_AUTODETECT, 640, 480, 0, 0);
<P> for(x3=0;x3<=640;x3+=32)
<BR> line(screen,x3,0,x3,480,55);
<BR> for(y3=0;y3<=480;y3+=32)
<BR> line(screen,0,y3,640,y3,55);
<P> for(y3=0;y3<ROWS;y3++)
<BR> for(x3=0;x3<COLS;x3++)
<BR> TileMap[(y3*20)+x3]
= 0;
<P> while(!FINISHED) //
loop until ESC key hit
<BR> {
<BR> show_mouse(NULL);
<BR> if(mouse_b & 1)
<BR> {
<BR> TileMap[((mouse_y/32)*20)+(mouse_x/32)]=1;
<BR> rectfill(screen, (mouse_x/32)*32,(mouse_y/32)*32,(mouse_x/32)*32+32,(mouse_y/32)*32+32,55);
<BR> }
<BR> if(key[KEY_X])
<BR> {
<BR> circlefill(screen,((mouse_x/32)*32)+16,((mouse_y/32)*32)+16,16,32);
<P> if(count==0)
<BR> {
<BR>
x=(mouse_x/32);
<BR>
y=(mouse_y/32);
<BR>
count++;
<BR> }
<BR> else if(count==1)
<BR> {
<BR>
x1=(mouse_x/32);
<BR>
y1=(mouse_y/32);
<BR>
count=0;
<BR> DisplayPath(x,y,x1,y1);
<BR> }
<BR> }
<P> if(key[KEY_ESC])
<BR> FINISHED=1;
<P> show_mouse(screen);
<BR> rest(300);
<BR> }
<P> 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> -Ozzy
<BR> </HTML>
--------------46003C0AF10F5A060574AABD--
- Raw text -