Handling collision on a turn-based 2D game

Question

I have implemented a collision check algorithm that I have created for my game, and the algorithm uses recursion.

Now it all works fine, and I thought to myself, what if there was a way to solve this algorithm, without using recursion, and more something with promise callbacks, or something, but unfortunately after researching, I could not find any way that I can think of at this time, so I thought I should ask there.

Now by turn-based I mean that the game is basically a big board of rectangles where each rectangle is a tile position, and there are ships, each ship can be on a tile unless its a rock, or another ship on there.

Now the collision is handled server-sided, so the coordinates are always integers, so it's not some graphical collision check, don't get me wrong.

There's an Example of collision, you can see that the ship selected the moves Right, Left, Right, and the left move collided, because the other ship does not move at that turn of the move.

So how does my algorithm work

    // Loop through all turns
    for (int turn = 0; turn < 4; turn++) {
        // Loop through phases in the turn (split turn into phases, e.g turn left is 2 phases, turn forward is one phase).
        // So if stopped in phase 1, and its a turn left, it will basically stay in same position, if in phase 2, it will only
        // move one step instead of 2 full steps.
        for (int phase = 0; phase < 2; phase++) {

             // Go through all players and check if their move causes a collision
             for (Player p : players) {

                 // If a player is already collided in this step, we don't want him to move
                 // anywhere, so we skip this iteration
                 if (p.getCollisionStorage().isCollided(turn)) {
                     continue;
                 }

                 // Checks collision for the player, according to his current step #phase index and turn
                 collision.checkCollision(p, turn, phase, true);
           }
        }
     }

So basically checkCollision(Player p, int turn, int phase, boolean setPos) is where the collision is handled, and is a big method. This method basically goes through the collision rules and saves into players' collision storage if it collided or not.

But here comes the recursion part: When a tile is already claimed, in the method, we check if the claimed player has a move placed on that turn, if yes, we will run the checkCollision method on that player that claimed it, if the player collided during his move, the method will return true, and then we know that this claimed player did not move, so the player we check for will collide with him. And now imagine a line of ships, and ship A wants to move forward, so we check ship B, ship B checks ship C and on and on and makes sure that every checkCollision returned false, so ship A can move and rest can move as-well.

Now I am curious, if there is a better way on implementing this besides using a recursion?

/**
 * Checks if a player has a collision according to his move, in the given turn and move-phase
 * @param p             The player to check
 * @param turn          The turn
 * @param phase         The move-phase step
 * @param setPosition   If to set the next position or not on non-collided result
 * @return  <code>TRUE</code> If the player was collided, <code>FALSE</code> if not.
 */
public boolean checkCollision(Player p, int turn, int phase, boolean setPosition) {
    // The current selected move of the player
    MoveType move =  p.getMoves().getMove(turn);

    // If this player was bumped, and a move was not selected, we want to process the bump animation
    // But we have to check if the position to be bumped is available to be claimed
    if (move == MoveType.NONE && p.getCollisionStorage().isBumped()) {
        Position pos = p.getCollisionStorage().getBumpAnimation().getPositionForAnimation(p);
        Player claimed = players.getPlayerByPosition(pos.getX(), pos.getY());
        // Claiming checking for the new position for bump
        return claimed != null && (claimed.getMoves().getMove(turn) == MoveType.NONE || checkCollision(claimed, turn, phase, false));
    }

    // Use the current position as default, imply we have already set it
    Position position = p;

    // If not set by default.txt on previous loops, gets the next position on the map for the given phase on the given move
    if (!p.getCollisionStorage().isPositionChanged()) {
        position = move.getNextPositionWithPhase(p, p.getFace(), phase);
    }
    // If the player has moved since his last position
    if (!position.equals(p)) {
        // Check for bounds collision with the border
        if (checkBoundCollision(p, turn, phase) || checkRockCollision(p, turn, phase)) {
            return true;
        }
        // Check if the next position is claimed by another player, null result if not
        Player claimed = players.getPlayerByPosition(position.getX(), position.getY());

        // If the result is not null, the position is claimed
        if (claimed != null) {
            Position claimedNextPos = claimed;
            if (!claimed.getCollisionStorage().isPositionChanged()) {
                claimedNextPos = claimed.getMoves().getMove(turn).getNextPositionWithPhase(claimed, claimed.getFace(), phase);
            }

            // Check if the claimed position doesn't move away
            if (claimed.getMoves().getMove(turn) == MoveType.NONE || claimedNextPos.equals(claimed)) {
                if (move != MoveType.FORWARD || claimed.getVessel().getSize() >= p.getVessel().getSize()) {
                    collide(p, claimed, turn, phase);
                }

                if (move == MoveType.FORWARD && canBumpPlayer(p, claimed, turn, phase)) {
                    bumpPlayer(claimed, p, turn, phase);
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }

                claimed.getVessel().appendDamage(p.getVessel().getRamDamage());

                return true;
            }
            else if (claimedNextPos.equals(p)) { // If they switched positions (e.g nose to nose, F, F move)
                collide(p, claimed, turn, phase);
                collide(claimed, p, turn, phase);
                return true;
            }
            else {
                // Make sure that the claimed position moves away successfully
                if (!checkCollision(claimed, turn, phase, false)) {
                    if (setPosition) {
                        // Moved successfully, claim position
                        p.set(position);
                        p.getCollisionStorage().setPositionChanged(true);
                    }
                }
                else {
                    // did not move successfully, collide
                    collide(p, claimed, turn, phase);
                    collide(claimed, p, turn, phase);
                    return true;
                }
            }
        } else {
            // List of players that collided with this player, while performing this move, in this phase
            List<Player> collisions = getPlayersTryingToClaim(p, position, turn, phase);

            if (collisions.size() > 0) { // Collision has happened
                collisions.add(p);

                Player largest = getLargestSize(collisions);

                if (countPlayersForSize(collisions, largest.getVessel().getSize()) > 1) {
                    // Stop players from movement
                    for (Player pl : collisions) {
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, pl, turn, phase);
                    }
                }
                else {
                    for (Player pl : collisions) {
                        if (pl == largest) {
                            continue;
                        }
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, largest, turn, phase);
                    }
                    if (!largest.getCollisionStorage().isPositionChanged()) {
                        largest.set(position);
                        largest.getCollisionStorage().setPositionChanged(true);
                    }
                }
                return true;
            } else {
                if (setPosition) {
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }
            }
        }
    }

    return false;
}

