Moving players into same square simultaneously?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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