Battleship is a game of two players which is played on grids on which each players fleet of ships are marked. Players take turns to take shots at the other player’s ships. The objective of the game is destroy the opponent’s fleet. Read more on Wikipedia. Building this game is also a very famous design interview question.
We are going to build the game in Kotlin using Redux architecture. We will implement the logic and not worry much about the UI since it’s secondary.
Rules of Battleship
Before we begin writing some code, it’s imperative that we familiarize ourselves with the rules.
- There are 2 players in the game. Each player has a board to place their fleet and a board to mark their shots.
- Each player is allotted identical fleet of ships. Based on the game, the type and number of the ships may vary.
- Each player take turns calling the shot alternatively until a player’s fleet is completely destroyed.
- When a player takes a shot at a grid on the board, the other player has to honestly acknowledge the shot and let the offense know if they hit a ship or not. The offense marks the grid based on the defense’s response.
Let’s analyze what type of models and data structures we will require to build the game.
User: The player.
Board: The board of size
(w, h)that belongs to the player.
Ship: A ship of size
s, located at grid
Point: A point
(x, y)denoting the grid on the board.
Direction: Direction of the ship -
Let’s start from the smallest model required.
The point denotes a grid on the 2D-board. The point and grid representation is from
A ship may have a name, but it’s not that important right now. A ship has a size - how many grids long it is. We also need to put the ship on the board, so we need start point and end point of the ship to correctly determine where the ship is.
If we take board as a 2D space, a ship can be termed as a vector which has a magnitude and a direction (vertical or horizontal). We need a fix point to place the ship on the board.
Let’s write a class for
This definition is not complete yet and we shall revisit this later.
A board has a size and contains the fleet.
These models just represent the setup of the game. It doesn’t support any gameplay, eg. what happens when a player takes a shot?
The logic of the gameplay is complex and would involve some changes to our models.
When a player takes a shot at a grid, they mark it down on their board if they hit a ship or missed. It means that we need to store if each shot was hit or missed. To keep track of hits and misses, we will add
hits: Set<Point> and
misses: Set<Point> to the board.
When a player takes a shot, the defense also marks down on their board if the shot hit or missed. We will add
opponentHits: Set<Point> and
opponentMisses: Set<Point> to the board model to keep track.
It’s also helpful if we mark the hits to the ship so that we can easily track if the ship is completely destroyed or not. We will add
hits: Set<Point> to the ship model.
We also need to keep track which ship are still active and which are completely destroyed so that we can know if the game is over once all the ships are destroyed. We can add
active: List<Ship> and
destroyed: List<Ship> to the board. The data structure is immutable and we should try to keep it lean as much as possible. We can use
active: List<Int> and
destroyed: List<Int> and unique
id: Int to each ship.
destroyed to the ship model.
id - unique identifier for the board and
user. We also added
opponentMisses to keep track of the moves and where the user can play. We added
lost to have better representation of the gameplay.
Kotlin operator overloading
Kotlin allows us to provide implementations for a predefined set of operators on our types. We can use
in and other operators to make our code concise and readable.
The board has a predefined fixed size and if we want to add a ship on the board, it should fit the board.
Now, we can check if a point is on the board or not by just calling
p in board which would return a boolean.
When a shot is taken, we need to check if it hit the ship or not.
We have not defined
Ship.end yet. So let’s do that now with the help of operators. We will define
WeighedDirection which is an actual representation of a vector.
direction * sizecalls
Directio.times()method and returns
start + WeighedDirectioncalls
Point.plus()which gives us the end point of the ship.
And now we can check if a point exists on the ship by calling
p in ship.
In the game, no two ships can overlap. So let’s overload another operator which would help us check if two ships overlap.
This is a complex logic and if you’re not in habit of solving such equations, I’d recommend that you try once. It took me some time to come up with the solution. We can use this operator to check if two ships overlap by simply calling
ship1 in ship2.
Explanation: If both the ships have same direction, we need to check if start or end point one ship lies on the other or not.
The logic becomes complex when the ships have different directions. We don’t care what direction the ships have since there are only two directions so we create instances for vertical and horizontal ship.
A horizontal ship has the same row for all the points and similarly, the vertical ship has the same column for all the points. So we check if the vertical ship passes through the row of the horizontal ship and the horizontal ship passes through the column of the vertical ship. This would get us the intersection point.
horizontal.start.row in vertical.start.row...vertical.end.row - 2 operators are used here.
in which we have overloaded in
.. which is the range operator.
Board models to build our battleship game. Here’s how the final version looks.
We have created our models and data classes. It’s time to work on the UI so that we can see the game in action.
Disclaimer: I’m not going to spend a lot of time in making amazing UI as it’s not the focus of the series. The UI is going to be super ugly!
We are going to use
GridLayoutManager to create the board. Each grid of the board will be a
ViewHolder. We shall use a custom view to draw some paint and dots which would represent ships and shots on the board.
This is how it’s going to turn out.
Let’s look at the components that are being used here.
- Cell: UI model which maps
Boardto an individual
Grid. After every update, we create new cells which represent grids of the board. For a board of size of 10 columns and 10 rows, we will have
10*10 => 100cells.
- SquareCell: UI representation of the
Grid. It extends
Viewand binds with
Cellto draw and display the data. It’s a square view which draws the ship, hit and missed points on the canvas.
- UiCellAdapter: RecyclerView Adapter that we use to draw the board on the screen.
Without going much in the details, here’s the code which will render the game UI. You can find the layout for ViewHolder here - square_cell_itemview.xml.
We have the components for the UI ready, but we still need to convert
List<Cell>. We create a list with capacity of
width*height and iterate over each point and create
Battleship in Action
Let’s write an Activity and configure some code so that we can play with it. We’ll use a layout which has a RecyclerView. After creating the adapter, we would set up the boards. For this, we will randomly place the ships on each boats. We will add a click listener on the grid so that you can take a shot on the board.
I have quickly gone through the UI composing part as the article already has too much content. If you have any questions, feel free to leave a comment or get in touch with me.
We are ready with our models and data structure. In the next article, we will use Redux architecture to implement the gameplay logic.
Redux architecture series
- Introduction: Redux architecture for android apps
- Middleware: Introduction and implementation
- Write your own Redux implementation in Kotlin
- Add Middleware to your Redux implementation
- Build Battleship Game with Redux - Groundwork
- Implement the Battleship gameplay with Redux