PezHack–Abstracting flow control with monads

:: fsharp, game programming, roguelike

It's been forever since I last posted, I worked quite a bit on PezHack and then stopped for a while. I'm back to it now. In this post I will describe a technique I used to greatly reduce the amount of code and abstract away some repetitive imperative code.

The Problem

PezHack is a turn based game. The screen does not re-render itself all the time like a real-time game, but only when something changes and at the end of a the player's turn. The agent-based approach I used to separate the various sub systems of the game allow me to provide isolation around the graphics processing. The graphics agent is totally responsible for knowing what it needs to draw and will draw it on demand when it receives the relevant message. It does not really know anything else about the game state at all except the visual data of the various tiles that are visible, some player data that allow it to draw the various data about the player, and any menus / other UI that it needs to draw. Other systems can send it messages to inform it of some new visual state it should care about.

Most actions that Pezi can perform require some form of additional input and conditional flow logic. For example, when you press the 'e' key to Eat, first a menu is displayed that shows the stuff in your inventory that is edible, if possible. If not it will display a message and not end the player's turn. Assuming the menu is displayed, the player then presses the key that relates to the item they wish to eat from the menu. If this key is invalid a relevant message is displayed, else the item in question is eaten. What then happens is dependent on the item, it might provide sustenance, or if it's a mushroom it could perform one of various kinds of effects, and then probably end the player's turn

This is a common pattern that appears everywhere, and at each stage the graphics need to be re-drawn to show the various messages, menus and so on. At each stage it might continue or it might not depending the player's input, and the returns differs at each stage (end the player turn, or not, for example). In an imperative language we would almost certainly model this control flow with a bunch of nested if/then/else statements which quickly gets ugly. Because I am using the agent based approach for the graphics, I would also need to post a request to the graphics agent each and every time I needed the changes to show on the screen, so suddenly the actions become a list of imperative statements peppered with common code to keep the screen updated.

PezHack–A Functional Roguelike

:: fsharp, game programming, roguelike

In my quest to learn the functional paradigm, one thing I have struggled with is game development. Assuming I mostly stick to the functional style of having little to no mutable state, how do you go about writing games? Games are pretty much ALL mutable state. Obviously, in a multi-paradigm language like F# you can have mutable state - and if used judiciously this can be very effective (not to mention offer some significant performance improvements). The blend of imperative and functional styles can indeed work well, I wrote a few small games with XNA and F# using this approach. However, I am still more interested for educational value to stick with a more pure functional approach. Along they way I have wrote a few small games such as a functional console based Tetris in about 300 lines, and a two player console based PONG clone (using the libtcod library as I will introduce in a bit) that uses the Windows Kinect as the input (was cool!) In these programs I would tend to have the game state formed with an F# record that is copied/modified on each game cycle, passing the new state back into the loop. This works well and both of these games used no mutable state at all. This approach soon falls down with something more ambitious though, you can't realistically propagate the entire game state through one loop.

The Roguelike

I decided to create something a lot more complex whilst attempting to stick with the functional guns. If you don't know what a roguelike is you can read all about them here and a great set of development resources with links to many on-going roguelike efforts here. I used to play these games a lot. Stemmed from D&D back in the days where the only computers were the terminal sort in colleges in universities (before I was alive!), a roguelike traditionally uses just ASCII characters as its graphics, leaving the rest to the player's imagination. If you haven't tried this before I highly recommend you try one, Nethack is probably the biggest most complicated one out there, but you can also play the original Rouge (where the roguelike genre name comes from) online here. A few things that make a roguelike;

  • Random procedurally generated dungeons - every time you play there is a new dungeon
  • Randomness in item drops - until things have been identified, you don't know what they are. The "clear potion" might be a healing potion in one game and a potion that causes severe hallucinations in the next
  • Peramadeath and hard difficulty. These games are hard. Expect to die lots, and when you die you have to start again. Often the objective isn't to finish the game, but just see how long you can survive
  • Roguelikes are usually turn-based affairs - although there is some variation with this
  • Complexity - these games are amazingly complex and deep. The developer(s) don't have to worry about impressive graphics engines, so they can focus a lot more on interesting game mechanics. You will be amazed at some of the stuff you can do in a game like Nethack.

Here's a picture from Nethack to illustrate how a typical roguelike looks :

Nethack-kernigh-22oct2005-25_thumb2

Getting at non-public property setters in a nice way :)

:: fsharp

