Battleship 2008

December 2007
Download source code - 12 Kb

Comment on this article at TheCodeProject

Introduction

Microsoft SQL Server 2008 introduces two new 'spatial' datatypes: GEOGRAPHY and GEOMETRY. They can be used to store, retrieve and query two-dimensional data including latitude/longitude coordinates (using the GEOGRAPHY datatype) and any flat-plane coordinate space (using GEOMETRY).

The rules for Battleship are on Wikipedia - go and read them there, this article will still be here when you're done...

...welcome back. As you can see, Battleship is generally played on a 10x10 grid (like the example to the right) - just the sort of thing that the GEOMETRY datatype can be used for. If you were going to build this in a procedural language, you'd probably start with a two-dimensional array or similar data-structure.

In SQL Server we're not going to 'create' a specific data-structure at all. Instead we'll just create LINEs representing the ships and then create POINTs for each shot, and check whether they Intersect (ie. a hit) or not (ie. a miss). For simplicity, this is just a single-player version of the game - the ships are automatically placed for you, you just have to sink them in the fewest number of shots.

The schema

The database schema is very simple: the two GEOMETRY columns are highlighted with green. I also used a DATE and TIME column - unnecessarily - just because they are also new features of SQL Server 2008.

You'll also notice the PlayOrder column is 'hidden' - in future the code could be extended to allow two players to 'compete' (creating their own boards, and shooting at someone elses on seperate SQL connections) - but that is left as an exercise for the reader...

About the 'code'

The code really consists of the table definitions, static lookup data and a handful of stored procedures:

NewGame	Requires your name to create Player and Game records, then generate a new/random board of ships. The GameId and PlayerId that it returns are required to play the game. It uses another Stored Procedure - AddShip - which you could also use to create playing boards directly.
Shoot	The main way you interact with the game - EXEC it with the supplied GameId and PlayerId to take a 'shot' at the board, and see whether you hit or missed a ship.
Cheat	Shows you the board (which is what you are trying to 'guess'). Useful for testing and understanding the code, but don't be tempted if you are playing!
Reset	Clears your shots so you can play the same board again from scratch.

"Well Known Text" not currently 'well known'

I hadn't heard of Well Known Text (WKT) before - but again Wikipedia has a useful definition. You only need to know about two types of WKT (and how to use it in T-SQL) for now:

LINESTRING

DECLARE @line  VARCHAR(500);
DECLARE @lingG GEOMETRY
-- LINESTRING(1 1,4 5)	
SET @line  = 'LINESTRING('+CAST(@StartX AS VARCHAR(2))+' '+CAST(@StartY AS VARCHAR(2))+
			 ','+CAST(@EndX AS VARCHAR(2))+' '+CAST(@EndY AS VARCHAR(2))+')'
SET @lineG = geometry::STGeomFromText(@line, 4326))

POINT

DECLARE @point  VARCHAR(500);
DECLARE @pointG GEOMETRY
-- POINT(2 2)	
SET @point  = 'POINT('+CAST(@X AS VARCHAR(2))+' '+CAST(@Y AS VARCHAR(2))')'
SET @pointG = geometry::STGeomFromText(@point, 4326))

STIntersects

And while there are dozens of GEOMETRY-specific functions (STLength, STArea, etc), we only really need STIntersects() for 'hit testing' - both when randomly generating the ships (to ensure they don't share locations)

-- Loop through ships (biggest to smallest) placing them
-- where they don't intersect with other ships
DECLARE ShipCursor CURSOR FOR
SELECT Id, Length FROM LU_Ship ORDER BY Length DESC
OPEN ShipCursor 
DECLARE @ShipId TINYINT; DECLARE @ShipLength TINYINT
FETCH NEXT FROM ShipCursor INTO @ShipId, @ShipLength
WHILE (@@FETCH_STATUS <> -1)
BEGIN
	DECLARE @placed BIT; SET @placed = 0
	WHILE (@placed = 0)
	BEGIN
		PRINT '--- Attempting to place ship '+CAST (@ShipId AS VARCHAR(2))
		SET @Orientation = ROUND(RAND(),0) -- Choose north/south or east/west
		IF @Orientation = 0
		BEGIN -- 'Horizontal'
			SET @StartX = ROUND(RAND()*(@BoardSize-1-@ShipLength)+1,0)
			SET @StartY = ROUND(RAND()*(@BoardSize-1)+1,0)
			SET @EndX = @StartX + @ShipLength - 1
			SET @EndY = @StartY
		END
		ELSE
		BEGIN -- 'Vertical'
			SET @StartX = ROUND(RAND()*(@BoardSize-1)+1,0)
			SET @StartY = ROUND(RAND()*(@BoardSize-1-@ShipLength)+1,0)
			SET @EndX = @StartX 
			SET @EndY = @StartY + @ShipLength - 1
		END
		-- Attempt to 'save' ship to board: STIntersects is called in AddShip
		EXEC AddShip @GameId, @PlayerId, @ShipId, @StartX, @StartY, @EndX, @EndY	
		-- Check the result, if it wasn't saved it must have overlapped, 
		-- so we'll try again in the WHILE loop
		SELECT @placed  = COUNT(*)
		FROM   GamePlayerShip
		WHERE  GameId   = @GameId AND PlayerId = @PlayerId AND ShipId   = @ShipId
	END -- WHILE
	SET @placed = 0
FETCH NEXT FROM ShipCursor INTO @ShipId, @ShipLength
END
CLOSE ShipCursor; DEALLOCATE ShipCursor

and when playing the game itself.

-- Hit test: does the point intersect a ship 'line'?
SELECT 	@GamePlayerShipId = Id
     ,  @ShipId = ShipId
FROM    GamePlayerShip
WHERE   [Line].STIntersects(@point) = 1 -- Means point intersects line
AND     GameId = @GameId
AND		PlayerId = @PlayerId

Installing the 'code'

Simply create a new database in SQL Server 2008 - I called mine Battleship then execute the supplied SQL Scripts 01_Battleship.sql, 02_Looksup.sql, 03_Diagram.sql. It (should be) that simple, and the resulting objects should look like this.

Running the 'code'

Here's an example "game" (OK, you can see the first thing I did was cheat to find out where to shoot)

Note that I ran all these queries 'at once' to get the screenshot. You would normally EXEC one Shoot at a time.

The idea is you keep Shooting - getting a Hit, Miss or Sunk result - until you have sunk all five ships, at which point the code will return Won

Conclusion

There's literally only 100 lines of T-SQL or so (excluding the table definitions), so there isn't much more to discuss.

Possible extensions:

StDistance() could be used in the random-board-generation to ensure ships are at least a certain number of squares away from each other (and you could respond to Shoot with "Miss, but close!" if desired)
Make a two-player game but adding some sort of 'state' (game being built, boards submitted, whose turn is next) so that two DBAs can play from different Management Studio instances
Allow the 'computer' to be the 2nd player, randomly Shooting until it Hits, then using the spatial functions to 'decide' the best guess for subsequent shots
Configurable board sizes, ships, Shooting rules

More Reading

Querying Properties and Behaviors of geometry Instances
Discussion of Geography vs Geometry datatypes