The North Pole Type Provider: Escape from Santa’s Grotto!

by Pezi 24. December 2014 02:41

This post is part of the F# advent calendar, which is filled with all sorts of other cool blog posts, be sure to check it out.  Thanks to Sergey Tihon for organising!

It’s Christmas!

Happy Christmas everyone!  I have the honour of the Christmas Day F# advent calendar post (Thanks Tomas, ha!).  I had a whole bunch of different ideas, and typically, I decided to choose the largest, most complicated one.  Because of this, there is a lot of code written in just a couple of evenings. It is for the most part, badly designed, horribly written, nowhere near finished and should not be used as an example on how to write anything approaching nice F# code!  /disclaimer

Some Background

If you know me at all you will know that I tend to write lots of crazy type providers.  This will, of course, be no exception.  In fact, even though I wrote this in just a couple of evenings, it’s probably the most complex ridiculous TP to date.   To achieve this, I have used my Interactive Provider which is basically a type provider abstraction that lets you create crazy type providers without writing any provided types code at all!  Rejoice.

The TP is a game, which is based on the legendary circa 1980~ game Rogue. I realise that many people will not know about Rogue (although the term Roguelike is used a lot more these days) so I will explain a few bits that characterise a roguelike game

  • There are no graphics.  The character is typically thrown into a dungeon which is rendered using ASCII characters only.
  • They are procedurally generated.  Not just the dungeons themselves – a red potion in one game will be very different to your next.
  • They are hard. Although there is an end, usually you just see how far you can get before you die
  • They have permadeath. When you die, that’s it – start over from the beginning
  • They are typically very complex. Modern roguelikes are epic works of engineering with vast amounts of crazy stuff you can do, cause, and interact with, often in strange and fascinating ways.

Escape from Santa’s Grotto!

So, Christmas Eve is finally over and Santa plus crew have been celebrating a bit too much in the grotto / workshop.  One things leads to another, and everyone is smashed on all the sherry picked up from the previous night.  Santa wakes up at the bottom of the grotto, hungover, and unfortunately discovers that most the Reindeer and Elves are either still on the sherries or have fallen asleep drunk.  Now, everyone knows drunk Reindeer and Elves are incredibly violent, even to Santa.  Can you help him navigate his way up through 5 levels of the grotto?

image

Above shows a typical example of a starting position.  Important note! For this to work you MUST use a fixed-width font for your editor tooltips!  I recommend Consolas 10-12  (anyone would think type providers were not designed to run games!)

Here is a list of the possible characters and what they depict in the dungeon

  • This is Santa, the player
  • Horizontal wall
  • |   Vertical wall
  • #  Corridors that connect rooms
  • .   Floor
  • /  Open door
  • +  Closed door
  • *  Piles of presents
  • % Carrots of various types
  • !   Mince pies of various types
  • E  Elf
  • R  Reindeer
  • <  Stairs leading downwards
  • >  Stairs leading upwards

As the game progresses, you gain experience by killing hostile elves / reindeer and will level up, which increases your maximum hit points, makes you hit harder and more often.  Santa will heal over time, but he also gets hungry and must eat.  Perhaps you can find some other items that can heal you?

A typical full level map might look something like this

image

Notice you cannot see any items or monsters that are not in Santa’s field of view (FOV).  The FOV algorithm is different in corridors to when you are in rooms, and it is largely terrible due to time constraints, but it still works ok :)  Each turn, you are presented with a list of properties in intellisense that represent the available actions for you to perform.  Some of these require further input in the form of another list of properties.  The available actions are as follows.

  • Movement. Represented as N, NW, W, etc.  This will move you one tile in that direction, if possible
  • Pickup. This will take an item at your feet and put it in your inventory. Note: you will see in the status at the bottom of the screen when you are standing on something you can pick up
  • Use Item.  This will present you with a list of things in your inventory which you can use.  Only trial and error will tell you what a Blue mince pie does, be careful!
  • Drop Item.  You can drop things.  You might notice that Reindeer and Elves sometimes eat stuff they stand on.  Perhaps this could be useful?
  • Open / Close.  You will be asked to pick a direction, at which point the door (if it exists) will be opened / closed. Note that the monsters cannot open doors!
  • Wait .  Waste a turn doing nothing.  Santa gradually heals over time, be he also starves to death if you don’t keep him fed!
  • Climb.  This will take you to the next or previous level if you are standing on some stairs.

