 Thanks to Julio Marchi for this space in MSX All Games Course Battleship

Portugues

Also known as Sea Battle, it is a strategy game, where one player must hit all ships from the opponent before the opponent hit your ships.

1. Game rules
There are some variations of this game. From the board size to the number of ships and their arrangement.
In this version, the board grid size is 10x10, where the horizontal coordinates are denoted by letters, while the vertical coordinates are represented by numbers. An example of a coordinate is "B7". Thus, this game has 10 ships, configured as follows:
``` Type             | Format  | Total
-----------------+---------+-----------
Aircraft Carrier | AAAA    | 1
Cruiser          | CCC     | 2
Battleship       | BB      | 3
Submarine        | S       | 4
```

Initially, each player places his/her ships on the board without exceeding the board dimensions.
```Valid   Invalid
.....   .....
.BB..   ....BB
.....   .....
.....   .....
.....   .....
```

The ship overlapping is not allowed. Also, the ships must be separated by at least one board cell from each other.
```Valid   Invalid   Invalid
.....   .....     ..S...
.BB..   .BS..     .BB..
.....   .....     .....
...S.   .....     .....
.....   .....     .....
```

The goal is to find the opponent's ships before hi/she finds yours.
There are two boards on the game: one for writing the player's own ship positioning, and the other to write the opponent's game, as soon as the player finds out the ships.
Each player informs a coordinate to the opponent and he/she answer "water" if a cell contains no ship or "hit a ...", if a part of a ship is found.

2. Game routines
Draw game

The game will take place on screen 1 for a better legibility.
```5 ' Rem MarMSX 2018
10 COLOR 15,0,0:SCREEN 1:WIDTH 32:KEY OFF
...
200 '
201 ' Draw game
202 '
210 DIM PX(2):PX(1)=0:PX(2)=18
220 FOR I=1 TO 2
230 LOCATE PX(I)+2,0:?"ABCDEFGHIJ"
240 NEXT I
250 FOR Y=1 TO 10:FOR I=1 TO 2
260 LOCATE PX(I),Y:PRINT RIGHT\$(" "+STR\$(Y),2);".........."
270 NEXT I,Y
275 LOCATE 4,12:PRINT"You":LOCATE 24,12:PRINT"Me"
280 LOCATE 0,17
290 FOR I=1 TO 5
300 LOCATE 0:READ A\$:PRINT A\$;
310 LOCATE 18:READ A\$:PRINT A\$;
320 LOCATE 26:READ A\$:PRINT A\$
325 IF I=1 THEN PRINT
330 NEXT I
340 RETURN
...
2000 '
2001 ' Game data
2002 '
...
2020 DATA Ship, Format, Total, Aircraft Carrier, AAAA, 1, Cruiser, CCC,
2, Battleship, BB, 3, Submarine, S, 4
```

Ship positioning routine

There are two ways to position the ships on the board: the first one is creating a routine where the player himself position the ships; the second one is creating a routine that places all ships automatically.
In this game version, we will place the ships automatically for both player and computer. So, we can take advantage of the same rotine to place all ships.
We will create a three dimensional matrix to store both boards together. In that case, "TJ" has the dimensions of 10x10x2.
```20 BT=10:DIM TJ(BT,BT,2):DIM N\$(4)
```
Obs: the size of the board is indicated by the variable "BT", which gives more flexibility to the positioning routine.

For example, if we would like to access the player's position 5,4, we should write TJ(5,4,1). For the same computer's coordinate, TJ(5,4,2). So, the last coordinate controls the player's or the computer's board.
The array "N\$" will store the symbol of four ship types:
• A - Aircraft Carrier
• C - Cruiser
• B - Battleship
• S - Submarine
In the game data area (lines 2000 to 2020), we will store the informations about the ships' symbols, length and amount. In this game version, all ships are drawn horizontally.
```2010 DATA A,4,1,C,3,2,B,2,3,S,1,4
```
Obs: as these data will be read before than the drawing routine data, they must appear first on the program listing.

