VC6.0 A星算法（AStar）问题求助，程序已经写出来，但结果不对，求高手帮忙调试通过，

头文件： Astar.h#include "stdafx.h"//typedef
struct NODE{
    long f,h;
    int  g,tmpg;
    int  x,y;
    int  NodeNum;
    NODE *Parent;
    NODE *Child[8];       /* a node may have upto 8+(NULL) children. */
    NODE *NextNode;       /* for filing purposes */
};/**************************************************************************/
/*                                 STACK                                  */
/**************************************************************************/
struct STACK {
    NODE *NodePtr;
    STACK *NextStackPtr;
};class CAstar
{
public :
CAstar();
~CAstar();public:
void  DrawMap(CDC* pDC);//画地图
void  DrawSelectDot(CDC* pDC,int x,int y);
void  DrawPathDot(CDC* pDC,int x,int y);
void  DrawPath(CDC* pDC,NODE* path); NODE   *OPEN;
NODE   *CLOSED;
STACK  *Stack;
//***********************************************************************
NODE*  FindPath(long sx,long sy,long dx,long dy);
NODE*  ReturnBestNode(void);
void   GenerateSuccessors(NODE* BestNode,long dx,long dy);
void   GenerateSucc(NODE* BestNode,long x, long y, long dx, long dy);
NODE*  CheckOPEN(int tilenum);
NODE*  CheckCLOSED(int tilenum);
void   Insert(NODE* Successor);
void   PropagateDown(NODE* Old);
void   Push(NODE* Node);
NODE*  Pop(); bool  FreeTile(int x, int y);
int   TileNum(int x, int y);
};

