• 新浪微博:
  • 按键公众号 :
按键精灵电脑版
立即下载

软件版本:2014.06
软件大小:22.9M
更新时间:03-18

按键精灵安卓版
立即下载

软件版本:3.5.3
软件大小:46.2M
更新时间:03-02

按键精灵iOS版
立即下载

软件版本:1.7.3
软件大小:29.2M
更新时间:12-06

最新企业版UiBot
立即下载

软件版本:3.3
软件大小:282M
更新时间:08-06

快捷导航

登录 后使用快捷导航
没有帐号? 注册

发新话题 回复该主题

[分享脚本] 求多点最短路线的算法分享 [复制链接]

1#
先看两个实例:
一、    游戏里接到几个任务需要去几个不同地点与NPC交互后最后到达同一个终点交任务,如何计算最短路线。
二、    2D游戏中识别到周围有N只怪物,如何获得最佳路线全部击杀后到达指定终点继续下一轮识别。

百度一下,就会知道,解决类似问题的算法都是非常复杂难懂的,那么有没有可能用简单的逻辑来实现呢。
楼主在地下城堡2手游中正好碰到了这个问题,经过几个小时的设计,找到了一个算法。
这里就以地下城堡2的例子来说明:
该游戏的怪物是分布在二维地图上的,算法前提是我们已经识别出了起点(就是自己当前的位置)附近11*11范围内的全部怪物,我们需要先全部击杀(只需要靠近怪物距离为1即可,不需要重叠),最后到达目标终点。
首先我们准备一个通用距离函数:
Function 求距离(x1, y1, x2, y2)
求距离 = Abs(x1 - x2) + Abs(y1 - y2)
End Function
然后,我们先将问题简化,写一个三个点求最段路线的函数,该函数应该获得从点1(x1,y1)靠近点2(x2,y2)到达点3(x3,y3)的最短线路的长度和最靠近点2的某个点的坐标:
Function 求中点(x1, y1, x2, y2, x3, y3)
//返回3个点从1
Dim 距离(4),返回数组(1),min,i
距离(0) = 求距离(x1, y1, x2, y2-1) + 求距离(x2, y2-1, x3, y3)
距离(1) = 求距离(x1, y1, x2, y2+1) + 求距离(x2, y2+1, x3, y3)
距离(2) = 求距离(x1, y1, x2-1, y2) + 求距离(x2-1, y2, x3, y3)
距离(3) = 求距离(x1, y1, x2+1, y2) + 求距离(x2+1, y2, x3, y3)
距离(4) = 求距离(x1, y1, x2, y2) + 求距离(x2, y2, x3, y3)
min=100
For i = 0 To 4
If 距离(i)<min then min=距离(i)
Next
Dim 返回值(1)
If min = 距离(0) Then
返回数组(1) = x2 & "," & (y2 - 1)        
ElseIf min = 距离(1) Then
返回数组(1) = x2 & "," & (y2 + 1)        
ElseIf min = 距离(2) Then
返回数组(1) = (x2 - 1) & "," & y2
ElseIf min = 距离(3) Then
返回数组(1) = (x2 + 1) & "," & y2
Else
返回数组(1) = x2 & "," & y2
End If
返回数组(0) = min
求中点 = 返回数组
End Function
最简单的解决了,那么增加点的数量后如何解决呢,这里采用递归算法:
Function 求路线(起点x, 起点y, 中间点序列, 终点x, 终点y)'中间点序列 是整数字符串,每一位标识的是怪物的序号,如"0123"
Dim 返回数组(1), l, 记录数组(7, 1)
Dim a,b,c,i,min,d,d1,e
l = len(中间点序列)
返回数组(0) = 0
返回数组(1) = ""
If l = 0 Then
返回数组(0) = 求距离(起点x, 起点y, 终点x, 终点y)
求路线 = 返回数组
Exit Function
ElseIf l = 1 Then
a=Cint(中间点序列)
求路线 = 求中点(起点x, 起点y, 怪物(a, 0), 怪物(a, 1), 终点x, 终点y)
Exit Function
End If
//超过1个怪的情况用递归,求出最短路线
//第一步,先顺序抽取某一位,作为第一个,然后对剩下的进行递归
For i = 1 To l
a = Cint(mid(中间点序列, i,1))'第i个转整数
If i > 1 Then
b = Left(中间点序列, i - 1)
Else
b=""
End If
If l > i Then
b = b & right(中间点序列, l - i)
End If
'TracePrint "抽取"&a&"递归"&b
c = 求路线(怪物(a, 0), 怪物(a, 1), b, 终点x, 终点y)'改变起点和中间序列
d = split(c(1), "|")
d1 = Split(d(0), ",")
e=求中点(起点x, 起点y, 怪物(a, 0), 怪物(a, 1),Cint(d1(0)),Cint(d1(1)))
记录数组(i - 1, 0) = c(0) + e(0)
记录数组(i - 1, 1) = e(1)&"|"&c(1)
Next
//第二步,对结果进行取小
min = 1000
For i = 0 To l - 1
If 记录数组(i, 0) < min Then min = 记录数组(i, 0)
Next
//第三步,返回最小值
For i = 0 To l - 1
If min = 记录数组(i, 0) Then
返回数组(0) = min
返回数组(1) = 记录数组(i, 1)
求路线 = 返回数组
Exit For
End If
Next
End Function
上面函数中使用到的怪物数组需要提前识别赋值,为了测试,我们来做一个模拟,先写一个地图数据赋值,用2代表非怪物,1表示怪物,0为障碍(关于规避障碍和坐标越界这里忽略):
Function 加载地图数据()
Dim str(12),arr,i,j
str(0) = "2 2 2 2 2 2 2 2 2 1 2 2 2"
str(1) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(2) = "2 2 0 2 2 2 2 2 2 2 2 2 2"
str(3) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(4) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(5) = "1 2 2 2 2 2 1 2 2 2 2 2 2"
str(6) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(7) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(8) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(9) = "2 2 2 2 2 2 2 2 2 2 2 2 2"
str(10) = "2 1 2 2 2 2 2 2 2 2 2 2 2"
str(11) = "2 2 2 2 2 2 2 2 2 2 2 9 2"
str(12) = "2 2 2 2 2 1 2 2 2 2 2 2 2"
//2表示空地,1为中间点,即怪物,5为,起点和终点
For i = 0 To UBound(str)
arr = split(str(i), " ")
For j = 0 To UBound(arr)
map(j,i)=Cint(arr(j))
Next
Next
End Function
再来一个地图数据输出:
Function 读取地图()
Dim str,i,j
For i = 0 To 12
For j = 0 To 12
str = str & map(j, i) & " "
Next
str=Replace(str,"2","十")'空地
str=Replace(str,"9","终")
str=Replace(str,"0","起")
str=Replace(str,"1","Ⅹ")'客户
TracePrint str
str=""
Next
End Function
所有的准备做好后,我们启动调试吧:
Dim map(100, 100)
Dim 怪物(7,1)
Dim 怪物数
Call 加载地图数据()
Call 读取地图()
怪物数 =0
For i = 0 To 12
For j = 0 To 12
If map(i, j) = 1 Then
怪物(怪物数, 0) = i
怪物(怪物数, 1) = j
怪物数 = 怪物数 + 1            
End If
Next
Next
Dim a1
a1 = 求路线(2, 2, "01234", 11, 11)
TracePrint "总长度="&a1(0)&",需要经过的中间点为:"&a1(1)
实际使用中,怪物是通过其它方式比如找图、找色、内存等待方式现行识别到后存入到数组里的。
下面是调试结果:

您的脚本在调试过程中,产生了下列调试信息:
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 Ⅹ 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 起 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:Ⅹ 十 十 十 十 十 Ⅹ 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 Ⅹ 十 十 十 十 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 十 十 十 十 十 十 终 十
脚本 多点最短连通路线.Q ,第121行:十 十 十 十 十 Ⅹ 十 十 十 十 十 十 十
脚本 多点最短连通路线.Q ,第18行:总长度=58,需要经过的中间点为:9,1|6,4|1,5|1,9|5,11
您所在的用户组无法下载或查看附件

路线长度含有很多首尾部分,实际结果只有30多步,因为只是在各条递归分支之间比大小,并不使用最后结果,所以无关紧要。
以上算法可能并非最好,也不会是最快,仅仅是最简单的算法罢了。

最后编辑zhao_771123 最后编辑于 2017-12-06 02:43:28
按键会友,共同进步,QQ 3766 9324地下城堡2辅助交流http://bbs.anjian.com/showtopic-660386-1.aspx
2#

没有精心排版,大家将就着看吧
PS:模拟数组里0是起点,9是终点,注释里写错了,懒得重新编辑了

按键会友,共同进步,QQ 3766 9324地下城堡2辅助交流http://bbs.anjian.com/showtopic-660386-1.aspx
3#

回家考虑回家考虑

4#

多谢

5#

值得学习

6#

好东西,,,楼主讲的明白

7#

谢谢分享,看看

8#

学习学习学习了

9#

学习啊亲

10#

终于看到个能学习的了

11#

看看

12#

好专业呀求学习

5年专业脚本作者,免费解决脚本异议和遇到问题,专业制作脚本,专业一对一收徒VX:dream_is_come
13#

旧帖子其实不该隐藏啦,被逼顶老帖。。。

好好疼你怀里的媳妇吧
14#

学习学习

15#

学习一下,谢谢分享

16#

好东西我要看看

17#

好东西,学习了

18#

火了

19#

跟大佬学习,好好学

20#

大佬好!

熊家班熊叫兽
发新话题 回复该主题