# Collision between complex polyominoes travelling at different velocities

This topic is 978 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

My first post here if there's anything wrong please do highlight it

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

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.

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.

##### Share on other sites

Unity most likely has a way to handle collision for you. It will be overkill for use in 2D but you can bet it'll be quite robust and generic. Will most likely not be a problem even if you're running on Atom.

##### Share on other sites

try a google on "pixel perfect 2d collision"

that should point you in the right direction.

basically, everything gets a bounding box, if BBoxes collide, then you check on a per pixel basis for overlap.

stepped movement may be required for sufficient accuracy / sufficiently high resolution collisions.

Edited by Norman Barrows

##### Share on other sites

Up-voted for the excellent diagram. As far as the other answers go - I think you're missing the point of his question... My initial reaction was that you would want to group objects together (to fix case 3). I think you're going to want some kind of iterative approach where you group things while there is no connection with the ground plane, and simulate the dropping as much as possible. Once something is in contact with the ground, detach it from any groups, and let everything else continue to fall in whatever groups remain. Repeat. I imagine this isn't going to be super-clean to implement, but if you treat it as a set of connected components, and re-construct (or adjust) those components as important events occur, it may not be too bad. Initially, the ground plane is the only immovable piece. As soon as any piece is touching that, it becomes part of the ground as well (flagged as such, or added to that immovable component). Everything else gets clumped according to connectivity - don't even try to distinguish the really hard cases (#3) from slightly simpler cases - just merge connected pieces while they're falling to avoid any race conditions on movement. As soon as a piece is resting on anything in the ground component, detach it from its previous component, and continue. (You may need to re-compute the components at that point, if a single block that now touches the ground was the only thing keeping two otherwise non-touching blocks connected).

Make sense?

##### Share on other sites

upon closer inspection, as osmanb mentions, to handle cases 3 thru 6, an iterative approach, and grouping to avoid race conditions while moving is required.

this is really about falling body physics, not collisions.

##### Share on other sites

Hey everyone thanks for all the responses and i'm sorry for the late reply but I was or just to tired from work to post a reply. Anyways after tinkering with the problem I think I've found a solution. It still has bugs but it might be because of other parts of the code that's causing it.

 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;
}

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

return false;
}
}

return true;
}

As you can see the handleVertical method looks relatively the same, except for the the bottom part and hashset that is passed down recursively. As you can see when i hit a shape that's not grounded i'll add that shape to the hitShapes set and call that shape's handleVertical method. When the the function finally exits the hashset will contain all the possible polyominos  that root polyomino will hit as it moves down. I'll then treat all these shapes as one giant shape and move it all together. This is practically the same as clumping the shapes together except that i'm building the shapes on the fly instead of caching them. I actually had a solution pretty similar to this one but the major mistake was like osmanb highlighted I was trying to hard to isolate case 3 and 4.

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631782
• Total Posts
3002338
×