What is the most efficient way to determine if a ship has been hit in a game of battleship?

Question

In both cases the ships do not overlap and may be adjacent to each other.

Case 1 - All ships are 1xN and are either vertical or horizontal

• Ship object contains the coordinates of the starting point (top
  left), direction, and size
  • Every time a shot is fired we iterate over all ships, for each ship we calculate their coordinates and determine if one of the coordinates matches shot coordinates

This already seems inefficient, since for each shot we have to iterate over all the ships.

Case 2 - All ships are arbitrary size, the board is 1 billion by 1 billion squares, and there are 1 million ships

• Using the previous method would definitely not work, since we how have to keep a list of all coordinates for each ship and each shot would take a significant time to process

What would be the most efficient way of tracking the ships location / coordinates, such that the solution scales gracefully?

Answer 1

It can be solved with clever indexing. So, all you need is some arrays. First, an array where you store the whole game, like this:

1 0 0 0 1 1 1 0
1 0 0 0 0 0 0 0
1 0 0 0 2 0 0 0
0 0 2 2 2 0 0 0

This reads as the first player got the first 4 columns as his field, and the last 4 columns belongs to the second player. The zeroes represents empty areas, while the 1's and 2's represents ships. Now ask yourself, does it really matter, if the ship gets hit at the center, or at the bottom? Not really. If the ship is hit, it's hp gets reduced by 1. So, how do you store the ships hp? Simple, more arrays! Let's create another 2d array. The first row represents the total hp left of the first player's ships, and the second row does the same, just with the second player.

0 3 2
0 3 2

Now, if a ship is hit, the corresponding value of the array will be decremented. The game is over for a player, when the sum of his rows is 0, or you can store the sum of the total ships, and decrement that too after each hit. But wait, what if you hit a zone with no ships, it still decrements the first ([0]) value, which affects the sum. Well, you can handle it with a simple if. But here is another solution, and guess what is it: an array! Let's create an array with columns of total ships + 1:

0 1 1

And decrement the hp array with the index of the game array value

hpArray[enemyPlayer][gameArray[hitX][hitY]] -= hitArray[gameArray[hitX][hitY]]

So, no matter what we hit, we get the result of what we wanted to do.

Another clever thing that will make this work faster and clearer, if you store the player turn in a simple int, with value of 0 or 1. Then you can always refer to the enemy player with 1 - playerTurn.

Answer 2

Let's assume for a moment that you can hold all the information in memory in a naive fashion.

Your board is of size N x M, and there are S ships of arbitrary size. I'm going to make some assumptions:

1. The ships are rectangular. It'd be easy enough to allow for irregularly-shaped ships, but rectangular is easier to talk about.
2. The ships sides are parallel to the grid lines. Again, it'd be easy enough to allow for arbitrary orientations.

You represent your ship as:

Ship
    Id
    Top
    Left
    Width
    Height
    Hits // array of [Height x Width] Booleans that indicates which positions have been hit.
    HitCount // number of positions that have been hit. When HitCount == (Width x Height), the ship is sunk.

And your board is an N x M array of references to ships. So a 5 x 4 board with two ships might look like:

     0     1     2     3     4
0  ship1 ship1 ship1 NULL  NULL
1  ship1 ship1 ship1 NULL  ship2
2  NULL  NULL  NULL  NULL  ship2
3  NULL  NULL  NULL  NULL  ship2

Now, somebody takes a shot at row 1, column 3. You look in the array and see that there is no ship in that square. Clean miss. The next shot goes to (2, 4). You index into the array and see that it's ship 2. You look up Ship 2, translate the board position (2, 4) to the ship's Hits array (in this case, it would be (0, 1), and record the hit. Increment the HitCount if that position had not been previously hit. When HitCount == (Width x Height), the ship is sunk.

That representation allows for direct lookup whenever a shot is made: no searching required. In asymptotic terms, it requires O((N x M) + S) memory, and shot processing is O(1). Actually, the worst case memory is 2*(N x M), because it requires Height*Width memory for each ship, and in the worst case the ships could fill the entire board.

The point is, if you have enough memory to represent the entire data structure, then lookup is very efficient and doesn't depend on the size of the board or the number of ships.

You can reduce the memory footprint of the structure above using some simple tricks. Using a bit array or something similar rather than an array of Booleans for the Hits, for example, can save you some space. And storing the ships in an array and using an index rather than a reference in the board can cut the space used for the board in half. But even with memory optimizations, that structure can only go so far. With 16 gigabytes of RAM, your maximum board size would probably be on the order of 100,000 x 100,000.

If you really want a board that's a billion by a billion, with a million arbitrarily-sized ships, the representation above would take a huge amount of memory. The board itself would be 2^60 cells. You'd have to get really creative in the use of sparse data structures, but since ships can be of arbitrary size, you'd have to allow for the worst case: the ships occupy so much space that the sparse data structure gives you no savings. Eventually you'd have to come up with a representation that can spill to disk, or that can be spread across multiple machines in a massive cluster.

Answer 3

I have to disagree with the quad-tree solution- while it is still fast and will get the job done, it completely ignores any innate structure of the data points being stored. If you want a fast, ready-made solution then that's probably the way to go since many languages will have support for quad trees or at least k-d trees (k=2). If you want something that's a bit faster and uses a bit less memory, then consider the following:

Iterate across the vertically-oriented ships, and bin them by their x-coordinate into arrays, storing tuples of their y-coordinate, size, and id (sorting by y-coordinate). Then construct another array that contains tuples of these arrays and their corresponding x-coordinates, sorted by x-coordinates. To find if a mark hits a vertical ship, you then perform a binary search on the first array to find all ships in that column, and then perform a second binary search to find the ship with the largest y-coordinate equal to or less than the mark's. Check if mark_y < ship_y + ship_size, if so the mark hit that ship, otherwise it hit nothing. Repeat this process for the horizontal ships, and optionally prioritize checking the orientation with more ships for a hit first.

While this sounds very similar to a quad-tree, there is an important difference- we partition the grid along one axis entirely before starting the other axis. We do this so that we are not storing every point the ships extend across; we only only store their anchor in the top-left. We cannot do this with a quad-tree, because we need to query that column specifically (or row for horizontal ships) to find if the ship "above" the mark extends through the mark. If the ships scale with the size of the board, this will result in a small asymptotic speedup over the naive quad-tree. If they remain at a fixed N, then it still reduces the number of queries by log2(N), and reduces the memory consumption by N.

Answer 4

I think this is a natural for a quadtree (https://en.wikipedia.org/wiki/Quadtree).

These work by recursively dividing a 2-d region into 4 subregions. It takes advantage of the fact that many subregions will be identical. I'll quote wikipedia:

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

The subdivided regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of quadtrees share some common features:

They decompose space into adaptable cells Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits The tree directory follows the spatial decomposition of the quadtree.

This should let you efficiently store and query your space.