解决方案 »

  1.   

    CPP文件  Astar.cpp#include "StdAfx.h"
    #include "Astar.h"#define X_SIZE   51
    #define Y_SIZE   51extern int wid;
    int maps[X_SIZE][Y_SIZE] = {
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,1,1,1,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
    };CString ss;
    int ii = 0;CAstar::CAstar()
    {
    }
    CAstar::~CAstar()
    {
    }
    接下面：
      

  2.   

    void CAstar::DrawMap(CDC* pDC)
    {
    CPen penblue(PS_SOLID,1,RGB(0,0,255)),*pOld;
    CBrush *pOldBrush,brush(RGB(0,0,255)),brushY(RGB(255,0,255));
    int i=0,j=0;
    for(i=0;i<X_SIZE;i++)
    {
    for(j=0;j<Y_SIZE;j++)
    {
    if(maps[j][i] == 1)
    {
    pOldBrush = pDC->SelectObject(&brush);
    }
    else
    {
    pOldBrush = pDC->SelectObject(&brushY);
    }
    pDC->Rectangle(wid*i,wid*j,wid*i+wid-1,wid*j+wid-1);
    }
    pDC->SelectObject(pOldBrush);
    }
    brushY.DeleteObject();
    brush.DeleteObject();
    penblue.DeleteObject(); Stack = (STACK*)calloc(1,sizeof(STACK));
    m_pDC = pDC; /*
    for(int i=0;i<51;i++)
    {
    for(int j=0;j<51;j++)
    {
    DrawProcessDot(j,i);
    }
    }
    */
    }
    void CAstar::DrawProcessDot(int j,int i)
    {
    DrawProcessGreenDot(j,i);
    for(int i=1;i<3000000;i++)
    {
    int nn = 0;
    }
    DrawProcessReadDot(j,i);
    }
    void CAstar::DrawProcessGreenDot(int x,int y)
    {
    CBrush *pOldBrush,brushb(RGB(0,255,0));
    pOldBrush = m_pDC->SelectObject(&brushb);
    m_pDC->Rectangle(x*wid,y*wid,x*wid+wid-1,y*wid+wid-1);
    m_pDC->SelectObject(pOldBrush);
    brushb.DeleteObject();

    //ss.Format("%d,%d",x,y);
    //m_pDC->TextOut(550,100,ss);
    }
    void CAstar::DrawProcessReadDot(int x,int y)
    {
    CBrush  *pOldBrush,brushr(RGB(255,0,255));
    pOldBrush = m_pDC->SelectObject(&brushr);
    m_pDC->Rectangle(x*wid,y*wid,x*wid+wid-1,y*wid+wid-1);
    m_pDC->SelectObject(pOldBrush);
    brushr.DeleteObject();
    }
    void CAstar::DrawSelectDot(CDC* pDC,int x,int y)
    {
    CBrush *pOldBrush,brush(RGB(0,255,0));
    pOldBrush = pDC->SelectObject(&brush);
    pDC->Rectangle(x,y,x+wid-1,y+wid-1);
    pDC->SelectObject(pOldBrush);
    brush.DeleteObject();
    }
    void CAstar::DrawPathDot(CDC* pDC,int x,int y)
    {
    x = x/wid * wid;
    y = y/wid * wid;
    CBrush *pOldBrush,brush(RGB(0,255,0));
    pOldBrush = pDC->SelectObject(&brush); pDC->Rectangle(x,y,x+wid-1,y+wid-1);
    //DrawSelectDot(pDC,x/,y); pDC->SelectObject(pOldBrush);
    brush.DeleteObject();
    }void CAstar::DrawPath(CDC* pDC,NODE* path)
    {
    while (path->Parent != NULL)
    {
    path = path->Parent; 
    DrawPathDot(pDC,path->x/wid*wid,path->y/wid*wid);
    ii++;
    ss.Format("%d,%d",path->x,path->y);
    pDC->TextOut(550,20+ii*15,ss);
    }
    DrawPathDot(pDC,path->x/wid*wid,path->y/wid*wid);
    ii++;
    ss.Format("%d,%d",path->x,path->y);
    pDC->TextOut(550,20+ii*15,ss); // Free Nodes up
    NODE* Node = OPEN->NextNode;
    //while (Node != NULL)
    //{
    // free(Node);
    // Node = Node->NextNode;
    //}
    Node = CLOSED->NextNode;
    //while (Node != NULL)
    //{
    // free(Node);
    // Node = Node->NextNode;
    //}
    ii = 0;
    }/**********************************************************************************/
    int CAstar::TileNum(int x, int y)
    {
    //生成特殊代号
    return (y * Y_SIZE + x + 53);
    }bool CAstar::FreeTile(int x, int y)
    {
    return (!maps[x][y]);
    }
    /*****************************************************************************************************************************************/
    /***************************** A* Algorithm **********************************************************************************************/
    /*****************************************************************************************************************************************/NODE* CAstar::FindPath(long sx,long sy,long dx,long dy)
    {
    NODE *Node, *BestNode;
    int TileNumDest; //得到目标位置，作判断用
    TileNumDest = TileNum((int)dx,(int)dy); //生成Open和Closed表
    OPEN=(NODE *)calloc(1,sizeof( NODE ));
    CLOSED=(NODE *)calloc(1,sizeof( NODE )); //生成起始节点，并放入Open表中
    Node=(NODE *)calloc(1,sizeof( NODE ));
    Node->g = 0;
    //这是计算h值
    Node->h = (sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt().
    //这是计算f值，即估价值
    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 (;;)
    {
    //从Open表中取得一个估价值最好的节点 (NODE *)
    BestNode = ReturnBestNode(); //如果该节点是目标节点就退出
    if (BestNode->NodeNum == TileNumDest)    /* if we've found the end, break and finish */
    break;
    //否则生成子节点
    GenerateSuccessors(BestNode,dx,dy);
    }
    return (BestNode);
    }
    接下面：
      

  3.   


    NODE* CAstar::ReturnBestNode(void)
    {
    NODE *tmp; if (OPEN->NextNode == NULL)
    {
    printf("ERROR: no more nodes on OPEN\n");
    //zp RestoreKeyboard();    // restore BIOS keyboard handling
    //zp closegraph();

    AfxMessageBox("OPEN为空，程序退出！");
    exit(0);
    } 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 CAstar::GenerateSuccessors(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 CAstar::GenerateSucc(NODE* BestNode,long x, long y, long dx, long dy)
    {
    int g,TileNumS,c=0;
    NODE *Old,*Successor; //计算子节点的 g 值
    g=BestNode->g+1;     /* g(Successor)=g(BestNode)+cost of getting from BestNode to Successor */
    TileNumS=TileNum((int)x,(int)y);  /* identification purposes */ //子节点再Open表中吗？
    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; //比较Open表中的估价值和当前的估价值（只要比较g值就可以了）
    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;
    }
    }
    //在Closed表中吗？
    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; //比较Closed表中的估价值和当前的估价值（只要比较g值就可以了）
    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; //再依次更新Old的所有子节点的估价值
    PropagateDown(Old); 
    }
    }
    else //不在Open表中也不在Close表中
    {
    Successor=(NODE *)calloc(1,sizeof(NODE));
    Successor->Parent=BestNode;
    Successor->g=g;
    Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);
    Successor->f=g+Successor->h; 
    Successor->x=x;             
    Successor->y=y;
    Successor->NodeNum=TileNumS;
    Insert(Successor); //再插入Open表中，同时排序。
    DrawProcessDot(y,x);
    for(c=0;c<8;c++)
    if (BestNode->Child[c] == NULL)
    break;
    BestNode->Child[c]=Successor;
    }
    }NODE* CAstar::CheckOPEN(int tilenum)
    {
    NODE *tmp; tmp=OPEN->NextNode;
    while (tmp != NULL)
    {
    if (tmp->NodeNum == tilenum)
    return (tmp);
    else
    tmp=tmp->NextNode;
    }
    return (NULL);
    }NODE* CAstar::CheckCLOSED(int tilenum)
    {
    NODE *tmp; tmp=CLOSED->NextNode; while (tmp != NULL)
    {
    if (tmp->NodeNum == tilenum)
    return (tmp);
    else
    tmp=tmp->NextNode;
    }
    return (NULL);
    }void CAstar::Insert(NODE* Successor)
    {
    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 CAstar::PropagateDown(NODE* Old)
    {
    int c,g;
    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 CAstar::Push(NODE* Node)
    {
    STACK *tmp;
    tmp = (STACK*)calloc(1,sizeof(STACK));
    tmp->NodePtr = Node;
    tmp->NextStackPtr = Stack->NextStackPtr;
    Stack->NextStackPtr = tmp;
    }NODE* CAstar::Pop()
    {
    NODE *tmp;
    STACK *tmpSTK; tmpSTK = Stack->NextStackPtr;
    tmp = tmpSTK->NodePtr; Stack->NextStackPtr = tmpSTK->NextStackPtr;
    free(tmpSTK);
    return (tmp);
    }
    //===========================结束==============================================
      

  4.   

    NODE* CAstar::FindPath(long sx,long sy,long dx,long dy) 
    { 
    //得到目标位置，作判断用 
    TileNumDest = TileNum((int)dx,(int)dy); //TileNum((int)sx,(int)sy) //生成Open和Closed表 
    OPEN=(NODE *)calloc(1,sizeof( NODE )); 
    CLOSED=(NODE *)calloc(1,sizeof( NODE )); //生成起始节点，并放入Open表中 
    Node=(NODE *)calloc(1,sizeof( NODE )); 
    Node->g = 0; 
    //这是计算h值 
    Node->h = (sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);  // should really use sqrt(). 
    //这是计算f值，即估价值 
    Node->f = Node->g+Node->h; 
    Node->NodeNum = TileNum((int)sx,(int)sy); //TileNum((int)dx,(int)dy)
    Node->x = sx; //Node->x = dxNode->y = sy; //Node->y = dy链表是逆向的，自己思考一下吧