OMG*_*gar 6 java algorithm collision multidimensional-array
我正在用 Java 开发一个模拟，其中对象在 2D 网格中移动。网格中的每个单元格只能被一个单元格占据，并且物体通过从一个单元格移动到另一个单元格来移动。
这比 Java 特定的更理论化，但是有人知道我应该如何使用这个网格进行碰撞处理吗？人们是否使用过任何算法来处理网格世界中的碰撞？
请注意，我不是在谈论碰撞检测，因为这是微不足道的，因为对象从一个单元移动到另一个单元。我说的是碰撞处理，它可能会变得非常复杂。
例如：对象 A 希望移动到与对象 B 相同的位置，而对象 C 希望移动到对象 B 的当前位置。由于每个单元只能包含一个物体，如果物体 A 能够移动到其所需位置，这将导致物体 B 保持静止，从而导致物体 C 也保持静止。
可以想象，这可能会产生更长的需要处理的冲突链。
人们使用过哪些算法或方法可以帮助解决这个问题？如果搜索结果没有被碰撞检测算法饱和，则几乎不可能搜索到这个问题。
编辑：所有物体同时移动。我想限制必须保持静止的对象的数量，因此我更喜欢首先处理具有较长碰撞链的对象（如本例中的对象 B）。
根据与 OP 的讨论，应该以最大化所有移动对象数量的方式移动对象。
对象及其引用形成了一片树木。如果一个对象A引用了B对象所占据的单元格，我们可以说它B是树中的父级。A因此，对象对应于树中的节点，引用对应于树中的边。每棵树的根部都会有一些空单元（所以这实际上是空单元对应一个节点的情况）。树没有公共节点。
在继续前进之前，我们必须承认可能存在循环的情况。像这样：
[A] -> [B]
^ v or [A] <=> [B]
[D] <- [C]
这种循环很容易识别。某些对象可能直接或间接引用也形成树的循环对象。该循环只能发生在树的根部。
假设我们已经建造了所有树。现在的问题是我们如何解决冲突？请记住，我们希望最大化移动节点的数量。冲突对应于具有超过 1 个子节点的节点。
在循环根树中，除了仅移动循环对象而不移动树中的任何其他对象之外，我们没有任何其他选择。很明显，我们不能采取其他方法。
在空单元根树中，首先我们必须决定将哪个根子节点放置在根空单元上。然后我们将有一个新的空单元格，我们必须在其中做出相同的决定。依此类推，直到出现叶节点。为了最大化移动节点的数量，我们必须采用从根到某个叶子的最长链并移动其节点。所有其他节点都不会移动。这可以通过使用一些递归函数遍历树并为每个节点f leaf = 0和f node = MAX(f child1 , f child2 , ...) + 1计算以下函数f来轻松完成。因此，上述决策是选择具有最大f 的子节点。
*
/|\
A B C The optimal move path is * <- C <- E <- H
/ /|\
D E F G
/
H