After creating all necessary informations, we are ready to place the ships on the boards.

Basic strategy for ships positioning:
```var TJ : array[1..10, 1..10, 1..2] of integer;
N : string;
C,T,X,Y : integer;
i, it, p : integer;

for i ← 1 to 4 do
read(N, C, T);
for it ← 1 to T do
for p ← 1 to 2 do
X ← random(10-C+1);
Y ← random(10);
insert_ship(i, X, Y);
end_for
end_for
end_for
```

Where:

 ```for i ← 1 to 4 do read(N, C, T); for it ← 1 to T do for p ← 1 to 2 do X ← random(10-C+1); Y ← random(10); insert_ship(i, X, Y); end_for end_for end_for ``` ```for i ← 1 to 4 do read(N, C, T); for it ← 1 to T do for p ← 1 to 2 do X ← random(10-C+1); Y ← random(10); insert_ship(i, X, Y); end_for end_for end_for ``` ```for i ← 1 to 4 do read(N, C, T); for it ← 1 to T do for p ← 1 to 2 do X ← random(10-C+1); Y ← random(10); insert_ship(i, X, Y); end_for end_for end_for ``` For each ship type, read the symbol (N\$), the length (C) and the total (T). For the same ship type, repeat T times. For each player, get randomly the X and Y coordinates and place the ship there.

How to ensure that the random value do not place the ship outside the board limits? If the object size is 1, the problem is solved by creating a random number between 1 and 10. Nevertheless, some objects have their length greater than 1 along the X axis.
To solve this issue, we will create a pivot on the least X coordinate of the object and delimit the X maximum value according to the object length "C". Ship pivot in green

For a 10x10 board, the random values are calculated as follows:
```Y: min=1, max=10
X: min=1, max=10-C+1
```
For example, the cruiser with length "C" equal to three, the variable X ranges from 1 to 8, and the variable Y ranges from 1 to 10, which corresponds to the red rectangle on the last figure.

After calculating X and Y, we must write the ship code in the "TJ" matrix. Thus, we must write it "C" times on consecutive cells. So:
```  for ic ← 0 to C-1 do
TJ[X+ic,Y,P] ← i;
end_for
```
Obs: once the "TJ" matrix uses integer values, we will store the ship code and not the ship symbol.

The code in Basic is:
```400 '
401 ' Place ships
402 '
410 FOR I=1 TO 4
413 LOCATE 0,2:PRINT"Placing ships:";INT(100*(I-1)/4);"%"
415 READ N\$(I),C,T
420 FOR IT=1 TO T
425 FOR P=1 TO 2
430 X=INT((BT-C+1)*RND(-TIME))+1
435 Y=INT(BT*RND(-TIME))+1
440 IF I>1 THEN GOSUB 500 ELSE 460
445 IF FV=1 THEN 460
450 X=X+1:IF X+C-1>BT THEN X=1:Y=Y+1
453 IF Y>BT THEN Y=1
455 GOTO 440
460 FOR IC=0 TO C-1:TJ(X+IC,Y,P)=I:NEXT
465 NEXT P,IT,I
470 RETURN
```

The lines 440-455 handle the objects overlapping. Nevertheless, it is not necessary to check overlapping for the first object (Carrier), once the board is empty.
The routine in line 500 is responsible for checking the overlapping. It returns "FV=0", if the current object overlaps another object.
If overlapping is true, we can adopt one of these two strategies:
• Repeat lines 430 and 435 and pick up X and Y randomly; or
• Move X and Y to the next position inside the red rectangle area.
Depending on the number of empty cells, picking up a valid X and Y randomly would take a considerable time. According to that, we adopted the second strategy (lines 450-455).

Overlaping free routine

