Moving players into same square simultaneously?

Consider a 2 x 2 grid of squares. A player can move onto a square if:

• no other player wants to move into the square next turn
• no other player has waited and is still occupying the square this turn

I have included the image above to describe my problem.

Players move simultaneously.

If 2 (or more) players try to move into the same square, neither move.

• can player move to each others tiles in one step? for example can yellow and blue switch places in exactly same step (blue goes one tile left, and yellow goes one tile right)? Commented Sep 29, 2011 at 20:15
• Gajet yes for now. But at some point I would not like 2 neighboring players to be able to swap places directly
– t123
Commented Sep 29, 2011 at 20:34
• then my answer solves that issue. Commented Sep 29, 2011 at 21:08
• EXTREMELY relevant: check out the movement rules for Diplomacy. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase Commented Sep 30, 2011 at 4:00

1. Flag all players as either stationary or moving, depending if they submitted a move this turn.
2. Go through the list of moves. If two moves point to the same location, remove them from the list and set the players stationary.
3. Loop through the list removing all moves that point to a stationary player or other obstacle. Do this repeatedly until the list doesn't change when you pass through it.
4. Move all players.

I think that should work. It certainly works for the case you posted, and a couple of other trivial cases I tested it on.

• Yes, this should work. Note that you don't actually want to loop repeatedly over the list of players; in practice, it will be much more efficient to resolve collisions by backtracking. Commented Sep 29, 2011 at 21:17

Collision resolution, instead of collision prevention.

Simply move the objects, then check if there have been any collisions. If there has been a collision with another block move back to previous square, or depending on the game type, a different square.

• Yes but if one has to move back then others will have to move back too...
– t123
Commented Sep 29, 2011 at 15:55
• You are correct, but again it depends on the actual game type, more information would be required and the situation would change based on the type. This was about the most generic answer available. Commented Sep 29, 2011 at 15:57
• you don't have to resolve all collisions in one step. move all object, check if there is any collisions reverse moves related in that collision, repeat this process until there is no collision left. Commented Sep 29, 2011 at 20:14
Move all players according to their request.
while there are still some squares multiply occupied:
For each square that is now multiply occupied:
For each player in that square that moved there this turn:
Return them to their previous square
Mark them as having not moved this turn


This requires that each player remembers where they just moved from, so that they can be returned, and also they remember whether they moved this turn. This second check means each piece will only need returning once and should guarantee the algorithm terminates properly. It also ensures that only players that moved are returned - the original occupant gets to remain as they are not considered for removal.

Another solution is to use a map 2x larger than what your are showing. each time you want to move players you move them twice so players always land on tiles with even value for both X and Y. again there will be some rare cases that will need more attention but most of possible cases are resolved (like the one you described) without thinking twice.

• I think that you have something in mind here, but it is not coming through in your answer. How does using a 2x map solve the collision problem? Commented Sep 29, 2011 at 23:53
• Okay. I think I see the answer. Two pieces moving opposite directions land on the same square and collide. Pieces moving around clockwise move half-steps, always leaving an open space for another piece to move into. Commented Sep 29, 2011 at 23:55
• @ZanLynx: that's exactly how it solves the problem, the only problem will be when two pieces (say green and blue) are going to collide and another piece (yellow) is going to fill green's last position. in cases similar to these (if they are possible) you need to resolve collisions as ultifinitus suggested. Commented Sep 30, 2011 at 1:00
• the easiest implementation I know for collision detection is a mix of mine and ultifinitus. mine is good to check if pieces are crossing each other and unltifinitus is good to solve other types of collision. Commented Sep 30, 2011 at 1:05

Register all requested moves using an array or map.

If there is a conflict, revert the move request in question. If that returns the object to a square another object is trying to occupy, revert the requesting object's request.

Pseudo code:

int[][] game; // game board

var doMoves() {
int[][] dest = [][]; // destinations; cleared each run

for (obj in gameObjects)
if (obj.moveRequest) {
var o = dest[obj.moveX][obj.moveY];
if (o) {
// collision!
o.doNotMove = true;
obj.doNotMove = true;
} else {
dest[obj.moveX][obj.moveY] = obj;
}
}
}

// check move validity
for (obj in gameObjects) {
if (obj.doNotMove) continue;

var o = game[obj.moveX][obj.moveY];
if (o and o.doNotMove)
revertRequest(obj, dest);
}

// process moves
//etc
}

// recursive function to back up chained moves
var revertRequest(obj, dest) {
if (!obj.doNotMove) {
obj.doNotMove = true;
var next = dest[obj.x][obj.y];
if (next)
revertRequest(next, dest);
}
}


Building on SimonW's answer, here's an explicit algorithm:

Let squares be an array indexed by the player locations, and containing, for each possible location, either the index of another location or the special value NULL. (You may want to store this as a sparse array.) The possible values of the entries in this array may be interpreted as follows:

• If squares[S] is NULL, the square S is free to move into.
• If squares[S] == S, either the player at S cannot or will not move, or two (or more) players tried to move to S at the same time and were both denied.
• Otherwise, squares[S] will contain the index of the square from which a player wants to move to square S.

On each turn, initialize all entries of squares to NULL and then run the following algorithm:

for each player:
current := the player's current location;
target := the location the player wants to move to (may equal current);
if squares[target] is NULL:
squares[target] := current;  // target is free, mark planned move
else
// mark the target square as contested, and if necessary, follow
// the pointers to cancel any moves affected by this:
while not (target is NULL or squares[target] == target):
temp := squares[target];
squares[target] := target;
target := temp;
end while
// mark this player as stationary, and also cancel any moves that
// would require some else to move to this square
while not (current is NULL or squares[current] == current):
temp := squares[current];
squares[current] := current;
current := temp;
end while
end if
end for


After that, loop through the list of players again, and move those which are able to do so:

for each player:
current := the player's current location;
if not squares[current] == current:
move player;
end if
end for


Since each move can only be planned once and cancelled at most once, this algorithm will run in O(n) time for n players even in the worst case.

(Alas, this algorithm won't stop players from switching places or crossing paths diagonally. It might be possible to adapt Gajet's two-step trick to it, but the completely naive way to do so won't work and I'm too tired to figure out a better way just now.)