【教程】【GC八段】魔兽自动寻路之二：最短路径算法LUA版本

老胡

对上篇帖子的回顾：
上次我发了一个帖子，关于如何自动躲避障碍物的方法，传送门，龙套、醉骚也提供了不少想法。

对这些想法进行研究之后，发现智能躲避障碍物有一个问题，采用之前提到的方法，只能躲避一些简单的障碍，对于那种迷宫式的障碍，很容易就会卡住。解决的办法就是需要知道魔兽的模型形状，然后采用A*算法就可以智能获取最短路径。——难点在于我不知道怎么获取地形，加上魔兽bt的模型，所以这条路暂时打住了。


本次主题：
最近尝试用了一下hb，主要是收菜，所以我就针对收菜来说，别的场景的也是类似。

根据人物在里面的行为，大概推测出hb是在要塞中先记录一些坐标，然后hb就通过在这些坐标之间移动，达到不会卡住的目的。如果不能理解这个，可以试想一下，要塞里面有N个梅花桩，你只能在梅花桩上走路的情形，走梅花桩是人肉就能做到的，很简单，而最短路径要解决的就是如何从你目前所在的位置到达目的坐标，例如从要塞里面到矿井。



拿上面这个图来举例子，每个橙色的圈代表一个坐标，坐标之间有线的代表这两个点是可见的（魔石用msII方法可以判断），线上的数字代表距离。如果两个点之间没有线，就代表不可见，也就是你走过去的话会卡住的。

假设我要从1走到5，最短路径就是1、3、4、5，我们的算法就是要计算出这个1、3、4、5。避免你的人物在几个点之间迷茫。

废话结束上代码：
最后一个方法是算法方法，算法是dijkstra。前面是我写的移动的例子。使用的时候只需要用m2方法就可以了，提前采集好中介点，然后m2矿洞，就自己过去了，m2钓鱼点就自己过去了，是不是很屌。

我试了一下可以用，大家可以试试看，有问题一起探讨~~

1. way_frame = way_frame or CreateFrame("frame");
   
2. MAXINT = 32767;
   
3. 
   
4. --------------------------------------------------------------
   
5. --移动到目标点
   
6. --tar可以是坐标、坐标table、unit
   
7. --mediators是中介点，可为空。为空的话就是简单的移动，加上中介点的话，可以使用这些点自动获取可用的最短距离进行移动
   
8. --例如：m2("target")
   
9. --例如：m2({1,2,3})
   
10. --例如：local mediators={{1,1,1},{2,2,2}}; m2("target", mediators);
    
11. --------------------------------------------------------------
    
12. function move2(tar, mediators)
    
13.         local xt, yt, zt;--target's point
    
14.         if type(tar) == "table" then
    
15.                 xt, yt, zt = tar[1],tar[2],tar[3];
    
16.         elseif type(tar) == "string" and UnitExists(tar) then
    
17.                 xt, yt, zt = ObjectPosition(tar);
    
18.         end
    
19.         
    
20.         if mediators and #mediators>0 then
    
21.                 local x0,y0,z0 = ObjectPosition("player");
    
22.                 local path = getShortestPath({x0,y0,z0}, {xt,yt,zt}, mediators);
    
23.                 moveAlongPositions(path);
    
24.         else
    
25.                 MoveTo(xt,yt,zt);
    
26.         end
    
27. end
    
28. m2 = move2;
    
29. 
    
30. --------------------------------------------------------------
    
31. --按照固定的点移动
    
32. --例如：list={{1,1,1},{2,2,2}};moveAlongPositions(list);
    
33. --------------------------------------------------------------
    
34. function moveAlongPositions(posList)
    
35.         local i=1;
    
36.         way_frame:SetScript("OnUpdate", function()
    
37.                 if not msgv("way_time") or GetTime()-msgv("way_time")>0.1 then
    
38.                         mssv("way_time",GetTime());
    
39.                         
    
40.                         local x0,y0,z0 = msGUL("player");--player's position
    
41.                         local x1,y1,z1 = posList[i][1], posList[i][2],posList[i][3];--target's position
    
42.                         if abs(x1-x0)>1 or abs(y1-y0)>1 then
    
43.                                 MoveTo(x1,y1,z1);
    
44.                         else
    
45.                                 print("到达：",x1,y1,z1);
    
46.                                 if i==#posList then
    
47.                                         way_frame:SetScript("OnUpdate",nil);
    
48.                                 else
    
49.                                         i=i+1;
    
50.                                 end
    
51.                         end
    
52.                 end
    
53.         end);
    
54. end
    
55. 
    
56. --------------------------------------------------------------
    
57. --获取最短路径点
    
58. --例如：start={1,1,1}; target={5,5,5}; mediators={{3,3,3},{2,2,2}}; list=getShortestPath(start, target, mediators);
    
59. --------------------------------------------------------------
    
60. function getShortestPath(start, target, mediators)
    
61.         local points = mediators or {};
    
62.         table.insert(points,1,start);
    