Once calculated the ship pivot coordinates X,Y, we must check if the ship overlaps another object.
Do not forget that objects must be far aways at least 1 cell from each other. In order to ensure that, we will create a bounding box enlarged by 1 cell and check if any object lies inside that area. The example on the figure above shows a verification area (green) for a cruiser.

Code:
```500 '
501 ' Check for overlapping
502 '
510 FV=1
520 FOR VY=Y-1 TO Y+C:FOR VX=X-1 TO X+C
530 IF VX<1 OR VX>BT OR VY<1 OR VY>BT THEN 550
540 IF TJ(VX,VY,P)<>0 THEN FV=0:RETURN
550 NEXT VX,VY
560 RETURN
```

Display player's game

This routine displays the player's game.

```1000 '
1001 ' Display player's game
1002 '
1010 FOR Y=1 TO 10:FOR X=1 TO 10
1020 LOCATE X+1,Y:IF TJ(X,Y,1)<>0 THEN PRINT N\$(TJ(X,Y,1)) ELSE PRINT " "
1025 'LOCATE X+19,Y:IF TJ(X,Y,2)<>0 THEN PRINT N\$(TJ(X,Y,2)) ELSE PRINT "X"
1030 NEXT X,Y
1040 RETURN
```

Main loop

After positioning the ships and drawing the screen, we create the main loop which controls the actions from both player and computer.

```30 PRINT "Battleship - MarMSX 2018"
40 GOSUB 400:CLS:GOSUB 200:GOSUB 1000
50 CX=20:CY=1:PJ=0:PC=0
100 '
101 ' Main loop
102 '
110 LOCATE CX,CY:A\$=INPUT\$(1):A=ASC(A\$)
120 IF A=29 THEN CX=CX-1:IF CX<20 THEN CX=20
130 IF A=28 THEN CX=CX+1:IF CX>29 THEN CX=29
140 IF A=30 THEN CY=CY-1:IF CY<1 THEN CY=1
150 IF A=31 THEN CY=CY+1:IF CY>10 THEN CY=10
160 IF A=32 THEN GOSUB 600:IF V=1 THEN GOSUB 650
170 GOTO 110
```

This code controls the player's moves on the opponent's map, this one used to save the opponent's ships locations.
The space bar marks the current location as visited (hits) and reveals to the player what is under that cell.
The routine called (line 600) returns a flag "V" indicating if the requested cell is valid. If true, it passes the control to the computer's routine (line 650).

Player move

This routine first checks if the required cell was not opened before by reading the screen coordinate and checking if the current chracter is a dot ".".
If the cell is unvisited, it marks as visited with a blank character " " if the "TJ(X,Y)" value 0, or with the ship corresponding symbol(N\$) otherwise.
By hitting a ship, the "PJ" variable is incremented informing that an object was found. When "PJ" reaches 20, the player wins.
```600 '
601 ' Player move
602 '
610 V=1:IF VPEEK(6144+CX+CY*32)<>46 THEN V=0:RETURN
620 LOCATE CX,CY:IF TJ(CX-19,CY,2)<>0 THEN PRINT N\$(TJ(CX-19,CY,2)):PJ=PJ+1 ELSE PRINT " "
630 IF PJ=20 THEN LOCATE 0,14:PRINT"** You win the game !! **":END
640 RETURN
```

Computer move

First we calculate the coordinate randomly. Then, we check if the X,Y position is already visited. If true, we shift X and Y on the board until an unvisited place is found.
The visited cells are marked with an "X".
If an object is hit, we increment PC, the computer score.
```650 '
651 ' Computer move
652 '
660 X=INT(BT*RND(-TIME))+1
665 Y=INT(BT*RND(-TIME))+1
670 IF VPEEK(6144+(X+1)+Y*32)<>88 THEN 685
675 X=X+1:IF X>10 THEN Y=Y+1:X=1:IF Y>10 THEN Y=1
680 GOTO 670
685 LOCATE X+1,Y:PRINT"X":IF TJ(X,Y,1)<>0 THEN PC=PC+1
690 IF PC=20 THEN LOCATE 0,14:PRINT"** I win the game !! **":END
695 RETURN
```

