NAV导航网格寻路.doc

NAV导航网格寻路介绍WayPoint寻路下图是一个典型的路点寻路另一种方法是使用多边形来记录路径信息，它可以提供更多的信息给ai角色使用。下图就是一个navigation mesh。以下列出几个WayPoint的不足之处：1. 一些复杂的游戏地图需要的WayPoint数量过于庞大2. 有时会使角色走“Z”型路径如下图A点和B点之间的路径NAV寻路如下图下图是路点寻路，如黄线，会产生“Z”字形下图为文章开始时展示的地图的比较，红线是wayPoint寻路，兰线是nav。3. 不能进行动态修正，如果地图中有动态障碍，处理起来会很困难 如要实现即时战略游戏中，一辆在路上行走的坦克会挡住你军队的去路，这个移动的坦克就是一个动态障碍。4. 不能根据角色的特性（不同宽度、高度等）改变路径如一个狭窄的通道，普通的人能够通过，而一辆马车的宽度超过通道宽度，应该不能通过。5. 不能保存地形的附加信息，如地表高度、地面特征（水面、沙地等） 比如一个游戏中的角色在走到沙地上时会降低移动速度，或走在一个斜坡上时人物会发生倾斜等。寻路方法nav寻路一般包含两部分，首先是使用工具根据地图信息生成寻路用的nav mesh，接下来就是在游戏中根据生成的nav mesh来自动寻路。一般人首先关心的就是寻路方法，所以这里把顺序颠倒下，先说寻路。一. 使用A*寻找所经过网格路径下图为一个已经生成nav网格的地图，深红色区域为不可行走区域，浅红色区域为可以行走的区域。如下图，现在如果要寻找从A点到B点的路径，首先要从所有可行走的网格中找到一条最优的网格路径（图中紫色的网格），然后再根据这些网格生成所需要的路径点。计算最优网格路径的方法可以使用流行的A*，也可以使用其它方法。A*算法网上很多就不说了，至于三角网格的A*实现因为涉及网格的数据结构会在系列的最后给出。二. 生成路径点nav寻路最常用的就是光照射线法了，这个在neoragex2002的blog上有讲，这里就不说了/neoragex2002/archive/2007/09/09/887556.html另一种方法就是拐角点法，如下图下图的5个凸多边形是已经生成的导航网格，多边形外部的区域为不可行走区域，current为起点，goal为终点，从图中就可以看出最短路径为图中红线，蓝色圈出的点为我们需要找出的点。所有多边形顶点均按逆时针方向存储（这些均在生成导航网格时处理，以后会讲到）。（1）下图显示出各区域之间的入口，即多边形的临边。由图中可以看出每个临边均为起点穿出该多边形区域的边，故以下称该边为穿出边。（2）首先找到起始点所在的多边形和穿出边的两个端点，由起点连接两个端点，形成两个线段lineLeft 和lineRight。如下图。绿色圈表示左点，红色表示右点（左点、右点是根据多边形顶点保存顺序而来）。（3）继续找到下一个穿出边的两个端点，判断新的左点是否在lineLeft 和lineRigh之间，如果在，则更新lineLeft为起点到新左点的线段。同样处理新穿出边的右点，如下图该步最后得到两个新的线段，如下图。（4） 继续判断下一个穿出边的两个端点，如下图，新的左点在lineLeft和lineRight的外面，则不更新线段。下图说明新的右点在两条直线之间，更新lineRight。该步最后得到两个新的线段，如下图。（5） 继续循环判断下一个穿出边的两个端点，该穿出边的两个端点都在lineRight的右侧，表示lineRight的终点即为路径的一个拐角点。（6） 循环以上步骤都可以找到从起点到终点的一条完整路径。一些必要的计算几何知识在继续下面的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 ) = 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多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针主多边形和裁剪多边形把二维平面分成两部分。内裁剪：AB外裁剪：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网格假设上图是一个游戏地图，红色的区域是不可行走的区域，浅灰色区域是可行走区域，要想在游戏中实现nav寻路，必须将可行走区域转化为nav网格并保存为一种固定形式的数据，如下图浅红色的三角形。nav网格必须是凸多边形，这里使用三角型，当然也可以使用4边形。下面介绍一种任意多边形的三角化算法。算法来自论文平面多边形域的快速约束 三角化作者：曾薇 孟祥旭 杨承磊 杨义军。详细内容请参考该论文。先来看几个定义：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中竟然没有代码的格式）二维点的定义public class Vector2f 包括矢量加减、叉积等方法。线的定义public class Line2D 包括下面方法：classifyPoint(point:Vector2f, epsilon:Number = 0.000001):int 判断点与直线的关系，假设你站在a点朝向b点， 则输入点与直线的关系分为：Left, Right or Centered on the lineequals(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, y3length():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： publicvertexV: Vector. /顶点列表，按顺时针方向排序cw():void 将多边形的顶点按逆时针排序 isCW():Boolean 将多边形的顶点按顺时针排序isSimplicity():Boolean 是否是简单多边形rectangle():Rectangle 返回矩形包围盒 Polygonunion(polygon:Polygon):Vector. 合并两个多边形(Weiler-Athenton算法)三角化的完整代码，注释比较全，就不再详细解释了/* 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.; /所有多边形，第0个元素为区域外边界 (输入数据) private var vertexV:Vector.; /所有顶点列表, 前outEdgeVecNmu个为外边界顶点 private var edgeV:Vector.; /所有约束边 private var outEdgeVecNmu:int; /区域外边界顶点数 private var lineV:Vector.; /线段堆栈 private var triangleV:Vector.; /生成的Delaunay三角形 public function createDelaunay(polyV:Vector.):Vector. /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) -1) lineV.splice(index, 1); else lineV.push(line13); if (indexOfVector(line32, this.edgeV) -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.):void /填充顶点和线列表 vertexV = new Vector.(); edgeV = new Vector.(); var poly:Polygon; for (var i:int=0; ipolyV.length; i+) poly = polyVi; putVertex(vertexV, poly.vertexV); putEdge(edgeV, poly.vertexV); outEdgeVecNmu = polyV0.vertexNmu; lineV = new Vector.(); triangleV = new Vector.(); /* * 获取初始外边界 * return */ private function getInitOutEdge():Line2D var initEdge:Line2D = edgeV0; /检查是否有顶点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 = edgeVloopIdx; break; while (loopSign & loopIdxoutEdgeVecNmu-1); /只取外边界 return initEdge; /* * 将srcV中的点放入dstV * param dstV * param srcV */ private function putVertex(dstV:Vector., srcV:Vector.):void for each (var item:Vector2f in srcV) dstV.push(item); /* * 根据srcV中的点生成多边形线段，并放入dstV * param dstV * param srcV */ private function putEdge(dstV:Vector., srcV:Vector.):void if (srcV.length 3) return; /不是一个多边形 var p1:Vector2f = srcV0; var p2:Vector2f; for (var i:int=1; isrcV.length; i+) p2 = srcVi; dstV.push(new Line2D(p1, p2); p1 = p2; p2 = srcV0; dstV.push(new Line2D(p1, p2); /* * 判断线段是否是约束边 * param line * return 线段的索引，如果没有找到，返回-1 */ private function indexOfVector(line:Line2D, vector:Vector.):int var lt:Line2D; for (var i:int=0; ivector.length; i+) lt = vectori; 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. = new Vector.(); / 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 = allVPoint0; 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 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 -