【VB】A*寻路算法实例（原理、资料、实例源码下载）

0xAA55 · 发表于 2016-7-14 04:46:13

欢迎访问技术宅的结界，请注册或者登录吧。

您需要登录才可以下载或查看，没有账号？立即注册→加入我们

×

A*搜索算法，俗称A星算法，是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。
这种寻路算法结合了BFS(Breadth First Search)和Dijkstra算法的优点，在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。

算法的主体是：

先将“开始位置”记录到开放节点。
从所有开放节点中，寻找“经过该节点时整条路的大致路程”这个数值最小的那个开放节点。
将这个开放节点移动到闭合节点中，并将其周围所有节点中，不是障碍物且没有被记录过的节点记录到开放节点中。如果其周围节点中，有一个节点等于我们的目标节点，那么寻路完毕，跳到第五步。
重新回到第二步，直到我们移除了最后一个开放节点，如果我们没有任何开放节点了，那么这意味着寻路失败，没有办法到达目的地。
我们找到了从开始节点到目标节点之间的完整的路程，通过逆推闭合节点来取得路径。

示例图：

VB示例关键部分的源码：

Function AStar_GetPath(ByVal StartX As Long, ByVal StartY As Long, ByVal EndX As Long, ByVal EndY As Long, WayOut() As WayPoint_t, TotalStepsOut As Long, Optional ByVal NoDiagonal As Boolean = False, Optional ByVal ShowSteps As Boolean = False, Optional ByVal XOff As Long, Optional ByVal YOff As Long) As Boolean
Dim I As Long, J As Long
Dim WayList() As WayPoint_t
Dim NbWayList As Long
Dim StartId As Long, EndId As Long, CurStep As Long, NewStep As Long
StartId = Map_GetId(StartX, StartY)
EndId = Map_GetId(EndX, EndY)
Dim CurX As Long, CurY As Long
CurX = StartX
CurY = StartY
Openset_Init
Closedset_Init
Closedset_Add StartX, StartY, StartX, StartY, 0, Est_Dist(StartX, StartY, EndX, EndY)
Do
'第一步：遍历当前位置周围的节点，添加到Openset表
If NoDiagonal Then
Sur_FromPos_No_Diagonal CurX, CurY
Else
Sur_FromPos CurX, CurY
End If
For I = 0 To m_NbSurround - 1
If m_Surround(I).MapId = EndId Then '如果已经找到终点，则退出循环
AStar_GetPath = True
Exit Do
End If
NewStep = CurStep + m_Surround(I).Cost
Openset_AddUnique m_Surround(I).X, m_Surround(I).Y, CurX, CurY, NewStep, NewStep + Est_Dist(m_Surround(I).X, m_Surround(I).Y, EndX, EndY)
Next
'第二步：从Openset表中找到分数最低的一个(大致全路程最短的一个)，选为下一步的节点。
I = Closedset_FromOpenset(Openset_GetLowestScoreId)
CurX = m_Closedset(I).X
CurY = m_Closedset(I).Y
CurStep = m_Closedset(I).CurStep
Loop While m_NbOpenset
'如果找出了路径，那就从闭合节点里逆推出完整路径
If AStar_GetPath Then
Wpt_Init
Wpt_Push EndX, EndY
I = m_NbClosedset - 1
Do Until m_Closedset(I).MapId = StartId
Wpt_Push m_Closedset(I).X, m_Closedset(I).Y
For J = I To 0 Step -1
If m_Closedset(I).PrevId = m_Closedset(J).MapId Then
I = J
Exit For
End If
Next
If J < 0 Then
AStar_GetPath = False
Exit Do
End If
Loop
Wpt_Push StartX, StartY
TotalStepsOut = m_NbWayPoints
ReDim WayOut(m_NbWayPoints - 1)
J = 0
For I = m_NbWayPoints - 1 To 0 Step -1
WayOut(J) = m_WayPoints(I)
J = J + 1
Next
End If
End Function

复制代码

其中我这个实例还会显示寻路过程的动画。在窗口左边的设置里面。
实例exe下载：

AStar.exe (36 KB, 下载次数: 29)
名称: AStar.exe
大小: 36864 字节
SHA1: C0119E9F9518B20058B495007507BE611E5ACFAA

若要下载源码，请先回帖。回帖后即可下载附件。

游客，如果您要查看本帖隐藏内容请回复

参考资料：
https://en.wikipedia.org/wiki/A*_search_algorithm
https://zh.wikipedia.org/wiki/A*搜寻算法

0xAA55 · 发表于 2016-7-14 04:50:15

虽然这需要我编写一个计算从当前节点到目标节点之间的大致路程的“估价函数”，但我并没有认真写。我只是随便写了个计算直线距离的函数而已。
另外我这个寻路算法实例其实支持不同属性的地形的，只是我没写属性地形，但在地图判断的地方，我留下了扩展不同属性地形的可能。其中Map_Step函数那里的注释我只写了“判断能否移动到某位置”，但这个函数实际是应该返回一个“经过该节点的成本值”。打个比方说某个节点的属性是“平整的道路”，那么Map_Step应该返回0.5f；如果这个节点是“普通的道路”，那么Map_Step应该返回1.0f；而如果这个节点是“泥泞的道路”，那么Map_Step应该返回1.5f。这样的话，经过A*寻路之后得到的路径不一定笔直，但一定是耗时最短或者成本最低的路线。

yes1111 · 发表于 2017-9-4 18:57:46

这个相当不错.学习一下.

阿呆在上海 · 发表于 2017-10-23 18:06:46

好好跟楼主学习

dedefans · 发表于 2017-11-26 10:09:06

这个可以学习

bigwind · 发表于 2018-8-2 21:34:14

若要下载源码，请先回帖。回帖后即可下载附件

搬砖工 · 发表于 2018-9-15 00:41:37

A星算法。。。

齐格飞 · 发表于 2018-10-1 10:52:54

老大，能用C或C++写一个通用的吗？

kkat1917 · 发表于 2018-12-14 08:41:26

学习中

mjm0101 · 发表于 2019-4-19 14:46:53

优化得怎么样

鱼头之王 · 发表于 2019-8-1 20:42:46

回帖后即可下载附件。

hxin123456 · 发表于 2020-4-3 21:11:53

看看学习下

大宝 · 发表于 2020-7-8 10:20:05

本帖最后由 china_shy_wzb 于 2020-7-20 13:57 编辑

寻路算法的实例

m000 · 发表于 2021-2-26 16:14:13

学习学习，感谢感谢

LP2020 · 发表于 2021-3-22 01:21:40

GOOD GOOD

wlddd · 发表于 2021-9-1 13:52:45

学习了好东西

xman2000 · 发表于 2023-3-9 05:48:28

好好跟楼主学习

gujin163 · 发表于 2023-3-14 09:59:14

你们懂的，楼主好人。

tlwh163 · 发表于 2023-3-14 10:13:17

为啥我不能回复

mmxx0212 · 发表于 2023-3-16 16:22:04

学习一下

账号		自动登录	找回密码
密码			立即注册→加入我们

【VB】A*寻路算法实例（原理、资料、实例源码下载）

欢迎访问技术宅的结界，请注册或者登录吧。

本帖被以下淘专辑推荐:

相关帖子