Unity导出地形给服务器做寻路与AI实现
2019-06-18 本文已影响1人
zhbd
转载请注明出处：
https://www.jianshu.com/p/63b66c4a2cf9
说明
本文主要针对MMORPG这种、unity前端做好地形、如何给后端读取并实现寻路等算法的使用。
因后端有可能采用各种语言，如C++也好、C#也好。。所以本文寻路这里、算法我直接写在前端了，作为一个Unity导出工具使用。
因为主要逻辑写在后端，前端代码没有做优化整理，只是急忙实现了下算法，所以会比较难看，只为说明思路用。（不过别担心，有看到本文的放心copy+C使用即可，也欢迎留言提问）
具体思路
1目的：
image.png
2具体思路：
- 烘培出Navigation网格
- 读取网格信息生成文件。
- --------传给服务器--------
- 读取文件生成地形
- 剔除不可行走部分。
- 计算网格间距（三角形之间）作为初步的A*寻路的G值（两个相邻格子移动消耗代价）使用。
- 寻路算法
2-1 我可以省略上面的1步骤吗？？
Yes，you can~~。If any万 有 what 疑问， please 留言。
2-2 读取网格信息生成文件
UnityEngine.AI.NavMesh.CalculateTriangulation();
这个函数会读取地形，返回如下结构体NavMeshTriangulation。
我们只关心结构体中的vertices和areas变量。
vertices： 储存了bake后的地形网格的所有点
areas： 储存了由点生成三角网格的字典。
什么意思呢？？？？？？？如下图
image.png
这样就清晰明了了。上图共2个三角形，分别是ABC和ACD。
2-3--------传给服务器--------
这个也略吧。。。就传呗。。。Linux的话用FTP，电脑下载个FileZilla一拖。。。就到服务器了。。。（具体需要配置下）。不知道咋配置的也百度不到的。。。给我留言吧先。。。
2-4读取文件生成地形
既然已知全地形所有三角形的点了，就可在字典中，如上图三个一组读取一次，这样就会获取到所有的三角形。
然后遍历所有三角形，发现只要有2个点重合的，那么这两个三角形就相邻。（判断重合最好不要用等号，最好是两点间距离小于某个值。。。）
2-5剔除不可行走部分
那么画说回来，这么多三角形，如何剔除不可行走部分呢？？？
image.png
image.png
如上图，蓝色划掉的部分那个沟壑（嘿嘿嘿。。）明显是地形之外的。那么如何去除呢？？？我们可以返回再看2-4读取文件生成地形这一步，判断三角形重合点。。那么问题来啦，第一个三角形和谁去重合？最起码有个基础三角形吧！！！所以我们只需要指定一个基础三角形，这个指定的三角形在你设计的可行走范围内随便选一个即可，然后计算三角形重合时候会不断的铺开。生成的就是可行走区域。如下图
image.png
我指定的是红线黄线包围的三角形。
2-6计算寻路代价
这里其实只需要计算相邻三角形的中心距离即可。距离即为代价（除非你有分什么沙漠地形、泥巴地形之类的行走速度会受影响，需要重新定制）。
2-7寻路算法
1首先判断角色属于某个三角形
2判断目标属于某个三角形
3根据A*计算寻路算法生成三角形上的行走路径
4优化行走路径
A算法计算路径就不再多说了，网上有很多讲解的。这里主要讲解A算法计算寻路后，路径只是一排三角形中点的行进路线，那么如何找出最优路线呢？？？
image.png
首先我们想象人眼睛只要能目测到的地方（没有被墙体阻挡视线）即可直线直接到达）。
那么假设人眼能发射探照灯。第一次探照的结果如下图：
image.png
黄色地方全都可以通过
再次探照如下图
image.png
最后一次探照如下图：
image.png
发现敌军就在视野范围内！！！在视野范围内说明啥？？请往上翻，看到的第一个黑加粗字体。。。就是可直线直接到达的啊！！！于是！！我们直接过去！！砍他！！刀他！！！一到999！！！极品屠龙，绿毒屠龙！紫毒屠龙！！哇！！！吴孟达来收装备啦！！！就这样。。。
那么我们一眼看不到呢？？？
image.png
很常见思路。。哪里挡住你视线了，走过去！！再看！！不就完了？？？如下图。。。这个就是多边形寻路。
（首先我们要明确再优化路径之前我们已经找到大致的路线了如上图黄点）
image.png
移动到遮挡部分，重新进行观测即可。
所以具体思路：
- 从起点进行观测，每次根据A*的路径移动一次，每次根据路径取出“视野最小的”观测范围（如上图第二次观测）
- 如果观测遇到障碍物彻底阻挡了视线，则阻挡的位置即为第一个目标目的地，我们先走过去，然后重新进行上一步的操作，不断进行观测，知道发现敌人。
其他注意点：
可能遇到如下路径
image.png
当刚好之后某些路径计算的时候，遇到拐点，并且拐点在下一个路径的一条边上。因为我们视线观测判断阻挡，从眼睛射出的射线是要分左右的，但是此时你站在拐点处，是无法区分左右的（因为和一个点重合了，此时判断射线左右需要首先找到当前你所属的三角形，通过三角形的中点计算左右。
代码：
代码我混合导出地形和寻路计算到了一起，寻路等是为了先在前端演示一下效果，然后再移动到服务器的。
懒得理解了可以直接复制
但是服务器寻路还是要参照下的。
（我的是linuxC++，因为没有界面不直观，所以先在前端写了一下大致算法，就是下面的，然后再到服务器写）
using UnityEditor;
using System.IO;
using UnityEngine;
using System.Text;
using UnityEngine.AI;
using System.Collections.Generic;
using ServerTools;
public class ExportNavMeshPathGround
{
private static string outFilePath = "path_ground.dat";
private static List<Triangle> listTriangle = new List<Triangle>();
private static int baseTag = 0;
private static float dis = 0.05f;
private static int startI = 0;
private static int endI = 113;
[MenuItem("Zhbd_Tools/Export_NavMeshData_Path_Ground")]
static void Export_NavMeshData_Path_Ground()
{
StringBuilder str = new StringBuilder();
FileStream outFile = new FileStream(Application.dataPath + "/" + outFilePath, FileMode.Create, FileAccess.ReadWrite);
listTriangle.Clear();
ServerPath.getInstance().listDraw.Clear();
NavMeshTriangulation nmt = UnityEngine.AI.NavMesh.CalculateTriangulation();
for (int i = 0; i < nmt.vertices.Length; ++i)
{
str.Append("x: " + nmt.vertices[i].x + ",y: " + nmt.vertices[i].y + ",z: " + nmt.vertices[i].z + "\n");
}
str.Append("\nindices:");
for (int i = 0; i < nmt.indices.Length; ++i)
{
str.Append(nmt.indices[i] + ",");
}
str.Append("\nareas:");
for (int i = 0; i < nmt.areas.Length; ++i)
{
str.Append(nmt.areas[i] + ",");
}
Debug.Log(str.ToString());
byte[] bytes = Encoding.UTF8.GetBytes(str.ToString());
outFile.Write(bytes, 0, bytes.Length);
outFile.Close();
for (int i = 0; i < nmt.indices.Length; i += 3)
{
Triangle t = new Triangle();
t.A = nmt.vertices[nmt.indices[i]];
t.B = nmt.vertices[nmt.indices[i + 1]];
t.C = nmt.vertices[nmt.indices[i + 2]];
listTriangle.Add(t);
}
ServerPath.getInstance().listDraw.Add(listTriangle[baseTag]);
listTriangle.RemoveAt(baseTag);
for (int i = 0; i < ServerPath.getInstance().listDraw.Count; ++i)
{
for (int j = 0; j < listTriangle.Count; ++j)
{
if ((ServerPath.getInstance().listDraw[i].A - listTriangle[j].A).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].A - listTriangle[j].B).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].A - listTriangle[j].C).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].B - listTriangle[j].A).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].B - listTriangle[j].B).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].B - listTriangle[j].C).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].C - listTriangle[j].A).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].C - listTriangle[j].B).magnitude < dis ||
(ServerPath.getInstance().listDraw[i].C - listTriangle[j].C).magnitude < dis)
{
ServerPath.getInstance().listDraw.Add(listTriangle[j]);
listTriangle.RemoveAt(j);
--j;
}
}
}
for (int i = 0; i < ServerPath.getInstance().listDraw.Count; ++i)
{
Debug.DrawLine(ServerPath.getInstance().listDraw[i].A, ServerPath.getInstance().listDraw[i].B, Color.green, 5);
Debug.DrawLine(ServerPath.getInstance().listDraw[i].A, ServerPath.getInstance().listDraw[i].C, Color.green, 5);
Debug.DrawLine(ServerPath.getInstance().listDraw[i].C, ServerPath.getInstance().listDraw[i].B, Color.green, 5);
}
Debug.DrawLine(ServerPath.getInstance().listDraw[0].A, ServerPath.getInstance().listDraw[0].B, Color.red, 5);
Debug.DrawLine(ServerPath.getInstance().listDraw[0].A, ServerPath.getInstance().listDraw[0].C, Color.red, 5);
Debug.DrawLine(ServerPath.getInstance().listDraw[0].C, ServerPath.getInstance().listDraw[0].B, Color.yellow, 5);
Debug.Log("AB和AC的夹角: " + Vector3.Angle((ServerPath.getInstance().listDraw[0].B - ServerPath.getInstance().listDraw[0].A),
(ServerPath.getInstance().listDraw[0].C - ServerPath.getInstance().listDraw[0].A)));
Debug.Log("AC和AB的夹角: " + Vector3.Angle((ServerPath.getInstance().listDraw[0].C - ServerPath.getInstance().listDraw[0].A),
(ServerPath.getInstance().listDraw[0].B - ServerPath.getInstance().listDraw[0].A)));
Debug.Log("AB和CA的夹角: " + Vector3.Angle((ServerPath.getInstance().listDraw[0].B - ServerPath.getInstance().listDraw[0].A),
(ServerPath.getInstance().listDraw[0].A - ServerPath.getInstance().listDraw[0].C)));
countG(ServerPath.getInstance().listDraw[startI]);
countG(ServerPath.getInstance().listDraw[endI]);
Debug.Log("listDraw.Count: " + ServerPath.getInstance().listDraw.Count);
ServerPath.getInstance().initNeighbour();
ServerPath.getInstance().countPath(0, endI);
}
public static void countG(Triangle t)
{
float my_a = (t.B - t.C).magnitude;
float my_b = (t.B - t.C).magnitude;
float my_c = (t.B - t.C).magnitude;
Vector3 myCenter = new Vector3((my_a * t.A.x + my_b * t.B.x + my_c * t.C.x) / (my_a + my_b + my_c),
(my_a * t.A.y + my_b * t.B.y + my_c * t.C.y) / (my_a + my_b + my_c),
(my_a * t.A.z + my_b * t.B.z + my_c * t.C.z) / (my_a + my_b + my_c));
Debug.DrawRay(myCenter, Vector3.up * 5, Color.red, 5);
}
}
using System.Collections.Generic;
using UnityEngine;
namespace ServerTools
{
public class Triangle
{
public Vector3 A;
public Vector3 B;
public Vector3 C;
public Triangle neighborA = null;
public Triangle neighborB = null;
public Triangle neighborC = null;
public int id;
public Triangle father = null;
public Triangle next = null;
public float F = 0f;
public float H = 0f;
public float G = 0f;
public bool finished = false;
public void reset()
{
F = 0f;
H = 0f;
G = 0f;
neighborA = null;
neighborB = null;
neighborC = null;
father = null;
next = null;
finished = false;
}
public Vector3 getCenterPosition()
{
float a = (B - C).magnitude;
float b = (B - C).magnitude;
float c = (B - C).magnitude;
Vector3 Center = new Vector3((a * A.x + b * B.x + c * C.x) / (a + b + c),
(a * A.y + b * B.y + c * C.y) / (a + b + c),
(a * A.z + b * B.z + c * C.z) / (a + b + c));
return Center;
}
}
public class ServerPath
{
private float countDis(Triangle TA, Triangle TB)
{
Vector3 ACenter = TA.getCenterPosition();
Vector3 BCenter = TB.getCenterPosition();
return (ACenter - BCenter).magnitude;
}
private ServerPath()
{
}
private static ServerPath instance = null;
public static ServerPath getInstance()
{
if(instance == null)
{
instance = new ServerPath();
}
return instance;
}
public List<Triangle> listDraw = new List<Triangle>();
private List<Triangle> listcheck = new List<Triangle>();
private List<Triangle> listfinish = new List<Triangle>();
public void initNeighbour()
{
for (int i = 0; i < listDraw.Count; ++i)
{
listDraw[i].reset();
}
for (int i = 0; i < listDraw.Count; ++i)
{
for (int j = 0; j < listDraw.Count; ++j)
{
if(i == j)
{
continue;
}
int bingleCount = 0;
bool hitA = false;
bool hitB = false;
bool hitC = false;
if ((listDraw[i].A - listDraw[j].A).magnitude < 0.05 ||
(listDraw[i].A - listDraw[j].B).magnitude < 0.05 ||
(listDraw[i].A - listDraw[j].C).magnitude < 0.05)
{
++bingleCount;
hitA = true;
}
if ((listDraw[i].B - listDraw[j].A).magnitude < 0.05 ||
(listDraw[i].B - listDraw[j].B).magnitude < 0.05 ||
(listDraw[i].B - listDraw[j].C).magnitude < 0.05)
{
++bingleCount;
hitB = true;
}
if ((listDraw[i].C - listDraw[j].A).magnitude < 0.05 ||
(listDraw[i].C - listDraw[j].B).magnitude < 0.05 ||
(listDraw[i].C - listDraw[j].C).magnitude < 0.05)
{
++bingleCount;
hitC = true;
}
if(bingleCount > 1)
{
tryToAddNeighbour(listDraw[i], listDraw[j], hitA, hitB, hitC);
}
}
}
}
public void countPath(int start, int end)
{
if(start >= listDraw.Count || end >= listDraw.Count)
{
return;
}
listcheck.Clear();
listfinish.Clear();
for(int i = 0; i < listDraw.Count; ++i)
{
listDraw[i].id = i;
}
Triangle nowTriangle;
tryToAddToListcheck(listDraw[start]);
int ci = 0;
while((nowTriangle = getPbByMinF()) != null)
{
++ci;
//Debug.Log(ci);
if(nowTriangle.neighborA == listDraw[end] ||
nowTriangle.neighborB == listDraw[end] ||
nowTriangle.neighborC == listDraw[end])
{
Triangle pbend = listDraw[end];
listfinish.Add(pbend);
pbend.father = nowTriangle;
while(pbend.father != null)
{
Debug.DrawLine(pbend.getCenterPosition(), pbend.father.getCenterPosition());
pbend.father.next = pbend;
pbend = pbend.father;
}
optimizationPath(pbend);
break;
}
if(countNeighbourF(nowTriangle, nowTriangle.neighborA))
{
nowTriangle.neighborA.H = (nowTriangle.neighborA.getCenterPosition() - listDraw[end].getCenterPosition()).magnitude;
nowTriangle.neighborA.F = nowTriangle.neighborA.H + nowTriangle.neighborA.G;
}
if(countNeighbourF(nowTriangle, nowTriangle.neighborB))
{
nowTriangle.neighborB.H = (nowTriangle.neighborB.getCenterPosition() - listDraw[end].getCenterPosition()).magnitude;
nowTriangle.neighborB.F = nowTriangle.neighborB.H + nowTriangle.neighborB.G;
}
if(countNeighbourF(nowTriangle, nowTriangle.neighborC))
{
nowTriangle.neighborC.H = (nowTriangle.neighborC.getCenterPosition() - listDraw[end].getCenterPosition()).magnitude;
nowTriangle.neighborC.F = nowTriangle.neighborC.H + nowTriangle.neighborC.G;
}
addToFinish(nowTriangle);
}
}
private Triangle getPbByMinF()
{
Triangle pb = null;
for (int i = 0; i < listcheck.Count; ++i)
{
if(pb == null || pb.F > listcheck[i].F)
{
pb = listcheck[i];
}
}
return pb;
}
private void tryToAddToListcheck(Triangle t)
{
for (int i = 0; i < listfinish.Count; ++i)
{
if (t.id == listfinish[i].id)
{
return;
}
}
for (int i = 0; i < listcheck.Count; ++i)
{
if(t.id == listcheck[i].id)
{
return;
}
}
listcheck.Add(t);
}
private void addToFinish(Triangle t)
{
t.finished = true;
listfinish.Add(t);
listcheck.Remove(t);
}
private bool countNeighbourF(Triangle A, Triangle Neighbour)
{
if(Neighbour == null || Neighbour.finished)
{
return false;
}
float G = countDis(A, Neighbour);
if (Neighbour.G == 0f || (A.G + G) < Neighbour.G)
{
Neighbour.G = A.G + G;
Neighbour.father = A;
tryToAddToListcheck(Neighbour);
return true;
}
return false;
}
private void tryToAddNeighbour(Triangle baseTriangle, Triangle neighbour, bool hitA, bool hitB, bool hitC)
{
if(hitA && hitB)
{
baseTriangle.neighborC = neighbour;
}
else if (hitA && hitC)
{
baseTriangle.neighborB = neighbour;
}
else if (hitC && hitB)
{
baseTriangle.neighborA = neighbour;
}
}
private void optimizationPath(Triangle start)
{
Vector3 v1 = new Vector3();
Vector3 v2 = new Vector3();
Vector3 v3 = new Vector3();
Vector3 v4 = new Vector3();
Vector3 p1 = new Vector3();
Vector3 p2 = new Vector3();
Vector3 p3 = new Vector3();
Vector3 p4 = new Vector3();
Triangle g1 = start;
Triangle g2 = start;
List<Vector3> listpath = new List<Vector3>();
Vector3 startPosition = start.getCenterPosition();
listpath.Add(startPosition);
Triangle tCount = start.next;
caculateV(startPosition, start, ref v1, ref v2, ref p1, ref p2);
int testi = 0;
while (tCount != null)
{
++testi;
caculateV(startPosition, tCount, ref v3, ref v4, ref p3, ref p4);
if (testi == 999)
{
Debug.DrawRay(startPosition + Vector3.up * 0.5f, v1, Color.cyan, 5);
Debug.DrawRay(startPosition + Vector3.up * 0.5f, v2, Color.cyan, 5);
Debug.DrawRay(startPosition, v3, Color.black, 5);
Debug.DrawRay(startPosition, v4, Color.black, 5);
tCount = null;
continue;
}
//左手坐标系，所以小于等于
if (Vector3.Cross(new Vector3(v3.x, 0, v3.z), new Vector3(v2.x, 0, v2.z)).y <= 0)
{
Debug.DrawRay(p2, Vector3.up * 10, Color.yellow, 5);
startPosition = p2;
tCount = g2;
g2 = tCount.next;
caculateV(startPosition, tCount, ref v1, ref v2, ref p1, ref p2);
listpath.Add(startPosition);
this.countNext(ref listpath, ref tCount);
continue;
}
//左手坐标系，所以大于等于
if (Vector3.Cross(new Vector3(v4.x, 0, v4.z), new Vector3(v1.x, 0, v1.z)).y >= 0)
{
Debug.DrawRay(p1, Vector3.up * 10, Color.yellow, 5);
startPosition = p1;
tCount = g1;
g1 = tCount.next;
caculateV(startPosition, tCount, ref v1, ref v2, ref p1, ref p2);
listpath.Add(startPosition);
this.countNext(ref listpath, ref tCount);
continue;
}
//左手坐标系，所以小于等于
if (Vector3.Cross(new Vector3(v3.x, 0, v3.z), new Vector3(v1.x, 0, v1.z)).y <= 0)
{
v1 = v3;
p1 = p3;
g1 = tCount.next;
}
//左手坐标系，所以小于等于
if (Vector3.Cross(new Vector3(v4.x, 0, v4.z), new Vector3(v2.x, 0, v2.z)).y >= 0)
{
v2 = v4;
p2 = p4;
g2 = tCount.next;
}
this.countNext(ref listpath, ref tCount);
}
for(int i = 0; i < listpath.Count - 1; ++i)
{
Debug.DrawLine(listpath[i], listpath[i + 1], Color.blue, 5);
}
}
private void countNext(ref List<Vector3> listpath, ref Triangle t)
{
if (t.next == null)
{
listpath.Add(t.getCenterPosition());
}
t = t.next;
}
private void caculateV(Vector3 startPosition, Triangle tCount, ref Vector3 v1, ref Vector3 v2, ref Vector3 p1, ref Vector3 p2)
{
if(tCount == null)
{
return;
}
if(tCount.next != null)
{
if (tCount.next == tCount.neighborA)
{
v1 = tCount.B - startPosition;
v2 = tCount.C - startPosition;
p1 = tCount.B;
p2 = tCount.C;
}
else if (tCount.next == tCount.neighborB)
{
v1 = tCount.A - startPosition;
v2 = tCount.C - startPosition;
p1 = tCount.A;
p2 = tCount.C;
}
else if (tCount.next == tCount.neighborC)
{
v1 = tCount.B - startPosition;
v2 = tCount.A - startPosition;
p1 = tCount.B;
p2 = tCount.A;
}
//start Position和另一个V，在同一个边上则边就确定了，从这个三角形中心找左右
if (Vector3.Cross(new Vector3(v1.x, 0, v1.z), new Vector3(v2.x, 0, v2.z)).y == 0)
{
Vector3 vcp_1 = p1 - tCount.getCenterPosition();
Vector3 vcp_2 = p2 - tCount.getCenterPosition();
if (Vector3.Cross(new Vector3(vcp_1.x, 0, vcp_1.z), new Vector3(vcp_2.x, 0, vcp_2.z)).y < 0)
{
v1 = p2 - startPosition;
v2 = p1 - startPosition;
Vector3 pswitch = p1;
p1 = p2;
p2 = pswitch;
}
else
{
v1 = p1 - startPosition;
v2 = p2 - startPosition;
}
}
//左手坐标系，所以小于等于
else if (Vector3.Cross(new Vector3(v1.x, 0, v1.z), new Vector3(v2.x, 0, v2.z)).y < 0)
{
Vector3 vswitch = v1;
Vector3 pswitch = p1;
v1 = v2;
v2 = vswitch;
p1 = p2;
p2 = pswitch;
}
}
else
{
v1 = v2 = tCount.getCenterPosition() - startPosition;
p1 = p2 = tCount.getCenterPosition();
}
}
}
}
大致的注解（因为自己用，再一个很多代码只是服务器代码的一个预演，凑合写下，所以注释基本没有，有几个变量的设置直接随意的放到里面，下图我大约注解一下。。。
image.png
代码Copy之后，如下图
image.png
