哪条路线是最安全的，敌方最多，哪里是最近的急救箱？ 使用称为“ Voronoi图”的数学分区，可以有效解决所有这些经常遇到的空间关系问题。 从这篇文章中，您将学习如何分析游戏卡并获得确保人工智能的真实性和成功的信息。
空间关系
空间关系是描述空间中的一个物体与另一个物体如何相关的任何信息。 例如：它们之间的距离，每个空间所覆盖的区域以及这些区域的交集，位于一个区域中的此类对象的数量。
这种关系经常在视频游戏中使用，并且可以提供非常有用的AI信息，以及提供给玩家本人。
Voronoi有一个答案
Voronoi图描述了紧密间隔的点或其最近的邻居之间的空间关系。 这是从点或位置获得的一组连接的多边形。 Voronoi“区域”的每一行都位于两点之间的中间。
要了解，请看一下图片：
如您所见，每条线恰好位于两点之间的中间，并且所有线都连接在中心。 向场景添加更多点，看看会发生什么：
图片变得更加有趣！ 我们已经有实际区域。
每个区域告诉我们什么？ 我们知道，保证在该区域中的位置最靠近也在该区域中的一个点。 这告诉了我们很多附近的事情。 这就是Voronoi图中的基本空间关系。
由内而外将Voronoi：Delaunay三角剖分
与Voronoi图相反的系统称为Delaunay三角剖分。 该图由从每个点到其最近邻点的线组成，并且每条线均垂直于与其相交的Voronoi边缘。 看起来是这样的：
白色标记了Delaunay线。 每条Delaunay线只对应一个Voronoi边。 乍一看，其中一些似乎跨越了几个边缘，但仔细观察，您会发现事实并非如此。
在图中，绿色的Delaunay线对应于Voronoi的粉红色肋。 试想一下，粉红色的肋骨走得更远，您会看到它们相交。
多亏了Delaunay三角剖分，我们看到现在有了许多三角形而不是多边形。 这非常有用，因为我们将区域划分为可以渲染的三角形。 此技术可用于图形的细分或三角剖分。 太好了！
此外，这是从多个点创建图形的好方法，以防我们要从一个点移动到另一个点。 例如，点可以指示城市。
Voronoi数据结构
我们已经知道Voronoi图是什么样子； 现在，让我们看看它的数据结构如何。 首先，我们需要保存作为Voronoi图基础的点：
class VoronoiPoint { float x float y VoronoiRegion* region }
每个
VoronoiPoint都有一个位置
(x, y)以及指向其所在区域的链接。
接下来，我们需要描述
VoronoiRegion ：
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
该区域存储了指向其
VoronoiPoint的链接以及
VoronoiEdges的
VoronoiEdges边缘的列表。
让我们看看
VoronoiEdges是什么
VoronoiEdges ：
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
边知道定义它的两个点以及它们之间的距离。 对于视觉显示以及构造多边形区域的形状，我们需要存储边缘的起点和终点。
仅此而已。 有了这些信息，我们可以轻松地构建Voronoi图。 下面我们将学习如何生成Voronoi图。 现在，让我们看几个如何使用此数据的示例。
查找离您最近的药柜
再次，查看Voronoi图以获取积分。
如果每个点都表示一个急救箱，那么我们可以快速确定最接近我们的地方，但是首先我们需要确定我们所在的区域。 Voronoi图没有提供定义区域的有效方法，但是，为了加快搜索速度，我们可以在
象限树或
R树中存储指向每个区域的链接。 在了解了该地区之后，我们将能够识别该地区的邻居以及该地区的邻居。
例如，如果您所在的地区不再有急救箱，那么您需要找到通往另一个最近急救箱的路径。 从上面显示的数据结构和伪代码，我们可以了解到，知道该区域，就可以识别其边缘。 在这些肋骨的帮助下，我们可以结识邻居。 我们将带上最近的邻居，看看其中是否有急救箱。
您也可以在此处应用Delaunay三角剖分。 它由急救箱之间的线组成。 然后，您可以使用A *路径搜索算法解决该问题，以找到最近的急救箱。
寻找安全的路线
用敌军watch望塔替换所有急救箱。 您需要找到它们之间最安全的路线，以免被抓住。 电子游戏中图形遍历的标准方法是使用
A *算法 。 由于Voronoi图是图形，因此实现搜索非常容易。 我们只需要A *算法即可，它支持一般的图形结构； 提前计划，它将对您将来有所帮助。
准备好图形后，您需要为每个边缘分配权重。 对于我们来说，权重值就是到这些钟楼的距离，您可以直接从数据结构中获取它：每个
VoronoiEdge知道其在两点之间的距离。 通常，边A *上的值越小越好，但是在我们的示例中，该值越大，因为它表示到塔的距离。
如果要从点A移至点B，则初始图形如下所示：
将权重应用于每个边缘，我们将看到哪个路线更好选择：
红色的肋骨表明与塔的最近接触点。 橙色表示更长。 黄色甚至更远，最后是绿色-最安全。 在使用这些权重执行A *之后，我们得到以下路径：
通过这种秤的使用，不是
最快的方法 ，而是
最安全的方法，这正是我们所需要的。 AI应该坚持这条道路，而不是偏离它！
您可以采取另一步骤来
保证安全的路径：消除比最小安全距离近的所有边。 例如，如果每个watch望塔的可见半径为30个单位，则可以从图形中删除所有边线（点到点之间的距离较短），而不会绕过。
您也可以使用此方法为无法通过瓶颈的大型设备找到最宽的路线。 每个边缘在两个点之间有一个距离，因此我们知道它们是否可以在此空间中通过。
您也可以执行相反的操作-使用Delaunay三角剖分图，并获取来自每个watch望塔的线路。 警卫的AI将能够快速确定附近还有哪些塔楼，并在必要时提供帮助。
搜索包装紧密的物品
假设我们需要从飞机上放下一块猫薄荷包裹，以便将一堆海豹坐在地上。 最好的丢弃方式是什么，以便最多的猫可以使用它？ 这可能是非常昂贵的。 但是，幸运的是，我们可以使用Delaunay三角剖分进行合理的假设。
提示：不要忘记Delaunay三角剖分只是Voronoi图的逆。 它是通过将每个Voronoi点与从边列表中获得的相邻点连接而形成的。
使用此三角形集合，您可以探索每个三角形所覆盖的区域。 如果找到面积最小的三角形，则我们有三个最近的点或猫。 它可能不是表面上最密集的平均簇，但这将是一个很好的假设。 如果我们可以用薄荷丢弃一些包裹，则只需标记已选择的三角形，然后按递增的尺寸移动到下一个三角形。
这种区域的名称也称为Delaunay三角剖分的
外接圆 。 每个圆是可以适合三角形点的最大圆。 这是Voronoi图的外接圆的图像：
您可以使用圆圈的确切中心来确定运送猫薄荷的区域的中心。 实际上，圆的半径是确定最佳折叠三角形的一种更合适的方法，而不是确定三角形的面积，尤其是在三角形的两个点彼此非常靠近且第三个点很远的情况下； 那么我们会得到一个面积很小的非常尖锐的三角形，但是定义它的点实际上相距很远。
Voronoi图的实现
有几种生成Voronoi图的方法，所用方法的选择取决于我们接收数据的时间。
财富算法
最快的方法称为
财富算法 。 它以
O(n log(n))运行，并且要求在生成开始时就知道用于生成图形的所有点。 如果以后添加新点，则必须重新生成整个图形。 如果只有几个要点，则可能不会引起问题，但是如果有10万个要点，则可能要花费很多时间！
该算法的实现是不平凡的。 交叉抛物线和特殊情况。 但是，这是最快的方法。 幸运的是，您可以使用此开源算法的许多实现，并且在下面提供了它们的链接。
让我们看看它是如何工作的。
该算法包括在具有点的区域上滑动一条线（垂直或水平）。 当他遇到一个点时，他开始从中画出一条抛物线，并以一条扫掠线继续。 这是此过程的动画：
相交的抛物线形成Voronoi肋骨。 但是为什么要抛物线？
要理解这一点，可以想象每个点都包含一个充气气球，该气球会膨胀直到与另一个球碰撞。 您可以将此想法转移到在2D平面上扩展的圆上。 我们将使另一个球向前移动，并在每个点处放置一个倒锥，其倾斜角度为45度，并增加到无穷大。 然后想象一条线状的扫掠线，也是45度，它会一直滑动直到与圆锥体碰撞。 由于平面和圆锥体位于同一角度，所以当它们交叉时，它们会形成抛物线。
长大后，视锥早晚与一个或多个其他视锥相交。 如果我们查看圆锥或圆的相交，我们会得到Voronoi边缘的直线。 在图中，红线表示圆锥的相交。 如果视锥细胞进一步扩大（垂直向上达到无穷大），则红线将继续延伸。
当平面滑动并且第一次与圆锥接触时，结果线将如下所示：
随着平面沿着圆锥的进一步移动，我们将看到抛物线是如何形成的：
飞机继续在场景中移动。 对于遇到的每个点，它将检查扫掠线上已经具有抛物线的相邻点，并在该点处开始一个新的抛物线。 她继续前进并成长，直到这种新的抛物线开始与之前叠加的抛物线重叠。 然后，之前的抛物线关闭。 这是Voronoi的三点线相交的点。
如上所述，这是很难理解的，因此这里是您可以使用和学习的开源实现的链接：
增量三角形插入
另一种方法是一次递增地插入一个点，从所有其他点的可能区域之外的三个点的基三角形开始。 此方法以
O(n^2)运行，并且在生成时不需要所有点。
插入新点时，它定义了它所属的现有区域。 然后细分该区域并创建新区域。
这是一个使用和学习的开源示例：
结论
现在，您必须想象Voronoi图可以为您的游戏及其AI提供什么。 如果您具有适当结构化的节点和边缘图，则可以索取重要信息，以便每个人都可以得到急救箱，猫薄荷，并越过敌人的防御塔。