欢迎来到优美算法小组！
作为实验，我们决定保留开发人员的“日记”，在其中我们将分享经验并重点介绍实验的一些有趣结果。 这是我们在“ Pathfinder 3D”项目上的首篇文章，该项目是Unity游戏引擎的资产，它使您可以在三维空间中搜索路径。 在其中，我们将讨论从思想的起源到成熟的产品的路径，以及我们遇到的一些问题。 对于希望开始其项目并在将来提供支持的人们，以及对于那些希望在太空中进行探索的人们，该材料将非常有用。
一个由两个人组成的团队开始对该资产进行工作。 第一个进行了一些开发，可以加快在复杂图上找到最短路径以充分实时运行的过程，并且渴望为它们找到实际的应用程序;第二个则具有与Unity合作的经验，并且正在寻找创业的想法。 由于他们经常相互交流，因此在某个时候出现了创建资产以在三维空间中搜索路径的想法就不足为奇了。
在研究Unity资产目录时，发现了许多解决方案来在二维空间中找到路径，而在三维空间中找不到一处。 很明显，这是进入Unity软件附加产品市场的绝佳机会，尤其是考虑到预期结果的可见性和娱乐性。
目标是直接实现在三维空间中的路径搜索以及现有解决方案在二维空间中寻找路径的典型功能。 我们开始工作：一种直接开发路径搜索机制，第二种用于管理路径搜索过程，配置界面，测试场景，文档，项目站点的类和方法，还参与注册和设置出售资产所需的服务帐户。
在工作开始后不久，很明显，团队需要某种共同的资源来做笔记：一系列需要解决的任务和问题，有关决策的信息，有趣的想法和未来的研究成果。 在分析了现有解决方案之后，我们在
Trello停留了，因为它的功能，简单性，便利性和令人愉悦的外观。 如实践所示，此服务对于小型团队非常方便。 如果团队有5个以上的人员，我们建议使用成熟的项目管理系统。
接下来，我们描述在开发资产的第一个版本期间做出的决策，以及制定决策时遵循的逻辑。 拥有Unity经验并熟悉寻路算法的人将立即了解将来出现问题的地方。 在这些地方，我们使用一种简单的解决方案来减少开发时间，直到收到该资产的第一个工作版本为止，以免陷入困境，因为热情有限且不稳定。 因此，我们处理了关闭此类创业公司的最常见原因之一，因为许多项目因此而生而死。 资产发布后，所有问题区域均已得到纠正。
为了找到路径，选择了
A *（A星）算法，因为它在大型开放空间中的运算速度很高。 大多数路径搜索算法都适用于由离散矩阵表示的图。 可以预先构造此矩阵，但是在具有障碍的三维空间中进行一次构造的过程在当时是一项相当困难的任务。 此外，不清楚如何在不牺牲性能的情况下执行此操作，因为在开始进行资产工作时，还没有使用Unity中的后台进程和多线程以及通常使用多线程的经验。 该图是通过在搜索方向上用物理射线（Physics.BoxCast）探测空间实时形成的。 将找到的轨迹简化为中间点较少的折断轨迹，然后通过样条曲线进行平滑。
主要的困难是不可能异步使用引擎的物理方法，因为它们只能在主线程中工作。 在不太复杂的场景中，同时使用不超过二十个代理的搜索功能不会显着影响帧速率。 为了摆脱罕见的FPS大幅下降，使用协程在时间上间隔了计算负荷。 这减慢了搜索速度，但效果不明显。
在提交资产进行审核之前，您需要按照要求整理代码，并草拟详细的文档，并注册和配置支持邮件。 还建议创建一个项目网站，以方便地显示开发新闻和演示。 无论是在审核通过期间，还是在购买前由用户研究您的资产时，这都是一大优势。 托管和邮件服务是我们从
BeGet订购的，因为当时它提供了最优惠的价格，并且每年的费用为1000r。
资产审核持续了22天并首次通过，因为我们非常仔细地访问了Unity存储中的文档和资产页面的设计。 发布后，该资产立即在脚本/ AI类别中排名第一。 从那一刻起，信件开始出现在支持邮件中，要求您解决某些问题。 有时每天几天，有时不是一个月。 如果您平均，那么一个月中有2个人询问问题，与之通信总共花费了2-3个小时。 并不是很多，但是应该记住的是，无论您当前的工作量如何，您都需要非常迅速地做出响应，以便愤怒的用户不会对产品发表不良评论，相反，对于质量支持充满热情，请留下积极的评论。 另外，邮件中也有很多问题，例如“如果...，您的资产会工作吗？”。 此类信件也不容忽视，因为这是一个可以离开的潜在买家。
收到第一批购买者的投诉后，很明显，许多用户在具有迷宫式或其他相连空腔结构的复杂场景中使用资产。 在这样的项目中，即使基于主流，我们基于冲突检查的寻路方案也不够有效。 因此，我们开始实施图形的早期构造，以便可以在不使用物理方法和访问场景对象的情况下，在支流中搜索路径。
三维空间的离散化将其分解为立方体。 存储有关所有分区多维数据集的信息是多余的，并且占用大量内存。 因此，这样做是合乎逻辑的，即仅存储无法通行的单元的坐标。
游戏障碍物是多边形，由三角形组成。 要在搜索图中考虑障碍物，必须找到与任何障碍物的任何三角形相交的分区的所有立方体。 在此阶段，已经奠定了动态移除障碍物并向其添加障碍物的可能性，不仅节省了所占用立方体的坐标，还节省了其中障碍物的标识符。 现在可以在游戏过程开始之前构建导航图，并且由于消除了在搜索路径期间的大量复杂计算，因此有两百多名特工可以同时制作它而不牺牲性能。
我们还知道另一个问题，那就是：A *算法及其修改在高幂图的有限空间中的工作情况极差。 由于他们的算法偏向于接近目标点的路线方向，因此任何导致目标的死锁都会极大地减慢对路径的搜索，因为在选择其他“发芽”方向之前，该算法首先“填充”了死角内部的整个空间。
在这种情况下，由于“填充”空间所需
的操作次数较少 ，因此
波动搜索算法（李算法）被证明非常有效。 因此，它是作为替代添加到资产中的。 在迷宫的舞台上进行测试时，路径的搜索时间减少了30倍以上。
为了加快场景的初步处理并找到资产的路径，增加了并行执行流程的可能性，但是并行效率极低，这是因为在使用存储占用单元格坐标的容器时，必须同步流，这是使用互斥锁，因为竞争性集合和许多其他工具可确保高效的同步仅在.NET Framework 4.5标准中实现，而在Unity中，直到2018年发行版都使用.NE版本。 T Framework 3.5。 我们尝试使用可用的工具解决此问题，但它们的性能非常中等，并且只有切换到2018 Unity版本后才能获得所需的结果。 竞争性收藏的使用也为实现场景中障碍物的动态变化提供了可能性。
在某个阶段，团队中就利润分配开始出现分歧，第三人加入了团队，该团队引入了评估团队每个成员的时间投入的系统，并开始参与代码检查和测试，从而显着提高了产品质量。
目前，用于估算时间成本的系统以Excel表格的形式构成，并且是一个自动化系统，在该系统中，您每月需要输入一次有关过去一个月中完成的销售和任务的信息。 团队成员需要评估解决特定问题所需的时间。 因此，在评估任务的时间复杂度时，要考虑每个参与者的速度。 参与者之一的异常高估或轻描淡写立即从其先前评估的累积统计数据中变得明显。 并且，在没有令人满意的解释的情况下，此问题由整个团队决定。 实践证明，这种方法可以使用六个月，并且可以收集有趣的统计数据。 我们没有找到可以提供所描述功能的现成的免费解决方案。 因此，目前，对于小型团队来说，以Excel表格的形式实现对我们来说似乎是最佳选择。 对于规模较大的团队，您很可能必须设计数据库，开发服务器部件和客户端，或者为现有项目管理系统之一实施扩展。
总结一下。 从开发开始到第一版已经过去了一年，它具有在实际项目中使用的最少必需的功能和足够的性能。 另外六个月用于改善性能和实施资产的多线程工作。 目前，我们估计该项目的时间成本为1065个工时（这是一个相当乐观的估计），该月的平均利润为9.5吨。 可以很容易地计算出，目前一个小时的平均工作成本约为160卢布，不是很多。 但是，此事件中最主要的是每个参与者获得的经验。 包括团队合作经验和软件产品支持经验。 该项目可以被认为是成功的。
现在我们的团队已经开始实施其他有用的功能：算法可达性验证； 将游戏对象分配给门户的能力； 动态障碍物支持； 代理之间的本地导航，以防止冲突并计划本地路线。
我们希望这种材料可以帮助某人将他们的项目带到终点。