找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 9418|回复: 21

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

[复制链接]
发表于 2016-7-14 04:46:13 | 显示全部楼层 |阅读模式

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

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

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

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


示例图:
Astar_progress_animation.gif

VB示例关键部分的源码:

  1. 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
  2. Dim I As Long, J As Long

  3. Dim WayList() As WayPoint_t
  4. Dim NbWayList As Long

  5. Dim StartId As Long, EndId As Long, CurStep As Long, NewStep As Long
  6. StartId = Map_GetId(StartX, StartY)
  7. EndId = Map_GetId(EndX, EndY)

  8. Dim CurX As Long, CurY As Long
  9. CurX = StartX
  10. CurY = StartY

  11. Openset_Init
  12. Closedset_Init

  13. Closedset_Add StartX, StartY, StartX, StartY, 0, Est_Dist(StartX, StartY, EndX, EndY)

  14. Do
  15.     '第一步:遍历当前位置周围的节点,添加到Openset表
  16.     If NoDiagonal Then
  17.         Sur_FromPos_No_Diagonal CurX, CurY
  18.     Else
  19.         Sur_FromPos CurX, CurY
  20.     End If
  21.     For I = 0 To m_NbSurround - 1
  22.         If m_Surround(I).MapId = EndId Then '如果已经找到终点,则退出循环
  23.             AStar_GetPath = True
  24.             Exit Do
  25.         End If
  26.         NewStep = CurStep + m_Surround(I).Cost
  27.         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)
  28.     Next
  29.    
  30.     '第二步:从Openset表中找到分数最低的一个(大致全路程最短的一个),选为下一步的节点。
  31.     I = Closedset_FromOpenset(Openset_GetLowestScoreId)
  32.     CurX = m_Closedset(I).X
  33.     CurY = m_Closedset(I).Y
  34.     CurStep = m_Closedset(I).CurStep
  35. Loop While m_NbOpenset

  36. '如果找出了路径,那就从闭合节点里逆推出完整路径
  37. If AStar_GetPath Then
  38.     Wpt_Init
  39.     Wpt_Push EndX, EndY
  40.     I = m_NbClosedset - 1
  41.     Do Until m_Closedset(I).MapId = StartId
  42.         Wpt_Push m_Closedset(I).X, m_Closedset(I).Y
  43.         For J = I To 0 Step -1
  44.             If m_Closedset(I).PrevId = m_Closedset(J).MapId Then
  45.                 I = J
  46.                 Exit For
  47.             End If
  48.         Next
  49.         If J < 0 Then
  50.             AStar_GetPath = False
  51.             Exit Do
  52.         End If
  53.     Loop
  54.     Wpt_Push StartX, StartY
  55.     TotalStepsOut = m_NbWayPoints
  56.     ReDim WayOut(m_NbWayPoints - 1)
  57.     J = 0
  58.     For I = m_NbWayPoints - 1 To 0 Step -1
  59.         WayOut(J) = m_WayPoints(I)
  60.         J = J + 1
  61.     Next
  62. End If
  63. End Function
复制代码
20160714052426.png

其中我这个实例还会显示寻路过程的动画。在窗口左边的设置里面。
实例exe下载: AStar.exe (36 KB, 下载次数: 32)
名称: AStar.exe
大小: 36864 字节
SHA1: C0119E9F9518B20058B495007507BE611E5ACFAA

若要下载源码,请先回帖。回帖后即可下载附件。
游客,如果您要查看本帖隐藏内容请回复


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

本帖被以下淘专辑推荐:

回复

使用道具 举报

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

使用道具 举报

发表于 2017-9-4 18:57:46 | 显示全部楼层
这个相当不错.学习一下.
回复 赞! 靠!

使用道具 举报

发表于 2017-10-23 18:06:46 | 显示全部楼层
好好跟楼主学习
回复 赞! 靠!

使用道具 举报

发表于 2017-11-26 10:09:06 | 显示全部楼层
这个可以学习
回复 赞! 靠!

使用道具 举报

发表于 2018-8-2 21:34:14 | 显示全部楼层
若要下载源码,请先回帖。回帖后即可下载附件
回复 赞! 靠!

使用道具 举报

发表于 2018-9-15 00:41:37 | 显示全部楼层
A星算法。。。
回复

使用道具 举报

发表于 2018-10-1 10:52:54 | 显示全部楼层
老大,能用C或C++写一个通用的吗?
回复 赞! 靠!

使用道具 举报

发表于 2018-12-14 08:41:26 | 显示全部楼层
学习中
回复

使用道具 举报

发表于 2019-4-19 14:46:53 | 显示全部楼层
优化得怎么样
回复 赞! 靠!

使用道具 举报

发表于 2019-8-1 20:42:46 | 显示全部楼层
回帖后即可下载附件。
回复 赞! 靠!

使用道具 举报

发表于 2020-4-3 21:11:53 | 显示全部楼层
看看学习下
回复 赞! 靠!

使用道具 举报

发表于 2020-7-8 10:20:05 | 显示全部楼层
本帖最后由 china_shy_wzb 于 2020-7-20 13:57 编辑

寻路算法的实例
回复 赞! 靠!

使用道具 举报

发表于 2021-2-26 16:14:13 | 显示全部楼层
学习学习,感谢感谢
回复 赞! 靠!

使用道具 举报

发表于 2021-3-22 01:21:40 | 显示全部楼层
GOOD GOOD
回复

使用道具 举报

发表于 2021-9-1 13:52:45 | 显示全部楼层
学习了好东西
回复 赞! 靠!

使用道具 举报

发表于 2023-3-9 05:48:28 | 显示全部楼层
好好跟楼主学习
回复 赞! 靠!

使用道具 举报

发表于 2023-3-14 09:59:14 | 显示全部楼层

你们懂的,楼主好人。
回复 赞! 靠!

使用道具 举报

发表于 2023-3-14 10:13:17 | 显示全部楼层
为啥我不能回复
回复 赞! 靠!

使用道具 举报

发表于 2023-3-16 16:22:04 | 显示全部楼层
学习一下
回复

使用道具 举报

本版积分规则

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-6-24 11:22 , Processed in 0.043685 second(s), 28 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表