2018-07-10在博客園寫的水文遷移到簡書而钞。
整體思路：
- 通過客戶端（Unity）導(dǎo)出地圖信息
- 將地圖信息放到服務(wù)端解析
- 服務(wù)端通過A*尋路算法計算路徑點栽渴，然后服務(wù)端將這些路徑點返回給客戶端
說明：
- 此方案只在場景障礙物都是靜態(tài)且不考慮高度的條件下有效
- 如果場景障礙物是動態(tài)且需要考慮高度的話，則服務(wù)端要非常強大的尋路庫實現(xiàn)坯临，這部分可以使用recastnavigation霍殴，同時這也是Unity內(nèi)部源碼使用的方案涮帘。
操作步驟：
Unity導(dǎo)出地圖信息
-
設(shè)置游戲場景里物體障礙物屬性為Navigation Static单寂，并按照物體屬性設(shè)置物體是否可行走（Walkable）和不可行走（Not Walkable）啄刹，因為不考慮高度，Generate OffMeshLinks可不勾選凄贩。
設(shè)置Object屬性
-
當(dāng)設(shè)置好所有障礙物信息后，執(zhí)行地圖網(wǎng)絡(luò)烘焙（Bake）袱讹。
a)點擊Bake烘焙出地圖網(wǎng)絡(luò)信息
b)烘焙后的網(wǎng)絡(luò)信息圖
- 如果服務(wù)端是通過頂點和索引導(dǎo)入地圖信息的疲扎，則通過UnityEngine.AI.NavMesh.CalculateTriangulation() 導(dǎo)出頂點和索引信息。
如果服務(wù)端是通過二維坐標(biāo)導(dǎo)入地圖信息的捷雕，則通過UnityEngine.AI.NavMesh.SamplePosition()逐一頂點采樣椒丧，如果hit中障礙物，則對應(yīng)點設(shè)為1救巷，否則設(shè)為0壶熏。
導(dǎo)出頂點和索引代碼：
using UnityEngine;
using System.Collections;
using System.IO;
using System.Text;
using UnityEditor;
using UnityEngine.SceneManagement;
using UnityEngine;
public class NavArrayExport: MonoBehaviour
{
#region Public Attributes
public Vector3 leftUpStart = Vector3.zero;
public float accuracy = 1;
public int height = 30;
public int wide = 30;
public float maxdistance = 0.2f;
public float kmin = -10;
public float kmax = 20;
#endregion
#region Public Methods
public void Exp()
{
exportPoint(leftUpStart, wide, height, accuracy);
}
public float ConvertToNearestHalfNum(float num)
{
float numFloor = Mathf.Floor(num);
float half = 0.5f;
float d1 = num - numFloor;
float d2 = Mathf.Abs(num - (numFloor + half));
float d3 = numFloor + 1 - num;
float d = Mathf.Min(d1, d2, d3);
if(d == d1)
{
return numFloor;
}
else if(d == d2)
{
return numFloor + 0.5f;
}
else
{
return numFloor + 1f;
}
}
public void exportPoint(Vector3 startPos, int x, int y, float accuracy)
{
StringBuilder str = new StringBuilder();
int[,] list = new int[x, y];
str.Append("[MAP_DESC]\r\n");
str.Append("startpos=").Append(startPos).Append("\r\n");
str.Append("height=").Append(y).Append("\r\nwide=").Append(x).Append("\r\naccuracy=").Append(accuracy).Append("\r\n");
for (int j = 0; j < y; ++j)
{
for (int i = 0; i < x; ++i)
{
UnityEngine.AI.NavMeshHit hit;
for (float k = kmin; k < kmax; k+=0.5f)
{
Vector3 p = startPos + new Vector3(i * accuracy, k, -j * accuracy);
if (UnityEngine.AI.NavMesh.SamplePosition(p, out hit, maxdistance, UnityEngine.AI.NavMesh.AllAreas))
{
//Debug.DrawRay(new Vector3(ConvertToNearestHalfNum(hit.position.x), hit.position.y, ConvertToNearestHalfNum(hit.position.z)), Vector3.up, Color.green);
list[(int)(ConvertToNearestHalfNum(hit.position.x) * 2), (int)(ConvertToNearestHalfNum(hit.position.z) * 2)] = 1;
break;
}
}
}
}
str.Append("map=");
for (int j = 0; j < y; ++j)
{
str.Append("[");
for (int i = 0; i < x; ++i)
{
str.Append(Mathf.Abs(1 - list[i, j])).Append(",");
}
str.Append("],");
}
//文件路徑
string path = Application.dataPath + SceneManager.GetActiveScene().name + ".ini";
//新建文件
StreamWriter streamWriter = new StreamWriter(path);
streamWriter.Write(str.ToString());
streamWriter.Flush();
streamWriter.Close();
AssetDatabase.Refresh();
}
#endregion
}
[CustomEditor(typeof(NavArrayExport))]
public class NavArrayExportHelper: Editor
{
public override void OnInspectorGUI()
{
base.OnInspectorGUI();
if (GUILayout.Button("Export"))
{
var exp = target as NavExport;
exp.Exp();
}
}
}
導(dǎo)出后的obj圖
導(dǎo)出二維坐標(biāo)的代碼：
using UnityEngine;
using System.Collections;
using System.IO;
using System.Text;
using UnityEditor;
using UnityEngine.SceneManagement;
using UnityEngine;
public class NavArrayExport: MonoBehaviour
{
#region Public Attributes
public Vector3 leftUpStart = Vector3.zero;
public float accuracy = 1;
public int height = 30;
public int wide = 30;
public float maxdistance = 0.2f;
public float kmin = -10;
public float kmax = 20;
#endregion
#region Public Methods
public void Exp()
{
exportPoint(leftUpStart, wide, height, accuracy);
}
public float ConvertToNearestHalfNum(float num)
{
float numFloor = Mathf.Floor(num);
float half = 0.5f;
float d1 = num - numFloor;
float d2 = Mathf.Abs(num - (numFloor + half));
float d3 = numFloor + 1 - num;
float d = Mathf.Min(d1, d2, d3);
if(d == d1)
{
return numFloor;
}
else if(d == d2)
{
return numFloor + 0.5f;
}
else
{
return numFloor + 1f;
}
}
public void exportPoint(Vector3 startPos, int x, int y, float accuracy)
{
StringBuilder str = new StringBuilder();
int[,] list = new int[x, y];
str.Append("[MAP_DESC]\r\n");
str.Append("startpos=").Append(startPos).Append("\r\n");
str.Append("height=").Append(y).Append("\r\nwide=").Append(x).Append("\r\naccuracy=").Append(accuracy).Append("\r\n");
for (int j = 0; j < y; ++j)
{
for (int i = 0; i < x; ++i)
{
UnityEngine.AI.NavMeshHit hit;
for (float k = kmin; k < kmax; k+=0.5f)
{
Vector3 p = startPos + new Vector3(i * accuracy, k, -j * accuracy);
if (UnityEngine.AI.NavMesh.SamplePosition(p, out hit, maxdistance, UnityEngine.AI.NavMesh.AllAreas))
{
//Debug.DrawRay(new Vector3(ConvertToNearestHalfNum(hit.position.x), hit.position.y, ConvertToNearestHalfNum(hit.position.z)), Vector3.up, Color.green);
list[(int)(ConvertToNearestHalfNum(hit.position.x) * 2), (int)(ConvertToNearestHalfNum(hit.position.z) * 2)] = 1;
break;
}
}
}
}
str.Append("map=");
for (int j = 0; j < y; ++j)
{
str.Append("[");
for (int i = 0; i < x; ++i)
{
str.Append(Mathf.Abs(1 - list[i, j])).Append(",");
}
str.Append("],");
}
//文件路徑
string path = Application.dataPath + SceneManager.GetActiveScene().name + ".ini";
//新建文件
StreamWriter streamWriter = new StreamWriter(path);
streamWriter.Write(str.ToString());
streamWriter.Flush();
streamWriter.Close();
AssetDatabase.Refresh();
}
#endregion
}
[CustomEditor(typeof(NavArrayExport))]
public class NavArrayExportHelper: Editor
{
public override void OnInspectorGUI()
{
base.OnInspectorGUI();
if (GUILayout.Button("Export"))
{
var exp = target as NavExport;
exp.Exp();
}
}
}
導(dǎo)出的二維數(shù)組表
服務(wù)端實現(xiàn)：
解決了客戶端導(dǎo)出的地圖信息后，服務(wù)端只需要通過獲取客戶端發(fā)送過來的start_pos和end_pos浦译，并通過這兩個點執(zhí)行尋路邏輯棒假，然后得到一串路徑點，然后將這些路徑點返回給客戶端精盅，客戶端通過路徑點執(zhí)行對應(yīng)人物的方向行走即可帽哑。不過要注意的是，這里客戶端之所以是通過方向行走而不是直接走到那個路徑點是因為我們是忽略了高度的因素）
- 服務(wù)端load地圖信息叹俏，具體代碼見navmesh的load()和load_map_array()
- 服務(wù)端尋路算法實現(xiàn)：
如果是通過頂點索引方案的方式尋路妻枕，則記錄所有三角形的重心，將重心抽象成地圖上的網(wǎng)絡(luò)點，然后計算尋路時屡谐，以這些網(wǎng)絡(luò)點當(dāng)成作用對象來進(jìn)行尋路述么，具體代碼見navmesh的calulate_path()
如果是通過數(shù)組的方式，那就更容易了愕掏，直接走傳統(tǒng)的A即可度秘，具體代碼見navmesh的calulate_path_array()*
navmesh代碼如下：
#!/bin/env python
# -*- coding:utf8 -*-
import os
import ConfigParser
import numpy
from heapq import *
from vector3 import Vector3
from triangle import Triangle
from math_tools import MathTools
from common.singleton import Singleton
from common.logger import Logger
class Navmesh(Singleton):
'''
服務(wù)端尋路組件
'''
def __init__(self):
self.vertices = []
self.indices = []
self.all_triangles = [] # 所有三角形
self.all_center_o = [] # 所有三角形的重心
self.point_2_triangles = {} # 點包含的三角形列表集合
# obj_file
dir = os.path.dirname(os.path.realpath(__file__))
#self.map_obj_file_name = '{}/{}'.format(dir,'test.obj')
self.map_obj_file_name = '{}/{}'.format(dir,'AssetsDeserScene.obj')
def load(self):
with open(self.map_obj_file_name, 'r+') as f:
Logger().I('loading map data({})...'.format(self.map_obj_file_name))
lines = f.readlines()
for line in lines:
for kv in [line.strip().split(' ')]:
if kv[0] == 'v':
self.vertices.append(Vector3(float(kv[1]),float(kv[2]),float(kv[3])))
elif kv[0] == 'f':
a = int(kv[1])-1
b = int(kv[2])-1
c = int(kv[3])-1
t = Triangle(self.vertices[a], self.vertices[b], self.vertices[c])
self.indices.append(Vector3(a,b,c))
self.all_triangles.append(t)
self.all_center_o.append(t.o)
if t.a not in self.point_2_triangles:
self.point_2_triangles[t.a] = [t]
elif t not in self.point_2_triangles[t.a]:
self.point_2_triangles[t.a].append(t)
if t.b not in self.point_2_triangles:
self.point_2_triangles[t.b] = [t]
elif t not in self.point_2_triangles[t.b]:
self.point_2_triangles[t.b].append(t)
if t.c not in self.point_2_triangles:
self.point_2_triangles[t.c] = [t]
elif t not in self.point_2_triangles[t.c]:
self.point_2_triangles[t.c].append(t)
return True
def load_map_array(self):
conf = ConfigParser.ConfigParser()
conf.read('map/AssetsDeserScene.ini')
map_data = conf.get('MAP_DESC','map')
self.h = conf.getint('MAP_DESC','height')
self.w = conf.getint('MAP_DESC','wide')
self.accuracy = conf.getfloat('MAP_DESC','accuracy')
self.nmap = numpy.array(eval(map_data))
def convert_pos_to_arr_idx(self, v_pos):
#(0,0,700)->(0,0)
#(100,0,700)->(0,199)
#(100,0,600)->(199,199)
x = (self.h - MathTools.convert_to_half_num(v_pos.z)) * self.accuracy - 1
z = MathTools.convert_to_half_num(v_pos.x) * self.accuracy - 1
return (int(x), int(z))
def convert_arr_idx_to_pos(self, idx):
return Vector3((idx[1] + 1) / self.accuracy, 0, self.h - (idx[0] + 1)/self.accuracy)
def calulate_path_array(self, start_pos, end_pos):
'''
通過二維數(shù)組的地圖數(shù)據(jù)尋路
@paramIn: [Vector3] start_pos
@paramIn: [Vector3] end_pos
'''
start = self.convert_pos_to_arr_idx(start_pos)
end = self.convert_pos_to_arr_idx(end_pos)
res = MathTools.astar(self.nmap, start, end)
paths = []
if res is False or len(res) == 0:
# 找不到就直接走向end
paths.append(end_pos)
return paths
# 將點路徑轉(zhuǎn)化為線段路徑
res.reverse()
paths.append(self.convert_arr_idx_to_pos(res[0]))
if len(res) > 1:
for i in xrange(1,len(res)):
if MathTools.check_points_in_line(start,res[i-1],res[i]):
paths[-1] = self.convert_arr_idx_to_pos(res[i])
else:
# 斜率開始不一樣，則添加最新的點
paths.append(self.convert_arr_idx_to_pos(res[i]))
start = res[i-1]
return paths
def calulate_path(self, start_pos, end_pos):
open_list = []
close_list = []
start_pos_triangle = Triangle(start_pos, start_pos, start_pos)
end_pos_triangle = Triangle(end_pos, end_pos, end_pos)
start_triangle, start_pos = MathTools.fix_border_point_if_needed(start_pos, self.all_triangles)
end_triangle, start_pos = MathTools.fix_border_point_if_needed(end_pos, self.all_triangles)
rv_path = {}
if start_triangle is None:
#Logger().W('start_pos is not in the navmesh')
return None
if end_triangle is None:
#Logger().W('end_pos is not in the navmesh')
return None
f = {}
g = {}
h = {}
open_list.append(start_pos_triangle)
while end_pos_triangle not in open_list and len(open_list) != 0:
# step 1. get the min triangle in open_list
t = open_list[0]
for i in xrange(0, len(open_list)):
if open_list[i] not in f:
f[open_list[i]] = 0
if f[t] > f[open_list[i]]:
t = open_list[i]
# step 2. remove the triangle from the open_list
open_list.remove(t)
# step 3. append the triangle to the close_list
close_list.append(t)
# step 4. explore
# step 4.1. get round triangles
current = t
if current == start_pos_triangle:
current = start_triangle
round_triangles = []
if current.a in self.point_2_triangles:
round_triangles = round_triangles + self.point_2_triangles[current.a]
if current.b in self.point_2_triangles:
round_triangles = round_triangles + self.point_2_triangles[current.b]
if current.c in self.point_2_triangles:
round_triangles = round_triangles + self.point_2_triangles[current.c]
# remove dulplicate triangles
round_triangles = sorted(set(round_triangles),key=round_triangles.index)
if end_triangle in round_triangles:
round_triangles.append(end_pos_triangle)
# step 4.2
for i in xrange(0, len(round_triangles)):
round_triangle = round_triangles[i]
if round_triangle is t:
continue
if round_triangle in close_list:
continue
if round_triangle not in open_list:
rv_path[round_triangle] = t
if t not in g:
g[t] = 0
g[round_triangle] = g[t] + MathTools.distance(t.o,round_triangle.o)
h[round_triangle] = MathTools.distance(round_triangle.o, end_pos)
open_list.append(round_triangle)
else:
if round_triangle not in g:
g[round_triangle] = 0
if round_triangle not in h:
h[round_triangle] = 0
G = g[round_triangle]
H = h[round_triangle]
F = g[round_triangle] + MathTools.distance(round_triangle.o, t.o) + MathTools.distance(round_triangle.o, end_pos)
if G + H > F:
rv_path[round_triangle] = t
g[round_triangle] = g[t] + MathTools.distance(t.o,round_triangle.o)
h[round_triangle] = MathTools.distance(round_triangle.o, end_pos)
open_list.remove(round_triangle)
path_list = []
t = end_pos_triangle
while t in rv_path and rv_path[t] is not None:
path_list.append(t.o)
t = rv_path[t]
path_list.reverse()
return path_list
# start_pos =Vector3(315.976135254,11.0661716461,360.217041016)
# end_pos = Vector3(315.970001221,11.86622715,350.790008545)
# nav = Navmesh()
# nav.load_map_array()
# print nav.calulate_path_array(start_pos,end_pos)
# start_pos = Vector3(-2.3, 0.3, -2.8)
# end_pos = Vector3(3.2, 0.0, -2.8)
# print nav.calulate_path(start_pos, end_pos)
# (-0.3, 0.1, -3.9)
# (1.7, 0.1, -4.2)
# (3.2, 0.1, -2.8)
- 路徑點返回給客戶端
感受與體會：
- 當(dāng)三角形非常大的時候亭珍，如下圖敷钾，使用上述代碼的calculate_path()方法會導(dǎo)致人物會出現(xiàn)“繞路”的情況，這是因為三角形太大導(dǎo)致重心已失去位置的“代表性”肄梨。如果想要使用三角網(wǎng)絡(luò)尋路的同時并且解決這個問題阻荒，建議用recastnavigation庫實現(xiàn)，因為這里的核心原理牽涉到很多復(fù)雜的圖論問題
三角網(wǎng)絡(luò)很大的情況 - 使用二維數(shù)組方案最高效且簡單
- 當(dāng)?shù)貓D比較大時众羡，需要對地圖進(jìn)行分塊劃分侨赡，以節(jié)省服務(wù)端內(nèi)存壓力，以及省去不必要的尋路計算
