A星算法其实并不是最短路径算法，它找到的路径并不是最短的，它的目标是能以最快的速度找到通往目的地的路，算法的时间平均复杂度为O(NLogN)，最差的情况是从起点出发把所有的格子都走了一遍，最后才找到目的地。
用一句话概括A星：用最贪婪的方法最快的寻找到通往目的地的路径。
它是如何用贪婪法的呢，我们拿方格来描述A星算法，这样描述很容易理解。
[][][][][]
[][][][][]
[][s][][][]
[][][][][]
[][][][][e]上图为5X5的方格，其中s为start起点(3,2)，e为end终点(5,5)。
用最贪婪的方法去找目的地：先将四周的点加入到列表中，在列表中找到与目的地e距离最短的那个，就是离目的地e最接近的，把这个点推出来继续用这个点向前探索，直到找到目的地。
简单来说从s点开始取出它周围的4个点，上，下，左，右，计算下它们与终点e的距离，哪个离e的距离最短，就推出那个点并取它周围4个元素继续进行同样的操作，直到找到目的地e。
[-][-][-][-][-]
[-][1][2][3][-]
[1][s][1][2][3]
[-][1][2][3][4]
[-][-][-][4][e]如上图中，s开始取到周围的4个点标记为1，计算距离，并推入到一个队列，把这个队列按到e点距离值从小到大排序一下，取出离e点距离最短的点，再从该元素周围取出4个元素标记为2，推入到队列，并对它们计算与e的最短距离，再排序一下，取出离e点距离最近的那个标记为3，依次重复这种操作，直到找到e目的地。所有被标记过的都不能再被重复标记。
我们来看看稍微复杂点的A星寻路例子：
[-][-][-][-][-]
[s][+][+][-][-]
[-][+][e][-][-]
[-][+][-][-][-]
[-][-][-][-][-]从s出发到e，图中‘+’为障碍物，用贪婪的A星寻路会怎么找到e呢，如下图：
[1][-][-][-][-]
[s][+][+][-][10]
[1][+][e][10][9]
[2][+][+][+][8]
[3][4][5][6][7]-
先取s周围的点标记1
-
取标记里最近的且没被取过的点，即下面这个1点，取它周围点标记为2
-
取标记里最近的且没被取过的点，即点3也可以是上面的1，但我们定个规则一样的距离以下面为标准，取它周围的点标记为点4
-
离e点最近的还是4，继续取它周围的标记为5
-
离e点最近的还是5，继续取周围点标记为6
-
离e点最近的还是6，取它周围的点标记为7
-
离e点最近的还是7，取它最近的点标记为8
-
离e点最近的是8，取它周围的点标记为9
-
离e点最近的是9，取它周围的点标记为10
-
离e点最近的为左边的10，取它周围的点时发现到达目的地e，结束。
当我们面对场景地图很大的时候，或者使用A星算法的寻路频率很高的时候，普通的A星算法就会消耗大量的CPU，设备的性能就会急剧下降，这样看来普通的A星性能依然无法过关，我们需要改进它让它变得更高效。
当我们需要寻路的两点距离很大，中间有很多障碍物时，A星的算法就会遇到瓶颈。我们前面展示了A星算法的伪代码来描述算法的步骤，我们从代码中可知open队列排序瓶颈，它会不断加入的可行走点使得排序速度越来越慢，这是最终导致CPU计算量过大画面无法动弹的主要原因。
也就是说，当两点的距离很长时，open队列有可能被塞入了太多的节点而导致排序变慢，而open队列不断被塞入节点和排序是不可避免的，那么当寻路距离太大时我们该怎么办？
我们可以把路径寻路的计算量大部分转化为离线下计算，其实很多时候我们可以把中间很长一段距离的计算过程放到脱机工具中去计算。路径不是非得实时计算出来才好，我们可以把一些常用的路径，在离线下算好放在数据文件中，当游戏开启时将已经计算完毕的常用点对点路径放在内存里，当角色需要寻路到某个节点时，我们可以从已经计算好的点对点数据中寻找起始点和目的地离我们最近的数据，如果我们要寻路的起点和终点这两个节点恰好是在我们计算好的数据附近，就可以将这段路径取出来直接使用，再拼上两点到真正起点和终点的实时寻路计算路径就成了一个完整的从起点到目的地的路径。这样我们节省了中间很长一段路径的计算量不再需要重新计算一遍，留给我们需要计算的仅仅是起点到伪起点和伪终点到终点的实时路径部分。
我们来举例说明这种情况的过程，假如地图中 A点 到 B点 的路径，我们已经算好并存放在了内存里，当我们在A点附近的C点要寻路到B点附近的D点时，即C到D，中间有A到B的相似路径。我们从内存中得知C点的附近有A，并且D点的附近有B，A和B是的路径已经计算完毕，那么我们就可以先计算从C点寻路到A点的路径，再调出A到B的路径直接拼在后面，再计算B点到目的D点的路径将它们拼在路径在后面就有了C到D的完整了路径。以这种方式来规避一些计算量比较大寻路计算量的消耗，这种方式在大型世界的RPG游戏里特别常用，我们通常称它们为导航点，只要角色到了这个导航点就能直接取出路径直达目的地，而不再需要大量的寻路计算消耗。
我们说实时计算中的寻路道路不能太长，太长的道路计算就会耗尽CPU让画面阻塞，离线计算的导航点也是一样，即使是离线计算也不能一口气把最南端的地图到最北端的地图的寻路路径计算完毕，这样的计算效率太差，因为路径越长情况越多，加入open列表的节点成指数级增长。
因此我们也需在长路径上设置众多导航点以便加快离线计算，有了众多导航点就能在长路径寻路前先做导航点寻路，再取出各路径上导航点之间的数据形成长距离路径，比如大地图上有5座城市里，每座城市都有4个出口点，这个4个出口点就可以做成离线的导航点，每座城市之间的导航点都做了离线的寻路计算并存储了路径在数据文件上，我们在寻路时可以先寻找到最近的一个导航点，再从最近的一个导航出发寻找到目的地附近导航点的导航路径，我们可能找到，导航点 a -> c -> e 的导航点路径，直接取出 a -> c 和 c -> e 的路径，再拼凑上实时计算的角色到 a导航点的路径以及 e导航点到目的地的路径，就完成了一条完整的长距离路径链。
前面我们多次提到open队列的问题，它在A星寻路中起到关键作用，由于每次插入open队列的点后，open就不再是有序的队列了，所以每次去拿最小值时都需要重新排序。排序的时间消耗随着队列长度的增大而增大，我们的A星大一部分消耗都在open队列排序上，所以对open排序做优化是比较重要的。
是不是可以不排序，其实可以不排序只查找并插入，先使用查找算法找到应该插入的位置再插入元素，可以让队列在不用排序的状态下做到有序。
通常我们使用最小堆的数据结构来做插入操作，由于每次只需知道最小预期值的节点，因此最小堆数据结构非常适合A星寻路的open排序。我们前面介绍过堆排序以及最大最小堆的基础知识，这里稍微简单阐述一下，最小堆的数据结构是完美二叉树结构，每个父节点都比子节点小，因此根节点肯定是最小的那个元素，每次插入或删除时都会重新寻找最小预期值的那个节点放在根结点上。它的插入和删除算法的时间复杂度为O(logN)，整体插入操作的复杂度为 O(logN + N)。
除了最小堆排序外我们也可以用二分查找代替最小堆，因为open队列在插入元素前一定是有序的，因此我们可以先用二分查找算法来找到插入的位置。每次插入时都使用二分查找算法查找插入点，再将元素插入进队列，那么每次的插入复杂度为O(logN + N)。无论最小堆或二分查找都比快排一次的时间复杂度O(NlogN)要好很多。
前面讲解A星算法时所举的例子中节点的期望值都是以当前点与终点e之间的距离来作为期望值，期望值越小越接近终点，这种方法简单但也不科学，这导致A星在障碍物比较多的复杂地图中寻找路径时会要绕比较大的弯路，也导致了在寻路过程中open队列中加入了比预期更多的节点使得open队列的排序变慢。
我们需要优化一下这个计算期望值的策略，我们选用一个更科学的方法
F 期望值= G 当前最近步数 + H 预测当前点到终点的步数
F 为我们需要计算期望值，G为起点s到当前点p的最少步数，H为当前点p到终点e的最短距离，将这两个值加起来就是 F 期望值。其中 G 是已经计算好并放入节点p中的值，因为q是被open队列推出来的，所以它的最少步数肯定是计算完毕的，该值就是我们在前面计算过程中起点s到当前点的最少步数。我们可以把每步计算好的步数都放入节点中，以待需要计算时使用。
function find_path(s,e)
{
open = new MinHeap(); //最小堆
close = new List(); //已经被取过的点
open.add(s); //从s点开始
close.add(s); //将s加入到close队列
for(!open.IsEmpty()) //重复遍历直到没有点可以取
{
p = open.pop(); //把最近的点推出来
if(p == e)
{
//找到终点
break;
}
p1 = p.left(); //取左边的点
p2 = p.right(); //取右边的点
p3 = p.top(); //取上边的点
p4 = p.down(); //取下边的点
plist.add(p1);
plist.add(p2);
plist.add(p3);
plist.add(p4);
for(int i = 0 ; i<plist.Count ; ++i)
{
pp = plist[i];
if( pp.IsNotInClose() && p.g + 1 + dis(pp,e) < pp.f)
{
pp.g = p.g + 1;
pp.f = pp.g + dis(pp,e);
if(pp.IsNotInOpen())
{
pp.SetOpen();//设置为已经在open中
open.Add(pp);//加入最小堆
}
else
{
open.Update(pp);//更新最小堆中的节点
}
}
}
//p点已经被取过了
close.add(p);
}
}上述代码与之前的相比我们又加入了新的期望值的计算方式，对于期望值有更新的节点在堆中进行更新。新的期望值计算方式的改变相当于原来我们只关注点到终点的距离大小，现在变为关注起点s经过当前点p路径再到终点e的总距离，虽然仍然是贪婪的简单预测算法，但比起原来只关注当前点p与终点e的距离更加科学化，这能让我们更快的找到更好更近的点位去接近终点。
我们改善了期望值的计算方式就能更快的接近终点是件很神奇的事，那么究竟改善期望值算法有怎样的意义呢？其实期望值的计算方法代表了在寻路过程中的我们探索的规则，如果我们的计算公式只关注于离终点距离最近的点位，那么在寻路过程中的选择点位的顺序就会偏向于与终点更近的点，无论能不能最终到达终点，只要它越靠近终点就行，但通常地图中很多点位很靠近终点但却无法达到终点。而如果期望值计算公式关注的是从起点到终点整段距离最小的点位上，那么在寻路过程中在选择点位上时也就会偏向整条路径最短的方向上去靠，这也间接加快了寻路的速度，即找到最快到达终点的点位。
通常游戏中对A星寻路算法使用的频次比较高，这使得在多次频繁寻路中对A星算法中每个运算，每行代码的运算细节都会有比较重大的考验。
比如我们在查看一个节点是否为被取过的节点，即是否为Close时，很多人都会在Close队列中寻找该节点是否存在，这个操作明显就没有考虑到性能的消耗，要在Close列表中找节点，就相当于遍历一遍所有已经找过的节点，Close里的节点越多越浪费CPU，而且是不只一次浪费每个循环都会浪费一次，性能消耗巨大。因此我们通常的做法是把节点作为一个实例，在实例中添加IsClose的变量，来判断是否被取过，或者说是否Close。但这种方法还是不够好，IsClose变量在寻路前是需要被初始化的，因为我们必须在每次寻路都要将前面寻路过的痕迹抹去才能开始全新的寻路过程。这就是又一个被很多人忽视的初始化的性能消耗，每次在A星寻路开始前必须将IsClose的变量初始化为false，就需要我们遍历整个数据结构来初始化每个实例中的变量。
倘若我们在每次寻路前都要遍历整个数据结构的话，在短路径的寻路上A星的优势就荡然无存了，因为在初始化部分的性能消耗就已经将A星节省下来的性能消耗完全覆盖掉了。可以这么说如果初始化的需要遍历整个数据结构，那么优化A星算法的意义就会减少很多，因此我们需要用更好的方式来判断IsClose功能，最好是无需初始化的。
我们可以改变一下判断方式，在寻路类中设置一个属性变量或者专门为寻路服务的静态变量也可以，暂名为FindIndex，让每个寻路节点中也存有一个变量FindIndex，每次调用寻路方法时先对FindIndex做加1操作，这样全局的FindIndex肯定比节点实例中的FindIndex要大。在判断IsClose时，当节点中的FindIndex与寻路类中FindIndex相等时则说明已经被当次寻路算法取出过，而如果它们两者不一样则说明这个节点没有被取出过。当节点被取出时，节点里的FindIndex应该设置为当前寻路类中的全局FindIndex值，以表明该节点已经被这次寻路算法计算过。
用整数比较方式来代替布尔型变量的初始化，省去了巨量的初始化操作。不只是IsClose部分，其他需要判断初始化布尔型的逻辑都可以用此方法来避免初始化的开销。
在A星算法这种经常用的算法中，一个小小的性能消耗就能放大很多倍，因此我们需要特别注意调用的函数的复杂度，公式的复杂度，以及运算的优化，尽量做到能不调用函数的不调用函数，能简化公式的尽量简化公式，能用&|<>位运算符号代替加减乘除的尽量用位运算代替，以节省A星算法的性能开销。
最简单的也是最易于理解的网格构建方式要属二维数组网格，它是一个二维数组，每个元素就代表一个可行走位置，我们可以假设元素中数字0代表无障碍，1代表有障碍，或者也可以用数字代表障碍阻碍难度，比1大的数字代表更高的障碍难度，数字越大障碍难度越大，到达某个数字比如999则认为该障碍难度无法跨越。
举个二维网格的例子：
[0][0][0][0][0][0]
[1][1][0][0][1][1]
[1][1][0][1][1][1]
[0][1][0][0][1][1]
[0][0][0][1][1][1]
这是一个 5 * 6 的二维数组，0代表无障碍，1代表有障碍。我们能从中很清晰的看到这张地图中有哪些是障碍点，张地图点都是连同的我们从任意一个可行走点出发都能到达任意终点，我们可以想象寻路时一步步按照方格的方式去行走。
用二维数组代表地图相对比较抽象，它需要与地图的尺寸相匹配，怎么与地图真正的关联起来呢？我们在脑海中需要把一整块地图也切成 5 * 6 这样30块地，比如这个张地图总共大小为 50米 * 60米 的大小，假如左下角为[0,0]位置，我们从0，0点开始，从10，10点到0，0点为一个方块与[0,0]这个点关联，从坐标10，10到坐标20，20为另一个方块与[1,1]这个点关联，从0，10点开始，10，20点到0，10点的方块与[0,1]这个点关联，依次类推。
在地图上每个10 * 10大小的一块正方形的区域都与数组关联，这样我们在用A星寻路中以及寻路后的结果都可以对应到地图上的坐标。
比如，我们寻路到从[0,0]点开始，到[1,4]点的路径为，[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]，反应到地图上时，是0，0点开始移动，先移动到第一个方块也就是(0,0)到(10,10)这个方块的中点，也就是坐标(5,5)的点位上，再移动到(10,0)与(20，10)这个方块区域的中点上，即(15,5)坐标点位上，再移动到(20,0)与(30,10)这个方块区域的中点上，即(25,5)坐标点位上，依次类推，直到移动到最后一个点位，即(10,40)与(20,50)这个方块区域的中点上，即(15,45)这个坐标上，到达终点。
因此A星寻路结束后，给出了[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]，即数组上的坐标路径，在实际地图中则移动的路径为(5,5)->(15,5)->(25,5)->(25,15)->(25,25)->(25,35)->(25,45)->(15,45)的坐标点位顺序。
相当于把整个地图想象成一个矩形，把矩形横切N刀，竖切N刀，成了一个与二维数组匹配的方块地图，每个方块与数组中的一个元素相关联，当我们使用A星算法从数组中算出一个具体的路径时，可以根据这个数组中的路径，来匹配地图上的点位，即方块的中点。
在数组与地图的匹配中，如果这个地图很大，但数组的大小很小，就无法实现细腻的路径与障碍，所以我们需要在内存占用量与地图寻路细节之间权衡。多大的数组与当前的地图才能匹配的更好呢，我们的数组不能过大因为过大的数组会造成内存的浪费，又不能过小因为过小的数组使得地图的障碍细节无法得到完美的体现。所以我们在决定数组多少的时候，需要考虑的是整个地图的大小，以及最小障碍物为多大，来决策究竟需要用多大的数组。
可视化地图编辑界面
这些切割与关联都是由我们的脑袋抽象出来的，毕竟我们在做游戏项目的时候，抽象的东西如果无法可视化的话，就会变得难以灵活运用，至少是难以灵活的编辑和扩展，于是可视化编辑也是一个比较重要的节点。
我们可以用最简单的方法Excel方式，建立一个Excel，在Excel表中填入一个与数组相等大小的矩形方格块，在方格内填入颜色或数字，绿色代表可行方块，红色代表不可行方块。这样在Excel内就可以设置地图的元素以及障碍物，可行走与不可行走区域一眼就能知道。那些标记为红色的方格是障碍物，那里是不可通行的，那些标记绿色的地方为空地，那地方是可通行的，整个地图下来哪些地方不可通行，哪些地方可通行一目了然。最后我们把这个Excel里的数据导出到文件，再在游戏中读取文件中的数据，就能得到我们需要的地图二维数组的可行走与不可行走的地图数据。
除了Excel，我们还可以使用UnityEditor提供的编辑器API编写的地图编辑窗口，把地图大小，方格大小，障碍物等以可视化的形式放在 UnityEditor UI编辑窗口中，并附上保存数据到文件和从文件读取地图数据的功能，这样的地图编辑窗口就能更形象的体现地图的元素。
如果这种可视化还不够，就在具体的3D场景中的地图上做些编辑功能，先要把整个地图加载并渲染在画面上，然后在地图上用颜色方块的方式画出不同颜色的块状，用具体地图为背景来编辑地图障碍和可行走区域。当然这也带来更加多的代码的编写和维护工作，但也同时是非常值得的可视化网格编辑器，为设计师提供了更加良好的编辑工具，这对游戏的创新设计会有更好的支持作用。
除了以上形式的地图编辑工具，也可以用类似地形贴图的形式来做为可行走点的依据，就像地形高度图那样，我们也可以用一张图来存储障碍数据。用一整张1024 * 1024图代表一整个地形的大小，或者也可以为 2048 * 256等按不同需求规格的大小，每个像素点代表二维数组的一个元素，(255,255,255)白色代表可行走区域，(0,0,0)黑色为不可行走区域，那么这张图就可以压缩成只有RGB通道的8比特的图，也加入更多元素，泥潭，沼泽等等分别用其他颜色代表，这样就可以用图片代替了Excel的数据，Unity3D自带的地形就是这么做的，它的地形图中包括了一张高度图和地图元素图，贴图中每个颜色像素都代表一种植被。当需要加载二维数组作为可行走数据时，则加载该图片读取像素中的每个元素录入到内存中，然后就可以依据内存中的二维数组来判定是否是可行走区域，以及相邻的格子是否是障碍物的判断。
由于一维数组在分配内存块时的紧凑度往往比二维数组要来的好，用一维数组来读取索引中的数值会更加的快，因此我们常常使用一维数组来代替二维数组，在调用索引时也只是多了一个简单的乘法和加法的操作，即 二维数组 [a, b] 等于 一维数组 [a * width + b]，这样一来只是整个内存访问都是连续的而不再需要内存地址的跳转，这有利于提高指令缓存命中率，加速了指令运算。
用二维数组的方式来构建寻路的基础数据有一定的局限性。当场景特别大，我们就要存储特别大的一个数组，编辑可行走区域的工作量也有所提高。假设我们的地图场景有 2048 * 2048 个数组这么大甚至更大，我们在制作可行走区域时就要把所有的障碍点都细致的设置一遍这样的工作量比较大。除了数组太大和需要编辑的工作量扩大外，二维数组下的寻路路径最多是8方向的，上，下，左，右，左上，左下，右上，右下，寻路后的行走时也会感觉比较不真实，感觉是直来直去行走方向，要么90度方向行走，要么180度方向行走，要么45度方向行走，没有其他角度的行走姿势，让人感觉不真实，在像素游戏上还感觉不出什么来，但在3D地形中则会感觉明显的怪异。
路点系统就弥补了一些二维数组形式的缺点。路点系统是一个易于理解的系统，它由很多个点构成，这些点我们称它们为路点，即路上的点。我们将路点放入地图中，并为每个路点标记ID，以及与哪些路点相连的数据。我们在地图中放入了很多个路点，并且为这些路点配置了连线
地图中每个路点都会有与其他某些路点相连接的线，我们可以称它们为路线，由路点与路点之间连线而成。如果把地图里的路点和路线铺设的更加复杂一点时，所有的点和线都拼成了一张网
这张网中，只要我们得到某个点，就能根据这些路点和路线，用A星的算法来寻路到目的地。图中当起点为A，与起点最近的路点寻路到与终点最近的路点的一条路径。
路点系统相对容易理解，因为它本身就是点与点之间的连路，我们在制作时也需要一些可视化的编辑器的支撑，因为所有的路点都需要在既有的地图上编辑，所以编写一个专门的地图编辑器也是必不可少的，没有地图编辑器至少也需要路点编辑器，可用来保存路点数据到具体的数据文件、从文件加载路点数据，以及增加路点，减少路点，添加和减少路点连接信息等功能。
路点系统相对简单，它的缺点也是比较严重的。当我们大范围设置可行走区域时它任然需要大量的工作来编辑可寻路的路点信息与连线。它的寻路方式也无法识别碰撞而只能用路点的形式来绕过障碍。当在大块空地上做寻路时，需要在这个大块空地上添加比较多的路点，才能平滑的适应各种寻路路径。
路点系统直观、门槛低、上手简单，一般情况下路点的数量相对比其他方式的网格少很多，因此内存消耗和CPU消耗都比较少。但它的缺点也比较大，行走路线的平滑程度依赖于添加的点的密度与形状，更糟糕的是它无法识别障碍区域，行走的路线也依赖路点之间的连线。三角形网格形式的寻路网格就很好的解决了路点系统的缺陷，它用算法自动生成的网格，无需手动编辑就能避开障碍区域。
那么三角形寻路网格是怎么生成的呢，这个问题在计算机图形学里叫做 “平面多边形的三角剖分问题”，意思是说我们在一张平面图上有很多的颜色，这些颜色就形成了很多的点，根据这些点将这幅图分解为由许多三角形组成的多边形。
平面多边形的三角形剖分问题是计算几何研究的一个基本问题，它广泛应用于模式识别、图像处理、计算机图形学以及机器人领域。一方面，三角形作为最简单的平面图形，较其他平面图形在计算机表示、分析及处理时方便得多。另一方面，三角剖分是研究其他许多问题的前提。
Delaunay三角剖分算法是一种三角剖分的标准，它是由前苏联数学家Delaunay提出来的：“对于任意给定的平面点集，只存在着唯一的一种三角剖分方法，满足所谓的“最大-最小角”优化准则，即所有最小内角之和最大。”这种剖分方法遵循“最小角最大”和“空外接圆”准则，“最小角最大”准则是在不出现奇异性的情况下，Delaunay三角剖分最小角之和均大于任何非Delaunay剖分所形成三角形最小角之和，三角形的最小内角之和最大，从而使得划分的三角形不会出现某个内角过小的情况，比较有利于有限的后续计算。“空外接圆”准则是Delaunay三角剖分中任意三角形的外接圆内不包括其他结点。因此在各种二维三角剖分中，只有Delaunay三角剖分才同时满足全局和局部最优。
Delaunay三角剖分算法由好几种，但都遵循Delaunay三角剖分特点，即其剖分后的多边形里的三角形必须满足：
1.除了端点，三角形的边不包含其他任何点。
2.除了在点上的连接，没有任何一条边是相交的。
3.所有的面都是三角形，且所有三角形的合集是所有点集合的凸包。
第一、二点要求三角形的边上没有任何其他的点和相交的线，第三个说的是所有的点都是三角形的点并且最后所有三角形所形成后是个凸多边形。
Delaunay三角剖分算法有翻边算法、逐点插入算法、分割合并算法、Bowyer-Watson算法，它们都只适用于凸多边形的三角剖分。这里我们仅对Bowyer-Watson算法进行讲解。Bowyer-Watson算法的基本步骤是：
1.构造一个超级三角形或多边形，把所有数据点都包围起来。
2.依次逐个加入新的顶点，找到包含新顶点的所有外接圆对应的所有三角形。
3.删除包含在所有外接圆中的边，这时围绕新插入的点构成了一个凸多边形。
4.将新插入的点与这个凸多边形的所有点相连，形成多个新的三角形。
5.返回到第二步，继续加入新的点直到所有顶点增加完毕则结束。
可惜Delaunay三角剖分只合适凸多边形，对于我们在场景中凹形区域占到了大量的面积和数量则需要另外考虑其他算法，Delaunay则可以用于其他凸多边形的情况我们将在后面介绍。现在我们需要的不只是凸多边形和凹多边形的三角形剖分，也需要考虑凹凸多边形中含有‘洞’(即不规则多边形阻挡物)的情况，甚至还有更复杂的‘洞’中有孤岛的情况，因此单单是凸多边形的三角形剖分不能满足我们实际的需求。
Ear Clipping 切耳算法是一个简单实用的三角形分割算法，其步骤可以简单的分为三步，在解释三步骤之前，我们先解释下几个名词的意思。
1.简单多边形是，所有顶点都是顺时针或者逆时针排列的顶点，每个顶点只连接两条边，边与边之间没有交叉的多边形，就叫做简单多边形。
2.耳点，耳点的意思是，多边形中相邻的三个顶点V0,V1,V2形成的三角形里，不包含任何的其他顶点，并且如果V1点是凸点，即V0-V1的连线与V1-V2的连线之间形成的夹角小于180度，则认为V1是耳点。所以一个由4个顶点组成的多边形中，至少有2个耳点。
3.耳朵三角形，三角形顶点中有耳点的就叫耳朵三角形。
我们知道耳点和耳朵三角形再来看这三步骤就容易理解的多，其三步骤为：
第一，找到一个耳点。
第二，记录这个耳朵三角形，然后去掉这个耳朵点，在剩余的顶点中，继续回到第一步
第三，直到剩下最后3个点形成一个三角形并记录下来，把所有记录的三角形拼接起来就形成了三角化网格。
经过这三个步骤的计算，所有的耳点都被切掉后，再把所有记录的三角形拼装成三角形网格，就完成了整个三角形剖分步骤。
除了普通的简单多边形(包括凹凸多边形)的三角剖分外，如果简单多边形中有‘洞’的情况怎么办。论文中也给出了解决方案，即，依旧使用上述三步骤来做三角形剖分，只是剖分之前定把‘洞’并入外围的简单多边形，即：
1，用外围的简单多边形上的点，连接‘洞’的简单多边形，因此为了保持所有点的一致性，‘洞’必须是与外围的多边形的点的顺序是相反的。即外围如果是逆时针的顺序，‘洞’则需要顺时针的顺序。
2，在连接处，产生两个一模一样的点，即连接点。
用这种方式来将‘洞’并入成为一个单独的简单多边形，如果有多个洞，则先并入的洞为，拥有x轴方向最大的点的‘洞’，依次并入。
也就是说，最终计算的还是一个单独的简单多边形，只是在计算之前，将‘洞’以凹形形态并入最外围的简单多边形。
如果’洞‘并不是完全包含在外围简单多边形下，有可能是一半在外面，一半在里面，这时只要做多边形裁剪就可以了，将原来外围的简单多边形根据这个’洞‘裁剪成一个凹形，就与’洞‘彻底分离开来了，形成了新的简单多边形。
除了有’洞‘，以及’洞‘包含在里面和’洞‘一半在里面一半在外面的情况，还有种情况是‘洞’中有’岛‘。这个‘岛’就像是湖中的‘孤岛’，虽然它也是需要三角剖分，但与外界是无法取得连接的，也就没有与最外围的简单多边形连接的需求。
因此’洞‘中有’岛‘，这个’岛‘就相当于另一个独立的简单多边形范围，可以另外单独拎出来，自己计算自己的三角化部分。
到此，这样就形成了一整个算法，即，如果有‘洞’则先合并‘洞’，如果有岛，则拎出来作为与外围的简单多边形同级别的简单多边形自行计算。所有三角化的计算过程可简单描述为，找耳朵，去耳朵，记录耳朵三角形，最后得到了所有三角形，这四个步骤。
应用到实际项目中，最外层的简单多边形，就是我们在地图中定义的可行走的多边形范围。而‘洞’则是地图上的那些静态的障碍区域，而‘洞’中的‘岛’，则是不可行走范围内的可行走的‘孤岛’。我们在构建三角寻路网格时，首先需要找出这个最外围的简单多边形以及孤岛，再根据切耳算法来构建三角形网格。因此我们需要根据地形来生成相应的可行走三角形网格，通过读取地图中的可行走区域的Mesh，以及读取障碍物Mesh，将它们的竖直方向y轴的值忽略后，再通过多边形合并算法来合并成为最外层的多边形，操作还包括裁切‘洞’一半在里面的情况，最后可以得到需要三角化的简单多边形，以及‘洞’的数据。最后将这些数据用切耳算法得到一个具体的三角网格。
前面讲了2D平面上的寻路网格构建，在实际项目中大部分时候，2D平面上的寻路就已经够用了，即使是有起伏的地面寻路，也可以用 2D寻路 + y轴射线碰撞的形式 获得位置坐标的方式，在服务器端以2D平面数据的方式去保存和运算数据，这样即满足了寻路的需求也满足了高低起伏的地形。
有一种解决方案可以用多层级的2D网格做3D寻路，它在2D的RPG游戏中比较流行，也曾在PC端的RPG网络游戏中流行过，在现代的3D网络游戏中相对比较少见，因为现在的高度网格构建算法已经有了比较成熟的解决方案，但这种多层级2D网格的做法任然有比较好的实用价值。
我们暂且称它为‘多层寻路网格’，‘多层寻路网格’需要把所有可行走的区域分成多个层级，每一层都有自己的网格数据，第一层与第二层之间也可以多出一个中间连接层，这就像我们拥有一个多层楼梯的古堡中，古堡有4层楼这么高，每一层都用楼梯连接着，这个楼梯就是连接层与层之间的中间层。
我们任然使用2D三角形网格构建法构建每一层的可行走区域，用这种方法我们假设构建出四层楼的寻路网格，每一层都有自己可行走的平面三角形网格数据，每一层的数据网格数据中可以包含当前层的楼梯部分的数据，例如二层的寻路网格数据可以包含一到二层的楼梯部分的数据，也将楼梯部分的数据单独拆分出来成为一个独立的层级。
有了这‘多层寻路网格’的数据，我们就可以开始寻路了，由于我们只关心我当前层的数据，以及当前层上一层与下一层的数据，所以遍历起来非常方便高效。当要跨越层级寻路时，首先必须确定的是‘我’在哪一层，目的地是哪个层级，按次序一层层往上走或者往下寻路。比如我们去的目的地是二楼，所在的起点是大厅的一楼，那么我们就必须由地面层级开始，先找到楼梯层的入口点，从起点寻路到入口点，从入口点进入楼梯层后，从楼梯层数据中找到与二层楼衔接的入口点并寻路，最后到达二层楼并向目的地寻路。
每一层都有自己独立的数据网格，跨越层级的寻路时需要层与层之间的连接点或连接信息，因此我们在制作时需要对层级之间的入口区域做记录，比如第一层某个矩形范围内为第一层与第二层的衔接，只要进入这个范围就认为我们上升了一层或者下降了一层，角色身上的层级标记也相应地变化，此时索引到的寻路网格数据也变成了当前层的数据。下楼也是同样的道理，在每一层中都有几个层与层之间的斜街区域可以通往下一个层级，只要到达这个范围以内就认为是进入了下一个层级，接着就在下一个层级的网格数据中寻路，每次跨层级寻路时都要先寻找上楼或下楼的衔接区域。
多层寻路网格在2D的RPG游戏中很实用，特别是那种有多个楼层的场景，也在王者荣耀、Dota的竞技游戏中用到，这些游戏的场景里面用到了有符号距离场，它是一个方格形式的网格数据，多各层级的网格数据对低洼和高起部分做了分层的可行走区域定制。
前面说的都是网格构建，那么怎样才能让A星与网格数据结合呢。
在二维数组下的A星寻路很好理解，邻近节点就是周围的4个点或者8个点，并且与目的地的期望值可以直接用方块之间的距离来计算。在路点系统中，也有邻近节点概念，它的邻近节点就是与该节点有线条连接的点，与目的地的期望值可以直接用点与点之间的距离计算得到。在平面三角形网格中，以三角形为单位，每个三角邻接三角形为与它们有共享边的三角形，与目的地的期望值可以用三角形的中点与目的地之间的距离计算得到，我们来看下它们三者在寻路后得到的结果的数据示例：
二维数组下，计算出来的路径，[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]。
路点系统中，计算出来的路径，(id=1)->(id=3)->(id=6)->(id=12)->(id=21)。
平面三角形网格中，计算出来的路径，(trangle_id=1)->(trangle_id=4)->(trangle_id=8)->(trangle_id=13)。
前两者的路径我们很好理解，而三角形网格寻路后，虽然知道了路径上的三角形，但是如果我们行走的路径定位在三角形中心点，行走的路径会比较诡异，每次都要先到达三角形的中点才能去下一个三角形，这样导致中点与中点连线的路径还不够平滑。折中的办法我们可以考虑用边的中点来记录路径，因为相邻三角形之间的穿越都是靠邻边来穿越的，所以邻边的中点更符合三角形穿越，从ID为1的三角形穿越到ID位2的三角形上时，穿越的是ID 1与ID 2三角形的共同边，这种邻边中点计算出来的路径，有更好更平滑的路径效果。
但是这种三角形进出领边中点的方式使路径依然会存在许多折线的情况，为了更好的解决路径平滑问题，我们需要用拐点路径算法来优化寻路后的路径。拐点算法有点像射线，所以也常常被称作为射线优化路径算法，我们来看看算法的步骤：
1.从起始坐标点出发，往与下一个三角形的入口边的两个顶点v1,v2产生两个向量line1、line2，然后再往下一个三角形的入口边的两个顶点v3,v4产生两个向量line3、line4。
2.通过计算这四个向量的叉乘，可以判定一个向量是在另一个向量的左边或者右边。我们可以计算出v3，v4是否在line1，line2形成的夹角。
我们主要用这两步来计算拐点，特别是第二步的结果，我们对第二步结果中的几种情况分别做了对应的操作：
1.line3和line4在line1和line2的夹角范围内，则把实用line3和line4的线作为下一次判断的基线。
2.line3或line4超出了line1和line2的夹角范围(这里指的是line3超出line1外或line4超出line2外，而不是line3反向超出line2或line4反向超出line1)，则使用未超出的线或原始的线作为下次判断的基线，例如line3超出line1和line2夹角，而line4未超出，则使用line1和line4最为下次判断的基线。如果line3和line4都在line1和line2夹角范围外，则使用line1和line2作为下次判断的基线。
3.当line3和line4都在line1左边时，则line1的坐标点成为拐点。类似的，当line3和line4都在line2的右边时，则line2的坐标点成为拐点。
4.当line3和line1是同一个坐标时，它们的坐标点成为拐点。同样，当line4和line2是同一个坐标是，这个坐标点成为拐点。
5.当寻路达到最后一个多边形，直接判断终点是否在line1和line2的中间，如果不是则用line1或line2的坐标点增加一个拐点，依照夹角偏向判定使用line1还是line2的坐标。
前面说的大都是2D上的寻路，即使多层寻路网格也只是用多个2D寻路网格数据来建立多个层次的寻路数据，但依然无法达到3D高度上自由寻路的功能。如果说要在高度上做到自由寻路则要加入’体素化‘这个概念。体素化就是将空间分割成一个个立方体小方块，每个立方体都标志着是否可行走的状态，如果人物角色有高度和宽度的细节，那么如果不够高或者不够宽的角色就无法通过狭窄的门缝或者矮小的洞穴。
RecastNavigation Navmesh 解决方案在各大引擎上非常流行，各大引擎都根据RecastNavigation Navmesh 对其做了相应的优化修改，不过其核心算法并没有变化。由于内容太多太深，我们并不打算把RecastNavigation Navmesh 里所有的算法都讲解一遍，而是将其制图的步骤和思路讲解一下，以便各位读者能在深入时能更好的理解。
RecastNavigation Navmesh 大体流程如下：
1. 体素化
2. 生成区域
3. 生成轮廓
4. 生成多边形网格
5. 生成三角形网格和高度细节
什么是地图编辑器？Unity3D本身的编辑器就是属于场景编辑器，它为场景中3D物体以及逻辑脚本服务，我们通过Unity3D的场景编辑器向场景里添加物件，同时可以做移动、旋转、缩放等操作。它也提供将场景里的物体数据保存下来成为具体的文件数据，即Unity3D的Scene资源文件，只是这并不是我们需要的，我们需要的是可自定义的可解析的地图数据文件。
对于一张完整的地图来说，我们需要的是能生成一个包含地图中所有元素数据的文件，并且我们可以通过这个文件还原整个地图。这个数据文件不只是可以在视觉上还原地图，还可以还原我们已经设定好的地图中的逻辑参数，这些参数包括障碍碰撞检测范围，触发事件，机关走向，剧情发展等。这时我们需要制作一个跟游戏逻辑有关的地图编辑器，以便设计师们能在地图中发挥对地图的设计理念。下面就让我们来说说地图编辑器是怎么实现的。
地图编辑器一般分为3部分，一是可行走区域与障碍编辑，二是地形与物件编辑，三是游戏逻辑包括关卡、触发、事件、怪物出生点等参数配置。可行走区域与障碍物的构建，我们在前面寻路网格章节中有讲到过一些，在地图编辑器中可以用不同颜色的多边形来展示可行走区域与障碍区域，如果是二维方格形式的寻路可以通过展示方格来编辑可行走区域和障碍，如果是三角网格则可以通过多边形来设置障碍区域，或通过标记障碍物体的flag来设置障碍物，最后再通过读取地表网格与障碍物网格来生成三角寻路网格，也可以使用RecastNavigation Navmesh来扫描、制作三角寻路网格，最好是能够理解它的原理熟悉它的API，这样就可以在编辑器中用颜色区分出生成的可行走区域和障碍区域。
地形一般都是一个或几块大的网格模型，也有用高度图来编辑的地形，与Unity3D的地形组件一样通过一张高度图和元素分布图来确定场景中的地形高低和植被范围。物件则以元素形式存在以坐标，旋转角度，缩放大小为基准形成的数据，大部分元素都是节点，模型，特效，因此坐标，角度，缩放这三样的数据记录是必不可少的。其他需要记录的数据也包括配置表ID，物件类型，范围大小，脚本名字等，即通常每个元素的数据为：
struct map_unit
{
position, //坐标
rotation, //旋转角度
scale, //缩放
type, //类型
table_id, //配置表ID
size, //大小
function_name, //功能名
}其中position, rotation, scale 是基础的数据类型，它记录了需要被展示在场景中的位置，角度，缩放大小。而其他的数据，例如 type 可以用来表示这个物件的类型，是人，是怪，是门，是机关，还是不会动的静态场景物件。talbe_id 可以用来表达这个前面 type 类型所对应的配置表ID，用 table_id 可以映射到具体数据表里或者说Excel表里的某一行数据。各种type下的展示效果可以根据这个 talbe_id 的不同而不同，例如怪物有很多种，每个talbe_id 都代表了怪物表里的一种怪物。size 大小则可以认为是物体所触发事件的范围，比如当角色进入5 * 5 这个size大小范围时将触发机关、触发剧情、触发任务、触发生成怪物等。
function_name 一般都会指向某个功能性逻辑或者功能性逻辑系统的配置文件。当某个物件size范围内被触发时，功能性逻辑就根据function_name调用配置文件执行操作或直接执行操作。使用它的意图是通过它指向的是某个具体的功能，每个物件都有可能具有不同类型的操作指令，指令可能是纷繁复杂的，因此它通常都不指向某个函数，而是指向某个配置文件，这个配置文件背后是一套执行流水线的系统，根据这个配置文件可执行一套固定的指令流水线。
为了能配合地图上的其他系统逻辑，地图管理类管理地图上的元素是必不可少的，这样其他系统才能有接口来调用地图上的元素从而执行逻辑。地图管理类更多的起到了存储、更新地图元素，以及存储和更新可行走区域数据的作用。
关于数据的存储与解析，我们在前面的数据协议章节中专门做了详细讲解，这里我们做一些应用，该怎么选择地图数据的数据格式和存储协议。各类协议在这里也能体现其不同的优势。
我们把数据都存储到文件中，当我们选定一种协议格式来存储数据文件，就得用相同的协议读取。使用每种协议都有其原因，假设说我们在众多协议中选择了使用Json协议，我们选择Json协议的意义是什么呢，乍一眼看来Json占用的空间又大，解析又慢，导致很多人都摒弃它，那么我们为什么还用它。肯定是因为Json的特性，简单、易学、明文易懂，只要有一点点编程知识的人都知道Json的格式，即使不知道也只需要花几分钟就能明白其原理，这对于众多新手来说是适合的门槛线，他们能快速上手快速融入团队。除此之外Json的容错率和对协议更新的支持能力也很强，这让Json在整个项目不断更新迭代中有着很好的适应能力。
也有很多协议比Json空间占用小，解析快，效率高，自定义格式的数据协议就是其中一种，如果我们要使用自定义格式的数据协议会是什么理由呢？假设说我们使用自定义格式的协议，把每个变量都转换成byte流形式存储，这种形式的存储是最能够节省空间，也是最能掌控数据的方式。用自定义协议做存储格式的理由，可能是想把空间压缩到最小，并且同时能掌控存储过程不让其他第三方干扰。自定义协议在开发过程中也有很大的缺陷，整个项目是在不断的迭代的因此数据常有变化，自定义二进制流格式对变化适应能力非常弱，虽然也不是没办法但确实有点代价。代价就是要为每个版本的数据格式各自写一个完整的数据读取和存储的程序。每增加一个版本，为了维护旧的数据，都要在原有的数据解析的程序外，增加一个新的数据解析程序。就如下面的伪代码：
void ReadData(io_stream)
{
version = io_stream.read_int();
if( version == 1 )
{
Read_version1(io_stream);
}
else if(version == 2)
{
Read_version2(io_stream);
}
}
voi Read_version1(io_stream)
{
id = io_stream.read_int();
level = io_stream.read_int();
}
voi Read_version2(io_stream)
{
id = io_stream.read_int();
name = io_stream.read_str();
gold = io_stream.read_int();
}代码中读取数据时考虑了多种版本的兼容，使用了不同函数应对不同版本的办法，为每个版本写一个特有的读取顺序，在读取开头，用一个int元素来代表是应该使用哪个版本来读取数据，得到数据版本号后就能对应到不同版本的读取方法。
自定义方式比Json大大减少了空间提高了效率，但也同时增加了维护的复杂度。如果非要使用二进制不如使用 Proto Buff 来的更好。使用Protobuff协议来作为存储格式，即使是数据格式升级和改变也都能轻松的应对，对于存储二进制形式的数据格式来说确实是一个比较好的选择，具有协议数据小、解析速度快、协议升级方便的优点。可惜它最大的缺点是不能明文显示，我们在项目迭代过程中常有对协议有重大改动，或者希望查找数据中的某项内容，由于不是明文，查找起来就会很不方便。
Json就具备了明文的特点，我们一眼就能知道内容，使用文本查找就能找出数据的问题和位置。因此我们在项目中可以使用两种协议，一种是Json这样明文的协议，在编辑时使用，另一种是使用 Protobuff 在真正发布的游戏中使用。即平时用Json编辑存储和编辑数据，发布打包时将数据转换成Protobuff，使得加载和使用更加高效，这种方式对工程项目来说可能会是比较两全其美的方案。
我们说地图编辑器主要的作用是场景地图的编辑功能并能有一个地图数据文件可供前后端使用，可视化体验良好的地图编辑器能够更好的帮助场景设计师、关卡设计师编辑他们觉得更好更绚丽更好玩的地图场景。也正因为有了地图数据，我们在游戏中实例化地图场景时更能够更有序，在加载地图时有更明确的目标。
地图数据到场景还原通过加载资源实例化资源的方式进行，这里我们来了解一下地图加载的几种形式。地图加载的形式有两种，一种是根据地图数据加载全部地图资源后实例化到场景，一种是异步的方式边玩边加载，在加入地图前先加载一些必要的资源然后边玩边加载和替换，其实边玩边加载也分好几种，其中一种就是按需加载地图中的元素模型。
全部加在资源并展示显然是最容易和方便的，根据地图数据文件把所有数据反序列化到内存，针对每个元素的数据，加载它们所指定的模型或效果的资源并实例化到指定的位置，设置旋转和缩放，如果需要的话再对挂在物体上的脚本参数进行设置。
一次性加载这么容易和方便，我们有时可以完全不需要地图编辑器，一个prefab搞定整个场景。这样说来话为什么还需要地图编辑器？对于场景比较单一的项目来说确实如此，但随着功能和需要的扩大，实际场景中开始时很多物件并不需要加载到场景中，而是根据个人玩家的游戏进度来判断加载的内容。这时如果还是按一个prefab搞定一个场景，把所有资源都加载进来，势必浪费很多内存和CPU。地图编辑器就能帮助我们根据需要加载物件，帮助我们节省不必要的开销。
场景比较大的项目，随着场景不断扩大，场景中物体的种类和数量也越来越多，加载全部资源需要消耗的CPU和时间也越来越多。从原本只要加载几个面片当做地形的prefab，发展成了带有众多山、路、草、石头、桥、人、建筑等的一整个大场景。这时即使是按需加载也可能会在加载整个场景中的阻塞很长时间，加在的体验会越来越差。异步边玩边加载的方式就在这时能够体现出更加好的体验。
根据地图编辑器的数据，进行异步流式的动态加载，让人能有逐步出现的视觉体验，相对画面等待的阻塞方式会更好。异步加载缓解了CPU在某个瞬间的消耗，使得CPU在场景加载和实例化上的消耗更加平滑。
RPG游戏场景中场景常常比较大，很多时候一张大地图无缝连接，这样才能体会到真实世界无缝的行走和旅行的体验。我们不可能把整个世界都加载进内存里，因此分块分批加载成了迫切需求。
九宫格方式原本是在服务器端上用来寻找人物角色的结构，每个角色的信息都存放在一个格子里，当一个角色信息变动只要通知周围8个格子的玩家要求它们更新角色状态，更远的格子由于太远而不需要同步，每次有新角色进入附近的格子都需要通知玩家，告诉他有新的角色信息以便玩家的客户端添加模型更新状态，或者附近格子中的角色有离开的也通知玩家，好让玩家的客户端程序可以删除指定角色，每次变化其实通知的范围都是以自己为中心的九宫格内的玩家，因为只有他们是离自己最近的并且在视线范围内出现在场景里的。
我们可以把一整个世界横竖切N和M刀，这样就有了分成 (N+1) * (M+1) 个块，每个块之间的地形可以拆分成相同大小或者用另一个更大的方格来描述地形，这样每块放个的内容都是独立的，可以被独立加载或独立卸载的内容。
在游戏中当玩家进入地图场景，一般来说我们会限制玩家看到场景内容的范围，因为范围太广的话，视野内的内容太多会导致渲染压力过大，因此我们一般只能看到一部分的画面，即周围的800-1200米范围内的画面，越远的地形和风景意义越来越少，远处的景色通常会用迷雾颜色遮起。我们使用九宫格规则来加载场景地图的话，假设每块500x500米大小，当前所在的地块加上周围的八个分割块足以能展示我们需要的画面，即九块的地图内容足以成为我们展示的画面内容。我们来看看用数据表示九宫格地图展示规则：
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][-][2][2][2][-][-]
[-][-][2][1][2][-][-]
[-][-][2][2][2][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
上图中角色所在的地图块标记为1，周围8块已经被加载进来的地图内容比较为2。
我们来设想下的我们控制的角色不断向前行进，离开了当前的地图块进入了另一个地图块，这时九宫格内容发生了变化，以我们角色为中心点的地图块周围的九块与原先我们所在的九块内容发生了变化。我们需要加载周围九块内容中，没有被加载进来的那三块内容，即：
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][3][2][2][2][-][-]
[-][3][1][1][2][-][-]
[-][3][2][2][2][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
图中1为角色所在块，向前移动到了另一块地图块中，原来所在的地块不再是角色所在地块了，到了新的地图块上，那么周围的九块地图的也发生了变化。此时我们需要加载新的地图块，来确保我们展示的内容仍然是完整的，即图中标记为3的内容块，同时我们还需要卸载被废弃的三块内容，即：
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][3][3][3][2][-][-]
[-][3][1][3][2][-][-]
[-][3][3][3][2][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
[-][-][-][-][-][-][-]
图中标记为2的内容块是被废弃的内容块，是需要我们卸载的内容块，卸载不必要的地图内容元素，包括物体实例、角色实例、模型、贴图、音效等元素。就这样我们根据九宫格的加载和卸载规则，在我们这个角色不断向不同方向行走，不断的跨越不同区块的内容，地图模块不断加载需要的地图内容块并卸载不需要的内容块，角色能始终看到完整的地图内容，内存仍然能在保持一个范围内上下波动，因为我们在不断的卸载那些不需要的地图块。
当然我们可以把它划分的更细致一些，将地图分的更细，然后再采用25宫格，49宫格形式来做加载和释放，在玩家不断移动的同时加载那些进入范围内的地图元素，卸载那些离开我们的地图方块。加载时我们也可以将阻塞加载和异步加载结合使用，把最关键部分用阻塞式的加载方式，比如地形和碰撞体以及主要景观模型，其他物件则用异步加载用由近到远的加载顺序，这会让加载导致的CPU消耗更加平滑，平滑的加载完成整个场景所带来的游戏体验将是绝佳的。
定制式地形比较常见，由3D设计师制作出来的网格模型作为地面的地形放置在场景中，相当于一个模型放置在场景上一样，给这个网格模型加入MeshCollider碰撞组件(这里因为是静态的地形所以静态的碰撞体使用 Mesh Collider 性能还尚可，如果是动态物体则不能使用 Mesh Collider)。也有不需要网格模型的，比如使用高度图来计算坐标。
有的项目会使用Unity3D内置的地形，也相当于将一个网格模型放置在场景中，Unity3D的地形可以通过更改地形高度图来改变起伏，不同通常地图项目用 Maya 和 3DMax 等模型软件来构建地形，这种做法能更加容易的被设计师掌控以及自由发挥，也更加节省资源，对程序来说在处理性能优化时会更加容易一些。其他3D物体，比如石头，小石块，草，树，动物等也是同种方式放置在场景中。
定制式地形的好处在于地形和地图的制作不受限制，地形设计师和场景制作师能根据自己的喜好和想象中的画面来自由得定制场景，他们可以任意的移动、旋转、缩放、更换、修整、完善等，这能让他们对场景上的把控有很大的自由度，这种方式是比较常用的单一场景的制作方式。
用程序拼接地形的主旨意图是希望能在一定的规则下更好的为设计人员自由设计更好的地图而选择的方式，这样在规则下去做一些事情从设计和性能上求得一个平衡点，整个地图由程序生成，通常会一个或者几个模型的结构铺满整个地图。
用这种方式制作地图最常见的要属2D的RPG游戏，2D角色扮演类游戏中，几乎整个屏幕的地形都需要用地图编辑器来建立和拼凑，运行时程序会将地图数据加载进来后，对每一块的地图都进行动态的拼合，这样一来整个地图就只有一个drawcall，因为它只使用了一个网格(程序生成的)和一个材质球。对此种方式我们做一些分析：
我们先来看看2D RPG游戏中，是如何动态拼合整个地图。现在很多2D游戏都通过Unity3D来实现，其实2D也是有Mesh、顶点、UV的概念，和3D比起来只是少了1个维度，因此在2D游戏中的地图程序拼合手法也是通过生成顶点和三角来完成的。我们可以设想整个地图就是一个大的矩形，地图中每个方块是这个大矩形中的一个格子，而每个格子都由2个三角形构成，既然我们能计算出每个方块的位置，我们就能计算出每个三角的顶点和位置。简单来说地图是一个大矩形，它由很多个大小相同的小方块构成，小方块的大小可以通过配置文件的形式来调整，这样有规则、大小一致、位置可寻的网格可以通过程序生成。
我们用三角形的方式拼接每个方块，并调整地图方块上顶点的UV，UV指向的是地图贴图中的某一块，而地图贴图以图集的方式存储地图上不同类型的贴图。就这样所有的方块拼合成了一个大网格，每个方块上的顶点上的UV都指向地图贴图中的某一块地块内容，地块贴图内容全部集中在一张图集里。
伪代码：
//生成地图
void Generate_map()
{
//遍历每块矩形的方块位置
for i to width_count then
for j to height_count then
mesh = generate_trangle_by_rectangle(i,j,_type, texture_info);
AddCombine(mesh);
end
end
CombineMeshList();
}
//生成矩形方块所需要的，4个顶点，4个索引，2个三角形，2个三角形的顶点索引，以及三角形的uv位置。
void generate_trangle_by_rectangle(int _x, int _y, int _type, texture_info _tex)
{
//矩形的4个顶点
point1 = vector2( (_x - 0.5) * width, (_y + 0.5) * height);
point2 = vector2( (_x + 0.5) * width, (_y + 0.5) * height);
point3 = vector2( (_x + 0.5) * width, (_y - 0.5) * height);
point4 = vector2( (_x - 0.5) * width, (_y - 0.5) * height);
//顶点增加后的索引位置
point_index1 = add_point(point1);
point_index2 = add_point(point2);
point_index3 = add_point(point3);
point_index4 = add_point(point4);
//三角形的生成时的顶点
trangle1 = [point1, point2, point3];
trangle2 = [point3, point4, point1];
//三角形顶点的索引信息
trangle_index1 = [point_index1, point_index2, point_index3];
trangle_index2 = [point_index3, point_index4, point_index1];
//4个uv点位的信息
point_uv1 = vector2(_tex.uv_x, _tex.uv_y);
point_uv2 = vector2(_tex.uv_x + _tex.width, _tex.uv_y);
point_uv3 = vector2(_tex.uv_x + _tex.width, _tex.uv_y + _tex.height);
point_uv4 = vector2(_tex.uv_x, _tex.uv_y + _tex.height);
Mesh mesh = new Mesh();
mesh.trangles = [trangle1 , tangle2];
mesh.trangles_index = [trangle_index1 , trangle_index2];
mesh.uvs = [point_uv1, point_uv2, point_uv3, point_uv4];
return mesh;
}上述伪代码中，对所有地图中的方块进行遍历，在遍历中生成了每个方块所需要的顶点、顶点索引、uv数据，进而生成三角形网格。遍历完毕后将所有网格数据合并，使得整个地图是一个一体化的网格，渲染时只产生一个Drawcall。用程序拼接的地图可以通过地图编辑器来改变地形地貌，拼接完成的地图在渲染上的代价也相当的小，假如想换个地图样式，只需更换贴图就可以非常方便。
我们需要注意整个地图需要些许工具链支撑，由于地图元素仅限于图集中的元素，每次增加、删除元素都需要操作地图图集，图集太大时就会有拆分图集的必要，把不同地图图集分为共享图集和各自地图的图集，这样就需要我们改变一个地图一个Drawcall的策略，渲染多个图集让多个Mesh凑成一个地图，每个Mesh代表一种类型的地图图集。
3D RPG角色扮演类游戏中，也常常使用这种技巧来绘制游戏地图，曾经在日本风靡一时的《白猫计划》就使用了这种方式。
这种程序拼合的地图，策划设计师、关卡设计师可以在地图编辑器上，任意的绘制、拼接、同种类型的不同样式的地图（即在同一张贴图内容中的模型和地图元素），因此大大缩短了大量的场景试错时间。它能大量的生成出不同样式的地图，不需要制作大量的不同类型的3D模型，大大缩短了项目时间进度，深受游戏制作人的喜爱。
那么在3D地图中是怎么拼接方块地形的呢？看上去比2D更加复杂的事情其实并不是。
首先，我们在制作3D地形前需要制定一下模型的规范。3D地图中不需要我们自己来拼接三角形，我们用固定的地形模型，把每个地形模型都做成一个固定大小的立方体。假设规定每块地形规定为 10 x 10，在制作和拆分地形模型时按规定来拼接，每个3D地形模型都必须以 10 x 10 的标准来定制。单个模型的尺寸大小按照项目的地图拆分来，也可以是20 x 20 或 30 x 30，只是当标准制定完毕后，地形模型的制作必须要按照标准来做，每个元素都相当于一个地图块。
其次，同一个地图上的地形模型的纹理贴图都最好并在一张图集上来制作，因为只有这样才能在合并模型才能合并材质球，并且在合并后让这么多的3D小方块只需要1个Drawcall渲染调用就可以绘制所有的地图，也只有这样才能解决太多模型需要渲染导致的爆量Drawcall问题。
然后，在3D地形模型制作时需要些提前的设计和考虑，因为地图都被拆分成了N种类型的地形立方体，所以在制作的初期需要对整个地形有哪些类型的需求进行设计和探讨。在读取地图编辑器编辑的地图数据后，除了拼合地形模型立方体，实例化场景地图时也需要增加些许逻辑，为的就是适应更好的模型拼合，就像我们在制作和拆分城墙时那样，当城墙处于拐角处时，我们需要选择不同的拐角模型代替，判断它的左右前后有没有其他城墙，如果有则应该选择适当的连接城墙来适应周边的模型，左连接、右连接、前连接、后连接、以及前后双向连接，左右双向连接等等总共9种情况，有不同的9种拐角城墙所代替，这样才能完美契合周围的地块模型。
最后的合并模型步骤就相对简单的多，按地形模型放在地图数据文件所描述的指定位置上，并如上面所说的选择好适配的模型，调用Unity3D的API方法 Mesh.CombineMeshes 合并所有模型。在合并时也会有三角面数的限制，合并后的模型三角形数量不能超过2的16次方减1个面(即65535个面)，如果超过则应该另起一个模型进行合并。
上面几节阐述了地图的拼接方式，其中用程序拼接合并地图块的方式确实大大降低了 Drawcall 的数量，提升了渲染的性能，但这也只是针对可拆分的地图类型项目，对大多数游戏类型来说地图是不可拆分成小块的立方体进行拼接的，因此我们还是需要更多的针对常规场景讲解优化的方法和技巧。
首先我们要清楚的是，是什么造成了场景的低渲染效率。我们在这里罗列一下主要的几个问题：
1.同屏渲染面数太多，GPU压力太大。
2.渲染管线调用次数太多(Drawcall太多)GPU的并行处理没有很好的发挥作用
3.贴图太重太大占内存大，导致显存的带宽负荷太重
4.动画太多，蒙皮的计算消耗的CPU计算量太多
5.Shader开销太大GPU的计算量开销太大
其实还有很多很多问题需要解决，比如实时阴影导致的 Drawcall 太多，以及透贴太多导致Overdraw 重绘问题比较严重，还有比如物体需要的Pass渲染太多，一个物体需要绘制多次才能完成，这些问题也是很重要的，这节我们就来说聊聊场景的优化。
渲染面数太多一般都是同屏展示的面数太多，整个场景的网格面数太多只会让内存上升，摄像机里同屏的渲染面数才是比较重要的。
Unity3D引擎会裁切掉在摄像头之外的物体，不让他们进入到渲染管线以减少消耗，虽然裁切也会消耗小部分CPU，但毕竟比起渲染整个物体要小的多。
很多45度固定摄像头视角的游戏并不会将摄像机抬起来让更多的画面进入摄像机，但有很多游戏摄像机的旋转角度是自由的，这导致在摄像机抬起时会让许多模型进入摄像机的渲染范围。大部分引擎包括Unity3D都有对模型物体在提交GPU前进行一次裁剪，在进入渲染管线前每个3D物体能计算出或者已经计算好了一个包围盒即Bounds，这个包围盒由8个顶点组成，加上旋转矩阵就能计算出每个顶点是否在摄像头的锥形体范围内。
裁切的算法中包围盒8个点中只要有一个点在锥视体内，就认为是需要渲染的不可被裁剪，如果8个顶点都不在摄像头的锥形体范围内，才认为是不需要被渲染的，这时Unity3D引擎会阻止这个模型渲染，在渲染调用前就抛弃它。因此我们要格外注意模型的包围盒，有些包围盒在模型制作时由于错误的操作导致包围盒并不适应模型大小，过大的包围盒导致GPU性能浪费。这种Unity3D引擎上的裁剪，帮助我们屏蔽掉了很多不需要渲染的物体，虽然裁剪也会花去些许CPU，但比起要绘制一个3D物体的计算量来说要少的多。
场景中如果是一个模型很大很长会让裁剪失效，常常在我们项目中有模型范围从南延伸到北贯穿整个场景，这样的模型包围盒会很大很长，常常让引擎的裁剪优化失效。一旦模型长到覆盖了整个场景，包围盒总有一段在摄像头内导致不会被引擎裁剪，这样就会浪费很多不必要的GPU计算，因为网格被传入后由GPU来负责对每个三角形裁剪，比起用包围盒的方式裁剪要费力的多。因此我们在场景中要考虑对过大过长的模型进行拆分，不能让它跨很多个区域范围，不过注意拆分的过细也不行，因为这样会带来更多的Drawcall，理解了裁剪原理会对场景物件的颗粒度大小的把控会更加清晰一些。
摄像机的远切面太长就会包含太多的物体在视野范围内，这导致我们前面说的引擎内裁减失效，更多的物体会被送去渲染，增大了GPU的压力。
最简单直接的方法就是，拉近摄像头的远切面距离，减少模型进入视野内的数量。视野范围内的物体减少，需要渲染的模型面数也就减少了，CPU和GPU的消耗自然下降，让视线范围在一个合理的范围内是我们需要关注的摄像机参数。
这种方法毕竟不能大用，因为它缩短了视野直接裁减三角形，让画面不那么细腻美观，我们很多时候希望看到更远的地方。我们既希望能看到更多更远的物件，也想降低渲染带来的压力。世上没有免费的午餐，想降低CPU和GPU的消耗，至少得用大量内存来换。LOD，即Level of detail，就精通此道，用内存换CPU和GPU。
LOD需要我们把3D模型做成多个不同细节级别的模型文件，每个级别的模型都比上一级模型的面数少一些，这样面数少的模型用于远距离的渲染，而面数多的则用于近距离渲染。当摄像头拉远时，启用面数更少的模型，当摄像头拉近时，则启用面数更多的模型。这样即使众多的模型在摄像头范围内等待渲染，也只有几个面数多的模型靠近摄像头，而大部分模型都离摄像头比较远启用的是面数比较少的模型。这些远离摄像头的3D模型面数很少，即使数量众多，它们所展示的低面数的总和也是可以接受的，当同屏需要渲染的面数少时，GPU需要处理的三角面也少，虽然Drawcall数量没变化，GPU需要处理的渲染指令数量没有变化(渲染状态和渲染指令时串行处理的)但处理的量少了，处理速度自然就快了。
我们常提到的 Mipmap 其实也点LOD方式的运作意味，只是Mipmap的主要意图不是优化性能而是物体像素比导致的画面瑕疵问题，由于Mipmap会根据远近来选择贴图大小，因此在绘制场景时也节省了不少GPU与内存之间传输数据的带宽，我们将在后面的渲染章节更详细的讲解，这里只是简单陈述一下。Mipmap和LOD有差不多的理念，对于离摄像机远的物体启用更小的纹理贴图，对离摄像机距离近的物体使用正常的纹理贴图，只是Mipmap使用的不是距离而是渲染时的像素与贴图像素块的大小比例。
当然天下没有免费的午餐，提升了CPU和GPU的性能就得增大内存的消耗，内存消耗太多也会有得不偿失的时候，因此在使用LOD时我们考虑分多少级的细节级别上也需要斟酌一下。针对不同的项目分级的层数不同，拿大型MMORPG来说，那种可以在天上飞的游戏，看到的物体自然就很多，如果LOD分级少了画面则会显得突兀，而中小项目LOD分级太多则加大了内存量和制作时间得不偿失。
除了渲染面数太多带来的GPU压力，渲染调用次数太多也是造成GPU瓶颈的一大问题。Drawcall太多的问题大都因为场景中的模型物体太多引起的，也可能附带着Shader中的Pass太多使得渲染压力更大。
这个问题是最简单粗暴就是‘干掉’在场景中众多的模型物体，以及‘注释掉’Shader中不必要的管线。这无疑将美术设计师和场景设计师的辛勤工作的成果给白白的浪费了，我们尽量不考虑这种方式，不过适当的移除些许不必要模型的其实也有助于场景制作。
我们希望在不毁坏场景的前提下做些优化，关键点就在于‘合并模型’。我们不希望破坏场景的美观，不想让设计师们辛苦设计的场景毁于性能优化，为了两全其美我们需要合并渲染。在制作完场景后同屏内需要渲染的面片数量已经确定，我们在不减模型在场景中的数量以及不减少单个模型面数的情况下，同屏画面上需要渲染的三角形面数已经不会变化。从整体上看当我们每次调用管线渲染（即调用Drawcall）都会传送给渲染管线一些三角形，如果传送的三角形数量比较少，则调用的Drawcall次数就会增多，因为三角形数量时确定的。我们需要合并这些三角形面片然后一并传递给管线，将原来需要多次的调用管线变成一次，只有这样才能大大降低 Drawcall 的数量，降低渲染调用次数。
那么减少渲染管线即减少 Drawcall 的数量究竟有什么好处？减少了渲染管线的数量，即降低了Drawcall的数量后，尽管并没有减少任何需要渲染的面片数量，只是每次传递给渲染管线的顶点和面片数增多了传递的次数减少了，三角形数据在进入渲染管线后可以开启GPU并行处理，原本单行线处理变成了多线处理，将像是单车道扩展为8车道那样速度成倍的增加。
原本调用一次渲染就要在队列中等待管线渲染完毕后才进行下一次渲染，合并后就不同了。不再是像以前那样调用这么多次Drawcall，渲染画面时Drawcall的队伍都要排的老长，都等在那排着队等待GPU处理。合并后就不再是这样了，排队的数量少了队伍短了，虽然每个排队的数据都很‘胖’（数据量很多），但是一旦进入GPU处理阶段上百条生产线并行处理这些数据，因此我们要想方设法的合并各种模型减少Drawcall。
Unity3D引擎自带有多种合批方式，前面几个章节有详细的介绍这里我们再简要的阐述一下，Unity3D引擎中有动态合批、静态合批、GPU Instancing 三种合批方式，其中动态合批在合并的模型时要求比较高，包括对模型面数、法线、切线、Pass数等都有要求，静态合批则放宽一些但也有自己的规则，它通过消耗的内存来换取CPU，而GPU Instancing 的原理是通过对一个模型传递更多的信息数据从而让它绘制在不同的位置与不同的样式以达到减少Drawcall的目的。
这里我们不讨论通过Unity3D引擎里的功能来做‘合并’的操作，我们希望能够自己掌控‘合并’效率和效果。部分原因也是因为引擎自带的合批方式通常都是通用的合批方式，规则比较严格，合批率比较低，我们假设搁置它而选择自己动手丰衣足食。
‘合并’分实时合并，与，非实时合并两种方法
实时合并会消耗大量的CPU，因为它要读取多个模型，并创建新模型数据，不断的创建新模型数据，就会导致CPU的消耗。这里由于前面模型的章节已经详细阐述过因此我们简单阐述一下，合并模型时要求模型使用相同材质球，读取所有具有相同材质球的模型数据，生成一个新的合并后的模型并隐藏原有的模型。倘若我们在制作时发现很多模型材质球使用的Shader和Shader的参数一样，只是贴图不一样，我们可以离线合并它们的贴图后再放到实时渲染时进行合并。
非实时合并则全是线下的合并，即大家常说的静态合并。Unity3D静态批处理的规则比较严格，即要求相同材质球相同贴图还要相同的模型，而且内存消耗比较大，因此我们还是建议使用自己手动合并的方式，即可以自己手动拼接场景中静态不动的、有相同材质球的模型，也可以用程序或插件来拼接，比如 MeshBaker，通过 MeshBaker 来制作和合并模型与纹理贴图。静态合并Mesh的好处就是，游戏中不需要实时消耗CPU去合并模型，节省了不少实时开销的CPU，同时也降低了很多Drawcall的数量。
合并这档子事当然也会过犹不及的，如果把所有的在场景内的物体全部合成为一个模型，无论摄像头能不能看到的地方都合并了，那么GPU的压力也同样会很大，因为这样的话我们前面提到的引擎自身做的第一层包围盒裁剪就不能生效了。渲染时会一股脑的将整个模型数据塞进渲染管线中由GPU来裁剪，这样会增大GPU的计算压力，GPU要裁剪整个地图的所有模型面片，计算量会是巨大的。因此我们在静态合并时也要适度，即合并附近距离不太远的、可以称为一块范围内的模型，这样即减少 Drawcall 次数，也为引擎裁剪让出了空间，降低了GPU裁剪的压力。
贴图太多宽带压力太大导致的问题，主要是因为GPU在渲染时需要将内存的纹理拷贝到显存中去才能使用在GPU中渲染造成的。所以拷贝的消耗和显存的消耗也是很大的。现代设备显存只存在于主机和PC游戏中，在手机中没有显存的概念，它只有内存，手机设备中的显存都是内存内部的拷贝，即手机中会为GPU预留出一块用于渲染的内存块作为缓存。
其实手机与PC机的架构完全不一样，这导致内存的存取方式也不同，PC机中向GPU传输纹理贴图是从内存向显存拷贝，这其实意味着贴图纹理有两份，一份在内存，一份在显存，当引擎调用渲染指令时会向GPU传输纹理贴图，通常GPU会拷贝一份纹理到现存中，不过这也是短暂的，显存只是相当于缓存作用，引擎的每次渲染调用都会重置渲染状态，向GPU传输纹理贴图，如果纹理贴图已经存在于显存中则不用再传输，如果显存不够则要清除掉显存中一部分内容以空出空间来应付当前的指令。显存理论上说是越大越好，这样每次渲染调用就不用被覆盖，在下一帧渲染时就可以重复利用前面已经传输过的纹理。
现代手机设备，安卓与IOS的架构则完全不同，手机中完美没有显存这个缓存硬件，只能从内存中分离出一部分来使用。而且在安卓和IOS的架构下也不再存在着纹理在内存和显存的拷贝，CPU和GPU的纹理地址指向同一个物理地址。当手机设备需要纹理时，系统从纹理文件中直接加载进入指定的物理内存不再拷贝到其他地方。
除此之外有两份内存的情况也时常在引擎内发生，Unity3D中贴图有个选项 Read/Write，当Write被勾上时就会在引擎的内存中有另一份拷贝，这是由于Write属性的贴图随时会被更改像素内容，为了不影响GPU贴图的渲染更好的在CPU与GPU之间运作，系统采用三重缓存机制，即系统会另起了一份贴图来使得CPU与GPU之间无障碍协作。因此我们在贴图设置时，首先要注意 Read/Write 选项是否需要被开启，绝大部分贴图是不需要被开启的，这些贴图被开启后造成的2倍内存也是不必要的。
贴图太大太多会影响渲染，主要影响的是GPU的拷贝过程，最好的办法是缩小贴图和压缩贴图。看起来挺简单的，其实我们在实际项目中，我们不能为了性能随意去缩小和压缩贴图，这样为导致项目因贴图质量太糟糕而影响画面效果。我们需要针对每个部分的贴图逐一去了解和设置参数，或者用Unity Editor脚本对某些文件夹下的贴图统一做强制性的设置。其实每个功能部分的贴图都有其用途，比如UI中的贴图分，大部分是图集和Icon图片，图集一般都是无损质量，不同级别的设备也会离线LOD的方式做多份拷贝，每份的设置都会有所区别，大部分UI贴图都不需要 Mipmap采样，Icon图也是一样。针对低端设备会对UI贴图做些压缩，压缩后UI的质量会有所降低，换来的是性能速度会快很多，这是由于无损的贴图在内存上和压缩的贴图通常有5-10倍的差距，贴图传入GPU所执行的拷贝过程会消耗一部分算力。
3D模型的贴图也是其自己的特点，模型纹理贴图通常都是2的幂次的大小存在。2的幂次大小的纹理GPU处理起来比较顺手，以前GPU只能处理2次幂大小的贴图，现在GPU已经强大到可以处理非2次幂大小的贴图了，但速度和效率还是会相对慢一些。这些贴图也通常是可以压缩的，并且大都需要带有 Mipmap 采样生成标记的。要压缩多少压缩到什么比例才适合，可能并没有绝对统一的标准，大部分项目都会针对设备平台去压缩，以及针对高中低端设备做压缩设置，如果你没有很好的压缩策略可以选择中位数策略即Normal Compress普通压缩。
贴图的大小也比较重要，每个项目在开始前最好能好好的规范一下，我们在模型章节里讲了许多规范的制定，只有遵守良好的规范项目才能稳步前进，毕竟不是一个人在努力，大家的努力要转化为有效的合作与更长远的发展。幸运的是，美术设计师无论将贴图做的多大，我们都可以在Unity3D里重新设置成我们需要的大小，Unity3D会将所有贴图都重新制作导出成我们指定大小的贴图和格式。因此即使前期贴图太大而导致的问题，可以在Unity3D的项目中将贴图设置回我们希望的大小尺寸。
模型动画确实是最令人头疼的一块内容，它是动态的而且时时刻刻都是计算网格的位置，不像静止的3D物件即使它们有时会出现或消失也不会消耗网格算力。而模型动画则不同，它们时时刻刻都在你眼前动来动去，即使不再屏幕上，大部分时候也需要一直保持动画的计算过程。
对于模型动画的优化，在模型动画章节中讲的比较详细，这里主要是在前面讲解内容基础上以实际的应用场景简单的讨论一下。
模型动画的消耗量最大的地方是CPU的蒙皮计算，如果有100个动画在屏幕中播放，CPU会极大的消耗在蒙皮计算上。蒙皮计算，其实质就是骨骼与顶点的计算，骨骼动画用骨骼点去影响顶点，每帧都需要计算骨骼点与顶点的偏移、缩放与旋转。如果动画模型的顶点数量很多，骨骼数量很多，由于顶点关联着骨骼点，多个骨骼点影响着顶点，那么计算量就会很大，消耗的CPU的算力自然就会很多。为了能减少计算量，我们减少顶点数是最直接的办法，又或者减少骨骼点的数量也是，这样能使得CPU降低消耗。
让3D模型设计师和动画师去做减面和减动画骨骼的工作绝非易事，它涉及到画面质量削减平衡，在削减的时候设计师们需要顾及画面质量。这些都是我们程序员无法控制的，我们能做的就是从程序上尽量的降低开销。由于每帧都要计算网格的形状所以很费CPU，如果能把计算好的每帧顶点偏移量存起来，播放的时候直接偏移过去就会好很多，这样就不需要计算了只需要存储与偏移。我们可以把每个动画网格分批计算好另存为一个文件，这样有多少帧动画就会有多少个具体的网格存放起来，每次播放动画时，直接拿出这些网格一个个替换就省去了网格顶点的计算。
先不说空间的占用量，毕竟这么多模型网格无法合并Mesh，每个动画模型都需要至少一个Drawcall来支撑，如果Shader中有多个Pass管线，就有更多，比如描边，实时阴影等。假设有100个这样的动画，就需要至少100个Drawcall来支撑。消耗还是太大，能不能合并Drawcall，就像合并普通Mesh一样，相同的材质球合并成为一个Drawcall呢？Unity3D的 GPU Instancing 为我们提供了合并的可能。它可以合并相同材质球，相同模型的Drawcall。它原理是将一个模型以不同的状态，在不同位置渲染只需提交一次GPU。
SkinMesh Instancing 就借此解决了这个问题，它建立在GPU Instancing功能之上的动画优化方案。它把动画的模型数据在离线状态下计算好并存储在贴图中，这样解放了CPU的算力并转移到GPU中渲染。它把动画文件中的数据与模型数据结合分批计算好网格顶点的偏移量并存储在贴图中，由可编程的顶点着色器来根据参数来完成顶点的偏移，这样我们就不仅不需要计算而且还能一次提交就能渲染很多个位置的模型，每次渲染只需将顶点偏移就可以了，省去了大量的CPU计算蒙皮的消耗。
与之相似的，也在着色器中解决动画问题的还有一些场景中的草、树、飘带和红旗的摇动，我们可以用顶点动画蒙皮计算的CPU消耗。这些摇动的动画是纯顶点算法计算出来的摇动，它用了一些摇动算法计算出顶点的偏移位置，使用消耗GPU算力来代替CPU算力，因为GPU它是并行的且更擅长顶点计算。
当然这几种方法也各有利弊，在实际项目中需要根据实际情况做出选择甚至混合使用，我们在使用时应该衡量他们在项目中的限制和作用，尽量做最适合的选择。
片段着色器中计算复杂逻辑，将计算转移到顶点着色器中 使用过多复杂的数学函数，使用近似公式代替 使用变量精度多大，减少不必要的精度 使用过多ifelse，编译器并不会分支 使用需要等待的功能，避免使用等待缓冲需要功能 使用过多pass，合并计算 使用mutile compile后的初始化，变体导致编译出有很多的shader，引擎在识别功能时会选择对应的shader，这导致很多shader没有被初始化的会被临时初始化 AlphaTest在手机设备上使用会让pre depth test 失效，导致性能开销反而增加 尽量能够在离线计算好的数值，尽量离线计算完后，使用常量来代替实时计算消耗