I’m sure every seasoned .NET developer has been in the situation at one stage or another, probably in testing code, where they need to access a non-public setter of a property (or maybe a private member), and it can’t be mocked.  We all know the (somewhat scary) reflection trick to get at the said setter method and invoke it.   I just hit this problem today trying to mock some response messages from a Microsoft Dynamics XRM 2011 OrganizationService.  Thankfully F# gives us cool things like Quotations and symbolic functions (custom operators) to make this process more succinct.  Instead of writing a method to reflect on a type, get the relevant method, then finally invoke the method and pass in both the original object instance and the new value being set, we can do the following:

1
2
3
4
5
6
let (<~) property value =
	match property with 
	| PropertyGet(Some(Value(x)),ri,_) -> 
	    ri.GetSetMethod(true).Invoke(fst x,[|value|]) |> ignore 
	| _ -> failwith "unsupported expression"

Emulating digital logic circuits in F#

:: digital logic, electronics, fsharp

In this article we will discover how to emulate simple logic gates, and then build them up to form more complex circuits. By the end of this 2-part article (edit - not that I ever wrote part 2) we will have created:

  • - Half-bit adder
  • - Full adder
  • - n-bit ripple carry adder formed from full adders
  • - 4:1 line decoder
  • - 4:1 multiplexer
  • - 1 bit ALU that supports addition, subtraction, AND and OR operations
  • - n-bit ALU formed from 1 bit ALUs

John - The Birth!

:: robotics, electronics


For my latest project, I've decided to make a tracked robot, cunningly named John. Tracks are really cool, and something I've not had on a robot before. Nice perhaps, but tedious to make, as hooking together 40+ segments of track with impossible to fasten pins makes for a pretty boring/annoying task..

Anyways, so far I have the chassis built, tracks built and motors in. He's looking cool so far, like the bottom of a mini Johnny 5 :)

The chassis is made from laser cut Lexan panels, with aluminium brackets. The tracks are heavy duty polypropylene and rubber, along with 7.2v 50:1 geared motors.

Obviously, at this stage, he does pretty much bugger all. In order for him to even move I've still got to fit a motor controller and a cpu, plus write all the inital movement routines. I intend to use a BASIC Stamp 2 for the brains at the moment, but will switch it over to the Propeller when I've got one.

Here be some initial pics:


And here's a picture of an airborne cat:

John - Meeting Nintendo!

:: electronics, robotics


I had today off work so I thought I'd work on something for John which doesn't require drastic hardware changes (ie trying to mount sensors near the front of the tracks) so I have decided to pursue some remote control for John using an ancient NES pad:



This kind of pulls away somewhat from full robotics, whereby the robot does everything on its own with no human input. This will be fun however, and I might learn something - sounds good to me. The first steps I took were to establish how the NES pad works exactly. I already know a bit about this from where I was going to use the pad for another project ages ago. Anyways just for fun I took the pad apart, to be presented with just one IC! (gone are the days of simple electronics eh)



A rubbish picture I know, that's what you get for using a phone as a camera. Anyway that single IC is a 4021 shift register, a common device that takes parallel inputs and then can be commanded to shift each value out serially. This has a huge benefit, as in order to monitor 8 inputs (the NES has 8 buttons, A, B, Start, Select, Up, Down, Left Right) it would take a whopping 8 IO lines! The shift register effectively cuts this down to just three IO lines to be able to monitor all eight buttons. The downside is that it's relatively slow in the electronics world, but it's easily fast enough for occasional polling.

In order to operate the register, you must of course provide it power and ground from the logic supply, and then you should be concerned with three pins, LATCH, CLOCK and DATA. Basically the DATA line will contain 0 or 1 that indicates the state of the current button (where LOW indicates button pressed). In order to cycle through the buttons, the LATCH line must be held low, and then each successive HIGH pulse on the CLOCK line will shift the next bit out onto the DATA line. Once this is repeated 7 times (DATA always holds the first value - the first CLOCK moves onto bit 2) LATCH is set HIGH again and the chip resets back to bit 0 on the DATA line again. As I said above the controller has 8 buttons which is perfect for a shift register as it the total button state can be represented in exactly a byte.

In order to verify this behaviour I setup a test circuit to work out which button appears at which point in the shift sequence. Thankfully I have a diagram that shows how the pins on the controller connector are mapped to the IC:


With that I knocked up a simple circuit that can be used to poll the state of the buttons. For this I have a LED on the DATA line to show the output, and the CLOCK and LATCH lines are hooked to ground through a push button. The resistors on these two lines are known as pull-up resistors, they basically always ensure that the line

