上周讲了A* 的基本原理, 不知道有人能看懂不? 其实原理并不是非常复杂, 但实现起来的方案倒是有不少, 就像所有算法一样, 一般来说, 实现都比原理难得多.不过篇幅有限, 这里就不谈实现了, 只谈原理.
寻路算法介绍完了之后, 就来讲讲如何生成数据, 就和人的双腿一样, 数据就是寻路模块的另一条腿.
这里我尽量简单的 用我自己的表达方式来描述, 由于过程很多, 我也没有能非常好的理解, 所以有遗漏还请大家补充.
我们的网格生成主要是用了这个方法Navmesh, 原理介绍我主要参考了这个网站, 有兴趣的同学也可以了解一下: http://www.critterai.org/nmgen_study
navmesh的生成主要有这么几步:
- Voxelization – Create a solid heightfield from the source geometry.
- Generate Regions – Detect the top surface area of the solid heightfield and divide it up into regions of contiguous spans.
- Generate Contours – Detect the contours of the regions and form them into simple polygons.
- Generate Polygon Mesh – Sub-divide the contours into convex polygons.
- Generate Detailed Mesh – Triangulate the polygon mesh and add height detail.
体素化Voxelization
这一步是向量空间(vector space) 到 体素空间(voxel space) 的转换. 用到的是叫保守体素化(Conservative voxelization) 的算法, 它保证了每个多边形面都能完全被生成的三维象素(voxel)包裹, 如下图:

体素化后, 生成的都是可寻路的高度场(heightfield)信息, 不可寻路部分被剔除.这一步是从一个固态高度场(solid heightfield) 生成一个开放高度场(open heightfield) 的过程, 一个开放高度场表示在一个固态空间上可能寻路的平面.
这个概念有点抽象, 请往下看…
区域生成Region Generation
这一步的目标是进一步的定义,那部分的面是可以寻路的, 并且把寻路区域分隔成连续的平面以供最后生成简单寻路多边形.
最终结果如下图, 墙体,围栏, 柱子, 桌子底等不可能寻路的平面在这步根据邻居信息和分水岭算法(the watershed algorithm) 被剔除, 一些孤立的小局域(比如桌子表面) 也被剔除.

留意楼梯, 虽然是多级, 个平面并没有连通, 但是也会被当做一个平面(绿色). 楼梯扶手等平面也被剔除.
轮廓生成Contour Generation
这一步将完成从体素空间回归到向量空间的转换. 区域(region) 的轮廓将被"遍历(walk)", 形成简单的多边形.
其中, 有些区域被合并, 多边形的边更平滑, 边长度被优化. 
这一步结束后, 可寻路区域已经被一些简化的多边形所表示
凸多边形生成Convex Polygon Generation
凸多边形生成算法很多,这里就不多介绍, 这里主要是使用了把多边形切分为三角形, 然后尽量合并的方式做, 结果如下图:

精细网格生成Detailed Mesh Generation
这是navmesh的最后一步, 凸多边形通过"德劳内三角化"(Delaunay triangulation) 算法三角化成包含高度信息的三角形(注意楼梯)

顶点信息也会在这里补到各个三角形上, 以保证高度信息和模型保持一致.
至此, 寻路的数据生成完毕, 可以用于简单寻路系统. 各部分数据都有可能被寻路算法使用, 有多种方法去获取到数据以用于决定寻路的各个步骤.
其实上面的每一步都可以展开很多, 整个navmesh的生成非常复杂, 而且用到了许多算法, 完全可以写几篇论文以介绍, 这里就不展开了(我也没这实力),
有兴趣深入的同学可以参考下面的几个网站, 里面都非常专业的提供了实现方面的介绍(包括实现):
http://digestingduck.blogspot.com/2010/05/constrained-movement-along-navmesh-pt-2.html

还可以说什么
周末看到一个新闻:”女童两次遭车压 十余路人漠视”
可能是心理上的应激反应, 我没有点开视频看. 对生命的漠视, 已经不能算是新闻, 已经忘记了听到过多少次世人的冷漠, 人也慢慢的开始麻木
而在终于点开视频, 看完后, 我依然还是忍不住想问: 这个社会究竟怎么了??!!
女童被碾压的过程我始终没有能看完, 不敢… 不忍… 没有勇气
有时候, 我们看着网上的视频, 已经练就一身好本事, 没有任何代入感, 感觉就像在看电影, 好像一切都离自己很遥远, 自己总会是幸运的一个, 厄运永远不会发生在自己身上…
我不认同.
让我想起美国波士顿犹太人屠杀纪念碑上所铭刻的马丁·尼莫拉的话:
在德国,起初他们追杀共产主义者,我没有说话——因为我不是共产主义者;接着他们追杀犹太人,我没有说话——因为我不是犹太人;后来他们追杀工会成员,我没有说话——因为我不是工会成员;此后他们追杀天主教徒,我没有说话,因为我是新教教徒;最后他们奔我而来。却再也没有人站出来为我说话了。
看了视频, 我有很强烈的代入感. 身为人父后, 多了一份责任. 而经历过几次生离死别后, 我更加珍惜生命, 更懂得活着的可贵. 看到这种对生命的漠视, 而且是如此幼小的一个生命…而且冷血的人还不只一个! 还看到一位带着小朋友的母亲….
语塞, 不知道还可以说什么…
下面是网上的视频片段, 没看的请补:
珍惜生命, 善待身边的人, 纵使素未谋面, 但是, 那是一个生命啊! 希望尚存良知的人会越来越多, 而不是慢慢灭绝….
也希望小朋友能够坚强, 我依旧相信着奇迹… UPDATE: 可怜的小悦悦已经被诊断为”脑死亡”…. 哀…