最短路径算法之A*(A-Star) - vb吧

level 11

小楠😳♀ 楼主

如果你在做游戏，不知道怎么让NPC追击玩家，可以试一下A*算法。
A*算法是计算在图中两点之间最短的路径，那有同学会提问了，两点之间最短距离不是直线吗。
如果加上障碍物，两点之间的直线就不一定是最短路径了。
要在两点之间找到最短路径就需要算法来计算，就少不了算法。
上测试图：

图中，每个顶点的数值，是对这个顶点的估值F。
F=G+H
G：该顶点到终点的代价
H：起点到该顶点的代价
计算代价我们用曼哈顿距离公式计算。
把A*计算的顶点化成一棵树，我们可以明显的看见一条起点到终点的路径。

2020年04月17日 00点04分 1

level 11

小楠😳♀ 楼主

实战演示：
Bilibili视频编号 BV1f5411t7Uf
打开Bilibili直接搜索即可

2020年04月17日 02点04分 2

level 11

小楠😳♀ 楼主

如果看不见源码地址或实战视频地址，回复我！

2020年04月17日 02点04分 4

level 11

小楠😳♀ 楼主

2020年04月17日 02点04分 7

level 11

小楠😳♀ 楼主

自顶

2020年04月17日 09点04分 8

level 11

璐村惂鐢ㄦ埛_0748V5Z馃惥

已经从你另一个帖子拿过了

2020年04月17日 11点04分 9

level 11

小楠😳♀ 楼主

自顶

2020年04月18日 00点04分 10

level 11

小楠😳♀ 楼主

自顶

2020年04月19日 01点04分 11

level 11

小楠😳♀ 楼主

自顶

2020年04月20日 09点04分 12

level 11

小楠😳♀ 楼主

结果一系列测试，发现了一个很严重的问题
因为贪图效率，我将寻找最小F的迭代从后往前
循环次数的确少了
但也造成了一个很严重的问题
在特殊地形中，寻找到的不是最短路径，反而绕了原路
从后往前迭代的效果：

从前往后迭代的效果

修改代码：

2020年04月21日 07点04分 13

璐村惂鐢ㄦ埛_0748V5Z馃惥

就是把循环方向改一下？

2020年04月24日 02点04分

小楠😳♀

@璐村惂鐢ㄦ埛_0748V5Z馃惥是的，从0开始循环

2020年04月25日 03点04分

璐村惂鐢ㄦ埛_0748V5Z馃惥

我觉得，你本楼的路径，不包括斜向的？

2020年04月25日 05点04分

小楠😳♀

@璐村惂鐢ㄦ埛_0748V5Z馃惥没有做斜向，如果要做斜向的话，只需要加几句就好了。

2020年04月26日 03点04分

level 11

小楠😳♀ 楼主

顶

2020年04月24日 02点04分 14

level 11

小楠😳♀ 楼主

需要源码，留下邮箱

2020年10月27日 08点10分 15

qfcy

邮箱: [email protected]

2020年10月27日 12点10分

小楠😳♀

@qfcy 已发

2020年10月29日 06点10分

qfcy

@小楠😳♀ 顺便分享自己的另一个源码: https://pan.baidu.com/s/1lbKaEyqHzuG9ZaYfETC-4Q 提取码: cqmt

2020年10月31日 07点10分

level 8

冰之源___

不考虑加个堆优化吗

2020年10月29日 12点10分 18

小楠😳♀

很久之前写的了，懒得再看了

2020年10月30日 07点10分

foxjinlin

易语言的A星看过，VB的还没看过，源码请发一份，谢谢： foxjinlin
#qq . com 请把#
换成@

2020年11月10日 04点11分

小楠😳♀

@foxjinlin 已发

2020年11月10日 06点11分

level 5

外面下很大的雨

[email protected]谢谢

2020年10月31日 08点10分 21

小楠😳♀

已发

2020年10月31日 08点10分

level 13

橡皮树😈

2020年11月16日 09点11分 22