精华内容
下载资源
问答
  • 谷歌的开源导航网格寻路算法源码,用于游戏寻路非常合适。
  • 基于ghostcat工具类的AStar算法改编而成,非6方向的网格寻路也可以使用; 专用于六边形/六方向寻路,使用时请注意不要与原本的4/8方向方法混淆; 地图为二维数组,示例为生成的地图为左右交错、简单直观的展示了基本...
  • 主要为大家详细介绍了Unity3D实现NavMesh导航网格寻路,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • recast navmesh导航网格算法源码分析 Author: 林绍川 本文为了方便,引用了一些网上的相关图片 图片出处:https://www.pianshen.com/article/3931589891/特此致谢 1 加载.obj文件 InputGeom::load--->...

    recast navigation navmesh导航网格算法源码分析

    Author:  林绍川

    本文为了方便,引用了一些网上的相关图片

    图片出处:Recast源码解析(二):NavMesh导航网格生成原理(上) - 程序员大本营 特此致谢

    1 加载.obj文件

    InputGeom::load--->InputGeom::loadMesh负责加载所有三角形

    取obj文件中顶点数据,和顶点索引数据

    1.1 obj的格式:

    v  6.5 0.07999992 20.5

    ...(每行以v开头,连着三个浮点数,为一个顶点坐标)

    f 1 2 3

    ...(每行以f开头,连着三个整数,为顶点索引)

    1.2 三角形空间分割

    rcCreateChunkyTriMesh,这个函数为之后建立高度场时,能快速索引出对应的三角形

    按如下步骤:

    1 此函数会为加载的三角形计算aabb盒(其实是xz坐标的包围矩形)

    2 以aabb哪个轴长(x轴方向长),就按哪个轴进行排序,然按三角形数量1分为2

    3 如此循环,直到划分的节点里三角形个数小于某个阀值(256)

    2 建立高度场

    结束加载obj,就要开始建立高度场

    1 Recast navmesh是将场景中的三角形光栅光,形成高度场体素,

    2 然后根据高度场计算layer,还生成导航多边形数据

    为何不直接利用obj中的三角形数据,原因可能如下:

    1 obj中的三角形数据可能细节更多,而导航寻路可以适当简化多边形细节,提高效率

    2 寻路有对象宽度限制,体素化利于处理

    3 obj中没有包含layer信息,需要处理

    layer是recast navmesh里的一个概念,是导入obj里,一些独立,不连通的区域,或者不同的层,彼此之间寻路上不能互通,

    或者通过port互通

    此处以 Sample_TempObstacles::handleBuild为例,说明这一过程

    这个sample支持动态创建障碍物,具体的处理方向如下步骤:

    1 将高度场数据划分成tile,

    2 障碍物改变与其相交的高度场体素,将处于障碍物(包围盒/或者圆柱体)中的体素标记为不可走

    3 然后将受影响的tile重新计算,局部重新生成导航多边形数据

    2.1 rasterizeTileLayers光栅化tile内三角形

    光栅化场景中的三角形,即用一个正方形单元(xz平面),对场景中三角形数据进行采样高度数据,此处借用网上的一个图,形象表示如下:

    图1

    对图中的每个小方格,以下会以span这一称呼来代替,

    一个span是xz大小固定的单元格,在y方向不固定

    (根据光栅光时,截取到的多边形高范围,记录ymax ymin)

    2.2 划分tile

    Sample_TempObstacles为了动态重新开销减少,需要划分tile,

    即将整个场景算出一个aabb,在xz平面上按固定大小分tile

    每个tile内包含一个span体素数组

    即tile是一个块, span则是一个最小的体素点,

    二维的span组成一个tile

    二维的tile组成一个场景

    2.3 rasterizeTileLayers的参数 rcConfig

    这个参数部分重要成员变量含义:

    cs:

    体素化的单位xz的量化(每个span在xz平面的长宽,为一个正方向)

    ch:

     y方向的量化单位

    walkableSlopeAngle:

    可攀爬的角度(0-90度),用来判断一个span是否可以行走(太斜了,就不能行走)

    walkableHeight:

    寻路单位的高度,高度不够,不能走, 例如:一个身高两米的人,不能通过只有1米高的门框之类的

    walkableClimb:

    同上,高度差小于此值,认为两个span是可以行走的

    walkableHeight walkableClimb会被ch量化,例如:

    ch=0.5  walkableHeight=2.0  那么 walkableHeight = walkableHeight / ch,

    最终walkableHeight =4;

    walkableRadius:

    可行走的宽度,即一个太窄,狭小的地方认为不能走

    walkableRadius会被cs量化

    例如:

    cs = 0.5  walkableRadius = 2.0

    walkableRadius = walkableRadius / cs 即walkableRadius = 4

    borderSize:

    为每个tile多准备一些span数据,相当于边框,值会设成比walkableRadius大,避免把一些span错误置成不可行走

    2.4 rcGetChunksOverlappingRect

    此函数比较简单,计算当前tile范围,将tile包含的三角形找出来

    2.5 rcMarkWalkableTriangles

    依据walkableSlopeAngle,根据法线,判断哪些三角形不能走

    2.6 rcRasterizeTriangles

    对每个三角形调用rasterizeTri光栅化(或者说体素化),

    形成一个高度场,(x,z)单元格,一个格子对应一个链表,链表里的数据按高度从小到大排列

    2.7 rasterizeTri

    对单个三角形进行光栅化(见图1)

    在xz平面,对三角形进行分割,

    循环调用dividePoly,先平行x轴模向切割, 再平行z轴纵切

    2.7.1 dividePoly

    分割多边形,以沿z轴平行分割为例,有如下 图2 图3两种情况

     图2

     图3

    假设蓝色的那条边是要被分割的线,该函数会计算线段两个端点A,B的z坐标与分割线的z坐标差值

    如果是图2的情况:

    1 如果处理的点是A记入上半个多边形顶点,是B记入下半个

    (根据d[i]的符号判断点是在A位置,还是在B位置)

    2 交点分别计下上下两个多边形顶点

    如果是图3的情况:

    点A记入上半个多边形顶点(或者下半个多边形顶点,根据d[i]的符号)

    代码片段,记算d[i]

    体素化分割截取形象表示如下网图

    三角形被x轴z轴的平行线切割后形成的多边形,取该多边形在y轴的最大值与最小值,生成span,

    即上面所提到的图1,再次贴如下:

    所对应的代码:

    2.7.2 addSpan

    这个函数会做一个处理,所有的span链表都是按高度从低到高排序的, span有多个邻居时,取高度最高的,

    原因如下图:

    2.7.3 最终高度场

    到此,完成了每个tile的高度场建立

    参考网上找到的示意图,高度场形象表示如下:

    每个span xz长度固定, y方向包含一个最大值最小值, 同一个xz坐标会有多个span,

    同一个xz坐标处的所有span形成一个链表,并且按高度排序(从小到大)

    2.7.4  rcFilterLowHangingWalkableObstacles

    根据同一个xz坐标不同span之间,如果它们的距离不walkableClimb,并且下面的span可走,则把上面的span也标记成可走, 即处理台阶楼梯之类的情形

    2.7.5  rcFilterLedgeSpans

    和周围的span比较,"空洞"的高度差是否大于阀值,不大于阀值,说明不够高,

    4个方向都不满足,该span也会被判断定为不能走,

    例如:该span周围被墙包围,

    如图所示的红线部分,rcFilterLedgeSpans这个函数,判断空洞交叠部分(红线长度)是否大开于路单位的高度walkableHeight

    2.7.6  rcFilterWalkableLowHeightSpans

    判断当前格子所形成的空间,是否足够高(>walkableHeight),不够高也判断为不可走

    如下图所示,同一个xz坐标上,一系列的span,它们之间的高度差要足够

    致此,完成了所有span能不能行走的标记

    2.8 rcBuildCompactHeightfield

    与周围的span进行比较,是否高度足够,并且高度差是可以走的,形成连接信息

    即每个span会记录与周围前后左右四个邻是否连通

    如果当前坐标为xz邻居方向dir值

    0:表示x-1的span

    1:表示z+1的span

    2:表示x+1的span

    3:表示z-1的span

    Recast navmesh邻居定义图示如下:

    2.9 rcErodeWalkableArea

    Erode的中文含义为侵蚀,即将障碍物周围可行走区域按radius值适当扩散不可行走区域,目的是寻路目标贴墙走时,留出一定的宽度

    在不可行走的区域周围,标记格子g(格子的邻居存在不可行走区域)

    格子g与障碍的距离dis标记为0(dis默认为0xff)

    继续处理,标记出所有格子与障碍物的距离,根据格子的可连通邻居dis值

    根据dis值与寻路物体宽度值radius比较,小则将该区域也标记成不可行走

    如下图所示,可行走区域要收缩一些,为寻路单位留出walkableRadius

    2.10 rcMarkConvexPolyArea

    这个是动态障碍用的,把一些span标记成不可行走

    函数很简单,不影响对主要代码的理解,不详细说明了

    2.11 rcBuildHeightfieldLayers

    完成了高度场"扁平化",

    每个layer

    rcHeightfieldLayer::area: 保存是否可行走

    rcHeightfieldLayer::heights:高度

    rcHeightfieldLayer::cons:连通性(低4bit)+是否为layer之间的通道(高4bit)

    以下说明该函数的执行过程:

    2.11.1 找出连通区域

    互相连接的span会形成一个区域,形成区域的规则如下图所示: (*每个代表一个span)

    对应的部分代码片段截图

    2.11.2 相邻的连通区域合并成一个区域

    2.11.2.1 根据区域内span的邻居的区域id,为每个区域添加邻居

      部分代码片段如下

    2.11.2.2 同时根据span的链表,可以查当该span同一个xz坐标处的其它layer,记录下

      形象图示如下

    对应的代码片段

    2.11.2.3 把所有互相连接的连通区域的打上同一个layerId, 排除掉自身的"不同层" 邻居的"不同层"

    即:区域之间根据邻接关系互联的时候, 不同的层不能是同一个区域, 邻居的不同层也不能进入同一个区域

    这样处理是为了扁平化高度场,区分出不同的层,

    将3d的场景,转化成不同的层级的2d场

    同时对于不连接的区域, 为了减少区域数量,对于高度差小于阀值的区域之间,也会进入合并处理

    (不理解可以跳过此段代码处理,对整个逻辑理解不影响,是一个优化操作)

    该优化部分代码片段如下:

    2.11.2.4 扁平化的高度场数据保存

    见2.11处

    每个layer保存

    rcHeightfieldLayer::area: 保存是否可行走

    rcHeightfieldLayer::heights:高度

    rcHeightfieldLayer::cons:连通性(低4bit)+是否为layer之间的通道(高4bit)

    3 buildNavMeshTilesAt从压缩的高度场中,重建导航数据

    大致过程如下:

    1 扁平化高度场数据会被压缩,解压高度场数据

    2 重建导航数据是逐个tile进行,

    3  tile先按区域进行边缘检测,得到多边形

    4 将多边形分解成三角形

    5 将三角形进行适当合并(保证合并后的多边形是凸的)

    6 记录tile多边形邻接信息

    7  tile之间检测多边形边交叠情况,记录连接信息

    下面进行详细说明

    3.1 标记动态障碍

    dtMarkCylinderArea

    dtMarkBoxArea

    dtMarkBoxArea

    动态障碍物标记,改变与障碍物相交的area(可以理解为前文提到的span)标记为不可行走
    对代码理解不影响,可以跳过

    3.2 dtBuildTileCacheRegions 再次生成区域数据

    部分逻辑参考 2.11 rcBuildHeightfieldLayers

    1 将已经扁平化的高度场数据重新生成区域,

    2 相信的区域组合成一个区域

    原因:因为动态障碍支持,不能从解压后的数据直接取结果

    canMerge函数比较难以理解,做个简要说明:

    1 oldRegId邻居中有一个regId为newRegId,可以合并

    2  count=0:表时newRegId并不在oldRegId邻居

    3  count>=2:说明oldRegId已与别的区域合并,不能再newRegId合并,否则会导致合并好的区域又分裂了

    4 这样处理,保证合并区域不断变大

    可以自行画三个相邻的区域,按代码来理解canMerge的含义

    因为数据已经扁平化,这里就没有扁平化处理了

    3.3 dtBuildTileCacheContours 轮廓处理

    dtTileCacheContour::verts:记录的轮廓 (即多边形的顶点)

    dtTileCacheContour::reg:区域id

    dtTileCacheContour::area可行走标识

    多边形的点的顺时针记录的

    以下进行详细说明

    3.3.1 walkContour

    遍历tile中所有xz坐标,

    从每个合法的点area(即span)查找边缘

    每个点与周围4个邻点,如果所处的reg不一样,则认为是边界点

    4个邻点标号如下图所示,从3号位开始比对

    #表示其它区域的点 1.2.3.4表示当前要查找的轮廓边缘点, 如果出现x(或z)坐标相同的点,则会把中间的点舍弃

    以上图为例从1点开始

    1.1的三号位,即点1的下方提#所以点1是边缘点

    2. 按代码逻辑,x,z不变,然后顺时针旋转,即dir=0,代码片段如下,可以看出当处理3号位时,只改变dir

     <代码片段1>

    3. 此时判断点1与点2,发现它们是同一个区域的,发现它们是同一区域,此时会把dir逆时针转回去

      即dir=0,同时x,z坐标变成点2,代码片段如下

    4.2的下方是#,说明点2是边缘点,dir这时又顺时针转,即dir=0,同时x,z还是点2的,见<代码片段1>的逻辑

    5.2的左边(dir=0)是不同区域,将z坐标加1(见<代码片段1>),到点3,同时dir=1,

        因为左下角是不同区域点3也算边缘点

    6. 3的上方(dir=1)是同一个区域,把xz坐标切到点4,并逆时针处理dir=0

    7. 4的左边(dir=1)是同不区域,点4是边缘点

    8. 就这样不断地旋,切坐标,把轮廓找出来,当回到点1 时,说明找到了完整的轮廓,判断代码如下

      

    9. 可以看出点是按顺时针存储的

    以下4图片形象说明了这一过程:

    3.3.2 simplifyContour简化轮廓

    将轮廓分段,如果该段内的点偏离段小于阀值,合并这些点

    采用Douglas-Peucker算法

    1 按顺序存储的一系列顶点,将首尾两点(记为V0和Vn)连成线段

    2 计算中间各点与该线段的距离,如果距离小于某个阀值忽略,大于阀值的记录下来,这个点我们记录Vmaxd

    3  Vmaxd与V0 Vn分别组成两条线段 V0-Vmaxd  Vmaxd-Vn,分别对这两条线段重复第2步骤,

    4 得到一系列线段,并且没有中间点与对应线段距离大于阀值,结束处理过程

    形象图示如下: 此图出处 Douglas-Peucker算法 - qingsun_ny - 博客园

    3.3.3  getCornerHeight

    如图所示的蓝点,如果轮廓中有这样的占,要去除,是一种容错机制,

    不好理解可以跳过,不影响后面的代码理解

    3.3.4 工具函数介绍

    distancePtSeg 计算点到线段的距离,根据向量点乘算出垂足坐标,再计算点与垂足的距离即可

    代码片段截取如下:

    3.4 dtBuildTileCachePolyMesh 生成邻接多边形

    navmesh导航算法需要确保多边形是凸的,此函数负责生成凸多边形,并生成邻接信息

    因为高度场已经扁平化,所以这个函数的操作都是在xz平面上行进的

    1 先把之前得到的多边形轮廓(有可能是凹的),分割成三角形

    2 再把三角形组合成多边形(确保是凸的)

    3 处理多边形之间的邻接关系

    以下详细说胆此函数

    3.4.1 triangulate

    将多边形(有可能是凹的)分割成三角形

    diagonal

    bool diagonal(int i, int j, int n, const unsigned char* verts, const unsigned short* indices)

    i和j分别为多边形的顶点(索引),此函数判断顶点i 顶点j的连线能否作为多边形的对角线

    用图表示如下:

    diagonal调用了一些工具函数,以下做一些简要说明

    工具函数 leftOn  left  area2  uleft

    这四个函数大同小异

    利用向量的叉积(即两个向量的夹角sin值),判断两个向量的方向关系

    以leftOn为例向量V1 =b-a  V2=c-a

    V1 V2的叉积:

    =0时 表示夹角为零(用于共线判断)

    >0时 表示V1转到V2是顺时针,如下图:

    <0时 表示V1转到V2是逆时针, 此时V1 V2与上图相反

    leftOn代码片段截取如下:

    返回0:表示 a b c 三点共线

    返回<0 表示 c 在向量ab的左边

    返回>0 表示 c 在向量ab的右边

    用右手,绕序abc,

    大拇指朝上: c在ab右

    大拇指朝下: c在ab左

    工具函数inCone

    此函数利用工具函数leftOn left保证一系列4个点是凸的

    代码片段如下:

    工具函数diagonalie

    此函数排除与多边线相交的对角线,如下图

    工具函数intersect

    此函数判断两个线段是否相交

    bool intersectProp(const unsigned char* a, const unsigned char* b, const unsigned char* c, const unsigned char* d)

    这个函数利用left工具函数判断

    1 点a和点b在线段cd的两边

    2 点c和点d在线段ab的两边

    如果满足1,2这两个条件,则说明线相交

    bool between(const unsigned char* a, const unsigned char* b, const unsigned char* c)

    利用area2判断是否共线,即叉积为0

    在共线的情况下,判断端点是否交叠,交叠才能算相交

    如果下图所示,要排除红蓝这种共线的方式,因为没有交叠

    致此,triangulate函数中找合法对角线相关的函数大部分介绍完毕

    切割三角形

    根据合法的对象线,从多边形中切割出三角形

    每次循环找出符合条件的对角线(程序中是长度最小)

    根据对角线,把对应的顶点分离出去,形成一个三角形, 剩余的点形成新的多边形

    多边形改变了,对受影响的点重新调用diagonal,计算对角线的合法性

    如下图所示,沿着绿色虚线,切出三角形,

    反复循环之后,多边形变成三角形,如下

    致此,完成多边形三角化

    3.4.2 合并三角形为凸多边形

    好像不合并也行,三角形一定是凸的,合并后数据更少,执行效率更优

    getPolyMergeValue

    判断两个多边形是否有共同的边,

    并且保证合并后是凸的,

    返回值是公共边的长度

    利用uleft来判断合并后是否是凸的,公共边的两个端点处都要判断,如下图:

    代码片段如下:

    mergePolys

    合并多点边形,这个函数比较简单,复制数据,保证点的绕序,代码与相应的注释说明如下:

    3.4.3  buildMeshAdjacency

    生成多边形邻接信息

    1 首先将所有的边,按顶点索引为key建立类哈希表

    2 对具有相同顶点的边进行判断,是否为公共边

    3 边连接

    4  port连接

    简单说一下有port连接,其实和普通的边连接是一样的

    如下图,  根据扁平化规则, 黑色线处(水平的黑色和斜的黑色)的span和蓝色线处的span会被划分至不同layer

    可回看addSpan  假设黑色斜的那一部分,在蓝色处形成投影,

    投影边缘的那些点(假设是蓝色面的边线),

    如果蓝色面周围有其它span邻居(假设是图中的红色,并且红色与黑色layer是同一个layer)

    蓝色面的边缘span会变成port,并形成port连接

    即port和 普通边连接可以认为不共存

    部分代码片段如下:

    如果是边连接,存放对应多边形的数组下标

    如果是port,则要额外打个0x8000的标记,存port的方向(0,1,2,3)

    这些数据会dtCreateNavMeshData里做转换

    Port(0,1,2,3,4)会转成 4,2,0,6

    3.4.4 dtNavMesh::addTile

    将数据添加进tile,这一步要处理tile之间的连接

    即不同的tile,要处理连缘处的多边形的连通情况,便于tile之间导航寻路

    如果只是想了解Sample_SoloMesh的业务逻辑,可以跳过本段

    connectIntLinks

    这个函数负责生成tile之内多边形邻居信息生成(主要是相邻多边形的公共边)

    findConnectingPolys

    1 此函数负责查找tile之间的多边形连接情况

    这种情况,记录的不是公共边,而是多边形相互靠近的两条边,它们的交叠部分记录下来

    2 此函数也负责tile之间,不同层之间的连通情况,即因为port产生的连接

      代码片段如下:

    Port可以认为是高一层的layer在低上层的layer上投影的边缘的那些点

    记录相邻边交叠部分的代码

    致此,导航需要多边形邻接信息生成完毕,

    之后就是利用这些信息进行寻路

    4 寻路

    4.1 dtNavMeshQuery::findPath   网格寻路

    此函数没有太多难懂的地方

    按网格邻接查找网格路径,类A*算法,按多边形中心点的距离估算cost

    m_openList:是一个堆(极小堆),每个弹出一个cost最优的节点进行循环迭代

    4.2 dtNavMeshQuery::findStraightPath  寻找拐点

    得到一系列相邻的多边形路径, 如何穿过这些多边形, 需要此函数处理,即需要知道要在哪些地方拐弯

    4.2.1 寻路初始

     如下图所示,

    从红点出发,要走到蓝点

    用红色标出每个多边形的邻接边:

    4.2.2 射线包络

    对第一条邻边,从起始的红点,与邻接边的端点,发出一条射线(图中的紫线)

    对第二条邻边也做同样的两条射线(图中的黄线)

    两条紫射线为一组,两条黄射线为一组,取它们的交集,

    以下图为例,交集显示是两条黄射线包络的那部分,

    如下图,处理到第三条邻边时的最小包络射线

    4.2.3 拐点出现的情况

    对之后的每条邻边重复上面的循环,直到出现没有交集的情况

    检测到拐点(粉红的那个点),

    如下图,此例在红色邻边的两个端点,此时与紫色的包络线已经没有交集了

    4.2.4 寻路结束

    然后以粉色点为新的起点,重复以上过程,就可以找到一条在多边形内部的路径,

    即最终的路径会是从红点走到粉点,再从粉点走到蓝色

    4.2.5 结束语

    致此,完成了导航网格生成与寻路功能说明

    ====================== 分割线 ============================

    4.3 一些工具函数简介

    寻路过程,使用了一些工具函数,以下做一个简要说明

    dtDistancePtPolyEdgesSqr / dtPointInPolygon

    利用射线与多边形的交点是奇偶判断是否在多边形内,

    看代码射线应该是平行x轴往x轴正方向

    代码片段如下:

    dtDistancePtSegSqr2D

    求点到线段的距离平方

    dtTriArea2D

    recast里有很多函数功能相似,此函数参考 leftOn

    利用差乘判断线段与点的位置关系

    getPortalPoints

    获多边形邻边的两个端点(如果是tile间的连接或者port,取出交叠的首尾)

    dtClosestHeightPointTriangle

    利用射线(特殊射线,垂与xz平面的)与三角形的交点计算方法,求出射线与三角形的交点

    三角形(p1 p2 p3)内部的顶点可以看到是

    向量v1 = p3 - p1;

    向量v2 = p2 - p1;

    内部点 px = p1 + u*v1 + v*v2;

    等同于: px = p1*(1-u-v) + p3*u + p2*v;

    另外 px = O + d*t   O:射线起点 d:射线方向 t:射线"长度"

    O + d*t = p1*(1-u-v) + p3*u + p2*v; 这样可以得到一个三元一次方程组 未知数为(t u v)

    根据克莱默法则解这个方组即可t u v   代入px = O + d*t即可得到对应的px坐标

    同时,这个函数dtClosestHeightPointTriangle的射线是特殊的,垂直于xz平面

    展开全文
  • Nav导航网格寻路

    万次阅读 多人点赞 2015-04-02 15:52:13
    在查找NavMesh资料的时候看到这篇blog写的不错,从原理到实现,...NAV导航网格寻路(1)-- 介绍  这篇是翻译的文章,原文 http://www.ai-blog.net/archives/2008_07.html WayPoint寻路 下图是一个典型的路点寻路

        在查找NavMesh资料的时候看到这篇blog写的不错,从原理到实现,很详细。另外也可以参考:基于导航网格的A星寻路,这篇blog的参考文献有详细介绍导航网格。以下内容转自http://blianchen.blog.163.com/ by 竹石

    NAV导航网格寻路(1) -- 介绍

    译自 http://www.ai-blog.net/archives/2008_07.html

    WayPoint寻路

    下图是一个典型的路点寻路


    另一种方法是使用多边形来记录路径信息,它可以提供更多的信息给ai角色使用。下图就是一个navigation mesh。


    以下列出几个WayPoint的不足之处:

    1. 一些复杂的游戏地图需要的WayPoint数量过于庞大
    2. 有时会使角色走“Z”型路径

    如下图A点和B点之间的路径


    NAV寻路如下图


    下图是路点寻路,如黄线,会产生“Z”字形


    下图为文章开始时展示的地图的比较,红线是wayPoint寻路,蓝线是nav。


    3. 不能进行动态修正,如果地图中有动态障碍,处理起来会很困难

        如要实现即时战略游戏中,一辆在路上行走的坦克会挡住你军队的去路,这个移动的坦克就是一个动态障碍。

    4. 不能根据角色的特性(不同宽度、高度等)改变路径

        如一个狭窄的通道,普通的人能够通过,而一辆马车的宽度超过通道宽度,应该不能通过。

    5. 不能保存地形的附加信息,如地表高度、地面特征(水面、沙地等)

        比如一个游戏中的角色在走到沙地上时会降低移动速度,或走在一个斜坡上时人物会发生倾斜等。

    NAV导航网格寻路(2) -- 寻路方法

    nav寻路一般包含两部分,首先是使用工具根据地图信息生成寻路用的nav mesh,接下来就是在游戏中根据生成的nav mesh来自动寻路。

    一般人首先关心的就是寻路方法,所以这里把顺序颠倒下,先说寻路。

    一.  使用A*寻找所经过网格路径

     下图为一个已经生成nav网格的地图,深红色区域为不可行走区域,浅红色区域为可以行走的区域。


    如下图,现在如果要寻找从A点到B点的路径,首先要从所有可行走的网格中找到一条最优的网格路径(图中紫色的网格),然后再根据这些网格生成所需要的路径点。

    计算最优网格路径的方法可以使用流行的A*,也可以使用其它方法。A*算法网上很多就不说了,至于三角网格的A*实现因为涉及网格的数据结构会在系列的最后给出。


    二.  生成路径点

    nav寻路最常用的就是光照射线法了,这个在neoragex2002的blog上有讲,这里就不说了

    另一种方法就是拐角点法,如下图

    下图的5个凸多边形是已经生成的导航网格,多边形外部的区域为不可行走区域,current为起点,goal为终点,从图中就可以看出最短路径为图中红线,蓝色圈出的点为我们需要找出的点。所有多边形顶点均按逆时针方向存储(这些均在生成导航网格时处理,以后会讲到)。


    (1)下图显示出各区域之间的入口,即多边形的临边。由图中可以看出每个临边均为起点穿出该多边形区域的边,故以下称该边为穿出边。


    (2)首先找到起始点所在的多边形和穿出边的两个端点,由起点连接两个端点,形成两个线段lineLeft 和lineRight。如下图。绿色圈表示左点,红色表示右点(左点、右点是根据多边形顶点保存顺序而来)。


    (3)继续找到下一个穿出边的两个端点,判断新的左点是否在lineLeft 和lineRigh之间,如果在,则更新lineLeft为起点到新左点的线段。


    同样处理新穿出边的右点,如下图


    该步最后得到两个新的线段,如下图。


    (4) 继续判断下一个穿出边的两个端点,如下图,新的左点在lineLeft和lineRight的外面,则不更新线段。


    下图说明新的右点在两条直线之间,更新lineRight。


    该步最后得到两个新的线段,如下图。


    (5) 继续循环判断下一个穿出边的两个端点,该穿出边的两个端点在lineRight的右侧,表示lineRight的终点即为路径的一个拐角点


    (6) 循环以上步骤都可以找到从起点到终点的一条完整路径。

    NAV导航网格寻路(3) -- 一些必要的计算几何知识

    在继续下面的nav网格生成算法之前,先介绍一下涉及到的计算几何知识。这里只罗列出结论,要详细了解参考相关书籍。

    • 矢量加减法:
       设二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量加法定义为: P + Q = ( x1 + x2 , y1 + y2 ),同样的,矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P,P - Q = - ( Q - P )。
    • 矢量叉积
      设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。
    • 折线段的拐向判断:
        折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:
        若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
        若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
        若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。
    • 判断两线段是否相交:
        我们分两步确定两条线段是否相交:
        (1)快速排斥试验
          设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交。
        (2)跨立试验
          如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是:( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。

    • 凸多边形
      假设我们在一个多边形上(包括多边形的边界及边界围封的范围)任意取两点并以一条线段连结该两点,如果线段上的每一点均在该多边形上,那么我们便说这个多边形是凸的。
    • 凸包
      给定平面上的一个(有限)点集(即一组点),这个点集的凸包就是包含点集中所有点的最小面积的凸多边形。

    • 点在凸多边形中的判断
      假设多边形是凸的,而且顶点p0,p1,...,pn按顺时针方向排列,则点在多边形任意一边 pi-1, pi 的右面。
    • Voronoi图及对偶图

    • Delaunay三角剖分(Voronoi对偶图)

      在实际中运用的最多的三角剖分是Delaunay三角剖分,它是一种特殊的三角剖分。先从Delaunay边说起:
          【定义】Delaunay边:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。
          【定义】Delaunay三角剖分:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。
      以下是Delaunay剖分所具备的优异特性:
          1.最接近:以最近临的三点形成三角形,且各线段(三角形的边)皆不相交。
          2.唯一性:不论从区域何处开始构建,最终都将得到一致的结果。
          3.最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。
          4.最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。
          5.区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。
          6.具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。
    • 多边形裁剪

      Weiler-Athenton算法

    –主多边形:被裁剪多边形,记为A

    –裁剪多边形:裁剪窗口,记为B

    多边形顶点的排列顺序(使多边形区域位于有向边的左侧 )外环:逆时针 ;内环:顺时针

    主多边形和裁剪多边形把二维平面分成两部分。

    内裁剪:A∩B

    外裁剪:A-B


    裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成,并且在交点处边界发生交替,即由A的边界转至B的边界,或由B的边界转至A的边界。

    如果主多边形与裁剪多边形有交点,则交点成对出现,它们被分为如下两类:

    进点:主多边形边界由此进入裁剪多边形内  如,I1,I3, I5, I7, I9, I11

    出点:主多边形边界由此离开裁剪多边形区域. 如, I0,I2, I4, I6, I8, I10 

    算法步骤

    (1)建立空的裁剪结果多边形的顶点表.

    (2)选取任一没有被跟踪过的交点为始点,将其输出到结果多边形顶点表中.

    (3)如果该交点为进点,跟踪主多边形边边界;否则跟踪裁剪多边形边界.

    (4) 跟踪多边形边界,每遇到多边形顶点,将其输出到结果多边形顶点表中,直至遇到新的交点.

    (5)将该交点输出到结果多边形顶点表中,并通过连接该交点的双向指针改变跟踪方向(如果上一步跟踪的是主多边形边界,现在改为跟踪裁剪多边形边界;如果上一步跟踪裁剪多边形边界,现在改为跟踪主多边形边界).

    (6)重复(4)、(5)直至回到起点

    NAV导航网格寻路(4) -- 生成nav网格


    假设上图是一个游戏地图,红色的区域是不可行走的区域,浅灰色区域是可行走区域,要想在游戏中实现nav寻路,必须将可行走区域转化为nav网格并保存为一种固定形式的数据,如下图浅红色的三角形。


    nav网格必须是凸多边形,这里使用三角型,当然也可以使用4边形。下面介绍一种任意多边形的三角化算法。算法来自论文《平面多边形域的快速约束Delaunay三角化作者:曾薇 孟祥旭 杨承磊 杨义军。详细内容请参考该论文。

    先来看几个定义:

    A. 我们称点 p3 为直线 p1p2 的可见点,其必须满足下面三个条件:

    (1) p3 在边 p1p2 的右侧 (顶点顺序为顺时针);

    (2) p3 与 p1 可见,即 p1p3 不与任何一个约束边相交;

    (3) p3 与 p2 可见

    B. DT点

    在一个约束Delaunay三角形中,其中与一条边相对的顶点称为该边的DT点。

    确定 DT 点的过程如下:

    Step1.  构造 Δp1p2p3 的外接圆 C(p1,p2,p3)及其网格包围盒 B(C(p1,p2,p3))

    Step2. 依次访问网格包围盒内的每个网格单元:

                对未作当前趟数标记的网格单元进行搜索,并将其标记为当前趟数

               若某个网格单元中存在可见点 p, 并且 ∠p1pp2 > ∠p1p3p2,则令 p3=p1,转Step1;否则,转Step3.

    Step3.  若当前网格包围盒内所有网格单元都已被标记为当前趟数,也即C(p1,p2,p3)内无可见点,则 p3 为的 p1p2 的 DT 点

    生成Delaunay三角网格算法如下:

    Step2. 取任意一条外边界边 p1p2 .

    Step3.  计算 DT 点 p3,构成约束 Delaunay 三角形 Δp1p2p3 .

    Step4. 如果新生成的边 p1p3 不是约束边,若已经在堆栈中,则将其从中删除;否则,将其放入堆栈;类似地,可处理 p3p2 .

    Step5. 若堆栈不空,则从中取出一条边,转Step3;否则,算法停止 .

    程序实现该算法(AS3语言)

    1。数据结构

    不难看出,要想实现该算法首先要确定一些基础对象,如点、线、三角型和多边形等对象。(才发现这个blog中竟然没有代码的格式NAV导航网格寻路(4) -- 生成nav网格 - 竹石 - 游戏...

    二维点的定义 public class Vector2f {}  包括矢量加减、叉积等方法。

    线的定义  public class Line2D {} 包括下面方法:

        classifyPoint(point:Vector2f, epsilon:Number = 0.000001):int
                     判断点与直线的关系,假设你站在a点朝向b点, 则输入点与直线的关系分为:Left, Right or Centered on the line
               equals(line:Line2D):Boolean
                     线段是否相等 (忽略方向)
               getDirection():Vector2f
                      直线方向
               intersection(other:Line2D, pIntersectPoint:Vector2f = null):int
                      判断两个直线关系 this line A = x0, y0 and B = x1, y1 other is A = x2, y2 and B = x3, y3
               length():Number
                      直线长度
               signedDistance(point:Vector2f):Number
                      给定点到直线的带符号距离,从a点朝向b点,右向为正,左向为负 

    三角型定义 public class Triangle:

        getSide(sideIndex:int):Line2D
                      取得指定索引的边(从0开始,顺时针)
                getVertex(i:int):Vector2f
                       根据i返回顶点
                isPointIn(testPoint:Vector2f):Boolean
                       测试给定点是否在三角型中
                setVertex(i:int, point:Vector2f):void
                       根据i指定的索引设置三角形的顶点  

    多边形定义  public class Polygon:

         public vertexV : Vector.<Vector2f>   //顶点列表,按顺时针方向排序

         cw():void 
                     将多边形的顶点按逆时针排序
                isCW():Boolean
                     将多边形的顶点按顺时针排序
                isSimplicity():Boolean
                     是否是简单多边形
                rectangle():Rectangle
                      返回矩形包围盒  Polygon 
                union(polygon:Polygon):Vector.<Polygon>
                      合并两个多边形(Weiler-Athenton算法) 

    三角化的完整代码,注释比较全,就不再详细解释了 

    <span style="background-color: rgb(255, 255, 255);">/*
    * @author 白连忱 
    * date Jan 22, 2010
    */
    package org.blch.geom
    {
        import flash.display.Sprite;
        import flash.geom.Rectangle;
        import flash.text.TextField;
        import flash.text.TextFieldAutoSize;
        import flash.text.TextFormat;
        
        /**
         * Delaunay
         * @langversion ActionScript 3.0
         * @playerversion Flash 10.0
         */
        public class Delaunay
        {
            public function Delaunay()
            {
            }
            
            private static const EPSILON:Number = 0.000001;    //精度
            
            private var polygonV:Vector.<Polygon>;        //所有多边形,第0个元素为区域外边界 (输入数据)
            
            private var vertexV:Vector.<Vector2f>;        //所有顶点列表, 前outEdgeVecNmu个为外边界顶点
            private var edgeV:Vector.<Line2D>;            //所有约束边
            
            private var outEdgeVecNmu:int;            //区域外边界顶点数
            
            private  var lineV:Vector.<Line2D>;    //线段堆栈
            
            private var triangleV:Vector.<Triangle>;     //生成的Delaunay三角形
            
            public function createDelaunay(polyV:Vector.<Polygon>):Vector.<Triangle> {
                //Step1.     建立单元大小为 E*E 的均匀网格,并将多边形的顶点和边放入其中.
                //            其中 E=sqrt(w*h/n),w 和 h 分别为多边形域包围盒的宽度、高度,n 为多边形域的顶点数 .
                initData(polyV);
                
                //Step2.    取任意一条外边界边 p1p2 .
                var initEdge:Line2D = getInitOutEdge();
                lineV.push(initEdge);
                
                var edge:Line2D;
                do {
                    //Step3.     计算 DT 点 p3,构成约束 Delaunay 三角形 Δp1p2p3 .
                    edge = lineV.pop();
    //                trace("开始处理edge###########:", edge);
                    var p3:Vector2f = findDT(edge);
                    if (p3 == null) continue;
                    var line13:Line2D = new Line2D(edge.getPointA(), p3);
                    var line32:Line2D = new Line2D(p3, edge.getPointB());
                    
                    //Delaunay三角形放入输出数组
                    var trg:Triangle = new Triangle(edge.getPointA(), edge.getPointB(), p3);
                    
    //                trace("DT 点p3", p3);
    //                trace("Triangle", trg);
                    triangleV.push(trg);
                    
                    //Step4.    如果新生成的边 p1p3 不是约束边,若已经在堆栈中,
                    //            则将其从中删除;否则,将其放入堆栈;类似地,可处理 p3p2 .
                    var index:int;
                    if (indexOfVector(line13, this.edgeV) < 0) {
                        index = indexOfVector(line13, lineV);
                        if (index > -1) {
                            lineV.splice(index, 1);
                        } else {
                            lineV.push(line13);
                        }
                    }
                    if (indexOfVector(line32, this.edgeV) < 0) {
                        index = indexOfVector(line32, lineV);
                        if (index > -1) {
                            lineV.splice(index, 1);
                        } else {
                            lineV.push(line32);
                        }
                    }
                
                //Step5.    若堆栈不空,则从中取出一条边,转Step3;否则,算法停止 .
    //                trace("处理结束edge###########\n");
                } while (lineV.length > 0);
                    
                return triangleV;
            }
            
            /**
             * 初始化数据
             * @param polyV
             */        
            private function initData(polyV:Vector.<Polygon>):void {
                //填充顶点和线列表
                vertexV = new Vector.<Vector2f>();
                edgeV = new Vector.<Line2D>();
                var poly:Polygon;
                for (var i:int=0; i<polyV.length; i++) {
                    poly = polyV[i];
                    putVertex(vertexV, poly.vertexV);
                    putEdge(edgeV, poly.vertexV);
                }
                
                outEdgeVecNmu = polyV[0].vertexNmu;
                
                lineV = new Vector.<Line2D>();
                triangleV = new Vector.<Triangle>();
            }
            
            /**
             * 获取初始外边界
             * @return 
             */        
            private function getInitOutEdge():Line2D {
                var initEdge:Line2D = edgeV[0];
                //检查是否有顶点p在该边上,如果有则换一个外边界
                var loopSign:Boolean;
                var loopIdx:int = 0;
                do {
                    loopSign = false;
                    loopIdx++;
                    for each (var testV:Vector2f in this.vertexV) {
                        if ( testV.equals(initEdge.getPointA()) || testV.equals(initEdge.getPointB()) ) continue;
                        if (initEdge.classifyPoint(testV, EPSILON) == PointClassification.ON_LINE) {
                            loopSign = true;
                            initEdge = edgeV[loopIdx];
                            break;
                        }
                    }
                } while (loopSign && loopIdx<outEdgeVecNmu-1);    //只取外边界
                return initEdge;
            }
            
            /**
             * 将srcV中的点放入dstV
             * @param dstV
             * @param srcV
             */        
            private function putVertex(dstV:Vector.<Vector2f>, srcV:Vector.<Vector2f>):void {
                for each (var item:Vector2f in srcV) {
                    dstV.push(item);
                }
            }
            
            /**
             * 根据srcV中的点生成多边形线段,并放入dstV
             * @param dstV
             * @param srcV
             */        
            private function putEdge(dstV:Vector.<Line2D>, srcV:Vector.<Vector2f>):void {
                if (srcV.length < 3) return;    //不是一个多边形
                
                var p1:Vector2f = srcV[0];
                var p2:Vector2f;
                for (var i:int=1; i<srcV.length; i++) {
                    p2 = srcV[i];
                    dstV.push(new Line2D(p1, p2));
                    p1 = p2;
                }
                p2 = srcV[0];
                dstV.push(new Line2D(p1, p2));
            }
            
            /**
             * 判断线段是否是约束边
             * @param line
             * @return 线段的索引,如果没有找到,返回-1
             */        
            private function indexOfVector(line:Line2D, vector:Vector.<Line2D>):int {
                var lt:Line2D;
                for (var i:int=0; i<vector.length; i++) {
                    lt = vector[i];
                    if (lt.equals(line)) return i;
                }
                return -1;
            }
            
            /**
             * 计算 DT 点
             * @param line
             * @return 
             */        
            private function findDT(line:Line2D):Vector2f {
                var p1:Vector2f = line.getPointA();
                var p2:Vector2f = line.getPointB();
                
                //搜索所有可见点             TODO 按y方向搜索距线段终点最近的点
                var allVPoint:Vector.<Vector2f> = new Vector.<Vector2f>();        // line的所有可见点
                for each (var vt:Vector2f in this.vertexV) {
                    if (isVisiblePointOfLine(vt, line)) {
                        allVPoint.push(vt);
                    }
                }
    
                if (allVPoint.length == 0) return null;
                
                var p3:Vector2f = allVPoint[0];   
    
                var loopSign:Boolean = false;
                do {
                    loopSign = false;
                    
                    //Step1. 构造 Δp1p2p3 的外接圆 C(p1,p2,p3)及其网格包围盒 B(C(p1,p2,p3))
                    var circle:Circle = this.circumCircle(p1, p2, p3);
                    var boundsBox:Rectangle = this.circleBounds(circle);
                    
                    //Step2. 依次访问网格包围盒内的每个网格单元:
                    //         若某个网格单元中存在可见点 p, 并且 ∠p1pp2 > ∠p1p3p2,则令 p3=p,转Step1;否则,转Step3.
                    var angle132:Number = Math.abs(lineAngle(p1, p3, p2));    // ∠p1p3p2
                    for each (var vec:Vector2f in allVPoint) {
                        if ( vec.equals(p1) || vec.equals(p2) || vec.equals(p3) ) {
                            continue;
                        }
                        //不在包围盒中
                        if (boundsBox.contains(vec.x, vec.y) == false) {
                            continue;
                        }
                        
                        //夹角
                        var a1:Number = Math.abs(lineAngle(p1, vec, p2));
                        if (a1 > angle132) {
                            /转Step1
                            p3 = vec;
                            loopSign = true;
                            break;
                        }
                    }
                    ///转Step3
                } while (loopSign); 
                
                //Step3. 若当前网格包围盒内所有网格单元都已被处理完,
                //         也即C(p1,p2,p3)内无可见点,则 p3 为的 p1p2 的 DT 点
                return p3;
            }
            
            /**
             * 返回顶角在o点,起始边为os,终止边为oe的夹角, 即∠soe (单位:弧度) 
             * 角度小于pi,返回正值;   角度大于pi,返回负值 
             */        
            private function lineAngle(s:Vector2f, o:Vector2f, e:Vector2f):Number 
            { 
                var cosfi:Number, fi:Number, norm:Number; 
                var dsx:Number = s.x - o.x; 
                var dsy:Number = s.y - o.y; 
                var dex:Number = e.x - o.x; 
                var dey:Number = e.y - o.y; 
                
                cosfi = dsx*dex + dsy*dey; 
                norm = (dsx*dsx + dsy*dsy) * (dex*dex + dey*dey); 
                cosfi /= Math.sqrt( norm ); 
                
                if (cosfi >=  1.0 ) return 0; 
                if (cosfi <= -1.0 ) return -Math.PI; 
                
                fi = Math.acos(cosfi); 
                if (dsx*dey - dsy*dex > 0) return fi;      // 说明矢量os 在矢量 oe的顺时针方向 
                return -fi; 
            } 
            
            /**
             * 返回圆的包围盒
             * @param c
             * @return 
             */        
            private function circleBounds(c:Circle):Rectangle {
                return new Rectangle(c.center.x-c.r, c.center.y-c.r, c.r*2, c.r*2);
            }
            
            /**
             * 返回三角形的外接圆
             * @param p1
             * @param p2
             * @param p3
             * @return 
             */        
            private function circumCircle(p1:Vector2f, p2:Vector2f, p3:Vector2f):Circle {
                var m1:Number,m2:Number,mx1:Number,mx2:Number,my1:Number,my2:Number;
                var dx:Number,dy:Number,rsqr:Number,drsqr:Number;
                var xc:Number, yc:Number, r:Number;
                
                /* Check for coincident points */
                
                if ( Math.abs(p1.y-p2.y) < EPSILON && Math.abs(p2.y-p3.y) < EPSILON )
                {
                    trace("CircumCircle: Points are coincident.");
                    return null;
                }
                
                m1 = - (p2.x - p1.x) / (p2.y - p1.y);
                m2 = - (p3.x-p2.x) / (p3.y-p2.y);
                mx1 = (p1.x + p2.x) / 2.0;
                mx2 = (p2.x + p3.x) / 2.0;
                my1 = (p1.y + p2.y) / 2.0;
                my2 = (p2.y + p3.y) / 2.0;
                
                if ( Math.abs(p2.y-p1.y) < EPSILON ) {
                    xc = (p2.x + p1.x) / 2.0;
                    yc = m2 * (xc - mx2) + my2;
                } else if ( Math.abs(p3.y - p2.y) < EPSILON ) {
                    xc = (p3.x + p2.x) / 2.0;
                    yc = m1 * (xc - mx1) + my1;    
                } else {
                    xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
                    yc = m1 * (xc - mx1) + my1;
                }
                
                dx = p2.x - xc;
                dy = p2.y - yc;
                rsqr = dx*dx + dy*dy;
                r = Math.sqrt(rsqr);
                
                return new Circle(new Vector2f(xc, yc), r);
            }
            
            /**
             * 判断点vec是否为line的可见点
             * @param vec
             * @param line
             * @return true:vec是line的可见点
             */        
            private function isVisiblePointOfLine(vec:Vector2f, line:Line2D):Boolean {
                if (vec.equals(line.getPointA()) || vec.equals(line.getPointB())) {
                    return false;
                }
                
                //(1) p3 在边 p1p2 的右侧 (多边形顶点顺序为顺时针);
                if (line.classifyPoint(vec, EPSILON) != PointClassification.RIGHT_SIDE)
                {
                    return false;
                }
                
                //(2) p3 与 p1 可见,即 p1p3 不与任何一个约束边相交;
                if (isVisibleIn2Point(line.getPointA(), vec) == false) {
                    return false;
                }
                
                //(3) p3 与 p2 可见
                if (isVisibleIn2Point(line.getPointB(), vec) == false) {
                    return false;
                }
                
                return true;
            }
            
            /**
             * 点pa和pb是否可见(pa和pb构成的线段不与任何约束边相交,不包括顶点)
             * @param pa
             * @param pb
             * @return 
             */
            private function isVisibleIn2Point(pa:Vector2f, pb:Vector2f):Boolean {
                var linepapb:Line2D = new Line2D(pa, pb);
                var interscetVector:Vector2f = new Vector2f();        //线段交点
                for each (var lineTmp:Line2D in this.edgeV) {
                    //两线段相交
                    if (linepapb.intersection(lineTmp, interscetVector) == LineClassification.SEGMENTS_INTERSECT) {
                        //交点是不是端点
                        if ( !pa.equals(interscetVector) && !pb.equals(interscetVector) ) {
                            return false;
                        }
                    }
                }
                return true;
            }
            
        }
    }
    
    import org.blch.geom.Vector2f;
    /**
     * 圆
     * @author blc
     */
    class Circle {
        public var center:Vector2f;        //圆心
        public var r:Number;            //半径
            
        public function Circle(cen:Vector2f, r:Number) {
            this.center = cen;
            this.r = r;
        }
    }</span>

    NAV导航网格寻路(5) -- 生成网格的一些补充

    如果你也实现了上一章提到的代码,不难发现对下图的两种情况会出现问题


    左面的是两个区域有相交的情况,右面的是多边形本身有自交,在这两种情况下,前面给出的代码均会产生错误的结果。

    对于两个多边形相交,可以在生成网格之前先合并多边形,合并后如图


    合并算法在前面多边形剪裁处已给出一个,这里只贴上代码:

    <span style="background-color: rgb(255, 255, 255);">         /**
             * 合并两个多边形(Weiler-Athenton算法)
             * @param polygon
             * @return 
             *             null--两个多边形不相交,合并前后两个多边形不变
             *             Polygon--一个新的多边形
             */        
            public function union(polygon:Polygon):Vector.<Polygon> {
                //包围盒不相交
                if (rectangle().intersection(polygon.rectangle()) == false) {
                    return null;
                }
                
                //所有顶点和交点
                var cv0:Vector.<Node> = new Vector.<Node>();//主多边形
                var cv1:Vector.<Node> = new Vector.<Node>();//合并多边形
                //初始化
                var node:Node;
                for (var i:int=0; i<this.vertexV.length; i++) {
                    node = new Node(this.vertexV[i], false, true);
                    if (i > 0) {
                        cv0[i-1].next = node;
                    }
                    cv0.push(node);
                }
                for (var j:int=0; j<polygon.vertexV.length; j++) {
                    node = new Node(polygon.vertexV[j], false, false);
                    if (j > 0) {
                        cv1[j-1].next = node;
                    }
                    cv1.push(node);
                }
                
                //插入交点
                var insCnt:int = this.intersectPoint(cv0, cv1);
                
                //生成多边形
                if (insCnt > 0) {
                    //顺时针序
                    return linkToPolygon(cv0, cv1);
                } else {
                    return null;
                }
                
                return null;
            }
            
            /**
             * 生成多边形,顺时针序; 生成的内部孔洞多边形为逆时针序
             * @param cv0
             * @param cv1
             * @return 合并后的结果多边形数组(可能有多个多边形)
             */        
            private function linkToPolygon(cv0:Vector.<Node>, cv1:Vector.<Node>):Vector.<Polygon> {
                trace("linkToPolygon***linkToPolygon");
                //保存合并后的多边形数组
                var rtV:Vector.<Polygon> = new Vector.<Polygon>();
                
                //1. 选取任一没有被跟踪过的交点为始点,将其输出到结果多边形顶点表中.
                for each (var testNode:Node in cv0) {
                    if (testNode.i == true && testNode.p == false) {
                        var rcNodes:Vector.<Vector2f> = new Vector.<Vector2f>();
                        while (testNode != null) {
                            
                            testNode.p = true;
                            
                            // 如果是交点
                            if (testNode.i == true) {
                                testNode.other.p = true;
                                
                                if (testNode.o == false) {        //该交点为进点(跟踪裁剪多边形边界)
                                    if (testNode.isMain == true) {        //当前点在主多边形中
                                        testNode = testNode.other;        //切换到裁剪多边形中
                                    }
                                } else {                    //该交点为出点(跟踪主多边形边界)
                                    if (testNode.isMain == false) {        //当前点在裁剪多边形中
                                        testNode = testNode.other;        //切换到主多边形中
                                    }
                                }
                            }
                            
                            rcNodes.push(testNode.v);          // 如果是多边形顶点,将其输出到结果多边形顶点表中
                            
                            if (testNode.next == null) {    //末尾点返回到开始点
                                if (testNode.isMain) {
                                    testNode = cv0[0];
                                } else {
                                    testNode = cv1[0];
                                }
                            } else {
                                testNode = testNode.next;
                            }
                            
                            //与首点相同,生成一个多边形
                            if (testNode.v.equals(rcNodes[0])) break;
                        }
                        //提取
                        rtV.push(new Polygon(rcNodes.length, rcNodes));
                    }
                }
                
                trace("rtV", rtV);
                return rtV;
            }
            
            /**
             * 生成交点,并按顺时针序插入到顶点表中
             * @param cv0 (in/out)主多边形顶点表,并返回插入交点后的顶点表
             * @param cv1 (in/out)合并多边形顶点表,并返回插入交点后的顶点表
             * @return 交点数
             */        
            private function intersectPoint(cv0:Vector.<Node>, cv1:Vector.<Node>):int {
                var insCnt:int = 0;        //交点数
                
                var findEnd:Boolean = false;
                var startNode0:Node = cv0[0];
                var startNode1:Node;
                var line0:Line2D;
                var line1:Line2D;
                var ins:Vector2f;
                var hasIns:Boolean;
                var result:int;        //进出点判断结果
                while (startNode0 != null) {        //主多边形
                    if (startNode0.next == null) {  //最后一个点,跟首点相连
                        line0 = new Line2D(startNode0.v, cv0[0].v);
                    } else {
                        line0 = new Line2D(startNode0.v, startNode0.next.v);
                    }
                    
                    startNode1 = cv1[0];
                    hasIns = false;
                    
                    while (startNode1 != null) {        //合并多边形
                        if (startNode1.next == null) {
                            line1 = new Line2D(startNode1.v, cv1[0].v);
                        } else {
                            line1 = new Line2D(startNode1.v, startNode1.next.v);
                        }
                        ins = new Vector2f();    //接受返回的交点
                        //有交点
                        if (line0.intersection(line1, ins) == LineClassification.SEGMENTS_INTERSECT) {
                            //忽略交点已在顶点列表中的
                            if (this.getNodeIndex(cv0, ins) == -1) {
                                insCnt++;
                                
                                / 插入交点
                                var node0:Node = new Node(ins, true, true);
                                var node1:Node = new Node(ins, true, false);
                                cv0.push(node0);
                                cv1.push(node1);
                                //双向引用
                                node0.other = node1;
                                node1.other = node0;
                                //插入
                                node0.next = startNode0.next;
                                startNode0.next = node0;
                                node1.next = startNode1.next;
                                startNode1.next = node1;
                                //出点
                                if (line0.classifyPoint(line1.getPointB()) == PointClassification.RIGHT_SIDE) {
                                    node0.o = true;
                                    node1.o = true;
                                }
                                //TODO 线段重合
    //                            trace("交点****", node0);
                                
                                hasIns = true;        //有交点
                                
                                //有交点,返回重新处理
                                break;
                            }
                        }
                        startNode1 = startNode1.next;
                    }
                    //如果没有交点继续处理下一个边,否则重新处理该点与插入的交点所形成的线段
                    if (hasIns == false) {
                        startNode0 = startNode0.next;
                    }
                }
                return insCnt;
            }
            
            /**
             * 取得节点的索引(合并多边形用)
             * @param cv
             * @param node
             * @return 
             */        
            private function getNodeIndex(cv:Vector.<Node>, node:Vector2f):int {
                for (var i:int=0; i<cv.length; i++) {
                    if (cv[i].v.equals(node)) {
                        return i;
                    }
                }
                return -1;
            }
    
    对于一个给定的多边形数组polygonV,可以象下面这样在三角化以前做预处理
    
            /**
             * 合并
             */        
            private function unionAll():void {
                for (var n:int=1; n<polygonV.length; n++) {
                    var p0:Polygon = polygonV[n];
                    for (var m:int=1; m<polygonV.length; m++) {
                        var p1:Polygon = polygonV[m];
                        if (p0 != p1 && p0.isCW() && p1.isCW()) {
                            var v:Vector.<Polygon> = p0.union(p1);    //合并
                            
                            if (v != null && v.length > 0) {
                                trace("delete");
                                polygonV.splice(polygonV.indexOf(p0), 1);
                                polygonV.splice(polygonV.indexOf(p1), 1);
    
                                for each (var pv:Polygon in v) {
                                    polygonV.push(pv);
                                }
                                
                                n = 1;    //重新开始
                                break;
                            }
                        }
                    }
                }
            }</span>

    对于多边形自交,可以采用类似多边形剪裁的方法将一个多边形拆分成多个,也可以直接禁止用户绘制这种多边形。我是采用后一种方法所以这里没有代码。 

    多边形的顶点顺序,上面多处代码都要求多边形顶点按顺时针或逆时针方向保存,但是我们不可能要求用户按哪个固定方向绘制图形,那么怎么判断多边形的顶点顺序。方法的基本思路就是取一个多边形的凸点,然后判断这个点的下一个点的方向,代码如下:

    <span style="background-color: rgb(255, 255, 255);">        /**
             * 将多边形的顶点按顺时针排序
             */        
            public function cw():void {
                if (this.isCW() == false) {    //如果为逆时针顺序, 反转为顺时针
                    this.vertexV.reverse();    //反转数组
                }
            }
            
            /**
             * clockwise
             * @return true -- clockwise; false -- counter-clockwise
             */        
            public function isCW():Boolean {
                if (vertexV == null || vertexV.length < 0) return false;
                
                //最上(y最小)最左(x最小)点, 肯定是一个凸点
                //寻找最上点
                var topPt:Vector2f = this.vertexV[0];
                var topPtId:int = 0;    //点的索引
                for (var i:int=1; i<vertexV.length; i++) {
                    if (topPt.y > vertexV[i].y) {
                        topPt = vertexV[i];
                        topPtId = i;
                    } else if (topPt.y == vertexV[i].y) { //y相等时取x最小
                        if (topPt.x > vertexV[i].x) {
                            topPt = vertexV[i];
                            topPtId = i;
                        }
                    }
                }
                
                //凸点的邻点
                var lastId:int = topPtId-1>=0 ? topPtId-1 : vertexV.length-1;
                var nextId:int = topPtId+1>=vertexV.length ? 0 : topPtId+1;
                var last:Vector2f = vertexV[lastId];
                var next:Vector2f = vertexV[nextId];
                
                //判断
                var r:Number = multiply(last, next, topPt);
                if (r < 0) {
                    return true;
                //三点共线情况不存在,若三点共线则说明必有一点的y(斜线)或x(水平线)小于topPt
                }
                
                return false;
            }
            
            /**
             * r=multiply(sp,ep,op),得到(sp-op)*(ep-op)的叉积 
             * r>0:ep在矢量opsp的逆时针方向; 
             * r=0:opspep三点共线; 
             * r<0:ep在矢量opsp的顺时针方向 
             * @param sp 
             * @param ep 
             * @param op 
             * @return 
             */        
            private function multiply(sp:Vector2f, ep:Vector2f, op:Vector2f):Number { 
                return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); 
            }</span>

    NAV导航网格寻路(5) -- 生成网格的一些补充  - 竹石 - 游戏...NAV导航网格寻路(5) -- 生成网格的一些补充  - 竹石 - 游戏...到此生成网格的关键代码都发出来了,下一章放上寻路的代码

    NAV导航网格寻路(6) -- 寻路实现  

    前面已经介绍了寻路的方法,现在给出我的一个实现。

    A*寻找网格路径

    A*算法就不说了,网上很多,这里只说下三角形网格如何使用A*算法,如下图,绿色直线代表最终路径和方向,路径线进入三角形的边称为穿入边,路径线出去的边称为穿出边。每个三角形的花费(g值)采用穿入边和穿出边的中点的距离(图中红线),至于估价函数(h值)使用该三角形的中心点(3个顶点的平均值)到路径终点的x和y方向的距离。


    下面只贴出关键代码

    <span style="background-color: rgb(255, 255, 255);">private var m_CellVector:Vector.<Cell>;
      
             private var openList:Heap;     //二叉堆
             private var closeList:Array;
    
     /**
             * 构建网格路径,该方法生成closeList
             * @param startCell 起始点所在网格
             * @param startPos 起始点坐标
             * @param endCell 终点所在网格
             * @param endPos 终点坐标
             * @return 
             */
    
     public function buildPath(startCell:Cell, startPos:Vector2f, 
                                      endCell:Cell, endPos:Vector2f):void{
                openList.clear();
                closeList.length = 0;
                
                openList.put(endCell);
                endCell.f = 0;
                endCell.h = 0;
                endCell.isOpen = false;
                endCell.parent = null;
                endCell.sessionId = pathSessionId;
                
                var foundPath:Boolean = false;        //是否找到路径
                var currNode:Cell;                //当前节点
                var adjacentTmp:Cell = null;    //当前节点的邻接三角型
                while (openList.size > 0) {
                    // 1. 把当前节点从开放列表删除, 加入到封闭列表
                    currNode = openList.pop();
                    closeList.push(currNode);
                    
                    //路径是在同一个三角形内
                    if (currNode == startCell) {
                        foundPath = true;
                        break;
                    }
                    
                    // 2. 对当前节点相邻的每一个节点依次执行以下步骤:
                    //所有邻接三角型
                    var adjacentId:int;
                    for (var i:int=0; i<3; i++) {
                        adjacentId = currNode.links[i];
                        // 3. 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,
                        //    则什么操作也不执行,继续检验下一个节点;
                        if (adjacentId < 0) {                        //不能通过
                            continue;
                        } else {
                            adjacentTmp = m_CellVector[adjacentId];            //m_CellVector 保存所有网格的数组
                        }
                        
                        if (adjacentTmp != null) {
                            if (adjacentTmp.sessionId != pathSessionId) {
                                // 4. 如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 
                                //    并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和F值;
                                adjacentTmp.sessionId = pathSessionId;
                                adjacentTmp.parent = currNode;
                                adjacentTmp.isOpen = true;
                                
                                //H和F值
                                adjacentTmp.computeHeuristic(startPos);
    
                         //m_WallDistance 是保存三角形各边中点连线的距离,共3个
                                adjacentTmp.f = currNode.f + adjacentTmp.m_WallDistance[Math.abs(i - currNode.m_ArrivalWall)];
                                
                                //放入开放列表并排序
                                openList.put(adjacentTmp);
                                
                                // remember the side this caller is entering from
                                adjacentTmp.setAndGetArrivalWall(currNode.index);
                            } else {
                                // 5. 如果该相邻节点在开放列表中, 
                                //    则判断若经由当前节点到达该相邻节点的G值是否小于原来保存的G值,
                                //    若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值
                                if (adjacentTmp.isOpen) {//已经在openList中
                                    if (currNode.f + adjacentTmp.m_WallDistance[Math.abs(i - currNode.m_ArrivalWall)] < adjacentTmp.f) {
                                        adjacentTmp.f = currNode.f;
                                        adjacentTmp.parent = currNode;
                                        
                                        // remember the side this caller is entering from
                                        adjacentTmp.setAndGetArrivalWall(currNode.index);
                                    }
                                } else {//已在closeList中
                                    adjacentTmp = null;
                                    continue;
                                }
                            }
                        }
                    }
                }
    
    }
    
     
    
    由close list取出网格路径
    
    /**
             * 路径经过的网格
             * @return 
             */        
            private function getCellPath():Vector.<Cell> {
                var pth:Vector.<Cell> = new Vector.<Cell>();
                
                var st:Cell = closeList[closeList.length-1];
                pth.push(st);
                            
                while (st.parent != null) {
                    pth.push(st.parent);
                    st = st.parent;
                }
                return pth;
            }
    
     
    
    根据网格路径计算路径点
    
    算法前面已经详细说明,以下是代码
    
     /**
             * 根据经过的三角形返回路径点(下一个拐角点法)
             * @param start 
             * @param end 
             * @return Point数组
             */        
            private function getPath(start:Vector2f, end:Vector2f):Array {
                //经过的三角形
                var cellPath:Vector.<Cell> = getCellPath();
                //没有路径
                if (cellPath == null || cellPath.length == 0) {
                    return null;
                }
                
                //保存最终的路径(Point数组)
                var pathArr:Array = new Array();
                
                //开始点
                pathArr.push(start.toPoint());    
                //起点与终点在同一三角形中
                if (cellPath.length == 1) {        
                    pathArr.push(end.toPoint());    //结束点
                    return pathArr;
                }
                
                //获取路点
                var wayPoint:WayPoint = new WayPoint(cellPath[0], start);
                while (!wayPoint.position.equals(end)) {
                    wayPoint = this.getFurthestWayPoint(wayPoint, cellPath, end);
                    pathArr.push(wayPoint.position);
                }
                
                return pathArr;
            }
            
            /**
             * 下一个拐点
             * @param wayPoint 当前所在路点
             * @param cellPath 网格路径
             * @param end 终点
             * @return 
             */        
            private function getFurthestWayPoint(wayPoint:WayPoint, cellPath:Vector.<Cell>, end:Vector2f):WayPoint {
                var startPt:Vector2f = wayPoint.position;    //当前所在路径点
                var cell:Cell = wayPoint.cell;
                var lastCell:Cell = cell;
                var startIndex:int = cellPath.indexOf(cell);    //开始路点所在的网格索引
                var outSide:Line2D = cell.sides[cell.m_ArrivalWall];    //路径线在网格中的穿出边
                var lastPtA:Vector2f = outSide.getPointA();
                var lastPtB:Vector2f = outSide.getPointB();
                var lastLineA:Line2D = new Line2D(startPt, lastPtA);
                var lastLineB:Line2D = new Line2D(startPt, lastPtB);
                var testPtA:Vector2f, testPtB:Vector2f;        //要测试的点
                for (var i:int=startIndex+1; i<cellPath.length; i++) {
                    cell = cellPath[i];
                    outSide = cell.sides[cell.m_ArrivalWall];
                    if (i == cellPath.length-1) {
                        testPtA = end;
                        testPtB = end;
                    } else {
                        testPtA = outSide.getPointA();
                        testPtB = outSide.getPointB();
                    }
                    
                    if (!lastPtA.equals(testPtA)) {
                        if (lastLineB.classifyPoint(testPtA, EPSILON) == PointClassification.RIGHT_SIDE) {
                            //路点
                            return new WayPoint(lastCell, lastPtB);
                        } else {
                            if (lastLineA.classifyPoint(testPtA, EPSILON) != PointClassification.LEFT_SIDE) {
                                lastPtA = testPtA;
                                lastCell = cell;
                                //重设直线
                                lastLineA.setPointB(lastPtA);
                            }
                        }
                    }
                    
                    if (!lastPtB.equals(testPtB)) {
                        if (lastLineA.classifyPoint(testPtB, EPSILON) == PointClassification.LEFT_SIDE) {
                            //路径点
                            return new WayPoint(lastCell, lastPtA);
                        } else {
                            if (lastLineB.classifyPoint(testPtB, EPSILON) != PointClassification.RIGHT_SIDE) {
                                lastPtB = testPtB;
                                lastCell = cell;
                                //重设直线
                                lastLineB.setPointB(lastPtB);
                            }
                        }
                    }
                }
                return new WayPoint(cellPath[cellPath.length-1], end);    //终点
            }</span>

    NAV导航网格寻路(7) -- 代码和一些优化

    这里发不了源码,本系列完整源码可以到http://bbs.9ria.com/thread-49841-1-1.html下。

           看下图,最优路径应该是从上面绕过中间阻挡区,而实际寻路产生的路径确是下面。这是由于,在网格面积过大或有某边长度过长时,由于a*中的花费是计算网格的两边中点距离而不实际的路径长度,所以产生的路径偏差较大。所以在一般的网格生成算法中都会加入网格最小面积和最大面积的限制,如果生成的网格小于最小面积时则抛弃,如果大于最大面积则拆分。


    一般地图中都会产生孤岛,如下图,两个阻挡区域交叉,合并后在中间深红色区域产生孤岛。按照上面介绍的剪裁算法,中间孤岛多边形会以逆时针方向存储(其他顺时针),因此在这一步能够判断出是否生成孤岛。对于生成的孤岛,如果游戏允许人物可以通过瞬移等方式进入孤岛,那么孤岛也需要生成nav网格,不过孤岛的nav网格和其他区域的网格最好能分成不同区域,这样在寻路时就可以优化(起点和终点不在同区域,可直接确定为不能通过)。




    展开全文
  • creator网格导航寻路

    2018-10-06 12:15:37
    网格寻路算法
  • 另外,对于六边形网格,这里使用的是简单的基于Y轴(三维Z轴)偏移的二维坐标,因此,在获取当前网格周围六个相邻格子时,对于偶数列,要做相应偏移。 另外有一些可以优化的点(用二叉搜索树代替待寻列表,布兰森汉...

     

    最近项目里有用到,记录一下,方便以后拿来即用

    基本思路:

    仍然是两个集合,一个保存待寻路的列表,一个保存已经走过or不考虑的,每次遍历拿出最优路径点.

    另外,对于六边形网格,这里使用的是简单的基于Y轴(三维Z轴)偏移的二维坐标,因此,在获取当前网格周围六个相邻格子时,对于偶数列,要做相应偏移。

    另外有一些可以优化的点(用二叉搜索树代替待寻列表,布兰森汉姆先检查两点是否直接连通,对路径进行平滑处理,缓存等)

    下面是思路和测试代码,正式工程禁止

    寻路相关HexPathFinder.CS:

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    public class HexPathFinder
    {
        /// <summary>
        /// 该类表示寻路路径上的一个路径点
        /// </summary>
        internal class PathPoint
        {
            /// <summary>
            /// constructor
            /// </summary>
            public PathPoint (Hex hex, Hex end,PathPoint prev)
            {
                _hex = hex;
                //get manhattan distance
                var h = Mathf.Abs( hex.X - end.X ) + Mathf.Abs( hex.Y - end.Y ) + Mathf.Abs( hex.Z - end.Z );
                F = G + h / 2;
                _parent = prev;
            }
    
            public int F { get; private set; } = -1;
    
            public Hex _hex { get; private set; }
            private PathPoint _parent;
    
            public int X => _hex.X;
            public int Y => _hex.Y;
    
            /// <summary>
            /// 这里可以不用parent,因为每个Parent没有保存其上一级Parent的引用
            /// </summary>
            public PathPoint Parent => _parent;
    
            public int G => GetG();
    
            public int GetG ()
            {
                var step = 0;
                var temp = Parent;
                while (temp != null)
                {
                    temp = temp.Parent;
                    step++;
                }
                return step;
            }
        }
    
        /// <summary>
        /// 基于AStar的寻路算法,该函数接收一个起点,一个终点,返回由起点至终点按顺序排列的坐标集合,如果寻路失败则返回空列表
        /// </summary>
        public List<(int x, int y)> FindPath (Hex start, Hex end )//#todo如果无法到终点是否达到最近路径点?
        {
            //#优化 Bresenham检查两点是否可以直接连通,可以直接返回
            //路径点集合
            var pointDic = new Dictionary<int, PathPoint>();//检查引用集合
            var openLst = new List<PathPoint>();//待寻列表
            var closeDic = new Dictionary<int, Hex>();//走过的
            var pathLst = new List<(int, int)>();//结果
    
            var startPoint = new PathPoint( start,end,null );
            openLst.Add( startPoint );
            while (openLst.Count != 0)
            {
                var curr = openLst[0];
                pathLst.Add( curr._hex.Coordinate );
                if (openLst.Contains( curr ))
                {
                    openLst.Remove( curr );
                    pointDic.Remove( curr._hex.ID );//如果有就删掉,没有也没关系
                }
                //for test
                Entrance.Ins.GetHex( curr.X, curr.Y ).HighLight();
    
                if (curr._hex == end)//终点
                    break;
                else
                {
                    if (!closeDic.ContainsKey( curr._hex.ID ))
                        closeDic.Add( curr._hex.ID, curr._hex );
                }
    
                PathPoint nearPoint = null;
                Hex nearHex = null;
                //拿周围六格
                //这里使用的是简单的偏移二维坐标,具体需要结合实际地图
                for (int i = 0; i < 6; i++)
                {
                    var isEven = curr.Y % 2 == 0;
                    //六边形网格的偏移量
                    var xOffset = 0;
                    var yOffset = 0;
    
                    switch (i)
                    {
                        case 0://右上
                            xOffset = isEven ? 0 : 1;
                            yOffset = 1;
                            break;
                        case 1://正右
                            xOffset = 1;
                            break;
                        case 2://右下
                            xOffset = isEven ? 0 : 1;
                            yOffset = 1;
                            break;
                        case 3://左上
                            xOffset = isEven ? -1 : 0;
                            yOffset = 1;
                            break;
                        case 4://正左
                            xOffset = -1;
                            break;
                        case 5://左下
                            xOffset = isEven ? -1 : 0;
                            yOffset = -1;
                            break;
                    }
                    nearHex = Entrance.Ins.GetHex( curr.X + xOffset, curr.Y + yOffset );
                    if (nearHex is null || !nearHex.IsPassable)//边界或不可通行
                        continue;
    
                    if (closeDic.ContainsKey( nearHex.ID ))//走过了
                        continue;
    
                    if (!pointDic.ContainsKey( nearHex.ID ))
                    {
                        nearPoint = new PathPoint( nearHex, end, curr );
                        pointDic.Add( nearPoint._hex.ID, nearPoint );
                    }
                    else
                        nearPoint = pointDic[nearHex.ID];
    
                    if (!openLst.Contains( nearPoint ))
                        openLst.Add( nearPoint );
                }
    
                //#优化 改成BST效率更高
                //保证每次都拿到最优路径点
                openLst.Sort( (x,y) =>
                 {
                     return x.F <= y.F ? -1 : 1;
                 } );
            }
    
            if (openLst.Count == 0)//没有可走的路径
            {
                pathLst.Clear();
                return pathLst;
            }
            return pathLst;
        }
    
        private static HexPathFinder _ins;
    
        private static HexPathFinder GetIns ()
        {
            if (_ins is null)
                _ins = new HexPathFinder();
    
            return _ins;
        }
    
        /// <summary>
        /// 单例
        /// </summary>
        public static HexPathFinder Ins => _ins is null ? GetIns() : _ins;
    }
    

    启动场景挂载加GameObject挂Entrance脚本以测试:

    Entrance.cs:

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    public class Entrance : MonoBehaviour
    {
        public static Entrance Ins = null;
    
        //[SerializeField] private Hex[] _hexArr;
        [SerializeField] GameObject _hexRoot;
    
        /// <summary>
        /// 六边形网格集合
        /// </summary>
        private Dictionary<int, Hex> _hexDic;
        private HashSet<(int X,int Y)> _hexSet;
        private List<List<Hex>> _hexList;
    
        private void Awake ()
        {
            _hexDic = new Dictionary<int, Hex>();
            _hexSet = new HashSet<(int,int)>();
            _hexList = new List<List<Hex>>();
            Ins = this;
        }
    
        private void Start ()
        {
            //测试代码。。。
            var hexArr = _hexRoot.GetComponentsInChildren<Hex>();
            //Init
            foreach (var hex in hexArr)
            {
                if (_hexDic.ContainsKey( hex.ID ))
                {
                    Debug.Log($"已经存在ID:{hex.ID}");
                    continue;
                }
    
                if (_hexSet.Contains( hex.Coordinate ))
                {
                    Debug.Log($"已经存在坐标:{hex.Coordinate}");
                    continue;
                }
    
                _hexDic.Add( hex.ID, hex );
                _hexSet.Add( hex.Coordinate );
            }
    
            Test();
        }
    
        private void Test ()
        {
            //test
            var start = GetHex( 0,0);
            var end = GetHex( 5,2);
            if (start is null || end is null)
            {
                Debug.Log("<color=red>路径点不存在</color>");
                return;
            }
            var lst = HexPathFinder.Ins.FindPath( start, end );
    
            foreach (var item in lst)
            {
                GetHex( item.x, item.y ).HighLight();
                Debug.Log( $"{item.x},{item.y}" );
            }
        }
    
        private void Update ()
        {
            if (Input.GetKeyDown( KeyCode.Delete ))
                Test();
        }
    }
    

    网格类型Hex.cs:

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    using UnityEngine.UI;
    
    public class Hex : MonoBehaviour
    {
        //ID
        public int ID => _id < 0 ? GetID() : _id;
    
        /// <summary>
        /// 坐标
        /// </summary>
        public (int X, int Y) Coordinate => (_x, _y);
    
        public int X => _x;
        public int Y => _y;
    
        /// <summary>
        /// 立方体Z轴坐标
        /// </summary>
        public int Z => CubeCoordinate.z;//对于六边形网格,在计算两点距离时需要额外的一个轴
    
        /// <summary>
        /// 立方体坐标
        /// </summary>
        public Vector3Int CubeCoordinate => GetCubeCoordinate();
    
        /// <summary>
        /// 生成立方体坐标
        /// </summary>
        private Vector3Int GetCubeCoordinate ()
        {
            if (_cubeCoordinate == Vector3Int.one)
            {
                var z = _x + _y;
                z *= -1;
                _cubeCoordinate = new Vector3Int( _x, _y, z );
            }
            return _cubeCoordinate;
        }
    
        public static bool operator + (Hex thisHex, Hex other) => thisHex.Coordinate == other.Coordinate;
    
        /// <summary>
        /// 是否可通行,true代表可以
        /// </summary>
        public bool IsPassable => _passable;
    
        private int GetID ()
        {
            _id = IDPool.ID;
            return _id;
        }
    
        [SerializeField] private int _x;
        [SerializeField] private int _y;
        [SerializeField] private int _id = int.MinValue;
        [SerializeField] private bool _passable = true;
    
        private SpriteRenderer _spRender;
    
        public void HighLight ()
        {
            _text.color = Color.green;
        }
    
        /// <summary>
        /// 立方体坐标
        /// </summary>
        private Vector3Int _cubeCoordinate = Vector3Int.one;
    
        private Text _text;
    
        private void OnEnable ()
        {
            _text = GetComponentInChildren<Text>();
            _text.text = $"{_x},{_y},{Z}";//set text
            _text.rectTransform.sizeDelta = new Vector2( 120f, 80f );
    
            _spRender = GetComponentInChildren<SpriteRenderer>();
            _text.color = _passable ? Color.white : Color.red;
    
            gameObject.name = $"{_x}_{_y}_{Z}";
        }
    }
    
    /// <summary>
    /// ID池
    /// </summary>
    public class IDPool
    {
        private static int _id = int.MaxValue;
    
        public static int ID => _id--;
    }
    

     

    展开全文
  • 比如格子游戏中的格子寻路,塔防怪物的行进路径,捕鱼游戏中的鱼群路径,RPG游戏中的怪物AI等,不同的需求对应的寻路策略的选择也不尽相同。 正文 在Unity3D中我们一般常用的寻路策略有: 1.路点寻路(WayPoint...

    引言

    寻路系统是当今众多游戏中不可或缺的功能模块。比如格子游戏中的格子寻路,塔防怪物的行进路径,捕鱼游戏中的鱼群路径,RPG游戏中的怪物AI等,不同的需求对应的寻路策略的选择也不尽相同。

    正文

    Unity3D中我们一般常用的寻路策略有:

        1.    路点寻路(WayPoint

    路点寻路是最简单,易理解,易操作的(如下图):需要预先设置好路径点坐标集合。然后对象按照规定的坐标集合运动。这种策略成熟的插件为Simple Waypoint System, 可在Asset Store获得。  使用较好的地方:塔防怪物行进路线,鱼群游动路径,AI的巡逻路径。

     

          劣势:(1):如大量怪物在某区域漫游,为了使怪物的漫游看起来更逼真则需要放置更多的路径点。即便如此怪物仍会选择到一些曲曲折折的路径,除非添加更大量的点。这样则造成了更多的工作内容,且效率低下。(2):只能按照规定好的路线行进,如果突然出现一个障碍物,则无法躲避,因为它对路径点以外的东西一无所知(3):路径点不支持参数不同的单位。比如下图一个玩家和一个坦克,玩家完全可以按照红色箭头路线行进。但坦克却不得不与障碍物保持一定距离以避免碰撞如蓝色箭头。

     

    2.    U3D自带的导航网格寻路(NavMesh

         这种方法使用一系列算法(拐角点算法)将原始地图转换成三角形网格的集合,网格和网格之间构成连通关系用于寻路。                                                        

          优点:能精确地表征世界。虽然也做不到百分百还原真实地图,但是它无疑比路点都更精确。                                                                                     

         缺点:1必须是在静态生成的,无法做到动态生成。 2静态生成后的navmesh文件位置已固定,不会随着物体移动。3由于工具集NavMesh算法,数据格式不开源,导致了游戏服务端无法使用,无法和客户端保持一致的导航寻路逻辑。4不能随意的编辑

     

    在Unity5.6以后版本有了新版NavMesh实现了动态烘焙,动态清除navmesh.asset文件,而且对效率做了极大的改善(可以选择只烘焙角色附近一定范围)。但仍然无法做到在服务器端使用。

    参考资料

     1.    https://github.com/Unity-Technologies/NavMeshComponents

    2.    https://zhuanlan.zhihu.com/p/36731426

    3.    https://www.jianshu.com/p/30f749eece88?tdsourcetag=s_pctim_aiomsg

     

    3.   插件A* Pathfinding project

          A* Pathfinding project 是一款在A*算法的基础上进行改进完善的寻路插件,因功能强大但容易使用被大多数对寻路需求较为复杂的游戏所采用。可在Asset Store中获得。

          A星寻路算法基本思路:要实现A星算法,首先将地图抽象成寻路网格,最简单的方式是将游戏地图划分为多个正方形单元,网格越精细,寻路的效果越好,但计算量也越大。A星算法的基本思想就是借助这些网格实现寻路,从起点开始遍历四周的点,寻找最有可能在最短路径上的点,并以这个点为基准继续向四周遍历,直至遍历到终点,路径也就找到了。

         A星寻路算法核心F=G+HF可以理解为通过这个点的总代价,代价越低,这个点当然就更有可能在最短路径上。G是从起点到这个点的代价,H是从这个点到终点的代价,这两个代价加起来就是这个点的总代价。

    我们还需要两个集合,一个是open集合,一个是close集合,open集合里存放的是还未计算代价的点,close集合里是已经计算过的点。开始时open集合里只有起点,close集合没有元素,每次迭代将open集合里F最小的点作为基点,对于基点周围的相邻点做如下处理:

    (1)如果这个点是障碍,直接无视。

    (2)如果这个点不在open表和close表中,则加入open表

    (3)如果这个点已经在open表中,并且当前基点所在路径代价更低,则更新它的G值和父亲

    (4)如果这个点在close表中,忽略。

    处理完之后将基点加入close集合。

    当终点出现在open表中的时候,迭代结束。

    如果到达终点前open表空了,说明没有路径可以到达终点。

    Grid Graph

    这是最直接的一种Graph,和名字一样,他生成的是栅格类型的Graph。它在大多数的场景下表现都是良好的,并且如果你需要在运行时动态更新graph数据也十分的容易和方便。(比如RTS或者塔防游戏)

    但它对于拥有巨量空间的大型世界表现乏力,因为栅格的特性,它会在所有的地方生成相同格式的数据,即使那些地方是大片的空白地区,因此它会消耗过多的内存和使用更长的寻路时间。

    Navmesh Graph

    这个寻路方式在大多数静态场景下(即不会在运行时动态调整障碍和阻挡点)是完美的。他通常来说性能要优于 grid graph,因为他搜索的节点少.(我们游戏中使用的就是这个)

    Recast Graph

     

    recast graph 的原理很简单,先收集你场景里所有的Mesh网格,然后进行体素化。(译注:体素可以理解为3D空间的基本单位,比如一个2D平面的绘制基本单位是像素,3D空间的基本单位叫体素)一个2D的模拟的体素化过程大概就是把一堆的三角形绘制到一张纹理里。然后再进行一些列的模拟设定,诸如角色的高,半径等得到一个可行走的导航网格。      

       这是目前为止最先进的graph生成器。他可以用几秒钟就自动生成一个,正常情况下可能几个小时才能手动生成的网格。

    Layered Grid Graph

    GridGraph的表现一般来说已经比较完美了。但是如果有一些场景有一些重叠的区域,比如移动建筑有很多层,他就不能很完美的处理这些情况了。所以这个graph就用来处理这种情况了。这里有点局限的地方就是目前只支持4方向的寻路,8方向的暂时不能支持。另外还有一些额外的内存开销,但是当你需要进行分层寻路的时候,你可能不得不去使用它

         A* Pathfinding project插件的功能十分强大复杂。具体功能学习可参考

     1. https://www.jianshu.com/p/d0812542239b

     2. https://www.zhihu.com/people/niuxingxing/posts?page=2

     

    总结

     

    每种策略都有自己的优点和缺点,应该根据应用场景选择合适的方式。

    如果开发时间有限,寻路线路相对固定(典型的如塔防游戏),不用考虑真实地形的影响,优先考虑路点寻路。

    如果开发时间有限,寻路需求较为复杂但为单机游戏优先考虑新版NavMesh。

    如果开发时间充裕,寻路需求较为复杂且为网络游戏优先考虑A* Pathfinding project。

    展开全文
  • unity NavMesh网格寻路

    千次阅读 2018-07-22 16:03:00
    NavMeshs是Unity自带的一个寻路系统,即一个点到另一个点寻找最短有效路径 如何使用NavMesh? 先直接使用便于理解,然后再介绍参数属性 直接先给模型添加NavMeshAgent组件,然后自己写一个脚本,通过代码控制它 ...
  • NAV导航网格寻路(1)-- 介绍

    千次阅读 2017-04-17 10:00:49
    WayPoint寻路 下图是一个典型的路点寻路   另一种方法是使用多边形来记录路径信息,它可以提供更多的信息给ai角色使用。下图就是一个navigation mesh。   以下列出几个WayPoint的不足之处:
  • 解析网格工作台 解析来自 Nathan Sturtevant 的的数据文件。 例子 var fs = require ( 'fs' ) var path = require ( 'path' ) var imshow = require ( 'ndarray-imshow' ) var parseMap = require ( '../map' ) var...
  • 一个简单和优化的网格寻路
  • 题目描述: 本题的主要问题是: 1、 输入的顶点数最大可能有1*10的4次方,如果用邻接矩阵表示,那么就要10000×10000大小的数组。明显是不行的。 最好还是要用邻接表(这里我用的是数组表示的邻接表)。...
  • 简单优化的探路者 一个简单的探路者,我试图尽可能地优化最大值,并分享我发现的内容:) 这个想法很简单,实现一个简单的A * Pathfinder并使用尽我所能进行最佳优化,尝试从方法本身中减少GC和MS ...
  • 上图大红框中是我们可以设置的配置的:我们可以设置agent(我们需要进行寻路的对象)的半径和高度还有可以爬坡的倾斜度,比如我们在刚刚设置的斜坡角度大于45°,那么我们的agent就上不去,还可...
  • NavMesh是3D游戏世界中用于实现动态物体自动寻路的一种技术,他将游戏场景中复杂的结构组织关系简化为带有一定信息的网格, 进而在这些网格的基础上通过一些列的计算来实现自动寻路。 二、简单的应用; 1、在...
  • Unity3D-NavMesh导航网格寻路

    万次阅读 2016-05-17 20:05:03
    NavMesh(导航网格)是3D游戏世界中用于动态物体实现自动寻路的技术。 NavMesh系统是人工智能的一种,它使用一个添加在游戏对象上或者作为游戏对象父物体的名为“导航网格代理”(NavMeshAgent)的组件来控制该游戏...
  • 一,概述 二,导航网格寻路系统简单实例 三,导航网格寻路系统相关参数 四,进阶使用
  • 1、Agent Radius(物体的半径)物体半径越小,生成网格面积越大。 2、Agent Height:物体的高度 3、Max Slope 斜坡斜度(最大60°),如果大于设定值就不会生成网格。 4、Step Height 台阶高度 ps这个高度不可以...
  • NAV导航网格寻路(6) -- 寻路实现

    千次阅读 2017-04-17 10:03:53
    前面已经介绍了寻路的方法,现在给出我的一个实现。 A*寻找网格路径 A*算法就不说了,网上很多,这里只说下三角形网格如何使用A*算法,如下图,绿色直线代表最终路径和方向,路径线进入三角形的边称为穿入边,路径...
  • COPY NAV导航网格寻路 -- 光照射线法

    千次阅读 2014-12-31 11:31:47
    上图是一个由任意凸多边形构成的导航网格,白线包围区域代表着不可进入的障碍区域,红线包围区域则可以进入或穿越。网格中所有多边形的顶点存储次序均为顺时钟序。在下面的讨论中,我们的运算一概采用左手系进行。 ...
  • 组件:导航网格寻路

    2019-03-08 17:44:17
    路径及障碍物设置 01.勾选Navigation Static 02.设置Navigation Area Not Walkable:不能经过该物体(不能从它顶部经过) Bridge:桥,指定路径(例如小兵按照某条路径行走) ...分离网格链接(OffMe...
  • Path Finding(路径跟随) Auto Traverse Off Mesh Linked:是否自动分离网格。(勾选时到达分离点时会从该分离点移动到另外一个分离点。)(一般不勾选,因为要配套爬墙或者跳跃的动画) Auto Repath:是否自动...
  • Unity高级功能—网格导航寻路

    千次阅读 2019-11-22 21:05:58
    接着,我们需要给Capsule加一个组件:Nav Mesh Agent,这个组件就是网格导航寻路组件 此时我们给胶囊体Capsule挂一个脚本: using System.Collections;  using System.Collections.Generic;  using ...
  • ,可以在生成网格之前先合并多边形,合并后如图 合并算法在前面多边形剪裁处已给出一个,这里只贴上代码: /* * * 合并两个多边形(Weiler-Athenton算法) * @param polygon * @return * ...
  • 蓝桥杯-网格寻路

    千次阅读 2014-03-09 20:44:18
    public class 网格寻路 { public static int sum=0; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int i,qiDian,zhongDian; ...
  • 上一个项目的寻路方案是客户端和服务器都采用了 NavMesh 作为解决方案,当时的那几篇文章(一,二,三)是很多网友留言和后台发消息询问最多的,看来这个方案有着广泛的需求。但因为是商业项目,我无法贴出代码,...
  • 开发环境:Win10、Unity5.3.4、C#、VS2015 创建日期:2016-05-09 一、简介 本节通过一个简单例子,演示如何利用静态对象实现导航网格,并让某个动态物体利用导航网格自动寻路,最终找到目标。 二、设计步骤 1、添加3...
  • nav寻路一般包含两部分,首先是使用工具根据地图信息生成寻路用的nav mesh,接下来就是在游戏中根据生成的nav mesh来自动寻路。 一般人首先关心的就是寻路方法,所以这里把顺序颠倒下,先说寻路。 一. 使用A*...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,826
精华内容 1,130
关键字:

网格寻路