旁注：我不确定这个问题是否属于游戏开发堆栈交换站点 - 但是，我觉得它属于这里，因为虽然上下文是游戏，但我希望实现的算法本身与应用程序无关。此外，我不是在寻找一种高级技术，因为我觉得我已经建立了一种，而是我正在寻求针对某个问题的更具体的帮助。无论如何，对于这个问题：
嘿大家！
我正在开发一个多人游戏，该游戏要求服务器可以为服务器控制的实体执行寻路。服务器是一个直接的 C# 应用程序，客户端使用 Unity 游戏引擎。在服务器上使用 Unity 不是一种选择。此外，我想完全避免使用本机库。
我已经检查了 Detour 的寻路功能，尽管它们确实有 C# 端口，但我宁愿自己实现实际的寻路位；因为这个过程足够简单，我希望它可以根据我的需要进行定制，以便它可以很好地与服务器上的现有组件配合使用。
Unity 内置了对 Recast/Detour 的支持。这很好，因为我可以在 Unity 中使用 Recast 来生成导航网格；然后使用我自己的寻路在服务器上使用它。问题是我似乎找不到合适的方法来根据 Unity/Recast 创建的网格生成图形。
我需要做的是在内存中创建一个图形，其中每个节点都是网格中的一个三角形，图形的每条边连接两个彼此相邻的三角形。
我能够从 Unity 的 API 中提取的唯一数据是生成的网格的顶点和三角形索引，因此我需要重新构建自己的图形。我的第一个实现只是为每个三角形创建一个节点，如果该三角形与另一个三角形共享另外两个点，则在它们之间创建一个链接 - 形成我的图形的边缘。
虽然这对大多数网格都很有效，但它不够用，因为似乎 Unity 正在吐出可以在区域（多边形）之间具有连接（边）的网格，即使它们不共享两个顶点。这是 Unity 将其生成的导航网格覆盖到我的关卡几何上的示例（Unity 确实将三角形合并为凸多边形，而我的代码没有 - 但是，无论哪种情况，问题仍然存在）
在此示例中，我生成的图形需要连接由白线分隔的多边形（我找不到任何解释为什么它在 Unity 中呈现为白色的文档）但无法这样做，因为它们只共享一个顶点。
我想知道是否有一种有效的算法来检测这些情况。我正在考虑做的是让多边形被认为是连接的：
if (sharedVertexCount == 2)
connectPolygons()
else if (sharedVertexCount == 1)
Vector3[] parallelLine = findParallelLineSharedByBothPolygons()
if (parallelLine != null)
Vector3 otherPoint = getUnsharedPointInLine(parallelLine)
if (isPointInLine(parallelLine, otherPoint))
connectPolygons()
我认为这应该可行，但我没有找到有效地做到这一点的方法。此外，我在“isPointInLine”实现方面遇到了一些麻烦，因为显然我的数学技能比我想象的要生疏。
无论哪种方式，都必须有一个更简单的解决方案；但是我在网上找不到任何东西可以将我指向那个方向......这就是为什么我问你们好人是否有什么我可以做的事情来有效地将生成的导航网格转换为连接的多边形图。无论是帮助我实现 isPointInLine 还是为我指明一个更明智的算法的方向，我都会感激不尽。