Collision handling of objects in a 2D grid

Question

I'm developing a simulation in Java where objects move around in a 2D grid. Each cell in the grid can only be occupied by one cell, and the objects move by moving from one cell to another.

This is more theoretical than Java specific, but does anyone have ideas as to how I should approach collision handling with this grid? Are there any algorithms that people have used to handle collisions in a grid-like world?

Please note, I am not talking about collision detection as this is trivial since the objects move from one cell to another. I'm talking about collision handling, which can get extremely complex.

Ex: Object A wishes to move into the same location as Object B, and Object C wishes to move into Object B's current location. Since each cell can only contain one object, if Object A is able to move into its desired location, this will cause Object B to remain stationary and thus cause Object C to also remain stationary.

One can imagine that this could create an even longer chain of collisions that need handled.

Are there any algorithms or methods that people have used that can help with this? It is almost impossible to search for this problem without the search results being saturated with collision detection algorithms.

Edit: All objects move at the exact same time. I want to limit the number of objects that must remain stationary, so I prefer to handle objects with longer collision chains first (like Object B in this example).

Answer 1

According to discussion with OP the objects should be moved in a way maximising the number of all moved objects.

Objects with their references form a forest of trees. If an object A is referencing a cell occupied by B object we may say that B is a parent of A in the tree. So objects correspond to nodes and references correspond to edges in trees. There will be some empty cell in the root of each tree (so this is actually the case when empty cell corresponds to a node). Trees do not have common nodes.

Before moving forward we must admit that there may be situations with cycles. Like this:

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

Such cycles can be easily identified. Some object may be referencing cycle objects directly or indirectly also forming a tree. The cycle can happen only in the root of the tree.

Lets say we have built all trees. Now the question is How can we resolve collisions? keeping in mind that we want to maximise the number of moved nodes. Collisions correspond to a node having more than 1 child.

In cycle-root trees we do not have any other option except of moving only cycle objects while not moving any other object in the tree. It is clear that we cannot do another way.

In empty-cell-root tree first we have to decide which root child will be placed on the root empty cell. Then we will have a new empty cell where we will have to take the same decision. And so on so forth up until a leaf node. In order to maximise the number of moved nodes we have to take the longest chain from root to some leaf and move its nodes. All other nodes do not move. This can be easily done by traversing the tree with some recursive function and calculating the following function f for each node f_leaf = 0 and f_node = MAX(f_child1, f_child2, ...) + 1. So aforementioned decision is choosing a child node with the biggest f.

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