World Representations
World Representations
我们现在知道寻路使用图来解决，但是我们的游戏场景并不是由多个节点和节点的连接组成的。那么我们就需要有游戏场景抽象话。
抽象场景的方式叫做划分方案（division schemes）,每个划分方案都有三个重要的性质：量化/定位（quantization/localization）、分区（generation）和有效性（validity）
Quantization and Localization
在游戏中，角色想要去商店，就需要把角色当前的位置转化到图中节点，同样商店的位置也要转化到图中节点。这个转化过程叫做量化（quantization）。
在找到了去商店的路径后，我们需要把路径中的节点转化为游戏场景中的位置，这个过程叫做定位（localization）
Generation
有很多分区的方法，每个游戏中用到的可能都不太一样。一般分为手动分区和自动分区。
手动分区最常用的是 狄利克雷分布（Dirichlet domain）
自动分区最常用的的 瓦片地图（tile graphs），可视化点（points of visibility）和 导航网格（navigation meshes）
Validity
我们寻路得到一个路径了，从节点A到节点B,那么意味着角色无论如何都可以从A点移动到B点，但是如果无法量化A点或者B点的话或者角色不具备通过这个路径中的某个能力（如游泳）。那么这个寻路就是无效的。
Tile Graphs
这种方式一般在2D游戏里使用，多出现在独立游戏里。但是也有很多3D游戏会使用网格在映射游戏。比如很多RTS游戏，在里面建造房子，以格子来设置房子大小以及位置。
Division Scheme
用网格代表游戏世界。每一个小块一般都是正方形的，换句话说就是棋盘格。每个小块周围有8个小块围绕，与每个小块连接的也就是8个。
Quantization and Localization
我们可以很简单的量化角色在那个节点，我们以网格左下角为原点，向上为Z轴，向右为X轴建立坐标系。我们就可以用下面的表达式获得角色节点位置：
tileX: int = floor(x / tileSize)
tileZ: int = floor(z / tileSize)
同样定位也可以很容易的做到，反向求一下x和z值就可以。
Generation
基本的网络生成一般都是自动的。因为它每一个片基本都是差不多。它可以在游戏运行时生成。
Validity
如果有的格子是半格可以走，半格被遮挡住。这种情况就需要在由节点定位到游戏场景位置时，考虑角色是否在那个位置。
Usefulness
在一个RTS游戏关卡里可能有成千上百的小块，这会使得寻路算法，花销很多。
从上图可以看到寻路得到的路径和理想上的路径有一定的区别，而且看起来不是那么的丝滑。
Dirichlet Domains
Division Scheme
寻路节点在空间中有一个称为特征点的关联点，并且通过将该点的狄利克雷分布的所有位置映射到该节点来进行量化。确定游戏中的一个位置的节点，我们找到了 最接近的特征点。
你可以把狄利克雷分布看作是来之源点的锥体。如果你从顶部查看它们。你就可以看到每个圆锥体的区域都是属于该源点的区域。这是一个很有用的排除故障的可视化方法。
我们可以为点增加一个权重，来调整圆锥的斜率，这样就可以调整么诶个圆锥覆盖的区域。当然也需要注意这关卡编辑时，设置关键点时，他的权重值不能过高。不然就会出现上图的情况。
Quantization and Localization
位置通过找到最接近的特征点来量化，节点的定位是由形成分布域的特征点的位置（即 上诉例子中锥的尖端）给出的 。
Validity
无法保证从一个域中的一个点移动到 连接域中的某个点不会通过第三个域。这第三个域可能无法逾越，而且可能已经被寻路器忽略了。在这种情况下，遵循该路径将会导致一个问题。有可能角色就撞墙了。
为了防止这种情况，我们 可以设置某种备份机制（如避免墙上的转向行为），来解决这个问题。
Usefulness
应用非常广泛。它的优点是非常容易编程，并且易于更改。可以在几倍编辑工具中快速更改寻路图的结构，而无需更改任何级别的几何结构。
Points of Visibility
在2D环境中最短的路径一般都是会经过转角处。那我们可以把几个转角连接起来就是最短路径了。如果我们移动的角色有半径，那么就从转角点向外偏移直到可以使角色转向过那个转角点。
Division Scheme
我们在连接两个点时，怎么判断两个点 之间是可以通过的呢？我们从其中一个点发射射线，如果这个射线并没有碰撞到其他物体，直接到达了对应点，那么我们就认为这两个点时可以相互走的。
Quantization and Localization and Validity
为了量化，通常用课件点来表示狄利克雷域的中心 。此外，如果使用狄利克雷域进行量化，则量化到两个节点的点可能无法相互到达。正如我们在上的狄利克雷域中所看到的，这意味着该图是无效的。
Usefulness
这是一个很好的方案，但是这其中有很多无用的连接，我们需要手动去处理。使用导航网格更好一些。
Navigation Meshes
这个是最常用的一个方式。
Division Scheme
可以对游戏场景中的地面做了多边形划分区域。对于每个多边形可以认为就是一个节点。如下图所示：
Quantization and Localization
我们做量化时，是不是就需要找到角色现在处于那个多边形内？最容易想到的方式就是遍历所有多边形，如果多边形少还可以，多了的话是不是就会等一会。这里有一种简单的方式，我们会记录下来角色上一帧所在的多边形，我们先检查这个多边形 ，然后以扩张（上一帧多边形周围）的方式来检查。这样可以更快的找到。
量化中有一个问题，如果游戏场景有多层的情况。我们划分多边形时，不考虑垂直方向的情况。这就会出现错误。比如：上图，量化看出人物在底层，但是实际上这个人物是在上层的。我们同样可以使用角色上一帧的多边形来确定角色是在上还是下。在一些特殊的情况下使用这样的方式还是会出现一定的问题，通常需要一些特殊的案例代码来知道一个角色何时在跳跃，或者推迟寻径，或者使用轨迹预测来确定它将降落在哪里。
定位一般是定到多边形的重心位置。当然多边形一定要是凸的。
Validity
理论上我们可以中一个区域的任何一个点直接到达相邻区域。
我们看上图，就出现了从一个区域到另一个去区域产生了碰撞的情况。这就是在生成多边形或是设计多边形时的错误。
Usefulness
这是个很好的方案，在一些特殊情况下也可以使用，比如爬墙，跳跃等。
有一个问题，如果分的区域很小，角色不能容纳进去。就会有一些问题。我们可以在设计时对其限制。
Edges as Nodes
地面多边形还可以通过将节点分配到多边形的边上，并使用跨多边形的面连接，从而将地板多边形转换为寻路。
这种方式在渲染中很常用叫做基于块渲染（portal-based rendering）。就是把一个整的几何体，分成多个小块，当我需要那个块时就渲染那块。
在导航网格中，每个楼层多边形的边缘都像一个块，因此有自己的节点。我们不需要做射线检测。根据定义，凸底多边形的每一条边都可以从其他的每一条边看到。
如上图，我们也可以把节点在多边形线上的位置改成动态的，改到角色移动的方向。这是一种连续的寻路算法。