algorithm - 使用运动矢量检测 2D 场中的影响

Question

给定一个坐标和一个运动向量。我怎样才能得到所有将被感染的 block 的列表？

我觉得有点像“视野中的物体”或“物体碰撞”？

例如原点O为(2, 2)，移动向量“→”为(0, 1)，方 block B 应该是 [(1, 3), (1, 4), (2, 4), (3, 3), (3, 4)]

 0123 y→
0.......
1...BB..
2..O→B..
3...BB..
x.......
↓.......

如果运动向量是(-1, 1)，B应该是[(0, 2), (0, 3), (0, 4), (1, 4) , (2, 4)]

 0123 y→
0..BBB..
1...↗B..
2..O.B..
3.......
x.......
↓.......

我正在考虑

point P (x, y) vector V (v, u)
x' = x + v
y' = y + u
set S = ([x'-1, x'+1], [y'-1, y'+1])
calculate a line L "y=ax+b" perpendicular to V crossing (x', y').
split S into two groups by L
chose the one V is facing

但我找不到实现最后两个步骤的方法。

任何建议都会有所帮助。

Answer 1

我想你要找的是 time-until-impact 或 time-until-collision 或类似的东西。

但在大多数游戏引擎中，这不是可行的方法。碰撞处理的标准技术是空间划分。这意味着，如果您的模拟中有 n 个刚体，那么一个简单的算法需要 n^2 检查(每个与另一个)以查看是否发生了碰撞。然而，在性能方面这是一个 killer 。相反，您应该通过(`均匀分区、Oct 树、Z 排序等)对您的空间进行分区，然后您只检查与相关单元格相邻的相邻刚体。

请注意，这里并不真正需要速度矢量(您所说的运动)矢量，因为在实践中它不会带来任何好处。