SQL-Battleship 2008

• Download Battleship2008 - 11 KB

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:

"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
-- 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)) 

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

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