is HIGH by default and prevents any noise or "floating" inputs. When a button is pressed the line is pulled to LOW.


Now, bearing in mind that the DATA line will always show the output of bit 0 even when the latch is HIGH, I quickly determined that bit 0 was button A, as pressing A made the LED switch off. Now, whilst holding the LATCH button, pressing the CLOCK button cycled through the button states. I held down the different buttons on the pad and cycled through to establish the buttons states were in the following order:

0 - A
1 - B
2 - Select

3 - Start
4 - Up
5 - Down
6 - Left
7 - Right


Nice! Phase two was to attempt to read this data in from the micro-controller (a basic STAMP 2). I modified the circuit so the DATA, LATCH and CLOCK lines were hooked up to BS2 instead of buttons / a LED.



The BS2 already has a nice function to read serial data in from external devices called SHIFTIN. This asks for a data and clock pin, and a variable with which to read the data into. Therefore the only thing I need to worry about is controlling the LATCH line which is very straightforward. I used the following simple program to read the button states in and display them in the debug terminal. Note that all inputs are HIGH by default and LOW when a button is pressed - this logic is a bit backward when coding so I XOR the result with 11111111 to produce a byte where a bit value of 1 means that button is pressed.

' {$STAMP BS2}
' {$PBASIC 2.5}
DAT PIN 3
CLOCK PIN 1

LATCH PIN 2

joyinput VAR Byte

Main:

'Attempt to r

ead the contents on the shift register in

LOW LATCH

SHIFTIN DAT, CLOCK, MSBPRE, [joyinput]

HIGH LATCH


'XOR the output to invert the bits

joyinput = joyinput ^ %11111111


'Show results


DEBUG BIN8 joyinput

PAUSE 100

GOTO Main

This worked very nicely, an example of output when button A and up are pressed is 10001000 as expected. I will be using the RF transmitter / receiver mentioned in a previous post to transmit this data to John for processing. Ideally I think I would have the NES circuit work out which direction to go and then send a nibble with a value in it indicating what's going on. This way it halves the amount of data being sent and eases up on some of the processing for John. For this test however I will just send the whole byte and have John do the processing.


What I want is for up / down to go forward and backward, left / right pivot left and right, and diagonal up/right up/left to turn right/left respectively. I'm not going to bother with backwards movement and turning for now. Button A will increase John's speed through Cautious, Cruise and Max, whilst button B does the reverse, and steps back through the speeds. Sending no movement commands will cause the movement to stop. For this to work properly certain states need a higher precedence, ie diagonally up/right should be checked before right on its own or up on its own, and if found then the others should not be checked. The other concern is that of the buttons - I'm sending radio pulses every 100ms, and when I press the button I want it to fire once and only once until I have let go of the button and pressed it again. One final precaution is to prevent any noise or rubbish data from suddenly making John do stuff I didn't ask - this is easily implemented by requiring two identical bytes to be recieved in sucession before acting on them.


All being said and done I now have a new version John's program that accepts a RF signal, then uses some bit masking to determine what the command was, which is then executed. I have also now added the output from the NES controller to be displayed across 8 of the LEDs in the development board. This is because the connection from the NES plug to the board is not very good (a few bits of wire), and can need some wiggling about when moved to get working properly. The LEDs act as real time debugging so I can see the circuit is working as it should be whilst away from the PC.

Full schematics for John as it stands, and the NES controller:

NES


John

I will post a video at some point. Happy to report John is working remotely via the NES pad - very cool! A nice use for a poor pad that thought it would never be used again -worth the £1.50 it cost me from Gamestation :)

john_rf.doc (48.50 kb)

John - Some Basics

:: electronics, robotics



Right it's been a little while since my last post, but John is now alive and functional, albeit with some drawbacks for the moment. Here's a few pics I took a minute ago of John as he stands:



In this next one you can just about see the motor controller board - it's sitting on the lower level



The brain is that of a BASIC STAMP 2 from Parallax (which is actually a PIC with some extra hardware to provide a easier interface to program), I'm using the board from my Toddler robot as I only have two stamps, and the other one is in my development board. The toddler board is great because it has a surface mount BS2, a prototype area (breadboard), several servo connections mapped internally to the stamp's IO pins, a reset button, three way power switch allowing you to not provide power to the servo connectors, and a programming connector (serial cable - rs232) all on one small board. Unfortunately the toddler takes a +6v supply which is then regulated to 5v within the stamp itself, leaving both +6v and +5v on different headers. Usually the 6v comes from the 3xAA battery holder in the toddler, I don't want to use that though so for now I've got my own 5v regulator on the toddler board which feeds the stamp from a 9v battery. I have a couple of cheap re

