视频地址:https://www.youtube.com/watch?v=-L-WgKMFuhE

参考:

https://www.youtube.com/watch?v=1-YPj5Vt0oQ

https://github.com/DevonCrawford/A-Pathfinding-Visualization

G = node和起点的距离

H = node与终点的距离

F = G cost + H 

定义开节点列表
定义闭节点列表
添加开始节点到开节点列表
开始循环
      当前节点 = 开列表中F值最小的节点
      将当前节点从开列表中移除
      将当前节点添加到闭列表
     如果当前节点等于目标节点
           返回
     遍历当前节点周围的8个临近节点
           如果临近节点是不可通行的或者临近节点属于闭列表
                跳过该临近节点
          
           如果到临近节点的新路径更短或者临近节点不在开列表
                 设置临近节点的F值
                 设置临近节点的父节点是当前节点
                 如果临近节点不在开列表中
                       添加临近节点到开列表

https://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

简单的愚蠢漏斗算法

[EDIT] 修复了下面的示例场景.

在 AIGameDev.com上有一个很好的关于寻路的大师班：Alexander Kring的分层寻路提示和技巧。关于 Left 4 Dead路径平滑的那张幻灯片让我感到很烦恼。令人遗憾的是，人们仍然使用“让我们追踪多边形边缘中点”作为路径平滑的参考算法。真的很伤心。

漏斗算法是一种简单的算法，可以沿着门户找到直线路径。最详细的描述可以在基于高效三角测量的寻路中找到。

这里是简单的愚蠢漏斗算法的实现。简单的愚蠢漏斗算法运行循环并在添加新角时从早期位置重新启动循环，而不是使用队列和所有那些花哨的东西。这意味着某些门户网站的计算频率可能比可能需要的更多，但它使实现更加简单。



上图显示了该算法的六个步骤。每当我们处理新的门户边缘（以黄色突出显示的虚线）时，我们首先：

• 检查左右点是否在当前漏斗内（由蓝线和红线描述），如果是，我们简单地缩小漏斗（AD）。

• 如果新的左端点位于渠道之外，则漏斗不会更新（EF）

• 如果新的左端点位于右侧漏斗边缘（F），我们将右侧漏斗添加为路径中的一个角，并将漏斗的顶点放在右侧漏斗点位置，然后从那里重新启动算法（G）。

同样的逻辑也适用于左边缘。重复此过程，直到处理完所有门户边缘。

如上例所示，由于重启，算法会多次重新计算一些边缘，但由于计算非常简单，这个简单的愚蠢技巧使实现更加简单，实际上也更快。

inline float triarea2(const float* a, const float* b, const float* c)
{
 const float ax = b[0] - a[0];
 const float ay = b[1] - a[1];
 const float bx = c[0] - a[0];
 const float by = c[1] - a[1];
 return bx*ay - ax*by;
}

inline bool vequal(const float* a, const float* b)
{
 static const float eq = 0.001f*0.001f;
 return vdistsqr(a, b) < eq;
}

int stringPull(const float* portals, int nportals,
         float* pts, const int maxPts)
{
     // Find straight path.
 int npts = 0;
     // Init scan state
 float portalApex[2], portalLeft[2], portalRight[2];
 int apexIndex = 0, leftIndex = 0, rightIndex = 0;
 vcpy(portalApex, &portals[0]);
 vcpy(portalLeft, &portals[0]);
 vcpy(portalRight, &portals[2]);

     // Add start point.
 vcpy(&pts[npts*2], portalApex);
 npts++;

 for (int i = 1; i < nportals && npts < maxPts; ++i)
 {
     const float* left = &portals[i*4+0];
     const float* right = &portals[i*4+2];

         // Update right vertex.
        if (triarea2(portalApex, portalRight, right) <= 0.0f)
  {
         if (vequal(portalApex, portalRight) || triarea2(portalApex, portalLeft, right) > 0.0f)
         {
              // Tighten the funnel.
             vcpy(portalRight, right);
             rightIndex = i;
         }
         else
         {
                 // Right over left, insert left to path and restart scan from portal left point.
             vcpy(&pts[npts*2], portalLeft);
             npts++;
                 // Make current left the new apex.
             vcpy(portalApex, portalLeft);
             apexIndex = leftIndex;
                 // Reset portal
             vcpy(portalLeft, portalApex);
             vcpy(portalRight, portalApex);
             leftIndex = apexIndex;
             rightIndex = apexIndex;
                 // Restart scan
             i = apexIndex;
             continue;
         }
     }

         // Update left vertex.
        if (triarea2(portalApex, portalLeft, left) >= 0.0f)
  {
         if (vequal(portalApex, portalLeft) || triarea2(portalApex, portalRight, left) < 0.0f)
         {
                 // Tighten the funnel.
             vcpy(portalLeft, left);
             leftIndex = i;
         }
         else
         {
              // Left over right, insert right to path and restart scan from portal right point.
             vcpy(&pts[npts*2], portalRight);
             npts++;
                 // Make current right the new apex.
             vcpy(portalApex, portalRight);
             apexIndex = rightIndex;
                 // Reset portal
             vcpy(portalLeft, portalApex);
             vcpy(portalRight, portalApex);
             leftIndex = apexIndex;
             rightIndex = apexIndex;
                 // Restart scan
             i = apexIndex;
             continue;
         }
     }
 }
     // Append last point to path.
 if (npts < maxPts)
 {
     vcpy(&pts[npts*2], &portals[(nportals-1)*4+0]);
     npts++;
 }

 return npts;
}

数组门户网站具有路径的所有门户网段，以简化第一个左边缘点和右边缘点。第一个门户的左侧和右侧位置设置为起始位置，最后一个门户左侧和右侧位置设置为路径的结束位置。像这样的东西：

// Start portal
vcpy(&portals[nportals*4+0], startPos);
vcpy(&portals[nportals*4+2], startPos);
nportals++;
// Portal between navmesh polygons
for (int i = 0; i < path->npolys-1; ++i)
{
 getPortalPoints(mesh, path->poly[i], path->poly[i+1], &portals[nportals*4+0], &portals[nportals*4+2]);
 nportals++;
}
// End portal
vcpy(&portals[nportals*4+0], endPos);
vcpy(&portals[nportals*4+2], endPos);
nportals++;

很酷的是，这个算法几乎可以用于任何导航格式。让它成为网格，四叉树，连通方格，路点或导航网格。只要您传递一个描述门户网站从一个节点到另一个节点的线段列表。

当与转向结合时，该算法也很棒。您可以通过计算接下来的几个转弯和转向下一个转弯来计算所需的移动速度。它是如此之快，以至于您可以在使用自己喜欢的转向代码之前计算每次迭代。

所以你有它。下一个上市并建议使用边缘中点和光线投射在A *之后找到更直接的路径的人将获得他的收件箱充满可爱超载每周选择以煽动他的宠物仇恨。

-----------------------

-----------------------

我可以想到一个漏斗效果不好的情况，这最终让我在我的修改版本中编写了用于在Recast / Detour中使用的光线投影中点技术，这是一个很好的巧合你在写这篇文章上周末很有问题。

如果A *发现的多边形本身不形成直接/平滑的目标路径，则可能会发生令人讨厌的地平线效应。当你随意地试验navmesh创建区域时，这似乎变得更糟（几个月前我写了我自己的实现，不知道你的解决方案，我还没有看到它们有多大差异），你选择的多边形可能有多少作为直线路径的一部分的其他外来多边形的边界，但由于它们的中点太远（通常是因为大的多边形）而没有被A *保留。所以你最终得到的路径在相对开阔的场地中间有这些奇怪的急转弯。无论A *结果如何，Raycasting至少具有寻找更直路径的优势，

我确实想过将光线投射找到的多边形重新用于漏斗算法，但是我觉得有趣的是平滑中点的另一个副作用是它经常使路径更喜欢远离障碍物（假设三角形不是太大） ，但这种情况可以通过采样处理），而不是紧紧地拥抱它们进行急转弯，看起来更自然并留下一些喘息的空间。当然这是一个可能在路径跟随逻辑中处理得更好的问题，但考虑到时间限制，现在它运行得很好。然而，使用本文中的修改漏斗算法可能会很有趣，尽管半径不是严格的排除，更像是一个首选的远离障碍距离，

当然我可能忽略了一些东西，但这是我能在很短的时间内想到的最好的解决方案。我很想知道你以前是否遇到过这个问题，对此有何看法？

---

这不是漏斗算法的问题，而是A *。理想情况下，您不应该修复路径平滑（因为它可以工作），但实际上在A *之后添加了额外的步骤，它试图调整路径多边形列表，以便创建更短的路径。

你应该花费极少的时间来尝试创建平滑的路径，因为当其他人在游戏世界中移动时它会发生变化。

使用转向算法等可以更好地处理像边界拥抱这样的东西，你只需通过这种方式获得更好的结果。

重申一下：

1）A *将图形转换为线性多边形集合，这将使您成为目标。
2）拉弦将告诉你朝向目标的方向
3）运动/转向将负责最终的平滑路径。

这样你就可以做必要的工作。在那个阶段，每一个智能比土拨片都在那里试图解决整个路径的困境，只是做了太多的工作，并且通常会产生不太好的结果，这可以被描述为“更自然，更像人类”;）

---

好帖子！你能谈谈你如何考虑代理半径大小吗？我处理这个问题的方法是迭代平滑点的最终列表，并将它们远离导航网格的边缘。问题是，你移动点的方向是什么，让它们远离导航网格的边缘？这里有一些伪代码来描述我用于偏移的方向：

a = points [i + 1] - points [i] 
b = points [i + 2] - points [i] 
c = Normalize（a * 05 + b * 0.5）
if（ClockwiseTo（b，a））
{ 
offsetDir = Cross（c，up）
} 
else 
{ 
offsetDir = Cross（up，c）
} 
points [i + 1] + = offsetDir * agentRadius

但是，我可以看到一些边缘情况，这不会给出最佳位置。你是如何通过转向处理这个问题的？

----

此实现假定已经调整了门户网站，以便它们包含代理程序半径。例如，navmesh会被代理半径缩小。

这种假设降低了使用navmeshes或任何导航表示所需的所有事情的复杂性。

转向的唯一转角就是当你真的靠近角落时。AFAIK没有很好的方法可以解决这个问题。我通常构建系统，以便我允许代理移动到非常接近角落（例如，0.1厘米），然后选择下一个角落。然后运动代码处理这个额外的污点。您可以查看Recast Demo以获取如何执行此操作的示例。

----

是。“让我们追踪多边形边缘中点”似乎是一个普遍的瘟疫。

我已经使用字符串拉取作为编码器面试问题很长一段时间了（感谢Danny！），60％的结果是“让我们追踪多边形边缘中点”加上一些不可思议的魔法。

到目前为止，只有一个人（实际上没有AI背景）提交了一个漏斗算法版本。

---

我的观点是，开发人员应该更清楚，而不是将他们的新方法与“让我们追踪多边形边缘中点”进行比较。

就好像有人会将Killzone2图形与平面阴影三角形进行比较。

---

Mikko，在你的一条评论中，你说，“理想情况下你不应该修复路径平滑（因为它有效），但实际上在A *之后添加额外的步骤，它试图调整路径多边形的列表，以便它将创建更短的路径” 。我很好奇这将如何运作？我想到的唯一方法是有效的字符串拉动以折叠冗余路径节点。

----

Cam，我没有过多考虑过。要检查的第一件事是看看额外的绕行是否总是以相同的模式发生。例如，A *和多边形的问题几乎总是发生在彼此相邻的大小时。

您可以使用漏斗算法找到的直线路径作为“启发式”来查看某个替代走廊的执行情况。TRA *论文对此有一些讨论。

我的观点是你应该尽可能快地保持字符串拉动，因为当你按照路径时你会不断更新它。

如果路径走廊不够好，那么你应该在问题的根处解决问题，而不是在需要更多处理来完成工作的地方。

---

是的，你可能对路径走廊错了。它通常发生在有大量瓷砖的开放区域。我所看到的基本上与此图像中的底部图像相似http://3.bp.blogspot.com/_-u6ZJlBFOL0/Sl8NQfhU_pI/AAAAAAAAADI/DS3h8mklIjc/s1600-h/heuristics_take2.jpg 

也许不是结束了但如果代理人相对于瓷砖相当小，那么很明显他们会采取稍微偏斜的路线。所以我有兴趣解决这种情况。在相关的说明中，您在Recast的生成设置上写的帖子非常有用，但它没有提到磁贴大小。你有没有写过关于选择好瓷砖尺寸的文章？大多数情况下，我一直在使用瓷砖来限制边缘的长度，而不是动态-网格。

----

图块大小取决于您首先使用图块的原因。我会写一篇关于它的帖子。

底部图像实际上非常好，认为自己很幸运;）

在你的情况下，字符串拉出路径*的失败模式包含“内部网格”顶点。如果遇到这种情况，可以使用raycast（）来检查内部顶点之后的直线路径顶点是否有直线。

如果有，则用raycast（）返回的结果替换路径走廊的开头。基本上，您可以找到最远的公共多边形，并将路径走廊批处理到该多边形。

您还应该有一个错误警报缓存，以便在上次测试失败时不要尝试快捷方式。

可能还有其他方法可以解决这个问题，比如试图找到坏顶点周围的另一条路径，但我非常肯定你可以使用内部顶点检查来查看何时应该尝试调整路径。我相信还会有其他案例。


*）当跟随路径时，我通常只查询接下来的2-3个直路径顶点，这个想法应该适用于那种查询的东西，你有点修复路径。

---

还有一件事：请注意，raycast（）用于修复走廊，_not_用于修复直线路径。

---

真酷啊 这就是我过去所做的。我的印象是你反对的，但我认为我得到了错误的结束:) 谢谢你的帮助。

---

只需确保使用光线投影修复走廊，并且不要在每次需要新的直线路径时使用它来修复字符串。然后我不反对:)

---

您是否需要检查目标点是否位于当前漏斗的上方或下方？如果是这样，您需要添加左/右点作为附加航路点。或者我错过了什么？
考虑这种情况：http：//bit.ly/aY0YHV 
（紫色是当前的顶点，左边是橙色箭头，蓝色箭头是右边，黄色箭头是门户，目标是圆圈，通道的开头是左上角）

kiitos为此博客; D.

----

多边形确实通常受到青睐，因为它们会产生较少的A *节点。这也是Detour使用它们的原因。内存使用情况通常类似。

这三个开发者的三维网格更好的原因是什么？

使用基于多边形的方法时，哪些代码部分较慢？

---

https://digestingduck.blogspot.com/2010/03/local-navigation-grids.html

本地导航网格

在过去的几个月里，我已经测试了几种不同的避免局部避障方法。不过最近，我已经完成了一场比赛。对于全局搜索混合和匹配导航的未知方式以及更多本地路径查询的动态-网格，我非常喜欢这些。

关于这种组合有一个可能令人讨厌的事情，那就是当本地网格说路径被阻止时该怎么办，但全球导航网不同意。我将通过假设所有不在全局navmesh中的东西都能以某种方式遍历来回避这个问题。让它四处走动，踢它或者把它点燃。

履行

即使该方法存在一些问题，我认为值得尝试。我将我的实现限制在跟随代理的小网格中。这背后的想法是网格只试图解决两个全局导航节点之间的寻路问题。在导航的情况下，该区域将是当前导航多边形的区域，如果使用航点，则它可以是航点之间的区域。

简化网格

网格对于创建障碍非常简单。网格的可怕副作用是它们创建了巨大的图形并且在性能上显示出来。由于我们使用小网格，20x20到64x64之间的东西可能就足够了，这不是一个大问题，但64x64仍然是用A *搜索的4096个节点。


我们可以做一个简单的技巧来大幅减少节点数。在构建网格之后，我们通过将网格存储为RLE跨度来简化我们的搜索表示（哦，是的，我是RLE的忠实粉丝！）。实际上，这将节点数从N ^ 2减少到2N。在我们的节点网格范围（N = 20..64）中，这意味着节点数量减少了一个数量级！

（我记得读过一些GDC幻灯片，描述了一些RTS使用的相同技巧，但我找不到参考。）

副作用是成本计算变得讨厌和混乱。但是我们还不在乎。相反，让我们通过做出更多假设来进一步减少我们的搜索。

简化搜索

如果我们不使用本地网格，那么通过该区域的路径将是一条直线。我们可以使用这些信息创建一些能够在直线存在的情况下做得很好的东西，而不是在任何其他情况下让我们远离障碍的方式，而不是为本地网格构建一个完整的A *探路者。和当地的最小值。我选择使用呼吸首先搜索这个。由于搜索空间表示，它非常有效。开放列表永远不会变得非常大，实际上开放列表大小通常在4左右，并且几乎不会超过8个项目。





为了获得直线路径，将要添加到打开列表的邻居节点进行排序，以便首先添加从起点到终点最接近直线的节点。这种偏差确保首先访问靠近中心线的节点。打开列表永远不会排序，只是添加到它的新节点。它不漂亮，但在实践中效果很好。寻找最终路径




在搜索期间，存储父节点的索引，并且pathfind基本上包括找到结束位置所在的节点并追溯节点直到我们到达起始位置。在找到结束节点时，我选择在呼吸首次搜索期间访问过的最近的节点。这确保我获得跟随目标的路径，即使该方式被暂时阻止。最后，漏斗算法用于找到通过区域的直线路径。漏斗算法只需要一系列片段，这些片段定义约束的左右边缘以沿着漏斗移动。在我们的例子中，门户是两个区域之间的共享边缘。




在我的原型中，最慢的部分是更新网格，每个单元存储1位。更新网格平均需要0.026毫秒，这包括大约6个段和6个代理。我相信你可以通过矢量化光栅化阶段来减少这个数字。路径查询（包括字符串拉取）平均需要大约0.012毫秒。所有结果都在2.8GHz Core Duo上。一个路径查询使用大约1.5kB的内存来存储所需的搜索空间表示和最终路径。

[编辑]上面更新了时间测量，原点是在调试版本中测量的。


结论

尝试使用本地网格方法很有趣。我认为它有很大的潜力，但是将局部网格故障同步到全球结构的潜在问题是一个令人讨厌的副作用。我认为有可能创建一个“假设界面”，例如我在开头句中解释的那个，以改进它。

----

我最近也在考虑避免动态避障。但我喜欢使用可见性图而不是网格光栅化的想法。特别是，我认为Oriented Visibility Graph可能运行良好（您之前在AiGameDev.com上提到过）。但是存在同样的问题，即维持静态和动态表示之间的一致性。OVG是O（V ^ 3），因为V是所考虑的所有对象的顶点数，并且可以非常快速地逐渐添加和去除顶点。另一个好处是，采用这种方法时不需要路径平滑，如果你经常运行这个程序，你也不需要任何转向代码。我想知道是否可以使用OVG来处理单个导航集群中的所有移动，然后使用更传统的路径规划器来解决抽象图上的路径，以便找到要在其间传输的簇。我希望我几乎可以在每一帧运行OVG算法，并且没有转向或字符串拉取代码，这将有效地结合转向和寻路。

---

我不认为这会起作用，但不要让它阻止你尝试！

我看到两个问题。

首先，闪烁。如果你经常寻找路径，你会得到很多闪烁。如果您可以将之前的结果用作偏差，那么它会有所帮助，但不同配置中的路径最终会有很大差异。

其次，当你有一群代理人时，你将最终遇到路径被阻止的情况。例如，在我的示例图片中，当最顶层的代理通过门时，路径将被阻止。

上面的示例图像可能有点误导，因为我通常不使用移动物体作为阻挡物，而是使用速度计划来避免它们。

---

任何基于计划的解决方案似乎都会遇到动态障碍。Christian Gyrling提到这是他的采访，他们使用2D网格方法未知，并且当机器人跟随动态障碍时它会显示问题，并且当他们可以跟随它们时，尝试围绕这些动态障碍计划路径。

任何想法如何解决这个问题？使用A *也可以更新障碍，但这看起来非常昂贵。也许A *根据到那一点的距离有某种预测的未来位置？（它现在变得与RVO相似了。）

---

它最初似乎并不那么容易:)有几个多智能体寻路文件（即网格地图上的可跟踪多智能体路径规划[1]）。它们通常是全局搜索，也就是说，所有代理都在同一时间处理，恕我直言，这使得它们的规模非常糟糕。它们都需要粗网格（cellsize = agentsize），有时还需要3D网格（x，y，时间）。这听起来不像我愿意实时做的事情。

http://vimeo.com/10404328（在编写本文时尚未转换，应在10分钟左右开始提供）

这是我的测试平台的视频，它只使用上面博客文章中的简单“本地”探路者。这个探路者的优点是，它只是尝试在本地解决问题，而不是花太多时间进行完全重新计划，这将是非常浪费的，因为大部分路径一直被抛弃。如果找不到好的路径，它将返回......尽可能接近目标的东西。即使路径暂时中断，代理也会继续运行。

多代理路径寻找部分是一个调度问题，而正常的A *对时间一无所知。我已经尝试将代理扩展到移动方向并根据与呼叫者的距离向前移动，但结果并不十分令人鼓舞。整个地方都有可怕的闪烁和50-50个死锁。

大多数本地方法表现出的一个简单而愚蠢的特征是分离（直接或直接）。这几乎是处理调度的最简单方法......也就是说，相互推动直到有人通过。

使用路径查找器，您可以为其他代理周围的区域增加更多成本，但这不会解决视频中的死锁，因为A *最终会返回最近的目标位置。

当我在pathfinds之间添加随机1-6帧延迟时，我用这种方法得到了最好的结果。

此外，保持流量是必不可少的，尤其是在拥挤的场景中。通过寻路，流动总是在人群中被打破。一种“修复”这种方法的简单方法可以是减少半径障碍，以便探路者能够找到代理之间的路径，并使用某种排斥力来处理其余部分。但是，许多论文报告说，你再次遇到振荡和反应问题。

它看起来像是一个简单的问题，但它真的很难......我听说它可能像NP-hard :) 

[1] http://ijcai.org/papers09/Papers/IJCAI09-310.pdf

---

https://digestingduck.blogspot.com/2010/03/custom-hrvo.html

自定义hRVO

我试图找到我不断增长的有趣的局部回避/速度规划方法的队列。对于我的TOI采样方案，有一些我喜欢的东西，但结果并不是我想要的结果。

最初让我创建TOI采样方案的一个原因是假设在大多数时间以最大速度移动是个好主意。在实践中，这似乎是一个错误的假设。它创造了一种匆忙的行为，就像一只无头的鸡在奔跑。特别是在拥挤的情况下。

所以我一直在思考的一件事是，如果我只是删除了这个假设并使用了大量的样本来测试不同的速度，那么可能会发生什么。很像RVOlib的作用。

您可以在上面的视频中看到结果。我认为现在情况有了很大改善。我使用样本评分方案作为我之前使用的TOI采样。它的好处是它可以很好地处理各种令人讨厌的事情。

这个自定义hRVO遭受的一个问题是别名。H是小写的，因为该方法不完全使用混合RVO方法，但确实具有与HRVO类似的侧偏。从4个代理人的接管情况中可以清楚地看到，代理商倾向于从右边传递对方。这减少了在头对头和超车情况下闪烁很多的速度选择。

我添加的另一个技巧是支持接近当前速度的速度。在我以前的尝试中，这总是导致代理人过分偏爱错误的解决方案，导致代理人互相拥抱，跳到日落并从此过上幸福的生活。

在这个实验中，我还使用了之前博客文章中的探路者来避免静态障碍。

无论如何，我认为这是一个成功的实验，即使不完全实用，因为每个代理的样本量很大。受多智能体碰撞避免视频几何方法的启发，我想我将尝试下一步的ORCA方法，看看我是否可以通过更便宜的计算获得相似的质量。

---

通过预测，你的意思是在选择速度时使用多次前向迭代？

如果是这样，上面的实现也没有使用它。通常你需要很多精度来解决视频中的示例情况，这意味着要找到第一个好样本的大量样本，这反过来意味着进行另一次迭代不太实际。

有点蹩脚的几何方法太精确了，它们往往很容易陷入僵局（参见多智能体碰撞避免视频的几何方法中的4种情况），而ramdom采样在那里增加了足够的噪音，使你变得更高得到解决的可行性，同时也遭受混叠。

如果你有一些做多次前向迭代的经验，我很想听听:)

----

我喜欢你的想法，可以根据不同的速度对运动可能性进行大量采样，并且会被你展示的结果所震撼。我喜欢这种方法，因为它是非常个人或基于实体的，因为我认为当我们移动时，我们的大脑正在工作（预测）非常相似。

你说每个实体所需的采样数量太多 - 我们谈论的样本数量是多少？
你测试了多少种不同的速度（低中高？）？ 
可能可以将度量应用于样本的“适应度”，因此您可以首先运行一些样本，如果它们不符合适合度量，则运行更多样本？

----

对于样本位置，它使用31x31网格，其中圆形区域外的样本被丢弃。那是大约700个样本，这是很多。但分辨率还不够。我在单个单元格中使用抖动来改善获得更好结果的变化。工作，但结果当然是不可预测的。

RVOlib使用250个随机样本。我也尝试过这种方法，但是“走廊中的头对头鸡”案例无法通过如此少的样本来解决。此外，一些其他紧凑的地方变得非常难以预测的那些小样本。

最昂贵的部分是碰撞时间光线投射，我认为应该可以将其投射到N个方向，然后从中推导出更慢/更快的样本。如果这种方法证明是好的，我稍后会尝试。

此外，我认为应该可以使用某种聚焦或边缘感知调整来进一步减少样本数量。那里也有很高的时间连贯性。

---

通过0预测，我的意思是ORCA（在文章示例中）似乎避免在最后可能的时刻导致实体之间的大量接触，其中RVO或HRVO试图更早地避免碰撞（我不是那些方法的好专家，因为我还没有实现一个）。

仅供参考我在Golaem工作的方法涉及一种仅使用200个样本的速度空间采样方法，它运行良好！

----

我认为ORCA冲突避免距离取决于代码被截断的程度。在ORCA的情况下，它是硬约束，但是使用TOI采样方法，它更加柔和约束。

你能说出你如何分发样品吗？

在上面的视频中，它是否可以像走廊中的两个代理人一样处理类似的情况？

---

https://digestingduck.blogspot.com/2010/03/detour-serialization-api.html

Detour Serialization API

我实现了一些帮助，使Detour navmesh数据序列化更简单。我选择简化我在之前的帖子中讨论过的方法。对于你们来说，实施更多一点，但反馈是大多数人不会使用我的高级功能。一旦你到了制作保存游戏并遇到问题的地步，请告诉我。我尝试改进API。

绕行API更改

此更改导致了一些API更改。

首先你会注意到init（）函数已经改变：

    bool init(const dtNavMeshParams* params);

我只是将参数移动到一个struct，行为是一样的。我还添加了一个函数来返回init值，因此更容易存储navmesh状态。

第二个更改是在addTile（）中：

    dtTileRef addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef = 0);

平铺坐标消失了，它们现在存储在平铺数据中。所以他们需要传递给dtCreateNavMeshData：

        params.tileX = tx;
        params.tileY = ty;
        ...
        if (!dtCreateNavMeshData(&params, &navData, &navDataSize))

现在，模糊的布尔标志消失了，我添加了一个枚举标志（DT_TILE_FREE_DATA）。现在更具可读性。

lastRef也有新的参数。它可用于将瓷砖放在指定位置并恢复盐。这确保了存储到磁盘的dtPolyRefs在保存游戏后仍然有效。

您还会看到removeTile（）也丢失了坐标：

    bool removeTile(dtTileRef ref, unsigned char** data, int* dataSize);

该函数使用tile引用指定要删除的tile。我添加了一堆访问器来在tile指针和refs之间进行转换，并在某些位置查询tile。

这允许在不丢失navmesh状态的情况下保存和加载切片。请参阅Sample_TileMesh :: saveAll（）和Sample_TileMesh :: loadAll（）作为示例，了解如何使用此新功能来保存和加载整个动态navmesh状态。

dtMeshHeader现在也有userId字段，可以用来识别导航网格，你可以从资源包中加载它，而不是用你的保存游戏读取和写入整个navmesh。

三角州

作为存储导航网格结构的新增功能，我添加了仅存储navmesh tile状态的功能。如果在运行时更改多边形区域类型或标志并希望在加载级别后恢复该状态，这将非常有用。

首先，有一个函数返回保存tile的五线谱所需的空间量（以字节为单位）：

    int getTileStateSize(const dtMeshTile* tile) const;

现在您已经分配了一个缓冲区（您可能只想分配一个缓冲区，该缓冲区是所有缓冲区大小的最大值并重用它），您可以使用以下函数填充数据：

    bool storeTileState(const dtMeshTile* tile, unsigned char* data, const int maxDataSize) const;

并将数据转储到磁盘。

当您想要恢复状态时，只需读取数据并调用此函数：

    bool restoreTileState(dtMeshTile* tile, const unsigned char* data, const int maxDataSize);

而已。比我希望的少一点自动化。保存游戏很特别，什么时候存储以及什么是游戏特定的，我不想在核心库中构建过多的游戏。

https://digestingduck.blogspot.com/2010/03/geometric-vs-sampling.html

几何与采样

受到样本hRVO事物的相对成功的启发，我虽然对我的旧ClearPath原型进行了除尘，并尝试将其与基于采样的方法进行比较。

我不得不承认，最近的ORCA解释视频也引发了一些气体。我认为在视频中看到它之后我终于得到了ORCA的东西。

没有进一步到期的视频。

实现

我在ClearPath上添加了一些技巧。我使用与HRVO相似的侧偏，即基于物体的速度和位置，VO的一侧被扩展。它有助于代理选择一侧并减少侧面选择闪烁。

我添加的另一个技巧是，我使用尖钉而不是像Butt一样用ClearPath纸张夹住VO锥体。这使得避免更加平滑，如头对头的例子所示。它增加了我在上一篇文章评论中提到的非常需要的预测Clodéric。

我使用不同的时间范围来表示静态和移动的障碍物，这允许代理人靠近墙壁移动，同时避开彼此。这对于在拥挤的地方获得良好行为非常重要。

突然的运动是由于基于相邻运动打开和关闭的薄条子部分引起的。

几何与采样

在许多情况下，几何方法比任何采样方法都要平滑得多。我认为它最大的缺点是结果是二进制的。你要么进出要么。但这也是它的力量，使结果准确。二进制结果也意味着，有可能进入根本没有允许速度的情况。

几何方法的另一个方面是速度选择。常见的方法是将速度移动到速度障碍边界处的最近位置。在拥挤的情况下，这会导致死锁，这也可以在视频中看到。我很确定如果浮点结果非常准确，那么死锁永远不会解决。

您可以在ClearPath视频中看到类似的阻塞，这也存在于我的视频中（当他们将速度提高到10倍时）。采样的VO看起来也更平滑，尤其是在锥形尖端周围。在实践中，这意味着您不太可能遇到没有允许速度的情况。您将受到与其他代理人碰撞的速度的高罚款，但采样允许您承担风险。采样还允许在计算最佳速度时组合多个不同的权重。这允许更有趣的方法来平滑速度选择。






我很想看到一篇学术论文，比较这两种方法之间的利弊和有根据的结论。太糟糕的是，大多数论文都提出了新的方法，因为切片面包是最好的，并且未能正确处理缺点。

结论

当我有129x129个样本时（例如上面的示例图片中），采样方法看起来非常好且平滑，但是这样的样本量是完全不切实际的。我认为大约200的样本数量开始变得可以接受，我希望少花钱。我会试着看看我是否可以制作一些古怪的稳定自适应版本以减少样本数量。

我认为如果能找到更好的方法来将速度钳制到VO的边界，几何方法可以得到相当大的改进。最近的一点显然不够好。

我喜欢这两种方法。在时间允许的情况下，我将继续努力解决两者的缺点。我有一种有趣的感觉，这些方法中的一种可能足以进行三A质量的代理运动。嗯，这仍然缺乏动画位，但这是另一个故事。

---

Mikko：我越是想到它，我越认为这是代理运动的错误方式。我的问题是，个人根本不会将世界视为一组移动的车辆。他们经常在其他代理商之间协商合同，如果他们发现前进实际上会导致他们两人停止移动。您之前的视频实际上显示了一些行为（最后的漏斗情况，其中一些代理只是移开了）。

我认为在这些方法之上添加一些超简单的个性建模可以解决一些代理人开始在一个群体中聚集的疯狂边缘情况。它将允许各个代理人基本上使自己适应转向问题。例如，想象一下，如果你有代理人走到一个圆圈的另一边，而不是当前的“每个圆圈向右转”的情况，他们中的一些只是留在外围并走在小组的外面，而其他人直接排队。

这就像你实际上可以尝试对真实人类的行为进行抽样的那种问题（通过寻找当地大学并让他们走向相同类型的点并录制结果）。也许有一天我会尝试与一群学生一起为你拍摄这部电影！

----

我认为过程是这样的，我可以拿走什么来解决它，而不是需要添加什么才能使它变得更好;）

我听到了你的观点，但我相信它也是合理的。在Gamma [1]以及IRISA [2]都有很酷的新兴研究，它试图根据人类记录的数据找到人群模拟的新解决方案。我一直在密切关注这项研究。

这实际上引起了前几天非常感兴趣的见解。速度选择的一个大问题是我们可以很容易地找到速度非常糟糕且物理上不可能的速度（即VO的任何衍生物），但在允许的速度中选择速度实际上是定义代理的行为！

这使得例如不可能在不同方法之间进行比较，因为结果是主观的。总会有一些愚蠢或醉酒的例子进行比较，以便您可以描述“人类喜欢”的动作。

这就是我喜欢上述研究的原因，他们正在针对普通的冷数据推销他们的算法，并且他们投入了大量精力来创建尽可能好的数据。

所以这就是我在遥远的地平线上瞄准的东西。同时，我希望使用比目前存在的更好的工具为社区提供支持。

目前公认的标准是“让我们追踪多边形边缘中点并添加一些力来避开其他的”。这是不可接受的。我想首先提出一个强大的解决方案，并以我们已经习惯的东西为基础，然后追求更大的目标。

