1
\$\begingroup\$

I am looking to see ideas for an algorithm which will handle collisions for some battle-ship tile-based board game.

A little about the game

The game is pretty simple. Basically there is a board, which usually sized 20x36 tiles. One tile is a position that a ship can be at, unless the tile is a rock tile.

Many ships are in the game, and all players have 35 seconds to select 4 moves that their ship will perform. After these 35 seconds, all ships will perform the selected moves parallel, by doing the first selected move, then going to the second, third and fourth, and then 35 seconds again to select new moves.

A ship can either move Forward, Left or Right.

Now these are the collision rules for the game:

  1. All ships that are moving (regardless of direction) attempt to "claim" the space that started directly in front of them. That space has five possibilites: a. That space is empty and unclaimed. Then move the ship into that space. b. That space contains a stationary ship. Then execute a "bump" (see below). c. That space contains a ship that is moving, and claiming the first ship's space. Then stop movement entirely (with a collision). d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision). e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision).
  2. All ships that are turning but have not "stopped entirely" then attempt to claim their destination space. Now that space also has five possibilities:

2.a. That space is empty and unclaimed. Then move the ship into that space.

2.b. That space contains a stationary ship OR a ship that moved there in step 1. Then stop movement entirely (with a collision).

2.c. That space contains a ship that is moving, and claiming the first ship's space. Then stop movement entirely (with a collision).

2.d. That space is empty but claimed by a ship of the same or larger class. Then stop movement entirely (with a collision).

2.e. That space is empty but claimed by a ship of smaller class. Then move the ship into that space (with a collision). Note: At the end, all ships have their orientation changed if they tried to turn... even if they had "stopped entirely." Note that (2b) does not depend on the ship's class. This allows a small ship to move forward into a tile even if a larger ship is attempting to turn into that tile. If two ships both try to move into the same tile for any other reason, the larger ship succeeds.

Example

So let's say you select the forward move on your ship, and there is another ship on the target tile you are aiming to (forward). So what do you need to make sure?

You need to check if that target tile is unclaimed. If it's not unclaimed, you can check if its a rock or another ship. If it is a rock, cancel movement. If it's another ship, and it does not move, push it by 1 tile and stay in the same location. If that ship does move, you have to ask it if that ship has successfully moved, but for it to return a success message, that other ship has to check if it can move, and that can have a lot of cases with a lot of callbacks and might end up not efficient.

So my question is, how can this be done, in the proper way?

Read more here about the collision mechanism rules

\$\endgroup\$
  • 2
    \$\begingroup\$ You've described the full algorithm already. What particular difficulty have you encountered in implementing these rules in your game? \$\endgroup\$ – DMGregory Sep 4 '17 at 15:38
  • \$\begingroup\$ If we go through the algorithm I described, this means I have to loop through all players atleast N times, where N is the amount of ships I have in the game. and that is only atleast. I assume that is not the most effective way of doing this \$\endgroup\$ – Ben Beri Sep 4 '17 at 17:17
  • 1
    \$\begingroup\$ @Jony How many players and ships do you have maximum? You should probably implement this first, and if it's too slow, then ask about it \$\endgroup\$ – Bálint Sep 4 '17 at 17:24
  • \$\begingroup\$ @Bálint Well it doesn't really matter if its slow or not, I just feel like the algorithm I described will just create me a big spaghetti and it will take me a long road to complete. I just want to see if there are more ideas to do this even better. \$\endgroup\$ – Ben Beri Sep 4 '17 at 17:26
  • 1
    \$\begingroup\$ I don't see any difficulties with implementing that algorithm. It's trivial. \$\endgroup\$ – Sopel Sep 10 '17 at 17:34
2
+100
\$\begingroup\$

I just feel like the algorithm I described will just create me a big spaghetti and it will take me a long road to complete

Not really. Appreciate that there is a difference between compile time code written to achieve a task, and the instructions / paths taken in silicon when that code is executed. The former's quite condensed and simple to read; whereas its runtime flow may be considerably more complex to follow, especially over multiple ticks. We don't usually look at the latter unless we are debugging, and at that point it is easy enough to follow our compile time code simultaneously to see how it drives the latter process.


