作者：陆泽西-《Unity3D高级编程：主程手记》
第七章-AI
7.1状态机
State基类-管理类->子类实现_>current指向当前状态。
基本的周期函数：Enter，Update，Leave。
但是不好处理复杂AI、无法处理突发状态。
7.2行为树
树状节点，自由灵活。
几种典型的Node类型：
- 复合节点Composite Node，条件检查
- 修饰节点Decorator Node，可以额外处理子节点的条件结果
- 条件节点Condition Node，大于小于、距离、与或非、True/Flase
- 行为节点Action Node，执行具体的行为，一般都是最后一层的子节点。
为了提供随机性，还有非线性迭代的加权随机变种、以及调试用的Log节点等。
使用行为树可以可以将AI配置化繁为简，让一个个节点组成一套完整的AI策略。
与之相似的是决策树，它也是树形结构。
“从理论上讲，决策树就是为了制定决策，而行为树是为了控制行为，它们是两个不同的理念。行为树更加注重变化，而决策树则更加注重选择。”
除此以外还有goap等AI方案。而对于更加复杂的AI需求，则需要考虑机器学习等方法。
7.3 非典型性AI
演算式AI
常见于页游、卡牌类游戏的自动对战，它根据一个随机种子算出正常战斗，然后将结果同步到客户端。
特点：结果确定\根据战斗进程，有时间轴的概念。
博弈式AI
比如棋类游戏的AI，这类AI的目标就是击败玩家。
特点：搜索下一步可能发生的情况，以及下几步可能发生的情况，选择最优解。
第八章-地图与寻路
8.1 A星
相较于其他搜索算法如Dijkstra和Floyd，A更加在时间和空间上的复杂度更低，前两者的时间和空间复杂度分别是O(N^2)、O(N^2)和O(N^3)和O(N^2)。而A的平均复杂度为O(N lgN)
基本思路：以2D四边形网格地图为例，寻找自身周边点内寻路代价最小的点（重点+当前位置；当前位置+重点）。将其作为当前点直至重点。
优化方案
在长距离导航的情况下，不加优化和剪枝的传统寻路算法会消耗大量计算。
优化思路有如下几个方面：
- 离线计算已经连同可行走的常用路径，寻路时只要计算起点到离线计算路径的起点，以及离线计算路径终点到终点即可。为了让离线计算更快，可以地图上设置一些距离较近的导航爹，先做导航点寻路再取出导航点之间的数据来拼接路径。
- 算法优化，对于open列表，每次从中寻找新的最低代价寻路点，都要排序或遍历一次，可以修改open列表为最小堆，这样根据最小堆的特性，在向open列表内插入和获取数据时，他就已经在最小的位置，无需排序和遍历。另外对于寻路期望值，也可以做一些优化。
- 权重引导，对于网格内的可寻路点，可以加上寻路权重，在计算最小代价点时，让权重也参与运算。
- 拆分区域，将地图分块，计算各个区域之间的路径。
- A*的变体，比如JPS，Theta，SubGoal等。
当然以上几种思路也可以搭配使用。
8.2寻路网格
数组构建网格
用一个二维数组表示寻路网格，0代表可寻走区域，1代表不可行走区域。如果地图太大而数组太小，则寻路精度不够。如果数组太大则性能有问题。
编辑/可视化：配表；工具；贴图
路点网格
地图由多个点组成（路点），路点与其他路点相连。然后寻路。
缺点是大范围设置可行走区域时，编辑较为麻烦，且无法识别碰撞。
平面三角形网格
平面多边形的三角剖分问题：多边形内剖分三角形。（寻路网格）
Delaunay三角剖分算法
最大-最小角优化准则：所有最小内角之和最大。
外接空圆：任意三角形外接圆内不包括其他节点。
- 除了端点，三角形的边不包括其他任何点
- 除了在点上的连接，没有任何一条边是相交的
- 所有的面都是三角形，且所有三角形的集合是所有点集合的凸包（所有点都是三角形的点，且所有三角形构成一个凸多边形）
Delaunay三角剖分算法有翻边算法，逐顶点插入算法，分割合并法，Bowyer-Watson算法等。
Bowyer-Watson算法：
1）构造一个超级三角形或多边形，把所有数据点都包围起来；2）依次逐个加入新的顶点，找到包含新顶点的所有外接圆对应的所有三角形；3）删除包含在所有外接圆中的边，这时新插入的点与删除边上的点相连构成一个凸多边形；4）将新插入的点与这个凸多边形的所有点相连，构成多个新的三角形；5）返回第二步，继续加入新的点，直到所有顶点增加完毕再结束。
切耳算法：三角形分割算法
概念：简单多边形；耳点；耳朵三角形；
多层级网格
2D网格+层级寻路。
2D寻路+Y轴射线获得位置坐标。
每个层级保存自己的寻路网格数据。
多应用于2D游戏中，或Dota、王者这类Moba游戏（有符号距离场）
3D场景体素寻路
三角网格中的A*寻路
如果路径点设置在三角形中心，则行走路径可能比较诡异。一种办法是取两个三角形邻边的中点作为穿越点。
但这样仍然可能存在许多折线的情况，解决办法是使用拐点算法（射线优化路径算法）。
- 从起始坐标点出发，连接下一个三角形入口边的两个顶点V1、V2产生两个向量line1、line2，再连接下一个三角形入口边的两个顶点V3、V4产生两个向量line3、line4。
- 通过计算这四个向量的叉乘，可以判定一个向量是在另一个向量的左边还是右边。还可以通过计算出V3、V4的值来判断line3和line4是否在line1、line2所形成的夹角内。
针对第二步的多种情况，有如下处理方式：
[图片缺失]
体素化寻路网格
基于体素，使用八叉树将空间分为八块，再将有障碍物的部分分割成更小的部分。
但仍然要区分对待寻路区域。因为地面没有高度，所以地面可以单独搞一套寻路。
NavMesh
寻路方案：Raycast。
体素化算法；区域划分算法；多边形轮廓构建算法；轮廓分割凸多边形算法；三角形剖分法
大体流程：
- 体素化，将空间分割成最小单位的三维方块，他们身上有行走标记
- 生成区域，要对不可行走区域进行过滤（障碍物，过高或过窄的地方），将剩下的地方集合起来进行体素区分，就是将相邻体素识别然后分割成不同区域
- 拆分区域为凸多边形，将划分好的区域构造成简单多边形
- 生成多边形网格，对多边形网格进行三角化，对凹凸不平的地方插入顶点
“RecastNavigation Navmesh最关键的部分是分区域，以及将区域拆分成多个凸多边形。因为拆分区域会加速寻路，所以使用A星算法寻路时只要关心区域与区域之间的路径即可，拆分凸多边形则让寻路变得更简单，因为凸多边形内的任意两点都是可以直达的，这使得当我们知道从起点到终点需要经过哪些区域时，就能根据这些区域得出路径，最终提高寻路的效率。”
8.3 地图编辑器
格式
json/自定义二进制byte流/protobuf
加载
一次性加载
异步、流式
动态加载
九宫格
当玩家行动时，只更新它周围八格的的玩家状态。
在实际游戏中，通过限制玩家的视野范围，搭配九宫格规则来做优化，将地图划分区域，当玩家向前前往下个区域，则它本身后边区域位置的资源将被释放掉，原本前方的区域成为此时玩家所在的区域，加载当前区域前方向位置区域的资源。
但仍然可以将地图划分的更细致，比如采用25宫格，49宫格等形式。同时也可以结合异步使用尽量减少卡顿。
场景制作和优化
定制地形
地编制作地形（一整个模型），搭配Mesh Collider。可以使用内置的地图编辑器，也可以使用建模软件。好处在于制作不受限制。
程序拼接地形，2D卷轴类游戏。对地图中所有的方块遍历，生成他们的顶点，索引，UV，然后将所有网格数据合并，形成单个的网格，这样只有一次drawCall（《白猫计划》）
在3D场景下，要先指定规范 ，固定每个地形块的大小。
优化
几个问题：
- 同屏面数太多，GPU压力大
- 渲染管线调用次数太多（drawcall太多），GPU的并行处理没有很好地发挥作用。
- 贴图大，压缩格式不合适，占内存多，导致显存的带宽负荷大。
- 动画太多，蒙皮在骨骼上的计算消耗的CPU多。
- 复杂的shader开销太大，GPU的计算量开销太大。
还有许多其他问题比如阴影导致的dc太多等。
- 面数问题，引擎层面会做视锥剔除，裁切算法中，只要包围盒有一个点进入相机视野范围，那么就不会剔除这个物体，如果一个物体太大而又符合上述情况就不会被裁切。所以要对场景内的过大物体进行拆分。另外也要注意相机的远裁面，防止过多物体进入相机视野。还有LOD、MipMap等方法。
- DC问题，合理合批
- 贴图太大，手机没有显存的概念，手机的显存都是内存，在PC上的流程是内存->显存->GPU。这会复制一份纹理到显存中。而在安卓和IOS架构下，CPU和GPU的纹理地址都指向同一个物理内存地址，但双份内存的情况在引擎内也会发生，即开启了Read/Write。这会导致运行时额外复制一份贴图到内存用以修改。对于模型贴图，尽量使用2的次幂大小。还要注意设置合理的压缩格式，比如有些不需要透明的贴图，则不用带透明通道。
- 动画，GPU Instancing、离线计算方式。
- shader，尽量不使用消耗性能的数学函数比如log、pow、三角函数等。尽量用相似方法代替，尽量少用if，除法可以改成乘法（倒数）等。