Collision problem

[josephjohn]

I am making a tile-based game where you can select multiple units and have them move. This is where the problem is. I have it set so that when you press "d", all the selected units move right. But if the placement is like this:
we have the units positioned like: XXXO, where X is a unit and O is an obstacle that units cant pass through.
If I press "d", all the units set their target x position to be 1 tile right of them. Then they check if the tile they will move to will be free in the future. So if we have: XX, and i press "d", both will first set their X position one tile to the right, and then check if that position will be occupied in the future. So, even though the first unit will, in the next frame, be in a position that is currently occupied by the second Unit, it only checks the future position, and since the future position of the second unit is not in the position the first unit is trying to move to, both units will move normally.

But if there is an obstacle next right of one of the units, everything goes whack, so it goes:
XXXO: unit placement, and then the next frame it goes:
X>X>X>O: each unit sets their desired future X position, which is one tile to the right, all currently occupied. Then, one by one, left to right, they check future collision:
X>X>XO: The first unit sees that the second unit's future position is set one tile to the right, so the first unit will move one tile to the right. The second unit sees that the last unit's future position is also set one tile to the right, and so it moves also, but then the last unit sees that it's future position will collide with the obstacle (O), and it doesn't move there. But since the second Unit did move to the right, now the second and the last unit are occupying the same position.

I attacked a picture to show you more easily what I'm talking about.

[MrFariator]

Perhaps the quickest way to resolve this is to start from the direction the objects are moving towards. Eq. if the objects are moving towards right, update the right-most object first, the second right-most second, etc. Thus if the first one moving to the right gets blocked, it could signal the ones following it to not move.

If this is not possible, then alternate approach is to let all objects in the chain resolve whether they can move or not first, and only then apply the movement based on the neighbor's result. Some application of observer pattern could also potentially be used (an object signals that it moved to tile (x,y), freeing tile (w,z), and another object expecting to move to (w,z) then does so), but probably unnecessary.

[zorg]

One solution to this is to "double buffer" logic; let me expand on what i mean by that.

A good and somewhat simple example would be an implementation of Conway's Game of Life. You have a 2D grid, and you constantly update cells based on their neighbours. Whether or not the playfield is toroidal (i.e. wraps around on the borders) you need to store both the persent state of a cell (that is read only) and the future state (to which you'll write based on reading from the past states of the adjacent cells); you can also call them past and present, doesn't matter as long as one's read-only and the other write-only.

Doing it like that makes it so that processing order (based on spatial coordinates or even other parameters) won't matter; you'll just need to "swap buffers" as it were, after processing all objects you need to. (Or just set the read-only variables to the new values that were calculated, and zero or nil the writeable ones after, although swapping might work faster, or at least just as well)

[josephjohn]

Perhaps the quickest way to resolve this is to start from the direction the objects are moving towards. Eq. if the objects are moving towards right, update the right-most object first, the second right-most second, etc. Thus if the first one moving to the right gets blocked, it could signal the ones following it to not move.

If this is not possible, then alternate approach is to let all objects in the chain resolve whether they can move or not first, and only then apply the movement based on the neighbor's result. Some application of observer pattern could also potentially be used (an object signals that it moved to tile (x,y), freeing tile (w,z), and another object expecting to move to (w,z) then does so), but probably unnecessary.

Worked perfectly, thanks!