我用 vb.2005写了一个A*寻路算法

系统崩溃

A*算法已成为经典的寻路算法，在不少实现实例中还做了细节改进。

在本站的算法文章里，有一篇《寻路算法新思维》，作者提出了一种称为“矢量寻路算法”的设想，不过只有设想理论。好像没有人讨论过这种设想是否存在漏洞，但是可以肯定的是，如果没有理论漏洞，该算法肯定比任何形式的A*算法高效。

sandy_zc_1

逆火十三: Re: Re:我用 vb.2005写了一个A*寻路算法


A*算法不至于在这个地图上算错

那可不一定，A*算法的效率取决于它的估价函数，估价函数的不同导致寻路结果不同。（所以不要以为所有的A*算法都一样）
从算法上看A*其实是DFS搜索的优化，但众所周知DFS不一定能求得最优解。

楼主的估价函数应该是两点之间的距离吧（开始那几步很明显），我也常用这种方式，不过楼主的好像还有其它优化，后面几步没有直接走到障碍。不过确实在复杂地图上有很大问题，我正考虑其它更高效的A*。

sandy_zc_1

griffin2006: Re:我用 vb.2005写了一个A*寻路算法

我喜欢！
不可达时需要较长的寻路时间，应该是一个bug吧。

这不是Bug，是算法本身的缺陷，当目的不可达时DFS会遍历每一个结点将这个地图全部搜索一遍以求找到可能的路径，当然会比较费时。地图越大越明显。

sandy_zc_1

楼主能否将程序改动一下，除了显示最终路径之外同时显示一下曾经搜索过的结点，这样对比可以看出算法的效率。

nocture

系统崩溃: Re:我用 vb.2005写了一个A*寻路算法

A*算法已成为经典的寻路算法，在不少实现实例中还做了细节改进。

在本站的算法文章里，有一篇《寻路算法新思维》，作者提出了一种称为“矢量寻路算法”的设想，不过只有设想理论。好像没有人讨论过这种设想是否存在漏洞，但是可以肯定的是，如果没有理论漏洞，该算法肯定比任何形式的A*算法高效。

这个理论已经有我的一个朋友做了实现，效率是很高的，问题是对于有面积大小的物体寻路有些困难，还在尝试。

可以参考一下他的BLOG：
http://blog.gameres.com/show.asp?BlogID=1721&column=0

马甲005

很不错啊，支持

我要做游戏

开始那几步肯定是有错误，我估计问题很可能因为没有考虑到斜跨一格和直走之间的长度差别，一般斜走的格子距离为直走的1.4倍就可以

我要做游戏

我写过的一个
使用鼠标左键画障碍，右键清除障碍

sandy_zc_1

楼上的不错。