📄 spath.c
字号:
#include "myheader.h"
void _interrupt _far New_Key_Int(void)
{
asm sti
asm in al,KEY_BUFFER
asm xor ah,ah
asm mov raw_key,ax
asm in al,KEY_CONTROL
asm or al,82h
asm out KEY_CONTROL,al
asm and al,7fh
asm out KEY_CONTROL,al
asm mov al,20h
asm out INT_CONTROL,al
switch(raw_key)
{
case MAKE_UP:
{
key_table[INDEX_UP]=1;
} break;
case MAKE_DOWN:
{
key_table[INDEX_DOWN]=1;
} break;
case MAKE_RIGHT:
{
key_table[INDEX_RIGHT]=1;
} break;
case MAKE_LEFT:
{
key_table[INDEX_LEFT]=1;
} break;
case MAKE_SPACE:
{
key_table[INDEX_SPACE]=1;
} break;
case MAKE_X:
{
key_table[INDEX_X]=1;
} break;
case MAKE_N:
{
key_table[INDEX_N]=1;
} break;
case BREAK_UP:
{
key_table[INDEX_UP]=0;
} break;
case BREAK_DOWN:
{
key_table[INDEX_DOWN]=0;
} break;
case BREAK_RIGHT:
{
key_table[INDEX_RIGHT]=0;
} break;
case BREAK_LEFT:
{
key_table[INDEX_LEFT]=0;
} break;
case BREAK_SPACE:
{
key_table[INDEX_SPACE]=0;
} break;
case BREAK_X:
{
key_table[INDEX_X]=0;
} break;
case BREAK_N:
{
key_table[INDEX_N]=0;
} break;
default: break;
}
}
//
// This routine restores the original BIOS keyboard interrupt handler
//
void RestoreKeyboard(void)
{
_dos_setvect(KEYBOARD_INT,Old_Isr); // restore BIOS keyboard interrupt
}
//
// This routine saves the original BIOS keyboard interrupt handler and
// then installs a customer handler for this program.
//
void InitKeyboard(void)
{
Old_Isr=_dos_getvect(KEYBOARD_INT); // save BIOS keyboard interrupt
_dos_setvect(KEYBOARD_INT,New_Key_Int); // install new int 9h handler
}
char far *image;
void SetUp(void)
{
detectgraph(&g_driver,&g_mode);
initgraph(&g_driver,&g_mode,"..\\BGI");
gotoxy(3,24);
printf("Use Cursors to move & Spacebar to place.");
gotoxy(50,24);
printf("N -->New Screen");
gotoxy(3,25);
printf("Press X for start/finish.");
gotoxy(50,25);
printf("Esc-->(Quit).");
setviewport(0,0,624,352,0);
setfillstyle(SOLID_FILL,2);
bar(0,0,TILESIZE,TILESIZE);
image=(void far *)malloc(imagesize(0,0,14,14));
getimage(0,0,14,14,image);
setfillstyle(SOLID_FILL,0);
bar(0,0,15,15);
putimage(1,1,image,XOR_PUT);
}
void DrawScreen(void)
{
int x,y;
setcolor(2);
rectangle(0,0,624,352);
for (x=TILESIZE;x<624;x+=TILESIZE)
{
moveto(x,0);
lineto(x,352);
}
for (y=TILESIZE;y<352;y+=TILESIZE)
{
moveto(0,y);
lineto(624,y);
}
}
void DrawSquare(int deltax,int deltay,int flag)
{
static x=0,y=0,oldx,oldy,flag2=1,draw=1;
if (flag) /* flag to switch from drawing (no erase) to drawing with erase */
{
flag2=flag2^flag;
draw=0;
}
if (flag2) /* draw and erase */
{
if (draw)
{
oldx=x; oldy=y;
putimage(oldx+1,oldy+1,image,XOR_PUT);
}
x+=deltax; y+=deltay;
putimage(x+1,y+1,image,XOR_PUT);
draw=1;
}
else /* free draw (don't erase) */
{
x+=deltax; y+=deltay;
TileMap[(y>>SHIFT)*COLS+(x>>SHIFT)+42]=1; /* place a tile in map */
setfillstyle(SOLID_FILL,2);
bar(x,y,x+TILESIZE,y+TILESIZE);
}
delay(100);
}
void DisplayPath(int x1, int y1, int x2, int y2)
{
struct NODE *path, *Node;
path=(struct NODE *)FindPath((long)x1,(long)y1,(long)x2,(long)y2);
setcolor(14);
moveto(x2,y2);
while (path->Parent != NULL)
{
path=path->Parent;
lineto(path->x,path->y);
}
lineto(path->x,path->y);
// 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;
}
}
int TileNum(int x, int y)
{
return ((y>>SHIFT)*COLS+(x>>SHIFT)+42); // The reason I add 42 to the
// tile number is because I want the tile number to start at the 2nd
// column and the 2nd row. Because if we do this we don't have to have
// a special case to test if at a boundary. In the function BoundaryTiles
// I place 1's around the boundary, in this way when I call the function
// FreeTile() it returns false because we can't go there.
}
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>>SHIFT)*COLS+(x>>SHIFT)+42]);
}
void BoundaryTiles(void) // This function places 1 around the boundary
{ // so that we don't go there. Also we don't
int c,cc,index=0; // have to treat the boundaries as a special case
for(c=0;c<TOTAL_TILES;c++) // zero out tiles.
TileMap[c]=0;
for(c=0;c<COLS;c++) // place 1's at boundaries.
TileMap[c]=1;
for(c=1;c<ROWS-1;c++)
{
index+=41;
TileMap[index]=1;
TileMap[index+40]=1;
}
index+=41;
for(c=index;c<TOTAL_TILES;c++)
TileMap[c]=1;
}
void main(void)
{
int x1,y1,count=1,x=8,y=8;
char key,key2;
SetUp();
DrawScreen();
InitKeyboard(); // install our keyboard handler
BoundaryTiles(); // setup boundary so that the path doesn't go off screen.
Stack=( struct STACK *)calloc(1,sizeof(struct STACK)); // setup the Stack.
while(!FINISHED) // loop until ESC key hit
{
if ((key_table[INDEX_RIGHT]) && (x<616))
{ DrawSquare(TILESIZE,0,0); x+=TILESIZE; }
else if ((key_table[INDEX_LEFT]) && (x>8))
{ DrawSquare(-TILESIZE,0,0); x-=TILESIZE; }
if ((key_table[INDEX_UP]) && (y>8))
{ DrawSquare(0,-TILESIZE,0); y-=TILESIZE; }
else if ((key_table[INDEX_DOWN]) && (y<344))
{ DrawSquare(0,TILESIZE,0); y+=TILESIZE; }
if (key_table[INDEX_SPACE])
{ delay(100); DrawSquare(0,0,1); }
if (key_table[INDEX_N])
{
clearviewport();
BoundaryTiles(); // Block the boundary tiles so we don't go off screen.
DrawScreen();
delay(100);
}
else if (key_table[INDEX_X])
{ setfillstyle(SOLID_FILL,4);
fillellipse(x,y,5,5);
setfillstyle(SOLID_FILL,2);
if (count++==2)
{
count=1;
DisplayPath(x,y,x1,y1);
}
else
{
x1=x; y1=y;
}
delay(200);
}
if(raw_key==1)
FINISHED=1;
}
RestoreKeyboard(); // restore BIOS keyboard handler
closegraph();
}
/**************************************************************************/
/***************************** A* Algorithm *******************************/
/**************************************************************************/
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 *)calloc(1,sizeof( struct NODE ));
CLOSED=(struct NODE *)calloc(1,sizeof( struct NODE ));
Node=(struct NODE *)calloc(1,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;
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)
{
printf("ERROR: no more nodes on OPEN\n");
RestoreKeyboard(); // restore BIOS keyboard handling
closegraph();
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 */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Upper */
if (FreeTile(x=(long)BestNode->x,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Upper-Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y-TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower-Right */
if (FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower */
if (FreeTile(x=(long)BestNode->x,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Lower-Left */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y+TILESIZE))
GenerateSucc(BestNode,x,y,dx,dy);
/* Left */
if (FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->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 *)calloc(1,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);
}
}
}
}
/**************************************************************************/
/* STACK FUNCTIONS */
/**************************************************************************/
void Push(struct NODE *Node)
{
struct STACK *tmp;
tmp=( struct STACK *)calloc(1,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);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -