c# - 使用 A* 并且仍然避免碰撞？

Question

我正在设计一款塔防游戏，为此我使用 A* 寻路算法从我的出生区域到达我的目的地。

这里的问题是所有单元都堆叠在一起，这在视觉上看起来并不好。有没有办法让它们以某种方式分组，如果没有足够的空间，可以传播更多？

该算法的工作原理是所有单元一次移动一个图块。

Answer 1

我的一位朋友曾经为您可能听说过的著名第一人称射击游戏进行 AI 设计，他讲述了一个关于他们的寻路算法如何产生假装行为的故事。你会在有限的空间内向一群敌人投掷手榴弹，他们会互相碰撞，试图走上通往单一出口的有效路径。它看起来很愚蠢，打破了幻想。

他们没有在更好的寻路过程中消耗宝贵的处理器周期，而是添加了一种启发式方法，这样如果一群敌人正在逃跑，而一个敌人在短时间内连续两次撞到另一个敌人，那么敌人就会停止试图逃跑，而是做一个鸭子和-掩护，然后通常被手榴弹杀死。这对玩家来说非常令人满意，并且看起来更加逼真。

也许你可以在这里做类似的事情。如果太多的单位最终朝着同一条路径前进并相互碰撞，这看起来不切实际，有没有什么便宜又简单的方法可以检测情况并更改动画？

Answer 2

您可以使用群体行为让它们遵循相同的一般路径，但不会相互叠加。MS在这里提供了一个XNA示例：http: //xbox.create.msdn.com/en-US/education/catalog/sample/flocking

Answer 3

您是否在每个时间步重新计算最短路径？

如果是：只要给一块瓷砖最多可以站立的单位数量。如果它已满，则不再有单位可以占用此图块。

如果否：依次计算每个单元的路径。给每个瓦片一个向量，告诉其他单位（随后）这个瓦片被占用了多少。将此信息放入您的 A* 算法中。注意：这样你的算法会慢很多。

我建议在每一步重新计算最短路径。

编辑 1 实际上，算法的复杂性在两种情况下都是相同的，但是，在我看来，情况 1 更容易实现。

Answer 4

如果你对被许多爬行者占据的格子添加惩罚，只要它们有移动的空间，它可能会将它们隔开。

不过，它不再是最快的路径了。它还可能使它们更加不可预测，这取决于您的目标难度可能是好是坏:)

Answer 5

迭代寻路怎么样？

1. 运行寻路算法，忽略重叠问题。这将找到最短路径。
2. 模拟蠕变运动。这个模拟应该以基于瓦片的移动运行，这样它会很快。
3. 选择一半（摆弄这个）排队等候并因此不动的小兵。重新运行这些小兵的算法，但在他们等待的这个位置增加额外的重量损失。该权重仅适用于具有额外权重的小兵。
4. 重复步骤 2-3 直到满足某些条件，并注意之前的额外权重。

该算法将需要摆弄才能完全合并成有用的东西。但是，它具有使用预先计划路径的优势，因此它不会有任何循环或小兵向后移动。它还允许您忽略诸如时间之类的事情，因此它在概念上更简单。但也可能效率较低。