63.         table.insert(points,target);
    
64.         
    
65.         for _,v in ipairs(points) do print(v);end
    
66.         
    
67.         local pointsDiagram = {};
    
68.         local i,j;
    
69.         for i=1,#points,1 do
    
70.                 local pd = {};
    
71.                 for j=1,#points,1 do
    
72.                         local dist = MAXINT;
    
73.                         if i==j then
    
74.                                 dist = 0;
    
75.                         else
    
76.                                 if not TraceLine(points[i][1], points[i][2], points[i][3]+1, points[j][1], points[j][2], points[j][3]+1, 0x10) then
    
77.                                         dist = msGD(points[i], points[j]);
    
78.                                 end
    
79.                         end
    
80.                         table.insert(pd, dist);
    
81.                 end
    
82.                 table.insert(pointsDiagram, pd);
    
83.         end
    
84.         
    
85.         local path = getShortestPathIdx(1,#points,pointsDiagram);
    
86.         
    
87.         local resultPoints = {};
    
88.         for i,v in ipairs(path) do
    
89.                 table.insert(resultPoints, points[v]);
    
90.         end
    
91.         return resultPoints;
    
92. end
    
93. 
    
94. --------------------------------------------------------------
    
95. --根据各点距离信息获得两点的最短路径
    
96. --例如：local A={{0,2,3,MAXINT,MAXINT},{2,0,MAXINT,4,MAXINT},{3,MAXINT,0,2,4},{MAXINT,4,2,0,1},{MAXINT,MAXINT,4,1,0}};Dijkstra(1,5,A);
    
97. --------------------------------------------------------------
    
98. function getShortestPathIdx(startIdx, endIdx, pointsDiagram)
    
99.         local dist={};--记录startIdx到各个点的距离
    
100.         local prev={};--记录路径
     
101.         local S={};--判断是否已存入该点到S集合中
     
102.         local pointCount = #pointsDiagram;
     
103.         local i;
     
104.         local j;
     
105.         
     
106.         --init
     
107.         for i=1,pointCount,1 do
     
108.                 dist[i] = pointsDiagram[startIdx][i];
     
109.                 S[i] = false;--初始都未用过该点
     
110.                 if dist[i] == MAXINT then
     
111.                         prev[i] = -1;
     
112.                 else
     
113.                         prev[i] = startIdx;
     
114.                 end
     
115.         end
     
116.         dist[startIdx] = 0;
     
117.         S[startIdx] = true; --起始点out
     
118.         
     
119.         --计算
     
120.         for i=2,pointCount,1 do
     
121.                 local mindist = MAXINT;
     
122.                 local u = startIdx;
     
123.                 --找出当前未使用的点j的dist[j]最小值
     
124.                 for j=1,pointCount,1 do
     
125.                         if not S[j] and dist[j]<mindist then
     
126.                                 --u保存当前邻接点中距离最小的点的号码
     
127.                                 u, mindist = j, dist[j];
     
128.                         end
     
129.                 end
     
130.                 S[u] = true;
     
131.                 for j=1,pointCount,1 do
     
132.                         if not S[j] and pointsDiagram[u][j]<MAXINT then
     
133.                                 --在通过新加入的u点路径找到离startIdx点更短的路径  
     
134.                                 if dist[u] + pointsDiagram[u][j] < dist[j] then
     
135.                                         dist[j] = dist[u] + pointsDiagram[u][j];--更新dist
     
136.                                         prev[j] = u;--记录前驱顶点
     
137.                                 end
     
138.                         end
     
139.                 end
     
140.         end
     
141.         
     
142.         local result={endIdx};
     
143.         i=endIdx;
     
144.         while i ~= startIdx do
     
145.                 i = prev[i];
     
146.                 table.insert(result,1,i);
     
147.         end
     
148.         return result;
     
149. end

复制代码

附赠一个录制坐标的方法，自动记录到魔兽目录下的_ys_points.txt文件中了，文件会自动生成。——这个是@醉骚原创的，我改写了一下。

1. function record2file(unit)
   
2.         unit = unit or "player"
   
3.         if not UnitExists(unit) then
   
4.                 print("unit not exists: "..unit)
   
5.                 return;
   
6.         end
   
7.         local X, Y, Z = ObjectPosition(unit);
   
8.         local folder = GetWoWDirectory();
   
9.         
   
10.         local filePath = folder.."\\_ys_points.txt";
    
11.         WriteFile (filePath,"{" .. X .. "," .. Y .. ","  .. Z .. "},\n" ,true )
    
12.         print (unit,X,Y,Z)
    
13. end

复制代码

自摸王

老胡给力   请收下我的膝盖

强力老猫

这个很666666老胡66666666666666

无相魔

这个叼炸天啊~~~~~~~~~~~~

深秋的黎明

这个太流弊了

老血

向科学致敬！

kleinsoul

老胡同志一看就是程序猿

白鼻子的黑猫

非常吊的原创！很给力

日后再说

测试下回帖速度

日后再说

测试回帖速度