Strategy

  • Roguelikes are risk management games.  Often a lot of chance is involved.  Food should be a top priority as lack of that will kill you off given enough time, no matter what.  To this end you should try to make sure that the monsters do not eat any food lying around on the floor by ensuring they don't walk on those tiles.  
  • Similarly, eating mince pies is a game of chance, you could get lucky, or it might go horribly wrong.  In any case, once you know what a specific colour pie does, you will know all other pies of that colour do the same thing.  
  • Another way to identify mince pies is to drop them in the path of monsters and see what happens to them if they decide to eat it.  
  • Use doors to your advantage - monsters cannot open them.  
  • Sometimes you will be able to sneak past monsters without waking them - you must balance this with fighting and gaining experience, as the monsters will get tougher in each level.  
  • Monsters cannot follow you up and down stairs.
  • It is easy to cheat as this is a type provider, you can just undo your steps. Don’t do that, you are only cheating yourself!
  • There are (at time of writing!) 8(!!) different types of mince pie! be sure to experiment, there are some interesting ones such as this!

image 

In order to attack something, simply move in its direction.  At the end of your turn, any monsters that are awake will probably try and close in on, or attack you.  You will see the results of this at the bottom of the screen in the status messages.  If there are more than 2 status messages, you will be presented with a single property named “More” which will continue to cycle though the messages until they are exhausted.  I didn't have time to write anything except very rudimentary AI so they are pretty dumb and you should be able to get them stuck on each other, in corridors, and all sorts.  Actually!  I have changed my mind.  They are all still drunk, that is why their path finding is practically non-existent, and not because I had no time to do it!

Some final notes!

Well, I must admit I was furiously coding away just to get this to work at all.  There are still some bugs in it, and balance is way way off.  Roguelikes usually have an element of luck but this one more so than normal :)  I only managed to get a small portion of what I would have liked in, but it still is quite playable (albeit incredibly hard sometimes) and I am fairly sure it is the only roguelike type provider in existence!

To get it running

Head on over to my github, clone and build the Interactive Provider.  The IP works by scanning assemblies in a given location to find types that implement IInteractiveServer which it then uses to provide the types. Because of this you will need to point the Interactive Provider to the location of the XMAS_2014.dll file, like so

#r @"f:\git\InteractiveProvider\InteractiveProvider\bin\Debug\InteractiveProvider.dll"
type GamesType = PinkSquirrels.Interactive.InteractiveProvider< @"F:\git\InteractiveProvider\XMAS_2014\bin\Debug\">
let games = GamesType() 
games.``Start The North Pole``.

 

Please have a go, and let me know if you beat by tweeting @pezi_pink and / or #fsharp over on twitter!  If you manage to escape, be sure to let us know how many presents you managed to pick up on the way!

HO HO HO!

Tags:

F# | type providers

2048 – Type Provider Edition

by Pezi 3. July 2014 11:36

Intro

I’m sure you would have all seen the highly addictive and annoying game 2048 by now (if not, follow the link and have a go now, don’t forget to come back here though! ).  Fellow F#er  @brandewinder wrote a bot that wins the game for you, subsequently turning it into an cool F# dojo.  It is London’s turn for this dojo next Thursday, so I figured before then I would have a go myself and do the obvious thing which is to turn it into a type provider :)

2048 TP Edition is available as part of my type provider abstraction the Interactive Provider.  You will want to set your tooltips to a fixed-width font for this to render for you properly. Here is a picture of it in action !

image

2048 Implementation

I will start by saying that I have not looked at any other implementations of either the game or any automated bots, so if this is terrible then please forgive me.  I had also not played the game at all until recently and as such the rules implemented here are from my brief analysis of playing it.  There might be some subtleties I have overlooked.

I first implemented this using arrays as it seemed like a natural fit for the 4 x 4 board, but although I got it to work, it was horrible and instead I replaced it with this much more functional version.

type data = Map<int * int, int> 
type direction = Up | Down | Left | Right

That covers the entire domain :)  Each location of the grid is stored in the map along with the value, if one exists. 

let shift (x,y) = function 
    | Up    -> (x,y-1) 
    | Down  -> (x,y+1) 
    | Left  -> (x-1,y) 
    | Right -> (x+1,y)

let moves = function 
    | Up -> 
        [for x in 0..3 do 
         for y in 0..3 do 
            yield x,y]        
    | Down -> 
        [for x in 0..3 do 
         for y in 3..-1..0 do 
            yield x,y] 
    | Left -> 
        [for y in 0..3 do 
         for x in 0..3 do 
            yield x,y]  
    | Right ->  
        [for y in 0..3 do 
         for x in 3..-1..0 do 
            yield x,y]

A couple of utility functions.  The first is pretty obvious, the second returns a list of tuples indicating the order that the cells should be processed.  The order is very important for a number of reasons as will become clear.

let rec move direction data (x,y) (px,py)  = 
    match x, y with 
    | -1, _ 
    | _, -1 
    | 4, _ 
    | _, 4 -> (px,py) 
    | x, y when Map.containsKey (x,y) data -> (px,py) 
    | _ -> move direction data (shift (x,y) direction) (x,y)

This function takes a location and attempts to move it in the specified direction until either it goes out of bounds, or it finds the location is already taken in the map. In either case, it returns the last good position that can be moved to.

