【A*算法】C++实现及地图寻路

    首先看一下效果吧：

    首先是点击“打开”菜单导入了一张背景图，接着点击“设置”菜单设置地图的大小（也就是几行几列），然后点击“标记障碍”工具画出了红色的障碍物，再设置一下蓝色的起点和绿色的终点并点击“测试”就得出了黄色的路径了。

    “导出”菜单用于导出地图，也就是用二维数组表示的地图，0表示可以通行，1表示障碍物。

导出的地图数据放在同级目录下的data.txt文件中，该文件是这样的：

     第一行是是地图的行数m和列数n，其余数据有m行n列，对应地图中的格子是否有障碍物。

    该程序是C#的WPF程序，而A*算法的功能在由C++实现的DLL中。

    压缩包可以在 https://github.com/WhiteOrangeChen/Projects 下载，名称为“地图制作”，包含了一个exe程序，AStar.dll及C++，WPF源码及一个使用说明文档。

    提示，可以用来做小游戏哦^_^。

A*算法的C++实现

    A*算法的主流程：

    

    如果找到路径，则返回一个路径的逆序单链表；否则否则空。

其中，Node的定义如下：

    Point是一个只包含 int x, y; 的结构体。

    Map是一个描述地图的结构体：

    添加节点的函数：

    也就是只有没访问过的才会加入队列中进行扩展，其中nodes是一个链表，保存了实际的节点数据，而队列queue和visit中保存的都是节点指针，以便更高效。

    曼哈顿距离的求法，就是 |x1-x2| + |y1-y2|，对于不同的问题，需要的估计代价的函数不同，具体问题具体分析。

    扩展节点的函数

上下左右移动的函数

    判断一个点是否有效的函数

    

最后

    需要帮助的话可以提出来的，也可以合作开发程序。