体贴的寻路AI
Considerate pathfinding AI
我想让 1 个宽的东西流能够找到路径，以便考虑到在同一个 2 个宽路径上进行的其他流。
假设我有一张这样的地图：（“0”是不能走，“-”是可以，“1”和 "A" 是起点，而“2” "b" 是目的地）
000000000000
0000000001A0
000000000--0
0B200------0
0--00------0
0------00000
0------00000
000000000000
如果我使用 A* 算法 "A" 到 "B" 的路径查找，它将阻止从“1”到“2”的路径。（“=”是路径）
000000000000
0000000001A0
000000000-=0
0B200======0
0=-00=-----0
0=====-00000
0------00000
000000000000
是的，我可以找到“1”到“2”的路径，然后创建 AB 路径，但这并不总是有效。典型的例子是：
00000000000000000000
000000000000000001A0
00000000000000000--0
0B200------00------0
0--00------00------0
0------00------00000
0------00------00000
00000000000000000000
从“1”到“2”的 A* 寻路阻塞了 "A" 到 "B"
的路径
000000000000000001A0
00000000000000000=-0
0B200------00=====-0
0-=00=====-00=-----0
0-====-00=====-00000
0------00------00000
00000000000000000000
"A" 到 "B" 块“1”到“2”
000000000000000001A0
00000000000000000-=0
0B200------00======0
0=-00=====-00=-----0
0=====-00=====-00000
0------00------00000
00000000000000000000
补充说明："A"、"B"、“1”和“2”可以位于用户创建的地图中的任何位置。可以有 1 到 10 条路径同时进行尽管 AI 只需要考虑其他当前路径，但时间和启动和停止是分开的。它还需要实时发生，因此计算甚至不能花几秒钟。
那么我怎样才能让 AI 足够聪明，不会挡住另一条路呢？现在我正在使用 A*，那么它是否有改进，或者我应该使用全新的 AI 系统？ （都对我有用）
如果我没理解错的话，您正在搜索Cooperative Pathfinding。在过去的十年中，针对这个问题提出了许多解决方案。您可以在 this paper.
中找到对它们的很好的总结
我给你一个小回顾：
- 局部修复A每个代理
使用 A* 算法搜索到目的地的路由，忽略除其当前邻居之外的所有其他代理。然后代理开始
跟随他们的路线，直到碰撞即将发生。每当代理要移动到已占用的位置时，它就会重新计算剩余的路线。有点 "brute-forcing"，它不是最先进的，但它是 "easy" 实施和视频游戏的当前行业标准。不幸的是，我找不到该算法的伪代码。 :(
- Cooperative A是一种求解Co-的新算法
可操作的寻路问题。任务解耦为
一系列单一代理搜索。个人搜索
在三维 space 时间内执行，并考虑其他代理的计划路线。 等待移动
包含在代理的操作集中，以使其能够保留
文具。
- 分层合作 A* 与以前一样，但采用分层方式。
- Windowed Hierarchical Cooperative A* 当时最先进的技术（我认为是 2005 年）。有一个有趣的演示 on the internet，其中包含 Java 源代码和所有内容。要了解为什么 WHCA* 更好，请转到论文的第 3 页。
我希望这足以让您在需要时开始自己探索这个领域。 :)
与大多数问题一样 - 找到实际约束有助于确定您正在查看的搜索 space。
如果两条路径可以采用截然不同的路线，或者如果这些路径必须并排行进，那么示例问题中并不清楚？你知道是否总有一个解决方案可以同时路由地图上的所有路径吗？
如果您只需要一条道路来支持 n 宽的间隙（对于 n 条平行路径），这似乎是对搜索 space/problem 表示的简单调整，这可能可以使用 A* 完成。
此外 - 您提到了流 - 随时间推移的行为是否是问题的一个维度？ - 是否可以选择分时（交替使用）多个流之间的狭窄间隙？或者可以自行寻找路径的更短的流元素车队？
我想让 1 个宽的东西流能够找到路径，以便考虑到在同一个 2 个宽路径上进行的其他流。
假设我有一张这样的地图：（“0”是不能走，“-”是可以，“1”和 "A" 是起点，而“2” "b" 是目的地）
000000000000
0000000001A0
000000000--0
0B200------0
0--00------0
0------00000
0------00000
000000000000
如果我使用 A* 算法 "A" 到 "B" 的路径查找，它将阻止从“1”到“2”的路径。（“=”是路径）
000000000000
0000000001A0
000000000-=0
0B200======0
0=-00=-----0
0=====-00000
0------00000
000000000000
是的，我可以找到“1”到“2”的路径，然后创建 AB 路径，但这并不总是有效。典型的例子是：
00000000000000000000
000000000000000001A0
00000000000000000--0
0B200------00------0
0--00------00------0
0------00------00000
0------00------00000
00000000000000000000
从“1”到“2”的 A* 寻路阻塞了 "A" 到 "B"
的路径000000000000000001A0
00000000000000000=-0
0B200------00=====-0
0-=00=====-00=-----0
0-====-00=====-00000
0------00------00000
00000000000000000000
"A" 到 "B" 块“1”到“2”
000000000000000001A0
00000000000000000-=0
0B200------00======0
0=-00=====-00=-----0
0=====-00=====-00000
0------00------00000
00000000000000000000
补充说明："A"、"B"、“1”和“2”可以位于用户创建的地图中的任何位置。可以有 1 到 10 条路径同时进行尽管 AI 只需要考虑其他当前路径，但时间和启动和停止是分开的。它还需要实时发生，因此计算甚至不能花几秒钟。
那么我怎样才能让 AI 足够聪明，不会挡住另一条路呢？现在我正在使用 A*，那么它是否有改进，或者我应该使用全新的 AI 系统？ （都对我有用）
如果我没理解错的话，您正在搜索Cooperative Pathfinding。在过去的十年中，针对这个问题提出了许多解决方案。您可以在 this paper.
中找到对它们的很好的总结我给你一个小回顾：
- 局部修复A每个代理 使用 A* 算法搜索到目的地的路由，忽略除其当前邻居之外的所有其他代理。然后代理开始 跟随他们的路线，直到碰撞即将发生。每当代理要移动到已占用的位置时，它就会重新计算剩余的路线。有点 "brute-forcing"，它不是最先进的，但它是 "easy" 实施和视频游戏的当前行业标准。不幸的是，我找不到该算法的伪代码。 :(
- Cooperative A是一种求解Co-的新算法 可操作的寻路问题。任务解耦为 一系列单一代理搜索。个人搜索 在三维 space 时间内执行，并考虑其他代理的计划路线。 等待移动 包含在代理的操作集中，以使其能够保留 文具。
- 分层合作 A* 与以前一样，但采用分层方式。
- Windowed Hierarchical Cooperative A* 当时最先进的技术（我认为是 2005 年）。有一个有趣的演示 on the internet，其中包含 Java 源代码和所有内容。要了解为什么 WHCA* 更好，请转到论文的第 3 页。
我希望这足以让您在需要时开始自己探索这个领域。 :)
与大多数问题一样 - 找到实际约束有助于确定您正在查看的搜索 space。
如果两条路径可以采用截然不同的路线，或者如果这些路径必须并排行进，那么示例问题中并不清楚？你知道是否总有一个解决方案可以同时路由地图上的所有路径吗？
如果您只需要一条道路来支持 n 宽的间隙（对于 n 条平行路径），这似乎是对搜索 space/problem 表示的简单调整，这可能可以使用 A* 完成。
此外 - 您提到了流 - 随时间推移的行为是否是问题的一个维度？ - 是否可以选择分时（交替使用）多个流之间的狭窄间隙？或者可以自行寻找路径的更短的流元素车队？