服务端寻路实现总结

作者: zthh | 来源:发表于2019-11-02 16:57 被阅读0次

2018-07-10在博客园写的水文迁移到简书。

整体思路：

通过客户端（Unity）导出地图信息
将地图信息放到服务端解析
服务端通过A*寻路算法计算路径点，然后服务端将这些路径点返回给客户端

说明：

此方案只在场景障碍物都是静态且不考虑高度的条件下有效
如果场景障碍物是动态且需要考虑高度的话，则服务端要非常强大的寻路库实现，这部分可以使用recastnavigation，同时这也是Unity内部源码使用的方案。

操作步骤：

Unity导出地图信息

设置游戏场景里物体障碍物属性为Navigation Static，并按照物体属性设置物体是否可行走（Walkable）和不可行走（Not Walkable），因为不考虑高度，Generate OffMeshLinks可不勾选。
设置Object属性

当设置好所有障碍物信息后，执行地图网络烘焙（Bake）。
a)点击Bake烘焙出地图网络信息

b)烘焙后的网络信息图

如果服务端是通过顶点和索引导入地图信息的，则通过UnityEngine.AI.NavMesh.CalculateTriangulation() 导出顶点和索引信息。
如果服务端是通过二维坐标导入地图信息的，则通过UnityEngine.AI.NavMesh.SamplePosition()逐一顶点采样，如果hit中障碍物，则对应点设为1，否则设为0。
导出顶点和索引代码：

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();
        }
    }
}

导出后的obj图

导出二维坐标的代码：

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();
        }
    }
}

导出的二维数组表

服务端实现：

解决了客户端导出的地图信息后，服务端只需要通过获取客户端发送过来的start_pos和end_pos，并通过这两个点执行寻路逻辑，然后得到一串路径点，然后将这些路径点返回给客户端，客户端通过路径点执行对应人物的方向行走即可。不过要注意的是，这里客户端之所以是通过方向行走而不是直接走到那个路径点是因为我们是忽略了高度的因素）

服务端load地图信息，具体代码见navmesh的load()和load_map_array()
服务端寻路算法实现：
如果是通过顶点索引方案的方式寻路，则记录所有三角形的重心，将重心抽象成地图上的网络点，然后计算寻路时，以这些网络点当成作用对象来进行寻路，具体代码见navmesh的calulate_path()
如果是通过数组的方式，那就更容易了，直接走传统的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):
    '''
    服务端寻路组件
    '''
    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):
        '''
        通过二维数组的地图数据寻路
        @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
        
        # 将点路径转化为线段路径
        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)

路径点返回给客户端

感受与体会：

当三角形非常大的时候，如下图，使用上述代码的calculate_path()方法会导致人物会出现“绕路”的情况，这是因为三角形太大导致重心已失去位置的“代表性”。如果想要使用三角网络寻路的同时并且解决这个问题，建议用recastnavigation库实现，因为这里的核心原理牵涉到很多复杂的图论问题
三角网络很大的情况
使用二维数组方案最高效且简单
当地图比较大时，需要对地图进行分块划分，以节省服务端内存压力，以及省去不必要的寻路计算

服务端寻路实现总结

整体思路：

说明：

操作步骤：

Unity导出地图信息

服务端实现：

感受与体会：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读