3

I'm working on a project where I'm programming a battleship game using objected-oriented principles of programming.

I got stuck at one problem that is purely mathematical and relates to the positioning of the battleships. I would like to ask you for an equation to help me out. Let get straight to the point:

Battleship playing board

  • I have converted a A2, G8, I9 notation into a lineta system with (x+1 + y*10) (x and y starting from 0) so that each mast has its numerical position (from 1 to 100).
  • Lets take the ship in the top-left corner as an example. It occupies positions 1 and 2 on the board.
  • In this case squares that cannot accept any battleships are: 3, 11, 12 (ships cannot touch one another)

Problem: What is the equation that would tell me what squares cannot accept any masts given the position of an already set mast?

Rules: 1. Ships cannot touch one another, 2. Masts of of a battleship can only be positioned along one another' sides - not diagonally.

Travis Willse
  • 99,363
luqo33
  • 157
  • Welcome to math.se! You may well get more useful answers if you include your own thoughts and ideally work on the problem. In fact, not doing so is grounds for closure of a question. (Also, it took me a good deal of effort to parse your notation for labeling squares, it might help too if you clarified this.) – Travis Willse Feb 09 '15 at 09:40

1 Answers1

2

If $(x,y)$ is occupied, then $(x+a,y+b)$ cannot be occupied by any other ship, where $a,b\in\{-1,0,1\}$. Translated into your onedimensional encoding, occupying position $p$ prevents other ships from positions $p-11,p-10,p-9,p-1,p+1,p+9,+p+10,p+11$. However, you have to be careful with wrap-arounds. Incidentally, if you have to use a onedimensional encoding, I suggest you allow some extra space by making the rows internally $11$ long. Then you can safely check positions $p-12,p-11,p-10,p-1,p+1,p+10,p+11,p+12$. While you are at it, you may want to let A1 start at index $12$, so that subtracting $12$ does not get you out of bounds (at least this allows you to spare some out of bounds check prior to each access); also ensure that adding $12$ to $L10$ does not get you out of bounds either.

Alternatively, you may want to make a collision check beforehand, given only the first and last positions of two ships: If one ship goes from $(x_1,y_1)$ to $(x_2,y_2)$ and another from $(x_3,y_3)$ to $(x_4,y_4)$ (with $x_1\le x_2$ etc.), then they collide/touch if $$(x_1\le x_4+1) \land (x_3\le x_2+1)\land (y_1\le y_4+1) \land (y_3\le y_2+1)$$

Hagen von Eitzen
  • 374,180