4

我正在编写一个简单的游戏模拟，其中有一些计算机控制的生物在节点图上移动。他们想朝着目标前进（想想，比如说，狼想要朝着兔子前进）。

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

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

我正在考虑做一种 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 秒只进行一次食物节点遍历......

4

2 回答 2

3

为什么不模拟图形周围的热量流动？也就是说，如果节点i在时间t的温度为 T i  ( t )，则设置：

T我 ( T + 1) = α F我 ( T ) + (1 - β) T我 ( T ) + γ Σ j ∈ n(我) T j  ( T )

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

使用这个方程，需要 O(|nodes| + |edges|) 来更新每个节点的温度，因此您应该能够定期计算它（理想情况下是每一帧）。

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

T我 ( T + δt) = δt α F我 ( T ) + (1 - β) δt T我 ( T ) + δt γ Σ j ∈ n(我) T j  ( T )

于 2013-03-22T09:25:36.453 回答
0

您的一般方法很好，但我认为您被热图概念蒙蔽了双眼。本质上，您想要计算所有目标的加权平均位置，并让您的猎人前往该点。我将按如下方式实现：

  1. 如果有比N更近的目标，则跟踪最近的目标；别的
  2. 计算比 Max 更近的所有目标的加权平均位置，权重函数 = D^2（只是猜测，但计算速度很快，因为不需要平方根）。猎人在每次迭代中都会前往该位置。
  3. 从 1 开始重复。
于 2013-03-22T08:59:43.017 回答