# Collision between complex polyominoes travelling at different velocities

My first post here if there's anything wrong please do highlight it :) First and foremost the problem I'm facing is practically identical to this earlier post here : Falling Blocks and complex shapes

For ease of use here is the graph used to explain the above problem:

I do have a working build that uses a similar approach to the answer suggested in the post above. However what I'm currently trying to do is move the polyominoes continuously with an independent velocity so that it accelerates as it falls.

The answer suggested in the link above only works if you assume all the shapes move at a constant velocity due to the way my game works the "ground" can be removed and blocks that were once static can start to fall again.

The problem arises when a block with a higher velocity collides with one with a lower velocity at the bottom. You could make it so that these blocks slow down as they "collide" with the slower blocks but using this approach causes a problem in cases 3 and 4 where the 2 interlocking shapes will collide endlessly with one another and just not fall.

I have tried a few ideas but they just don't seem to really work. And for anyone who wants to say it's too complex or try something simpler well I don't really have a choice in the implementation it's what someone else wants :(

Also I don't think that it really matters but I'm using Unity to build this game just in case if you wanted to know.

Again I thought it wouldn't hurt to throw this question out there rather than just bashing my head by myself.

the method that handles collisions:

protected bool handleVerticalMovement(ref Vector2 moveDelta)
{
var ySign = (int)Mathf.Sign(moveDelta.y);
var yDeltaMag = Mathf.CeilToInt(moveDelta.y * ySign);

for (int i = 0; i < _monominoes.Count; i++)
{
var x = _monominoes[i].gridPositionX;

for (int yDelta = 0; yDelta <= yDeltaMag; yDelta++)
{
var y = Mathf.CeilToInt(_monominoes[i].transform.localPosition.y * ySign + yDelta) * ySign;

// check if it has hit the boundary of the grid
if (!Board.Instance.IsValidTile(x, y))
{
var deltaToBoundary = Mathf.Clamp(y, 0, Board.Instance.height - 1) -
_monominoes[i].transform.localPosition.y;

if (moveDelta.y * ySign <= deltaToBoundary * ySign) break;

moveDelta.y = deltaToBoundary;

return false;
}
// ignore if the cell is empty or is part of this shape
if (Board.Instance.GetTileAt(x, y) == null ||
Board.Instance.GetPolyominoAt(x, y) == this) continue;

//check to see if i hit a tile that is grounded
if (Board.Instance.GetTileAt(x, y).isGrounded)
{
var detltaToGround = y - _monominoes[i].transform.localPosition.y - ySign;

if (moveDelta.y * ySign <= detltaToGround * ySign) break;

moveDelta.y = detltaToGround;

return false;
}

var deltaToTile = Board.Instance.GetTileAt(x, y).transform.localPosition.y -
_monominoes[i].transform.localPosition.y - ySign;
// if the tile is not grounded check to see the delta movement will overlap the tile if so cap the delta
if (moveDelta.y * ySign <= deltaToTile * ySign) break;

moveDelta.y = deltaToTile;
break;
}
}

return true;
}


To further elaborate my current thought process on the matter currently this method takes in a delta value iterates through the grid to see if it collides with anything. If does collide with something it will adjust the delta value and if it hits the the bounds of the grid or any shape that's grounded it will exit returning false meaning after moving this frame it will also be grounded..

The complication arises when one block hits another block that's also not grounded adjusting the delta value to slow it down it will cause the 2 blocks in case 3 and 4 to collide into each other infinitely causing them to float in mid air.

What I've tried to do is call the other block's handleVerticalMovement method to ask how far it can move and this in turn will end up a sort of recursive call to other blocks that that other block will hit. I managed to get this to work when the blocks were moving one cell at a time but it doesn't seem to work as well when the blocks are moving continuously with a pseudo gravity value causing the blocks to accelerate overtime.

I have thought about clumping the block's together and making them fall as one object this will definitely solve case case 3 and 4 but this can potentially cause problems with case 5 and 6 where if one object gets hit and becomes grounded the other "connected" block should still be able to fall a bit more.

This means if I were to make them fall as one block while they are free falling when one the "sub" blocks collides I still need some way to identify what can continue falling what blocks cannot.

Again if there's any gaping holes in my logic please do point it out.

## 2 Answers

Actually that is not that hard. As I don't know your complete design, I will just talk a bit more general.

I assume, each block construct as an independent enitity. So in picture 2 as an example, you would have 3 entities. I also assume, that your design includes mass for each entity. If all this is correct then next will help you.

As soon as 2 entities collide, determine the one with the bigger mass. This entitiy transforms into the parent entity of all other entities colliding. So now they all move no more independent, they are driven by the parent. The velocity break if 2 objects collide is a physics based calculation.

After the collision just move the parent with it's break down velocity.

When another collision is detected to the calculation again, but update the mass of the parent object to have the mass of all children too.

We go through all of your example pictures with my parent/child system.

Picture 1 - 1 Entity

Keeps falling till grounded

Picture 2 - 3 Entities

Green Entity and yellow Entity fall red entity is grounded. Let's assume green entity has a higher velocity then the yellow one and hits yellow before any of both get's grounded.

Green Entity detects a collision with yellow. We decide (because mass doesn't care for you) that green as first entity get's the new parent. So we set for yellow the parent as green and for green the child to yellow. Next they keep falling. Yellow is no longer moved or done collision detection because it has a parent. We move green and ask if has children and use both data for collision detection and movement.

We detect a collision of 1 child, yellow collided with the floor. So we set it to be grounded, remove it from the parent and set it has no parent. Next we do this for green, it collides with yellow, has no children anylonger so just set it as grounded. Done.

Picture 3 - 2 Entities

We detect a collision between green and red. We take green as the first entity of our list and set the children as red and on red the parent as green. Next we do collsion and movement only for green, because red has a parent and so will not be used in collision detection and movement.

Green hits the ground and will be marked grounded. Green has children so we remove the children and set their parents to be null.

Next we check red and detect a collision with green. we set green as parent of red and it is no longer part of the collision detection. But it is not grounded. As soon as green get's removed from the board, we free red and red will eventually start falling again till also grounded.

Picture 4 - 3 Entities

Red/Green is the same as on Picture 3.

Green detects a collision with it's children against yellow. Yellow is grounded and has there for the "master" right. So we set Green with it's children as a child of yellow. They are no longer used for collision detection, as long as yellow exists.

If yellow get's removed of the board, remove the children of yellow and set their parents to null, and they start falling again.

Picture 5 - 3 Entites

If we assume yellow falls faster or red or both have same velocity doesn't care. The algorithm is allways the same.

We assume red falls faster.

We detect a collison between yellow and red. yellow will the get the parent because first in the entity list. Next we detect a collision of yellow's child with green.

We set green as the parent of yellow because green is grounded and so the master. We free all children of yellow because yellow is connected of a master/grounded entity. We also free yellow of green because it is no longer colliding with green.

So yellow starts falling again and detects a collision between yellow and red. But red is connected to a master/grounded entity so we set yellow as a child of red and red as a child of green and set on all

Picture 6 - 3 Entites

Same as picture 5.

You see how the algorithm grows from picture to picture. To summarize the algorithm.

1. Check if entity collides with another entity
2. Check if the colliding entity is a "grounded" one
3. If not grounded determine one as parent and set the rest as children
4. If grounded free all children and do collision again for all
5. If grounded and not children, set as children of grounded.
6. If colliding with ground - free all children and set grounded

Done.

That's it.

• I haven't really looked at the problem using physics largely because I started of with something closer to tetris and the shapes moved one cell at a time instead of with a speed over time. Also even though I have made the constructs their own entity they have no "mass". It just falls with a given speed and I do the velocity calculation assuming the mass is 1 irregardless of how big the shape is. – MDZ Nov 10 '15 at 10:12
• ..continued. Looking at how velocity breaks when objects collide could be helpful but the part I'm having trouble with is when one "entity transforms into the parent entity of all other entities colliding" because no matter how I look at it this part is gonna end up being recursive and that's the part I haven't really nailed down yet... ( maybe I should post some pseudo code) – MDZ Nov 10 '15 at 10:13
• Sorry but as I look around in ur Collision detection, I would say u have a major problem with your design. It is maybe just my opinion, but nowadays I highly recommend to build every game, even a stupid snake or pong game, on base of a entity/component system. This generally leads you two major possibilities - have the perspective of the entity and add/remove components easily of entities. – Yosh Synergi Nov 10 '15 at 14:02
• What part of my design makes u think I don't have a component/entity based design? I am using a entity based design, on top of that I'm using Unity. Unity's monobehaviour class uses a state/entity design pattern... Yes it does allow you to add and remove components which allows you to use composition instead of inheritance. But the problem here is not the adding and removing is hard its deciding what should be added and removed.. – MDZ Nov 10 '15 at 16:01
• OK sorry I was too fast with my decision. But I don't understand the trouble with the collision. When 2 or more objects collide and u have no mass just pick the first entity and as the parent there is no recursive operation. Maybe I don't see what's ur problem but I don't see it in any way – Yosh Synergi Nov 10 '15 at 18:31

So after a little bit of trial an error I got something that works. I still have a few bugs in my game but it might be due to other parts of the code that are causing bugs.

protected bool handleVerticalMovement(ref Vector2 moveDelta, HashSet<Polyomino> hitMinos)
{
var ySign = (int)Mathf.Sign(moveDelta.y);
var yDeltaMag = Mathf.CeilToInt(moveDelta.y * ySign);

for (int i = 0; i < _monominoes.Count; i++)
{
var x = _monominoes[i].gridPositionX;

for (int yDelta = 0; yDelta <= yDeltaMag; yDelta++)
{
var y = Mathf.CeilToInt(_monominoes[i].transform.localPosition.y * ySign + yDelta) * ySign;

if (!Board.Instance.IsValidTile(x, y))
{
var deltaToBoundary = Mathf.Clamp(y, 0, Board.Instance.height - 1) -
_monominoes[i].transform.localPosition.y;

if (moveDelta.y * ySign <= deltaToBoundary * ySign) break;

moveDelta.y = deltaToBoundary;

return false;
}

var otherMino = Board.Instance.GetPolyominoAt(x, y);

if (Board.Instance.GetTileAt(x, y) == null || otherMino == this) continue;

if (hitMinos.Contains(otherMino))
break;

if (Board.Instance.GetTileAt(x, y).isGrounded)
{
var detltaToGround = y - _monominoes[i].transform.localPosition.y - ySign;

if (moveDelta.y * ySign <= detltaToGround * ySign) break;

moveDelta.y = detltaToGround;

return Board.Instance.GetTileAt(x, y).isAnimating;
}

var deltaToTile = Board.Instance.GetTileAt(x, y).transform.localPosition.y -
_monominoes[i].transform.localPosition.y - ySign;

if (moveDelta.y * ySign <= deltaToTile * ySign) break;

if (otherMino == null ||
Board.Instance.processedPolyominos.Contains(otherMino))
{
moveDelta.y = deltaToTile;
break;
}

hitMinos.Add(otherMino);

if(otherMino.handleVerticalMovement(ref moveDelta, hitMinos))
break;

return false;
}
}

return true;
}


so the method still looks the same except when I hit a tile that's not grounded I call that tile's handleVertcalMovemt method but I add that tile to a hashSet that contains all the shapes that were hit before. When I exit this method i would have a set of all the different polyominos that were would be hit if the root polyomino were to move down. From here all these shapes as one shape and move them all at once. This is practically the same to clumping shapes together except this builds the shape on the fly instead of caching them in a list.