What is the most efficient way to determine if a ship has been hit in a game of battleship?
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?
3 Answers What is the most efficient way to determine if a ship has been hit in a game of battleship?
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.
Dave 1 months ago
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
Dillon Davis 1 months ago
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:
- The ships are rectangular. It'd be easy enough to allow for irregularly-shaped ships, but rectangular is easier to talk about.
- 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.