Important: the access to the opponent's board is only allowed at the player's or computer's play. Any other access out of a play is like "cheating" the opponent. Because of that, lines 670 (computer routine) and 610 (player routine) check only the screen information.

3. Improving the computer's intelligence
The computer move routine (lines 650-695) is quite simple and always performs a "shot in the dark", once the computer's behaviour is not changed after identifying a ship. The routine always calculates X and Y randomly.
We may improve this by making the computer search for the adjacent cells everytime it hits an object with the size greater than 1.
The first step is to create another array "N" to store each ship type size, once now this information it is useful.
```20 BT=10:DIM TJ(BT,BT,2):DIM N\$(4):DIM N(4)
...
415 READ N\$(I),C,T:N(I)=C
```

By this time, there will be two options for computer to calculate X and Y: the first is randomly; the second, we will perform an object searching along the X axis.
We will create a flag to indicate the which strategy the computer will adopt: random or search.
```50 CX=20:CY=1:PJ=0:PC=0:OE=0
```

The resulting code is:
```655 IF OE=1 THEN 690
656 ' Random routine
660 X=INT(BT*RND(-TIME))+1
665 Y=INT(BT*RND(-TIME))+1
670 IF VPEEK(6144+(X+1)+Y*32)<>88 THEN 685
675 X=X+1:IF X>10 THEN Y=Y+1:X=1:IF Y>10 THEN Y=1
680 GOTO 670
685 IF TJ(X,Y,1)<>0 THEN OE=1:CR=N(TJ(X,Y,1)):C=CR:DX=1
690 LOCATE X+1,Y:PRINT"X":IF TJ(X,Y,1)<>0 THEN PC=PC+1
695 IF PC=20 THEN LOCATE 0,14:PRINT"** I win the game !! **":END
700 IF OE=0 THEN RETURN
705 ' Search routine
710 IF TJ(X,Y,1)=0 THEN DX=-DX:GOTO 760
720 CR=CR-1:IF CR=0 THEN OE=0:RETURN
730 X=X+DX
740 IF X<1 OR X>10 THEN DX=-DX:GOTO 760
750 IF VPEEK(6144+(X+1)+Y*32)<>88 THEN 770 ELSE DX=-DX
760 X=X+DX:IF VPEEK(6144+(X+1)+Y*32)=88 THEN 760
770 RETURN
```

The line 685 checks if the random X,Y is a ship. If true, sets the "OE" flag, reads the ship length in "CR" (remaining length) and sets the initial shift "DX" as positive.
In the next rounds, the search routine (line 705) will take place until CR=0.
If the target is "water", change the "DX" signal. Move X until an unvisited cell is found (line 760).
We calculate the next X value now. If the next position is a visited place, change the "DX" signal and move X until an unvisited cell is found (line 760).

Situation 1: Obs: the green rectangle is the current X,Y coordinate, while the light gray rectangle is the future X,Y.

Situation 2: The line 690 represents the computer's play for both random and seach strategies.

We also can mark the object surroundings in order to minimize the efforts from the computer.
```720 CR=CR-1:IF CR=0 THEN OE=0:GOSUB 800:RETURN
...
800 ' Mark suround
810 IF X>0 THEN IF TJ(X,Y,1)<>0 THEN X=X-1:GOTO 810
820 Y=Y-1
830 FOR PY=Y TO Y+2:FOR PX=X TO X+C+1
840 IF PX<1 OR PY<1 OR PX>10 OR PY>10 THEN 850 ELSE LOCATE PX+1,PY:PRINT"X"
850 NEXT PX,PY
860 RETURN
```

4. The whole game
Download:

battle.zip - both Basic and ASCII Basic.

Marcelo Silveira
Systems and Computing Engineer
Expert in Image Processing and Artificial Intelligence
© MarMSX 1999-2021