If we go through the algorithm I described, this means I have to loop through all players atleast N times, where N is the amount of ships I have in the game.

But that's stock-standard collision detection / resolution in games like this. It behooves you to forego multiple phases / conditions of "did someone move here before me during this turn". See code below.

Still, there are many different ways to achieve collision detection and resolution. If you are working in a floating point space, then a trivial implementation will often go for the O(n^2) ("big-oh n squared") solution that you mention here. However, because you are working on tiles, there is a much simpler, finite space solution that I provide below. All you need to do for each ship is look at the proposed tile it wants to move to. You don't have to compare each ship to each of the other n-1 ships.


You delve into certain rules that make it difficult to write up an exact solution, which is to be expected: Even pro game devs hit a wall when their own specs go too far into the realm of speculation. That's when you need to stop thinking, pick up your keyboard, and start writing code in order to determine further requirements... until you do so, all you have is a fragile house of cards. It's like trying to explore the next room in a house when you don't even know where all the doors leading outward from the current one, are! Exploring game designs is a highly iterative process and requires you to constantly push, in code, to the leading edge of your ideas in order to explore further without wasting time.


Loose, rough, incomplete, untested C# code follows as a guide. (Please do not ask me to repeatedly come back and change this, as already it has taken a fair effort to draft this for you; and any areas I've left out are either trivial to implement, up to your interpretation, or were in conflict with other matters in your mini-spec. I am however happy to answer general questions in the comments, below.)


public class Tile
{
    Ship ship;
    Rock rock;
}

public enum Occupation
{
    None,
    Ship,
    Rock
}


public class Ship
{
    //assume 8 ship-facing directions (N, NE, E, SE, S, SW, W, NW in that order to represent a clockwise rotation)
    const int turnDegreesMax = 8;

    static const Vector2 offsetByHeading[] = new int[]
    {
        new Vector2(){0,-1}, //N
        new Vector2(){+1,-1}, //NE
        new Vector2(){+1,0}, //E
        new Vector2(){+1,+1}, //SE
        new Vector2(){0,+1}, //S
        new Vector2(){-1,+1}, //SW
        new Vector2(){-1,0}, //W
        new Vector2(){-1,-1}, //NW
    };

    public int sizeClass; //you could also prefer an enum here, to have named classes.
    public Move[] moves = new Move[4];
    public int moveStatus;
    public int heading;
    //suggest you use a integer, not float vector class, to avoid casting and other confusions
    public Vector2 position;

    public Vector2 ProposeMove()
    {
        //TODO - you need to check whether you will be outside of map bounds here,
        //i.e. (0-100) in x or y! and do not add delta if so.

        return position += offsetByHeading[heading]; //should return a new Vector2
    }

    public void MoveTo(Vector2 position)
    {
        //TODO - you need to check whether you will be outside of map bounds here,
        //i.e. (0-100) in x or y! and do not add delta if so.

        position += delta;
    }

    public void Turn(int delta)
    {
        heading += delta;

        //remember to ensure heading is still within range
        if (heading > turnDegreesMax-1)
            heading %= turnDegreesMax-1;
        else if (heading < 0)
            heading += turnDegreesMax-1;
    }
}


public class Move
{
    //for simple 8-directional gameplay, make range 0 to 7 representing each direction; else use float degrees / radians here.
    //range -1 to +1 inclusive: -1 is left turn, 0 is remain facing ahead (see heading), +1 is right turn; else use float here.
    public int turnDirection;
    //are we moving forward this move round? and if so, where are we moving relative to heading?
    public int linearDirection; //0 = no direction, 1= left, 2 = forward, 3 = right

    //NOTE: only ONE of these should be set non-zero at a time, as in one round,
    //you cannot be turning and moving into a new tile AND turning (for simplicity). 
}

public class Game
{
    Tile[,] tiles = new Tile[100,100]; //or whatever size
    //you will have pre-populated this in initialisation and other places,
    //e.g. where a shop or shipyard constructs a new ship for use.
    List<Ship> ships = new List<Ship>(); 