如果解决方案过于激烈并且需要大量工作才能将其实施并集成到现有的生产流水线中，那么任何人都不会遵循它，并且代理运动的遗憾状态将保持不变。

我看到等待的问题（没有任何其他好的避免手段）是避免障碍成为调度问题，这也不是很容易。选择何时停止以及何时再次移动可能会变得复杂，而不是加入其他人的快乐。我在某些方面做了一些关于停止和等待的实验，虽然它在某些情况下起作用，但大部分时间都会导致死锁。

不过，我很想看到有关该主题的研究和原型！


在
多智能体碰撞避免视频[3] 的几何方法中可以看到并且支持您的假设的一件事是它们实际上使用随机的期望移动速度来解决它们的回避方法的一些缺点。

我可以屈服于尝试使用这种行为来改变不同情况下的速度。期望的速度和所需速度的变化已经表达了相当多的行为。


我真正讨厌的一件事是不同的学科如何以不同的方式命名这个问题。有人称它为多代理导航，有些人称之为虚拟助行器而不是。使谷歌搜索相当沮丧的工作。我认为“虚拟步行者”可能与您的工作最相关。


[1] http://gamma.cs.unc.edu/RCAP/ 
[2] http://www.irisa.fr/bunraku/Julien.Pettre/dataset1.html 
[3] http://www.youtube。 COM /手表？ν= oleR0ovxgN8

----

我对你最终获得ORCA的评论微笑了。它也花了我一些东西，但是一旦我做了并实现了它，我对此非常满意。我正在将它用于四足动物，并对结果感到满意。

你几个星期前做了一个评论，这是真的：最好的碰撞技术告诉你不允许的速度，而不是告诉你好的速度，所以CA需要与一些路径/导航方法一起工作。

----

布鲁斯，很高兴听到它运作良好。

你是如何实现线性编程的？我从来没有实现过，我也找不到任何简单的指针。如果我无法弄清楚任何更聪明的东西，我可能只会用ORCA平面剪一个矩形。

在旁注中，我使用我的采样与几何方法进行了一些分析，并且几何方法比使用150个样本的采样快2倍。我想象实现ORCA的方式，如果不是更多，它将至少快2倍。

这应该让我达到我的目标，这是20+代理在不到0.5ms。

---

我在de Berg等人的Computational Geometry的第76页上使用了LP算法。他们在论文中使用的那个实际上是在同一章的后面，但是由于我在做概念验证，我坚持使用最简单的算法。一旦你获得直觉，该算法非常直观。我认为，实现中的技巧是拥有一个非常强大的边界类，它可以告诉你：

1。给定一个点和一个边界，该点在哪一边，以及距离。

2.两个边界之间的交叉点。

ORCA的一个实际问题是处理2个实体位于安全区（BminusA）<半径AB内的情况。我把BminusA夹紧到半径AB + epsilon，这似乎工作正常。我也做了真正的边界计算而不是清晰的路径近似。

在一个不同的（和推测性的说明），几年前（1995年），我做了一个基于合成视觉的避碰方案，效果出奇的好。我有一个可以在DOOM环境中“导航”的自主动画狗（他可以在一个水平上移动，穿过开口，避开墙壁等......）这个想法非常简单：我从狗的头部渲染场景计算每个像素的连续图像之间的运动能量（我记得我做了64 x 64或32 x 32阵列）。运动能量就是颜色变化了多少。要保持在走廊的中间，你有一个简单的控制律，可以平衡图像右半部分和左半部分的运动能量（这实际上就是蜜蜂在自然界中的表现）。我有特殊情况处理正面接近墙壁的情况，以及我记得的一些其他特殊情况。它确实要求表面纹理化。这一切都在GPU等之前。

我并不是提出这个方法，而是建议将CA视为视力问题可能是一个有利可图的探索方向。我认为当你处理类似于一个包或一组的东西而不是一大群人时，这可能尤其如此，其中运动的精细细节实际上很重要，并且角色形状的分析近似开始具有可见的伪像。只是猜测。

---

谢谢，布鲁斯！看起来像一本值得拥有的书。昨天我做了一个快速的黑客攻击，我只是用一个矩形加注星形，然后将每个ORCA平面切掉。

我注意到的一件事是你选择飞机变得非常重要。起初我只是尝试使用我为ClearPath原型创建的多边形，虽然它与几个代理一起使用，但是当有许多代理时，我的结果非常糟糕。飞机开始闪烁，并经常创造零允许集。我接下来会尝试平滑的边界。

如果允许的集合是nul，你如何处理这种情况？或者你使用3D线性编程？


我正在考虑测试一个使用采样和orca约束的版本。类似于使用最大混合模式渲染渐变，然后在此之后找到局部最小值。这可能也允许组合其他权重。


至于你的旁注，我想如果你眯着眼睛，我之前的TOI采样可以被认为属于那个类别。基本上我在代理周围渲染1px高“深度图”并基于此进行操纵。

---