Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

Example Diagram

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.

share|improve this question
1  
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)? –  Ali.S Sep 29 '11 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 –  tm1rbrt Sep 29 '11 at 20:34
    
then my answer solves that issue. –  Ali.S Sep 29 '11 at 21:08
2  
EXTREMELY relevant: check out the movement rules for Diplomacy. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase –  TehShrike Sep 30 '11 at 4:00
add comment

6 Answers

up vote 8 down vote accepted
  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.

share|improve this answer
    
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. –  Ilmari Karonen Sep 29 '11 at 21:17
add comment

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.

share|improve this answer
1  
Yes but if one has to move back then others will have to move back too... –  tm1rbrt Sep 29 '11 at 15:55
2  
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. –  ultifinitus Sep 29 '11 at 15:57
5  
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. –  Ali.S Sep 29 '11 at 20:14
add comment
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.

share|improve this answer
add comment

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.

share|improve this answer
    
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? –  Zan Lynx Sep 29 '11 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. –  Zan Lynx Sep 29 '11 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. –  Ali.S Sep 30 '11 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. –  Ali.S Sep 30 '11 at 1:05
add comment

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);
    }
}
share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.