游戏地图寻路算法 -- A*（分析 + 实现 + 教学视频连接）

首先理解游戏地图怎么设定那里不让走那里让走：

把图片分成一块一块格子，标记各个格子是否能走；

介绍一下A*
A*的核心就是 : 一个评估函数 F = G + H 和 2个表

假设 从A点到B点：
F = G + H：
- F: 从A到B的最短路径长度；
- G: 从起点，沿着产生的路径， 移动到指定点的耗费；
- H: 预估值，估计从A到B多长；（是一个比较理想的值）

A* 需要两个表保存数据： 一个启动表 和一个关闭列表；

• 1 . 把起点加到启动表中；
• 2 . 在把启动表中找到权值最小的格子，
  
  • 在当前格子周围只要能走就加入到启动表，
  • 除了 已经在启动列表 或 关闭列表 或 阻断点；
  • 把周围格子的父节点设置为A，
  • 把A从启动表中删除，并把他放到关闭列表中；
• 3 . 直到终点在启动列表中找到了！
  
  • 如果启动列表中已经没有格子了，代表没有找到；

---

不愿意往下看的，附上我的完整代码资源：
开发工具： VS2013
开发语言： C++
下载链接： http://download.csdn.net/detail/tianjing0805/9921693
教学视频： http://edu.51cto.com/center/course/lesson/index?id=94592

---

话不多说上代码：

//定义每个格子的宽度
#define LatticeLen 10
//用1表示阻断点，3表示起始点，4表示终点，2表示路径~
//虚拟一个地图出来
int G_PathLattice[10][10]=
{
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 3, 0, 1, 0, 1, 4, 0, 0 },
    { 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }
};

struct stNode
{
    int row;
    int rant;
    int f;
    int g;
    int h;
    struct stNode* pParent; //当前节点的前一个节点
};