    //call once all players have queued their moves and hit "Go".
    void EnactRounds()
    {           
        //for each move out of 4 (do 1st phase moves for all ships, then 2nd phase moves for all, etc.):
        //NOTE: Unless we make explicit changes like shuffling the list or ordering by initiative,
        //we proceed in an order defined by the order in which ships were inserted into this list.
        //If you don't, certain ships will _always_ take move precedence over others.
        for (int i = 0; i < 4)
        {
            foreach (Ship ship in ships)
            {
                Move move = ship.moves[i];
                if (move.linearDirection != 0) //attempt linear move along current heading 
                {
                    //note: I don't deal with linearDirection's value here, I just need to know its non-zero to move forward:
                    //implementing left / right "strafe" movement is left to you as it is not central to collisions.
                    Vector2 proposedPosition = ship.ProposeMove();
                    Occupation occupation = IsTileOccupied(proposedPosition);
                    switch (occupation)
                    {
                        case Occupation.none:
                            //this updates the Tiles map, so that in the next foreach loop iteration calling this method,
                            //we will have the updated map ready for the next ship - remember: ship list order matters!
                            ship.MoveTo(proposedPosition);
                            tiles[proposedPosition.x, proposedPosition.y].ship = ship; 
                            break;

                        case Occupation.ship:
                            Ship shipOther = tiles[proposedPosition.x, proposedPosition.y].ship;
                            if (ship.sizeClass > shipOther.sizeClass)
                            {
                                //note we do not use shipOther.Bump(ship), because this will need access to higher level
                                //(map) data structures that the player's Ship instance / class may not have access to.
                                BumpInto(ship, shipOther);
                            }
                            else
                            {
                                //do whatever UI + sound FX to show player cannot go there.
                                BounceOff(ship, shipOther); 
                            }
                            break;
                        case Occupation.rock:
                            Rock rock = tiles[proposedPosition.x, proposedPosition.y].rock;
                            BounceOff(ship, rock); 
                            break;
                        default: break;
                    }
                }
                else
                {
                    if (move.turnDirection != 0) //ship is busy turning in it's current Tile / position
                    {
                        ship.Turn(move.direction);
                    }
                    else //no order was issued
                    {
                        //Ship waits through this round.
                    }
                }
            }
        }

        //...do other stuff...
    }

    Occupation IsTileOccupied(Vector2 position)
    {
        //you can rather generalise Ship and Rock to a supertype Entity and then just check the type, here (or in Tile). 
        if (tiles[position.x, position.y].ship != null) return Occupation.Ship;
        if (tiles[position.x, position.y].rock != null) return Occupation.Rock;
        //...etc.
        return Occupation.None;
    }
}

Obviously, I cannot write your game for you. This cannot be anywhere near exact, but it can provide a path to a solution. Try this out, and if it gets you on track to the solutions you desire, great.

\$\endgroup\$
  • \$\begingroup\$ @Jony Thanks for the accept. Just edited / improved the switch statement. \$\endgroup\$ – Engineer Sep 12 '17 at 16:06
  • \$\begingroup\$ Is there a way I can contact you some how, as in chat? Because there are some misunderstanding \$\endgroup\$ – Ben Beri Sep 16 '17 at 13:03
  • \$\begingroup\$ @Jony We can discuss some time next week. I'm working, now, and will be for the next few days. \$\endgroup\$ – Engineer Sep 16 '17 at 14:01
  • \$\begingroup\$ Ok! no problem, ill hit you up in a week. \$\endgroup\$ – Ben Beri Sep 16 '17 at 17:18
  • \$\begingroup\$ hey! are you available? I've got something to show aswell \$\endgroup\$ – Ben Beri Sep 18 '17 at 19:03
0
\$\begingroup\$

The algorithm will be a bunch of if-statements. But the data structure I think is more interesting. Since you did not provide a programming language, I will assume C++ in the following example:

typedef enum {
    EMPTY,
    SMALL_SHIP_1,
    SMALL_SHIP_2,
    BIG_SHIP_1,
    ...(etc)
} _tile_t;

This will define a type for a ship (basically an integer, since it may not be necessary to create a class for each type of ship if they share a lot of similarities. Then creating a container for the ships:

_tile_t game_board[20*36];

This will give you an implementation which is fairly easy to extend. Considering collision-detection for a ship in index i of the game board, check for game_board[i-1] for left (remember to account for the width of the game map), and game_board[i-WIDTH] for above (remember to account for the height of the game map).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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