java - 二维网格中对象的碰撞处理

Question

我正在用 Java 开发一个模拟，其中对象在二维网格中四处移动。网格中的每个单元格只能被一个单元格占据，对象通过从一个单元格移动到另一个单元格来移动。

这比 Java 更理论化，但是有人知道我应该如何处理与这个网格的碰撞处理吗？人们是否使用过任何算法来处理类似网格的世界中的碰撞？

请注意，我不是在谈论碰撞检测，因为这是微不足道的，因为对象从一个单元格移动到另一个单元格。我说的是碰撞处理，这可能会变得非常复杂。

例如:对象 A 希望移动到与对象 B 相同的位置，而对象 C 希望移动到对象 B 的当前位置。由于每个单元格只能包含一个物体，如果物体 A 能够移动到其所需位置，这将导致物体 B 保持静止，从而导致物体 C 也​​保持静止。

可以想象这会产生更长的需要处理的碰撞链。

是否有人们使用过的算法或方法可以帮助解决这个问题？如果搜索结果不饱和碰撞检测算法，几乎不可能搜索这个问题。

编辑:所有对象同时移动。我想限制必须保持静止的物体数量，所以我更喜欢先处理具有较长碰撞链的物体(如本例中的物体 B)。

Answer 1

根据与 OP 的讨论，应该以最大化所有移动对象的数量的方式移动对象。

对象及其引用形成了一个森林。如果对象 A 正在引用被 B 对象占用的单元格，我们可以说 B 是 parent A 在树中。所以对象对应于节点，引用对应于树中的边。每棵树的根部都会有一些空单元格(所以当空单元格对应一个节点时实际上就是这种情况)。树没有公共(public)节点。

在继续前进之前，我们必须承认可能存在周期的情况。像这样:

[A] -> [B]                 
 ^      v       or     [A] <=> [B]
[D] <- [C]                 

这样的周期很容易识别。一些对象可能直接或间接地引用循环对象也形成一棵树。循环只能发生在树的根部。

假设我们已经构建了所有的树。现在的问题是我们如何解决冲突？请记住，我们想要最大化移动节点的数量。碰撞对应于具有超过 1 个子节点的节点。

在 cycle-root 树中，除了只移动循环对象而不移动树中的任何其他对象之外，我们没有任何其他选择。很明显，我们不能采用其他方式。

在 empty-cell-root 树中，首先我们必须决定将哪个根 child 放置在根空单元格上。然后我们将有一个新的空单元格，我们必须在其中做出相同的决定。依此类推，直到 leaf 节点。为了最大化移动节点的数量，我们必须采用从根到叶的最长链并移动其节点。所有其他节点都不会移动。这可以通过使用一些递归函数遍历树并为每个节点 f_leaf = 0 和 计算以下函数 f 来轻松完成>f_node = MAX(f_child1, f_child2, ...) + 1。因此，上述决策是选择具有最大 f 的子节点。

    *
   /|\
  A B C         The optimal move path  is   * <- C <- E <- H
 /   /|\
D   E F G
   /
  H