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

Exhortation

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? – Mancini

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. – Exhortation

What will be the next state of such situation [A]->[ ]<-[B]? Will it be [A] [ ] [B] (they just remain where they were)? – Mancini

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]. – Mancini

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? – Exhortation

I have an idea. Forget about priority :). You may opt to resolve collision favouring A object in case it has very long chain, right? – Mancini

Yes, correct!! I want to limit the number of objects that have to remain stationary, so this means giving move priority to objects that have longer chains (like A in this example). – Exhortation

Let us continue this discussion in chat. – Mancini

Hi Ivan, I still can't possibly find an example where your solution would not work. Thanks so much again for helping. If you submit a very brief explanation of your solution (the idea of building trees), I would be happy to mark it as the answer. Thanks again! – Exhortation

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

Mancini

Great answer! I have two questions; 1) How would you break ties? 2) What if objects weren't necessarily moving at the same time? – Bowl

Answer 2

Checking "ahead of time"/"next step" will lead to hard calculations and even explosions.

Instead, you can (in-parallel) use checking "which particle can move to this spot?" on each cell. For this, you need velocity map having a velocity vector in each cell. Then following that vector backwards, you spot a cell. If there is a particle, get it to the cell.

This way no collisions occur because only 1 action per cell is done. Just get closest cell from the negative velocity vector's end point.

This is somewhat tricky to compute since velocity may not land exactly on the center of cell. Needs probability(if it is very close to corners than center) for equality of motion / macro effects too.

So there will be a race condition on only the index of cells, and that will be tolerated by randomness of movement(or particle picking depending on the distance from center of cell)

On quantum physics, particles can leap otherside of a wall, stand still(even if it shouldn't) and do some other things that are not natural for classical physics. So if resolution is high, and velocity is not higher than map size, it should look natural, especially with the randomness when multiple cells compete to get a particle from another cell.

Multiple passes:

• calcuate which cells need to gather from which cells,
• calculate probabilites and then winning cells
• winnings cells gather their particles from source cells in parallel.
• (not recommended), if still there are non-picked particles with a velocity, then doing per-particle computation to move them (if their target cell is empty), should reduce stationary particles even further.
• diffuse particle velocities on cells for a few times(using a 2D stencil) to be used in next iteration.(this one handles the complex collision calculation easily and in an embarrassingly parallel way, good for multithreading-gpgpu)(if particles can only go to closest neighbours, this also helps to know which one, even without any priority nor probability since each cell bents neighbouring cells velocities with the velocity diffusion)

check for Gauss-Seidel(https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method) method to solve many linear equations.

computation is done on cells instead of particles so the map borders will be implicity bullet-proof and calculation can be distributed equally among all cores.

---

Example:

particle A going down

particle B going right

they are in collision course

solve for velocity map equilibrium state(Gauss-Seidel)

now particle A's cell has a velocity to down+right

same as B

as if they were collided but they are still on their cells.

Moving them with their cells' velocities will make them look like they are in collision.

Floating