技术宅的结界

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

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 1046|回复: 8
收起左侧

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

[复制链接]

1010

主题

2246

帖子

5万

积分

用户组: 管理员

一只技术宅

UID
1
精华
200
威望
265 点
宅币
16901 个
贡献
33732 次
宅之契约
0 份
在线时间
1608 小时
注册时间
2014-1-26
发表于 2016-7-14 04:46:13 | 显示全部楼层 |阅读模式

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

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

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

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


示例图:
Astar_progress_animation.gif

VB示例关键部分的源码:
[Visual Basic] 纯文本查看 复制代码
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
20160714052426.png

其中我这个实例还会显示寻路过程的动画。在窗口左边的设置里面。
实例exe下载: AStar.exe (36 KB, 下载次数: 14)

本帖被以下淘专辑推荐:

1010

主题

2246

帖子

5万

积分

用户组: 管理员

一只技术宅

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

0

主题

2

帖子

10

积分

用户组: 初·技术宅

UID
2835
精华
0
威望
1 点
宅币
6 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2017-9-4
发表于 2017-9-4 18:57:46 | 显示全部楼层
这个相当不错.学习一下.

0

主题

17

帖子

44

积分

用户组: 初·技术宅

UID
3001
精华
0
威望
0 点
宅币
27 个
贡献
0 次
宅之契约
0 份
在线时间
2 小时
注册时间
2017-10-23
发表于 2017-10-23 18:06:46 | 显示全部楼层
好好跟楼主学习

0

主题

4

帖子

16

积分

用户组: 初·技术宅

UID
3125
精华
0
威望
1 点
宅币
10 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2017-11-22
发表于 2017-11-26 10:09:06 | 显示全部楼层
这个可以学习

2

主题

61

帖子

458

积分

用户组: 中·技术宅

UID
2364
精华
0
威望
0 点
宅币
397 个
贡献
0 次
宅之契约
0 份
在线时间
53 小时
注册时间
2017-3-30
发表于 2018-8-2 21:34:14 | 显示全部楼层
若要下载源码,请先回帖。回帖后即可下载附件

0

主题

31

帖子

89

积分

用户组: 小·技术宅

UID
1457
精华
0
威望
2 点
宅币
54 个
贡献
0 次
宅之契约
0 份
在线时间
5 小时
注册时间
2016-1-29
发表于 2018-9-15 00:41:37 | 显示全部楼层
A星算法。。。
回复

使用道具 举报

0

主题

6

帖子

31

积分

用户组: 初·技术宅

UID
3983
精华
0
威望
0 点
宅币
25 个
贡献
0 次
宅之契约
0 份
在线时间
4 小时
注册时间
2018-6-23
发表于 2018-10-1 10:52:54 | 显示全部楼层
老大,能用C或C++写一个通用的吗?

0

主题

2

帖子

17

积分

用户组: 初·技术宅

UID
4555
精华
0
威望
2 点
宅币
11 个
贡献
0 次
宅之契约
0 份
在线时间
0 小时
注册时间
2018-12-14
发表于 前天 08:41 | 显示全部楼层
学习中
回复

使用道具 举报

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号|网站地图

GMT+8, 2018-12-16 07:04 , Processed in 0.112984 second(s), 41 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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