Answer 1

I'm not sure if you're looking to exactly reimplement the Puzzle Pirates collision mechanics described on the wiki page you linked to, or if you're simply looking to develop some reasonable collision handling system for a turn and tile based game. For this answer, I'm going to assume the latter, simply because I really don't feel like reading through the dense and complex set of rules listed on the wiki.

(For that matter, I'm not even sure whether your current code actually implements the rules described on that wiki page or not.)

In any case, you certainly can handle collisions non-recursively. You do need some method of dealing with "domino collisions" where a single collision triggers another one, but that can be handled e.g. by adding such secondary collisions into a "to do" queue (or stack) for deferred processing.

Here's a general outline of the algorithm I'd use to handle movement on each turn:

1. Save the original positions of all the ships.
2. Tentatively move all ships to their target positions.
3. If any two ships ended up on the same tile in the previous step, add this tile to the collision queue.
4. While the collision queue is not empty, repeatedly remove one tile from the queue and resolve the collision e.g. by moving all ships currently on the tile back to their original positions. If those positions already have other ships on them, add those tiles also to the collision queue.

Or, in pseudocode:

for each ship:
    ship.originalPosition = ship.currentPosition
    ship.setCurrentPosition(ship.moveTarget)

for each tile with more than 1 ship currently on it:
    queue.append(tile)

while queue.length > 0:
    tile = queue.removeNext()
    for each ship on tile:
         if ship.currentPosition != ship.originalPosition:
             ship.setCurrentPosition(ship.originalPosition)
             if ship.originalPosition has other ships on it:
                 queue.append(ship.originalPosition)

As long as the ships did not collide in their original positions, and as long as the collision resolution just moves ships back where they came from, this algorithm will always terminate. (If you wish to prove this rigorously, you can do so using the fact that there's a finite number of tentative moves to undo, and that each collision resolution always undoes at least one move, and does not introduce other new moves.)

A few notes about this algorithm:

• If two ships attempt to move into the same vacant tile, the algorithm as written above will prevent both of them from moving. If you want, you can let one of them (e.g. the bigger or the faster one) stay at the target tile when resolving the collision. However, if there's already a stationary ship at the tile (either because it didn't move at all, or because its planned move was undone due to another collision), then it should be the one to stay.

• If you want to implement "bump" mechanics, where a stationary ship may be forced to move due to a collision, that's probably best done in a separate pass before the actual collision resolution. That is, after initial tentative movement (step 2 above), check for cases where a single moving ship tries to move onto a stationary ship and make the stationary ship move in the same direction. This way, the actual collision resolution (step 4) still only undoes moves, and thus provably terminates.

• It's possible to implement partial movement failure (e.g. a ship being forced to go straight instead of turning and colliding) by queueing up multiple successive tentative moves per ship (e.g. first straight, then sideways) and undoing them one at a time if necessary. Note that in such cases the order in which the queued collisions are resolved (e.g. FIFO or LIFO) might sometimes affect the outcome.

• The algorithm above doesn't prevent two adjacent ships meeting head on from "slipping past each other" and exchanging positions. If you want to prevent that, that's probably also best done in a separate pass before the actual queue based collision resolution.

• For efficient collision detection with a lot of ships, you need some way to ask which ship(s) are currently at a given tile, e.g. by having each tile store a list of ships on it. I have not explicitly described this in my pseudocode above, but rather just assumed that the ship.setCurrentPosition() method takes care of maintaining all such state. (If you only have a few ships, simply iterating through them all may be practical, but it scales poorly.)

• You may want to give your tiles an "already queued" flag, to avoid queuing the same tile multiple times. Of course, the flag should be cleared when you remove the tile from the queue, so that the same tile can be re-queued if another collision occurs there. Alternatively, if your queue data structure supports efficient membership tests, you can use that instead. Or you can accept the possibility that tiles may be redundantly queued, and just make sure that your collision handling code will deal gracefully with cases where there isn't actually any collision because the tile has already been dealt with on a previous pass.

---

Ps. Note that there may be scenarios where a naïve implementation of recursive collision detection, like you describe, could end up recursing forever. For example, imagine you had four ships moving clockwise in a tight circle, like this:

_|_|_|_|_
_|_|A|_|_
_|D|_|B|_
_|_|C|_|_
_|_|_|_|_

with ship A trying to move onto the current position of ship B, ship B trying to move to where ship C currently is, and so on.

A naïve recursive collision resolver might start with, say, ship A, observe that the place it's trying to move was previously occupied by B, recurse to check if B can move, which would require it to further check if C can move, and then to check if D can move, and then — if the code is not smart enough to detect such loops — again recursively check if A can move, and so on.

The queue-based algorithm I described above doesn't suffer from this problem. Indeed, in this specific scenario, all the tentative moves will succeed, and thus no collision resolution is needed at all. However, if a fifth ship E tried to simultaneously move onto one of the ships A-D, then there would indeed be a collision, which would typically propagate through the queue and stop all the ships from moving — probably not an entirely unrealistic handling of such a complex traffic jam.