在创建
《见证人》的过程中，
它已经成为我最喜欢的游戏之一。 从
乔纳森·布洛（Jonathan Blow）开始开发它的那一刻起，我就开始演奏它，迫不及待地想要发布它。
与约翰·
布雷德（ John
Braid）之前的游戏不同，
见证人（The Witness）的资源和编程规模更接近AAA项目，而不是独立游戏。 每个从事此类项目的人都知道，选择此路径时的工作量会大大增加。 与《
辫子 》相比，
《见证人》上工作的人很多，但是与该级别的任何项目一样，许多方面需要更多的关注，而项目管理人员则无法承受。
因此，在发布游戏时，我一直想找到空闲时间来帮助创建
The Witness 。 因此，有一天，感恩节，约翰和我坐下来，看了一下代码库中可以从另一位程序员的额外努力中受益的事情清单。 在确定了列表中项目的相对重要性之后，我们决定，如果我们改善玩家的移动代码，那么游戏性将受益最大。
墙上的Walkmonster
在
《见证人》的背景下，玩家的移动代码的目标是尽可能不引人注目。 玩家必须完全沉浸在替代现实中，在这种游戏体验中，每个细节都很重要。 我们想要的最后一件事是让玩家注意到他正坐在计算机旁并在移动虚拟摄像机。
因此，玩家的移动代码必须绝对可靠。 如果玩家紧贴角落，卡在墙壁中，从地板掉下，从山上掉下来而无力返回等，这将立即消除沉浸感，并提醒玩家他处于虚假的游戏过程中，受到不可靠系统的干扰。位移。 在某些情况下，如果玩家没有机会通过重新启动游戏或重新加载（可能很旧）的“保存”来解决问题，甚至可能给玩家带来灾难性的后果。 如果您经常玩游戏，那么您一定会遇到此类问题，并且您知道我的意思。
在讨论之后，我开始着手这项任务。 首先，我决定编写用于处理玩家运动代码的集成工具，以便我们可以对其进行分析并观察其当前行为。 打开项目后，我遇到了一个我已经知道的严重问题：我应该如何命名第一个源代码文件？ 这始终是任何项目中最重要的部分（
就像鲍勃·波拉德 （
Bob Pollard）曾经说过的音乐团体和专辑的名称一样 ）。 如果给源文件起一个合适的名称，那么进一步的工作将是清楚而顺利的。 选择错误的一个-您可能会破坏整个项目。
但是，确保玩家动作代码质量的系统名称是什么？ 我以前从未写过这样的代码。 当我考虑到这一点时，我意识到我自己只看到了一个这样的代码示例：在玩
Quake的早期Beta时。 它包含与怪物位置有关的错误，在控制台窗口中，您会看到错误消息，指出已创建怪物，而不是在地球表面上创建怪物，并且部分与关卡的几何形状相交。 每条调试消息均以短语“ ...处的墙壁走动怪物”开头
宾果！ 找到比“ walk_monster.cpp”更好的代码文件名称是很困难的。 而且我几乎可以确定，从现在开始，代码将毫无问题地被创建。
运动到点
当您要测试系统时，最重要的是
实际测试系统 。 尽管此规则看起来很简单，但是编写测试的人经常无法遵守。
在我们的特定情况下，很容易
想象我们正在测试玩家的移动代码而没有实际对其进行测试。 这是一个示例：您可以分析在游戏中可以移动的碰撞和曲面的数量，寻找较小的曲面，间隙等。 消除了所有这些问题后，我们可以说现在玩家可以安全地在世界各地移动和行走了。
但是实际上，我们测试了数据，而不是代码。 即使使用高质量的数据，运动代码中也很可能会导致错误行为，从而导致不良行为。
为了避免这种陷阱，我希望测试系统尽可能接近实际控制游戏中角色移动的人员的行为。 我首先编写了两个程序，这些程序将成为此类测试的基础。
第一个过程最接近真实的人类行为。 这是一个更新调用，它连接到
The Witness的输入处理系统，并将合成的键盘和鼠标事件传递给它。 一个人可以做的简单的事情：环顾四周，朝某个点，看着某个点等等。 该过程通过简单地模拟用户与键盘和鼠标的交互来执行这些操作，因此我确信在处理
The Witness的输入时，所有操作都将像在测试期间一样进行。 在以下文章中，我将详细讨论该系统及其使用。
第二个步骤是此级别未使用的一个步骤。 这是一个称为
DriveTowardPoint的函数，该函数接收世界上的两个点，并导致玩家现有的碰撞系统试图从一个点无缝移动到另一个点。 执行返回操作时，她会发送有关尝试的信息：她在途中遇到了什么障碍，以及是否设法到达终点。
此功能不如使用合成输入的测试方法可靠，因为它从测试中消除了玩家运动系统的一部分。 例如，如果碰撞系统出现问题，与玩家位置相关的任何错误状况都不会影响使用此功能进行的测试。 不过，我认为这种级别的测试很有价值，因为它可以更快地测试广阔的区域，因为它不需要执行整个游戏周期，也就是说，它可以在全世界更多地使用，而不仅仅是在单独的测试中使用。
还值得注意的是，该功能不会传输物理输入数据； 例如，没有为起点指示速度。 这是因为
“见证人”不是一款动作游戏，因此玩家几乎没有什么明显的物理属性。 玩家无法跳跃，在墙壁上奔跑或开启子弹时间。 您可以使用稍后将描述的系统来支持此类行为，但是它们会增加项目中所不需要的复杂性级别。
不管怎样 ，在实现
DriveTowardPoint之后，我可以开始解决系统的第一个任务：确定玩家可以移到
见证岛的位置。
快速探索随机树
玩家可以去哪里？ 这似乎是一个简单的问题，但是当开发团队不知道真正的答案时，您会惊讶地发现发布了多少款游戏。 如果可能的话，那么我希望
《见证人》成为少数几款游戏之一，在这些游戏中，开发人员在发行前确切地知道玩家可以及不能获得的位置-毫不奇怪。
这使问题陈述（但可能不是其解决方案）非常简单：如果有一个
DriveTowardPoint函数可以可靠地确定玩家是否可以在两点之间直线移动，请创建一个覆盖图，显示玩家可能在哪里。
出于某种原因，由于无需编写任何代码，出于某种原因，我认为最好使用
快速探索随机树 。 对于那些不熟悉该算法的人，我将进行解释：这是一个非常简单的过程，在该过程中，我们会记录所有访问过的点，并以此作为起点。 要在树上添加一个点，我们在世界上任何地方获取一个随机的目标点，选择树中已有的最接近它的点，然后尝试从该点到达目标。 我们最终到达的地方将成为下一个采样点。
通常，此算法用于搜索路径：对于随机点，我们总是选择与目标相同的点。 这倾向于朝目标点探索空间，而这是我们唯一的任务是实现目标时所需要的。 但是在这种情况下，我想为玩家可能落入的地方创建完整的地图，因此我仅使用随机样本。
实施此算法后（幸运的是，它非常简单并且不需要太多时间），我发现他在探索空间方面做得很好（显示的路径用白色路径表示，垂直的红色线条表示算法与障碍物碰撞的位置） ：
但是，观察他的行为后，我意识到实际上我不需要这种算法。 例如，即使经过多次迭代，他仍然无法探索类似于以下所示房间的房间，尽管外面的区域覆盖范围很广。 这是因为他根本无法在房间内选择足够的随机点：
如果我在开始工作之前就考虑了这一点，那么我将理解，像快速探索随机树这样的算法的优势在于它们可以有效地探索高维空间。 实际上，这通常是使用它们的主要原因。 但是
见证人没有高维空间。 我们有一个二维空间（是的，分布在一个复杂的物种上，但这仍然是一个二维空间）。
在这种低维空间中，快速探索随机树的优势很弱，其缺点对我的任务至关重要：该算法旨在最有效地搜索空间中连接的点对的路径，而不是有效搜索该空间中所有可到达的点。 如果您有这样的任务，那么实际上快速探索随机树将花费大量时间来解决它。
所以我很快意识到我需要寻找一种有效地完全覆盖低维空间的算法。
3D洪水填充
当我真正考虑选择算法时，很明显，实际上我需要像老式的二维填充那样的东西，该东西用于填充位图的区域。 对于任何起点，我只需要填写整个空间，并详尽检查所有可能的方式。 不幸的是，由于多种原因，
“证人”的解决方案比二维位图要复杂得多。
首先，我们对点的有限连通性没有明确的概念。 所有空间都是连续的。 这是针对一个像素的，我们可以轻松列出从给定点可以到达的4个可能的位置，并依次检查每个位置。
其次，空间中没有固定的位置大小，例如位图上的像素。 玩家在其上移动的表面以及障碍物可以在任何地方，它们没有最大或最小的拓扑大小，也没有绑定到任何外部网格。
第三，尽管可以将
见证人空间中的移动局部地视为沿着平面移动，但该空间本身实际上是一个相互联系且变化多端的流形，其中玩家的可步行区域位于其他区域的正上方（有时可以有多个级别位于另一个之上） 。 此外，根据世界情况（打开/关闭的门，上升/下降的电梯等），连接也会有所不同。
考虑到所描述的困难，提出自己的版本的fill实现非常简单，结果将充满相交区域，缺少重要的路线以及有关歧管复杂位置的连接的错误信息。 最后，该算法将过于笨拙，因为要考虑到世界状况的变化，必须重新运行该算法。
我没有立即想到任何好的解决方案，因此我决定从简单的实验开始。 使用我编写的
快速探索随机树代码，我将目标点的选择从随机更改为高度受控。 每次将新点添加到树中时，我都会指出，这些点沿主方向与要被视为未来目标点的点之间的距离为单位距离，就像在简单的二维填充中一样。
但是，当然，如果不小心的话，这将创建一个无用的采样周期。 该点将分支到周围的8个点中，但是这8个点将再次尝试返回起点，并且将一直持续下去。 因此，除了对目标点的受控选择外，我还需要一个简单的限制：不在距现有目标点一定最小可用距离之内的任何目标点都不会被考虑在内。 令我惊讶的是，这两个简单的规则创建了一个非常成功的填充：
对于一个相当简单的实验来说还不错。 但是该算法遭受了我称之为“边界回波”的困扰。 在研究地图期间拍摄的以下屏幕截图中可以看到这种效果：
在没有障碍物的区域，该算法通过以相对相等的距离进行采样可以很好地工作。 但是，当相交点触及边界时，它们将创建“在网格外部”的点，也就是说，它们并未根据样本的模式对齐，从而根据算法填充了相邻的开放区域。 “在网格中”的点不会产生过高的镶嵌效果的原因是，每个试图返回到先前点之一的新点都在此处找到了先前点，并拒绝再次对其进行重新计数。 但是，在边界上创建新点时，它们完全不对齐，因此无法阻止它们返回已探索的空间。 这会导致产生一堆有偏差的样本，该样本会持续到到达随机靠近其他地方的点的随机线为止，以便算法可以找到与点的移动前沿一致的位置。
尽管这似乎不是一个严重的问题，但实际上是至关重要的。 这种算法的重点是将样本集中在最有可能产生成果的区域。 我们花更多的时间对广阔的空白区域进行采样和重新采样，花费在标记该区域的面孔上的时间就越少，这些正是我们所需要的信息。 由于我们正在处理连续空间，并且其无数个样本可以描述其真实形状，因此有效样本与无关紧要样本的比率实际上是算法在创建玩家可传递的曲面时的有效性的度量。
但是，有一个针对此特定问题的简单解决方案：您需要扩大将两个点视为“非常接近”的距离。 这样，我们将减少
对我们
不重要的地方的采样密度，但也会在
对我们
不重要的地方失去采样密度，例如，我们要仔细检查边界是否存在“空洞”的区域。
局部定向采样
可能是因为我从快速探索随机树开始，所以我的大脑取代了其他所有想法，除了邻近性想法。 例如，所有先前的算法都将接近度用于其任务，以便确定下一个需要考虑的新点，或者选择要从中开始到达新目标点的点。
但是在考虑了一段时间后，我意识到，如果我们不仅考虑邻近性，而且考虑
方向 ，一切都会变得更加合乎逻辑。 然后它变得显而易见，但是如果您从事类似的任务，那么您知道很容易陷入狭it的思维陷阱而看不到大局，即使事实证明这很简单。 那正是我发生的事情。
当我改变对事物的看法时，正确的抽样方法似乎显而易见。 每当我想从一个点扩展对空间的探索时，我都要求在本地环境中存在附近的点。 , , ( , ).
, «» , , ( , -, ). - , , . , , , . , , .
. , , :
, , , :
, . , , . , , .
, . , ? . , ( - ).
, , , , . , , , , .
, , . , , . , , , , .
. , :
:
, , .
, , Walk Monster , . , :
, . , . , , , .
The Witness , , , , , . , , - . , , , , .
, Walk Monster , . — Walk Monster , - ( — ), . , ( ). !
, , . , , ! , , . , .
-, , ? , , , , .
-, , «»? , , ?
-, — ? , , , , , .
-, , ? , , , - , . ? ?
, Walk Monster , , . , , . . , , - , Walk Monster .