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).

As I can understand you example situation looks like this [A]->[ ]<-[B]<-[C]. Depending on who should move first A or B provided C moves last you may end up with two results: [ ] [A] [B] [C] and [A] [B] [C] [ ]. Do you have any order to process the cells? Do cells move simultaneously? — Ivan Gritsenko
Your understanding is correct! All objects move at the exact same time (just added that, thanks) and I do not have an order to process the cells (although I would be willing to create some sort of order if needed). The example I provided does not seem too difficult, but you can imagine the complexity if the chain was expanded, like if another Object wanted to move into C's location and another one wanted to move into A's location. — OMGitzMidgar
What will be the next state of such situation [A]->[ ]<-[B]? Will it be [A] [ ] [B] (they just remain where they were)? — Ivan Gritsenko
If you will have an order in which you will be processing the moves of the objects then the problem is very simple! Just iterate over the list (priority queue) processing moves of the objects one by one. In case cell tries to move into occupied cell you may just ignore such move. So situation like [A]->[B]->[ ] will resolve to [A] [ ] [B]. — Ivan Gritsenko
But based on the example you just provided, what if Object E wants to move into object A's cell? The collision between Object A and B need to be handled first, because the outcome of that move determines if Object E can move into its desired location or not. How do I know to process the A-B collision before the A-E collision? Priority queue sounds great, but how do I determine the priority of each object? — OMGitzMidgar

Ivan Gritsenko Ivan Gritsenko · Accepted Answer · 2017-02-21T02:48:09

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

Collision handling of objects in a 2D grid

2 Answers