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 (i.e., a hit) or not (i.e., 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 else's on separate 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 generates 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:
DECLARE @line VARCHAR(500);
DECLARE @lingG GEOMETRY
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))
DECLARE @point VARCHAR(500);
DECLARE @pointG GEOMETRY
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):
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)
IF @Orientation = 0
BEGIN
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
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
EXEC AddShip @GameId, @PlayerId, @ShipId, @StartX, @StartY, @EndX, @EndY
SELECT @placed = COUNT(*)
FROM GamePlayerShip
WHERE GameId = @GameId AND PlayerId = @PlayerId AND ShipId = @ShipId
END
SET @placed = 0
FETCH NEXT FROM ShipCursor INTO @ShipId, @ShipLength
END
CLOSE ShipCursor; DEALLOCATE ShipCursor
and when playing the game itself.
SELECT @GamePlayerShipId = Id
, @ShipId = ShipId
FROM GamePlayerShip
WHERE [Line].STIntersects(@point) = 1
AND GameId = @GameId
AND PlayerId = @PlayerId
Installing the 'code'
Simply create a new database in SQL Server 2008 - I called mine Battleship then executed 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 is 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 second 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