let replace direction data inputs = 
    let move = move direction 
    (data,inputs) 
    ||> List.fold(fun m p -> 
        match move m (shift p direction) p with 
        | newpos when newpos = p -> m 
        | newpos -> let v = m.[p] in m |> Map.remove p |> Map.add newpos v)

let compress direction data = 
    direction 
    |> moves 
    |> List.filter(fun k -> Map.containsKey k data) 
    |> replace direction data

These functions effectively “compress” the map in a specified direction.  What this means is that if we are going Up, it will start from the top row, and moving downwards it will move each cell up as far as it can go, resulting in a new compressed map.  You can think of this much like defragging memory, but with a direction bias.  It’s like applying gravity from different directions :)

let merge direction data =   
    let moves = direction |> moves |> Seq.pairwise |> Seq.toList    
    (data,moves) 
    ||> List.fold( fun data ((x,y), (x',y')) -> 
            match Map.tryFind (x,y) data, Map.tryFind(x',y') data with 
            | Some first, Some second when first = second -> 
                data 
                |> Map.remove (x,y) 
                |> Map.remove (x',y') 
                |> Map.add (x,y) (first*2)                
            |_ -> data)

This one is a little more fun :)  The idea of the merge function is to, based on the direction, merge any pair cells that are touching and have the same value, replacing them with one cell (based on the “gravity” direction) that has double the value.  This code uses pairwise to serve up each pair of locations – the order that the cells are generated from the moves function is critical here

let step direction =  (compress direction) >> (merge direction) >> (compress direction)

Using function composition, I can now say that one step of the simulation consists of compressing the map in a certain direction, merging the resulting cells together where appropriate, and then compressing again to fill in any blanks that appeared from the merge step.  I think this is pretty awesome :)

Type Provider

As mentioned before, this uses my Interactive Provider so there is no gnarly provided types code.  Instead, I have a very simple state that gets passed back and forth

type ``2048State`` = 
    | NewGame 
    | GameOn of Map<int*int, int> 
    | GameOver of bool 
    interface IInteractiveState with 
        member x.DisplayOptions: (string * obj) list = 
            match x with 
            | NewGame  -> ["Begin Game", box ""] 
            | GameOn(data) -> ["# Show Grid", box "show";"Up", box "up";"Down", box "down";"Left", box "left";"Right", box "right";] 
            | GameOver(true) -> [] 
            | GameOver(false) -> [] 
        member x.DisplayText: string =  // omit drawing code for brevity 

Very simple .. at the start it shows “Begin Game” and from then on displays the directional choices as properties along with a “# Show Grid” property that shows  the current state of the grid.

type ``2048``() = 
    interface IInteractiveServer with 
        member x.NewState: IInteractiveState = NewGame :> IInteractiveState        
        member x.ProcessResponse(state: IInteractiveState, response: obj): IInteractiveState = 
            let (|Win|Lose|Continue|) (data:Map<int*int,int>) = 
                ((true,0),[for x in 0..3 do 
                           for y in 0..3 do 
                           yield x,y]) 
                ||> List.fold(fun (b,highest) k -> 
                    match Map.tryFind k data with 
                    | Some v -> if v > highest then (b,v) else (b,highest) 
                    | None -> (false,highest)) 
                |> function 
                    | (_, 2048) -> Win 
                    | (true, _) -> Lose 
                    | _ -> Continue data

            match (state:?>``2048State``), (response :?> String).ValueOption() with 
            | NewGame, _ -> 
                let x, y = rnd.Next(0,4), rnd.Next(0,4) 
                GameOn( Map.ofList[(x,y),2])                
            | GameOn(data), Some "show" -> GameOn(data) 
            | GameOn(data), dir -> 
                let dir = 
                    match dir with 
                    | Some "left" -> Left 
                    | Some "right" -> Right 
                    | Some "up" -> Up 
                    | Some "down" -> Down 
                    | _ -> failwith "" 
                match step dir data with             
                | Win -> GameOver true 
                | Lose -> GameOver false 
                | Continue data -> 
                    let rec aux () = 
                        let x, y = rnd.Next(0,4), rnd.Next(0,4) 
                        if Map.containsKey (x,y) data then aux() 
                        else x,y 
                    GameOn(data.Add(aux(),2))                
            | _, _ -> failwith "" 
            |> fun x -> x :> IInteractiveState

There is really not a lot to this.  The active pattern at the top cycles through all the possible grid states, collecting the highest cells and whether or not all the cells are populated. With this information it can return if the game has been won, lost, or should continue.

When the game is running, it simply looks at the direction that was selected, and pattern matches on the results of calling the composed step function using the active pattern above.  Assuming the game is still running, it finds a random location to put a new 2 in, and returns the new data map.

 

Conclusion

Now you can really spend time in Visual Studio playing games instead of working, because this is a lot more fun than minesweeper!  2048 Type Provider Edition for the win!

Tags:

F# | type providers