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.
