【教程】【GC八段】魔兽自动寻路之二：最短路径算法LUA版本
本帖最后由 托托 于 2016-2-3 21:32 编辑对上篇帖子的回顾：
上次我发了一个帖子，关于如何自动躲避障碍物的方法，传送门，龙套、醉骚也提供了不少想法。
对这些想法进行研究之后，发现智能躲避障碍物有一个问题，采用之前提到的方法，只能躲避一些简单的障碍，对于那种迷宫式的障碍，很容易就会卡住。解决的办法就是需要知道魔兽的模型形状，然后采用A*算法就可以智能获取最短路径。——难点在于我不知道怎么获取地形，加上魔兽bt的模型，所以这条路暂时打住了。
本次主题：
最近尝试用了一下hb，主要是收菜，所以我就针对收菜来说，别的场景的也是类似。
根据人物在里面的行为，大概推测出hb是在要塞中先记录一些坐标，然后hb就通过在这些坐标之间移动，达到不会卡住的目的。如果不能理解这个，可以试想一下，要塞里面有N个梅花桩，你只能在梅花桩上走路的情形，走梅花桩是人肉就能做到的，很简单，而最短路径要解决的就是如何从你目前所在的位置到达目的坐标，例如从要塞里面到矿井。
拿上面这个图来举例子，每个橙色的圈代表一个坐标，坐标之间有线的代表这两个点是可见的（魔石用msII方法可以判断），线上的数字代表距离。如果两个点之间没有线，就代表不可见，也就是你走过去的话会卡住的。
假设我要从1走到5，最短路径就是1、3、4、5，我们的算法就是要计算出这个1、3、4、5。避免你的人物在几个点之间迷茫。
废话结束上代码：
最后一个方法是算法方法，算法是dijkstra。前面是我写的移动的例子。使用的时候只需要用m2方法就可以了，提前采集好中介点，然后m2矿洞，就自己过去了，m2钓鱼点就自己过去了，是不是很屌。
我试了一下可以用，大家可以试试看，有问题一起探讨~~
way_frame = way_frame or CreateFrame("frame");
MAXINT = 32767;
--------------------------------------------------------------
--移动到目标点
--tar可以是坐标、坐标table、unit
--mediators是中介点，可为空。为空的话就是简单的移动，加上中介点的话，可以使用这些点自动获取可用的最短距离进行移动
--例如：m2("target")
--例如：m2({1,2,3})
--例如：local mediators={{1,1,1},{2,2,2}}; m2("target", mediators);
--------------------------------------------------------------
function move2(tar, mediators)
local xt, yt, zt;--target's point
if type(tar) == "table" then
xt, yt, zt = tar,tar,tar;
elseif type(tar) == "string" and UnitExists(tar) then
xt, yt, zt = ObjectPosition(tar);
end
if mediators and #mediators>0 then
local x0,y0,z0 = ObjectPosition("player");
local path = getShortestPath({x0,y0,z0}, {xt,yt,zt}, mediators);
moveAlongPositions(path);
else
MoveTo(xt,yt,zt);
end
end
m2 = move2;
--------------------------------------------------------------
--按照固定的点移动
--例如：list={{1,1,1},{2,2,2}};moveAlongPositions(list);
--------------------------------------------------------------
function moveAlongPositions(posList)
local i=1;
way_frame:SetScript("OnUpdate", function()
if not msgv("way_time") or GetTime()-msgv("way_time")>0.1 then
mssv("way_time",GetTime());
local x0,y0,z0 = msGUL("player");--player's position
local x1,y1,z1 = posList, posList,posList;--target's position
if abs(x1-x0)>1 or abs(y1-y0)>1 then
MoveTo(x1,y1,z1);
else
print("到达：",x1,y1,z1);
if i==#posList then
way_frame:SetScript("OnUpdate",nil);
else
i=i+1;
end
end
end
end);
end
--------------------------------------------------------------
--获取最短路径点
--例如：start={1,1,1}; target={5,5,5}; mediators={{3,3,3},{2,2,2}}; list=getShortestPath(start, target, mediators);
--------------------------------------------------------------
function getShortestPath(start, target, mediators)
local points = mediators or {};
table.insert(points,1,start);
table.insert(points,target);
for _,v in ipairs(points) do print(v);end
local pointsDiagram = {};
local i,j;
for i=1,#points,1 do
local pd = {};
for j=1,#points,1 do
local dist = MAXINT;
if i==j then
dist = 0;
else
if not TraceLine(points, points, points+1, points, points, points+1, 0x10) then
dist = msGD(points, points);
end
end
table.insert(pd, dist);
end
table.insert(pointsDiagram, pd);
end
local path = getShortestPathIdx(1,#points,pointsDiagram);
local resultPoints = {};
for i,v in ipairs(path) do
table.insert(resultPoints, points);
end
return resultPoints;
end
--------------------------------------------------------------
--根据各点距离信息获得两点的最短路径
--例如：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);
--------------------------------------------------------------
function getShortestPathIdx(startIdx, endIdx, pointsDiagram)
local dist={};--记录startIdx到各个点的距离
local prev={};--记录路径
local S={};--判断是否已存入该点到S集合中
local pointCount = #pointsDiagram;
local i;
local j;
--init
for i=1,pointCount,1 do
dist = pointsDiagram;
S = false;--初始都未用过该点
if dist == MAXINT then
prev = -1;
else
prev = startIdx;
end
end
dist = 0;
S = true; --起始点out
--计算
for i=2,pointCount,1 do
local mindist = MAXINT;
local u = startIdx;
--找出当前未使用的点j的dist最小值
for j=1,pointCount,1 do
if not S and dist<mindist then
--u保存当前邻接点中距离最小的点的号码
u, mindist = j, dist;
end
end
S = true;
for j=1,pointCount,1 do
if not S and pointsDiagram<MAXINT then
--在通过新加入的u点路径找到离startIdx点更短的路径
if dist + pointsDiagram < dist then
dist = dist + pointsDiagram;--更新dist
prev = u;--记录前驱顶点
end
end
end
end
local result={endIdx};
i=endIdx;
while i ~= startIdx do
i = prev;
table.insert(result,1,i);
end
return result;
end
附赠一个录制坐标的方法，自动记录到魔兽目录下的_ys_points.txt文件中了，文件会自动生成。——这个是@醉骚原创的，我改写了一下。
function record2file(unit)
unit = unit or "player"
if not UnitExists(unit) then
print("unit not exists: "..unit)
return;
end
local X, Y, Z = ObjectPosition(unit);
local folder = GetWoWDirectory();
local filePath = folder.."\\_ys_points.txt";
WriteFile (filePath,"{" .. X .. "," .. Y .. ",".. Z .. "},\n" ,true )
print (unit,X,Y,Z)
end
老胡给力 请收下我的膝盖:hug: 这个很666666老胡66666666666666 这个叼炸天啊~~~~~~~~~~~~ 这个太流弊了{:5_236:} 向科学致敬！ 老胡同志一看就是程序猿 非常吊的原创！很给力 测试下回帖速度 测试回帖速度
页:
[1]
2