int Distance(int row1, int rank1, int row2, int rank2)
{
    //得到格子中心点的坐标
    int x1 = rank1*LatticeLen + LatticeLen / 2;
    int y1 = row1*LatticeLen + LatticeLen / 2;

    int x2 = rank2*LatticeLen + LatticeLen / 2;
    int y2 = row2*LatticeLen + LatticeLen / 2;

    //计算2个格子的中心坐标
    return (int)sqrt((float)(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}

//判断一个节点是否在俩目标中
bool IsNodeInList(stNode* pNode, list<stNode*>nodeList)
{
    for (list<stNode*>::iterator it = nodeList.begin(); it != nodeList.end(); it++)
    {
        if (pNode->row == (*it)->row && pNode->rant == (*it)->rant)
        {
            return true;
        }
    }
    return false;
}
stNode* GetNearestNode(list<stNode*>nodeList)
{
    stNode* pNode = NULL; 
    int tempF = 10000000;  //随便设置一个大数
    for (list<stNode*>::iterator it = nodeList.begin(); it != nodeList.end(); it++)
    {
        //比较F值， 如果当前点的F小于tempF
        if ((*it)->f < tempF)
        {
            pNode = (*it);
            tempF = (*it)->f;
        }
    }
    return pNode;
}
//pNode 周围的点放到ListNear 中， 要求点不在启动列表和关闭列表，且不能是障碍点
void GetNearNodeList(stNode* pNode, list<stNode*> & listNear,
    list<stNode*> listStart, list<stNode*> listEnd, stNode* pEndNode)

{
    //把一个节点旁边的8个点,3*3的格子放到ListNear
    for (int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            //点自己不加
            if (i == 0 && j == 0) 
            {
                continue;
            }
            //得到周围点的座标
            int rowTemp = pNode->row + i;
            int rankTemp = pNode->rant + j;

            //越界的格子不加
            if (rowTemp < 0 || rowTemp > 9 ||
                rankTemp <0 || rankTemp > 9)
            {
                continue;
            }
            //阻断点不加
            if (G_PathLattice[rowTemp][rankTemp] == 1)
            {
                continue;
            }

            //在开启表
            stNode node;
            node.row = rowTemp;
            node.rant = rankTemp;
            if (IsNodeInList(&node, listStart))
            {
                continue;
            }
            if (IsNodeInList(&node, listEnd))
            {
                continue;
            }

            stNode* pNearNode = new stNode;
            pNearNode->g = pNode->g + Distance(pNode->row, pNode->rant, rowTemp, rankTemp);
            pNearNode->h = Distance(rowTemp, rankTemp, pEndNode->row, pEndNode->rant);
            pNearNode->f = pNearNode->g + pNearNode->h;
            pNearNode->row = rowTemp;
            pNearNode->rant = rankTemp;
            pNearNode->pParent = pNode;
            listNear.push_back(pNearNode);
        }
    }
}

void EraseFromList(stNode* pNode, list<stNode*>& nodeList)
{
    for (list<stNode*>::iterator it = nodeList.begin(); it != nodeList.end(); it++)
    {
        if (pNode->row == (*it)->row && pNode->rant == (*it)->rant)
        {
            nodeList.erase(it);
            return;
        }
    }
}

void ClearList(list<stNode*>nodeList)
{
    for (list<stNode*>::iterator it = nodeList.begin(); it != nodeList.end();it++)
    {
        delete *it;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    //起点的横坐标、纵坐标，终点的横坐标、纵坐标
    int rowStart, rankStart, rowEnd, rankEnd;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            if (G_PathLattice[i][j] == 3)
            {
                rowStart = i;
                rankStart = j;
            }
            else if (G_PathLattice[i][j] == 4)
            {
                rowEnd = i;
                rankEnd = j;
            }
        }
    }
    //构建起始点
    stNode* nodeStart = new stNode;
    nodeStart->row = rowStart;
    nodeStart->rant = rankStart;
    nodeStart->g = 0;
    nodeStart->h = Distance(rowStart, rankStart, rowEnd, rankEnd);
    nodeStart->f = nodeStart->h;
    nodeStart->pParent = NULL;

    //构建终点
    stNode* nodeEnd = new stNode;
    nodeEnd->row = rowEnd;
    nodeEnd->rant = rankEnd;


    list<stNode*> listStart;
    list<stNode*> listEnd;

    //1.把A加入启动列表
    listStart.push_back(nodeStart);
    //2.在启动列表中找权值最小的格子
    //终点是否在启动列表中，如果在，说明已经找到路径，退出循环；
    stNode* pNowNode = NULL;//当前遍历到的节点
    while (!IsNodeInList(nodeEnd, listStart))
    {
        //2.在启动列表中找权值最小的格子--找到最小的格子作为当前点
        pNowNode = GetNearestNode(listStart);
        if (pNowNode == NULL)
        {
            //说明启动列表中没有点了！说明路径不存在
            printf("路径不存在\n");
            break;
        }

        //3. 在当前格子周围的格子，放到启动列表中
        list<stNode*> listNear; //存放当前格子周围符合加入启动列表条件的格子
        GetNearNodeList(pNowNode, listNear, listStart, listEnd, nodeEnd);

        //把当前节点放到listEnd里面
        listEnd.push_back(pNowNode);
        //把当前节点从启动列表删除
        EraseFromList(pNowNode, listStart);

        //把周围点全放到开启列表中；
        for (list<stNode*>::iterator it = listNear.begin(); it != listNear.end(); it++)
        {
            listStart.push_back(*it);
        }
    }

    if (pNowNode == NULL)
    {
        printf("路径不存在\n");
        ClearList(listStart);
        ClearList(listEnd);
        return 0;
    }

    //在开启列表中找到终点
    stNode* pNodeFind = NULL;
    for (list<stNode*>::iterator it = listStart.begin(); it != listStart.end(); it++)
    {
        if ((*it)->row == nodeEnd->row &&
            (*it)->rant == nodeEnd->rant)
        {
            pNodeFind = (*it);
            break;
        }
    }

    if (pNowNode == NULL)
    {
        printf("路径不存在\n");
        ClearList(listStart);
        ClearList(listEnd);
        return 0;
    }

    //从最后一个点， 通过parant指针，逆向打印出路径
    while (pNodeFind)
    {
        G_PathLattice[pNodeFind->row][pNodeFind->rant] = 2;
        pNodeFind = pNodeFind->pParent;
    }

    for (int i = 0; i < 10;i++)
    {
        for (int j = 0; j < 10; j++)
        {
            if (G_PathLattice[i][j] == 0)
            {
                printf("^ ");
            }
            else if (G_PathLattice[i][j] == 1)
            {
                printf("* ");
            }
            else if (G_PathLattice[i][j] == 2)
            {
                printf("# ");
            }
            else if (G_PathLattice[i][j] == 3 || G_PathLattice[i][j] == 4)
            {
                printf("@ ");
            }


        }
        printf("\n");
    }

    ClearList(listStart);
    ClearList(listEnd);
    return 0;
}

---

3. 效果

//设置的虚拟地图： 3：开始点， 4 是终点，1：阻断点，0：可以走的点
int G_PathLattice[10][10]=
{
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 1, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 3, 0, 1, 0, 1, 4, 0, 0 },
    { 0, 0, 0, 0, 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, 1, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 }
};

‘’#‘’：路径
‘’* ‘’：阻断点
‘’^‘’：可走点

免费观看的教学视频