algorithm - 有没有一种有效的方法来计算节点图上的热图之类的东西？

Question

我正在编写一个简单的游戏模拟程序，我有一些计算机控制的生物在节点图上移动。他们想要走向目标(想想，比方说，狼想要走向兔子)。

我已经实现了简单的寻路，因此生物可以找到直接通往给定目标节点的最快路线，但是在多个目标的情况下(多个节点上有很多食物)，我想我想生成类似图表上的热图梯度，这样狼就可以查询邻居节点并走向 HitTest 的邻居。

有人知道在图表上生成热图的有效方法吗？我能想到的最快的方法是进行 N 次全图遍历(N=食物节点数)，每次从每个食物节点开始进行 BFS(或最近/ HitTest 未访问节点首次遍历)，计算图中每个节点上来自该食物节点的热量，然后在一次收集过程中将来自每种食物的所有热量相加。我不喜欢这样，因为，好吧，如果我有一个大图和大量食物节点，我可能必须进行许多完整的图遍历，每个遍历都有很多节点。

我正在考虑做一种 BFS，我从所有食物节点的开放集开始，然后从那里向外移动，但随后我将只计算到最近的食物节点的距离；一组食物节点不会产生非常热的位置，因为我不能返回以增加先前遍历的节点的热量(如果我允许这样做，我基本上就像我之前的例子一样访问每个节点 N 次) .例如如果我开始:

F-O-O-O-O-O-O-O-O
| | | | | | | | |
F-O-O-O-O-O-O-O-F

其中 F 是食物，O 是空节点，假设食物节点的热量为 5，每个节点的衰减为 1，我希望我的热图看起来像

9-7-5-3-1-1-2-3-4
| | | | | | | | |
9-7-5-3-2-2-3-4-5

但是 BFS 风格的遍历(其中任何节点只能被访问一次)看起来像:

5-4-3-2-1-1-2-3-4
| | | | | | | | |
5-4-3-2-2-2-3-4-5

有人有更聪明的方法来做到这一点吗？最坏的情况也许我可以进行多次 N 次图遍历，但要按计划进行，所以我每 X 秒只进行一次食物节点遍历...

Answer 1

为什么不模拟图形周围的热流？也就是说，如果节点 i 在时间 t 的温度是 T_i (t)，然后设置:

T_i (t + 1) = α F_i (t) + (1 − β) T_i (t) + γ Σ_{j ∈ n(i)} T_j (t)

其中 F_i (t) 是节点 i 在时间 上的食物量t，n(i)是节点i的邻居集合，α，β，γ是模拟的参数。 α 是热量进入系统的速率，β 是热量离开系统的速率，γ 是热量从一个节点流向其相邻节点的速率。所有这些都应该是小数字:您必须通过试验为它们找到合适的值。

使用这个等式，需要 O(|nodes| + |edges|) 来更新每个节点的温度，因此您应该能够定期(最好是每帧)计算它。

上面的等式适用于离散模拟(具有恒定时间步长)。如果您有可变时间步长 δt，请尝试:

T_i (t + δt) = δt α F_i (t) + (1 − β)^δt T_i (t) + δt γ Σ_{j ∈ n(i)} T_j (t)