mote control monster trucks that use a 6v source, and they have a battery pack and recharger, so I will be chopping one of those out to use soon. It's all about the rechargeable battery packs.

The motors themselves are powered by a 7.2v Ni-Cd battery at 1800mA through a very nice dual H-Bridge, which I bought this time rather than making my own. Its a M22 made by Devantech, a English manufacturer, and it's got a whole bunch of nice features. You can't really see it in those pics above so here's a picture of it:

<-- rawr!

This can take motors that require up to 50v and up to 5A per motor without a heat sink. Fine for John's requirements. It is capable of multiple different modes of operation, including straight analog control over each motor, RC mode which allows the motors to act like servos ( speed set by pulses at

different frequencies) or I2C mode which uses the popular Phillips I2C p

rotocol for complete programmatic control over every aspect of the motors, which is what I will be using for John. I will be adding some more I2C devices later as well.

The biggest benefit using DC motors rather than servos is that once you tell the motors to do something, they go off and do it until you tell them to stop - servos require the same pulse frequency to be sent every certain time period, usually about 25ms. This makes coding more tricky when the project is quite advanced, as you have to make sure the pulses are sent around all the other processing that's happening. Great fun with you have 4+ servos. Using motors frees up the code to do other things all the time, which can only be good! You can however buy or make a dedicated servo controller board (co-processor) which frees up this restraint in the same way. I will be using a servo controller board when I get a robotic arm for John.

Next up is sensors - for the time being John just has one sensor, which is an ultrasonic range finder capable of finding distances up to 3 meters, and it uses just one IO pin! You can see it in the pictures, it looks like John's "eyes". The Ping))) works on the same principal as a sonar - an ultrasonic pulse is transmitted, and the distance is measured by timing how long it takes to echo back. I have this mounted on a standard hobby servo, capable of 180 degree rotation, allowing the "eyes" to point in different directions and take distance readings.

<-- echo, echo, echo!

One of John's biggest problem at the moment is being able to see in front of the actual tracks - finding walls and objects straight ahead is one thing, but it doesn't cover an area wide enough in front of John for all situations. This job is well suited to infrared sensors or "whisker" type application, however it's going to be tricky to get anything mounted down there, but will be necessary soon.

You might have noticed the two antenna sticking up in the air - these are radio frequency transmitter and receiver modules, and will be used for communications across the airwaves to other circuits - they aren't currently being used in John but they are hooked up and ready - just need to be coded and have something to talk to.


<-- bad boys

That's about it at the moment for hardware. Currently have a simple program which tests all the systems, which allows John to roam around a bit, and when detecting a wall at 30cm he will pivot right until they way is clear to move forward. It's not very impressive but more a framework of lower level routines to get all the systems running, ie I2C communications and Ping))) distance acquisition. The motors themselves are capable of some quite high speed and torque, however for inside testing use I have him set to "caution" speed, otherwise I have to dive around the house trying to catch him before any disaster strikes. The torque is indeed quite powerful, John easily drives straight over anything that gets in his way, which can result in toppling over backwards and wrecking all the electronics (as almost happened this morning whilst driving over the N64 with Goldeneye in it). This can be avoided by fitting an accelerometer which measures tilt - I have one lying around somewhere that I might fit and try out.


One of the things I like most about the tracks is the ability to almost pivot on the spot - it can often be difficult to turn around without hitting other stuff but this does it really well.

I have attached the program I'm currently using. It's wrote in PBASIC and isn't the most efficient at the moment. PBASIC has several limitations such as having no subroutines/functions (GOSUB and GOTO for the win) and GOSUB will only nest 4 levels which can make it difficult to re-use a lot of the code. Another limitation with the STAMP is that it doesn't have a great deal of RAM to play with - in this example I'm already using a chunk:


In order to minimize memory usage, I will need to share variables where possible which can be tricky if you're not careful, not to mention making reading the code much harder to follow. I will be using basic subsumption architecture (fancy state machine) which will allow different movement patterns to be stored in the EEPROM and free up some space.


That's it for now, next up I will be looking at either getting some sensors in front of the tracks and in the centre lower down, or RF communication with the PC. I also have a ancient NES pad which I might hack and use it to remote-control john using another circuit and RF communications. I will also be designing a state machine and will have a lot of code to write ! Nex time I post I will upload a video and the schematics too (yay!)

john_basic.doc (42.50 kb)