Mark Gilbert's Blog

Science and technology, served light and fluffy.

Grand Theft Wumpus – Adventures in F#

My functional language user’s group, FLUNK, is currently working our way through Conrad Barski’s "Land of Lisp".  Barski takes up the challenge to teach Lisp by writing video games with the language.  My functional language of choice is F#, so I’ve been implementing the games using that instead.

The latest one is a takeoff of a 1970s game called "Hunt the Wumpus" (http://en.wikipedia.org/wiki/Hunt_the_Wumpus).  True to form, Barski decides to reboot it as "The most violent programming example ever put into a textbook", and "Grand Theft Wumpus" is born.

To get the full source code and executable for my implementation, download the "GrandTheftWumpus.zip" archive from http://tinyurl.com/MarkGilbertSource.

Visual Improvements
As I worked my way through the requirements, I decided to take a few liberties and improve upon the game.  Several of my improvements were visual.

Barski models Congestion City as a graph of nodes connected to each other by edges, and then uses an open source program called GraphViz (http://www.graphviz.org/) to display it pictorially.  Barski directs you to generate the graph using GraphViz, and open the resulting image in your web browser.  I decided to take a slightly more integrated approach with my implementation: I’d create a C# front-end that would do the job of calling GraphViz, and would immediately refresh an Image box to the new image.  I would call this with every move, and as a result you would constantly be updated with where you were and what was around you.

App Screen Shot 1

Implementing the game engine in F# and the UI in C# meant that the former would have to take commands via a public method, and raise events that the latter could handle. That alone meant that my game engine would look and feel more like an object oriented solution than a functional one.  Furthermore, this game was a lot more involved than I thought it would be, and I ended up working almost down to the wire to get it finished.  As a result, there are several places where I fell back to my OO/imperative habits of loops rather than the more functional lambda expressions and other F# constructs.  I don’t know what these two approaches look like under the covers – they may be optimized down to the same thing – but I still felt like a phony writing it that way.  I may go back and try to revise the loops out later.

A couple of other minor improvements were in how the graphs were drawn.  GraphViz has a lot of options for arranging and coloring the nodes and edges.  For starters, I knew I wanted an easy way to show which node you were standing on.  I was already tracking which node was "current", so I simply color that node green (see the screen shot above).

Another adjustment was in how the edges with police were represented.  As Barski presents the game, if you come upon a node with "Sirens" on it, you can be sure that one or more edges connected to that node have police on them.  However, you don’t know which ones.  That made it very much a crap shoot whether you would walk into a barricade (and lose) with your next move.  It made for a very frustrating game.  To simplify it, and move the game slightly closer to reality, I color the edges with police blue.  That simulates you hearing sirens in a given direction, not just hearing them in general.  That allowed you to still be constrained by the barricades, but still be able to play the game with a certain level of strategy (as opposed to luck).

I also found that if I only included the nodes you had visited and the nodes you could see in the data file pumped through GraphViz, it would arrange those nodes in a given layout.  When I moved to a new node, and additional new nodes were revealed, GraphViz would re-lay out the entire graph, making it hard to figure out where you had already been, and where you had not yet explored.  To get around that issue, I include all nodes and edges every time, but I color the ones that you shouldn’t see yet white (edges, nodes, and node text).  You still get a little shifting when you visit a new node because the text goes from something like "(14) ?" to "(14) Lights Sirens", but not nearly what I was getting originally.  It also explains why the nodes and edges look broken in places – you’re seeing the white lines overlaid on the black/blue ones.

Finally, if you just pass the data file to GraphViz, the nodes overlap quite a bit. To avoid that, I pass an additional command-line parameter of "-Goverlap=scale" which forces the nodes apart.  Unfortunately, GraphViz gets a little overzealous with this sometimes, and as a result the graphs tend to be quite large.

Solving the Island Problem
Of all of the improvements that I made to the game-as-presented, the one I am most proud of is the solution to the island problem.  How do you create a random city of X nodes, and guarantee that you can actually get to all of the nodes when starting from any of them?  In other words, how do you prevent islands?

Once he creates the initial, random city, Barski actually walks the graph to find any islands, recording which nodes he’s visited along the way (and making sure he hits all of them).  I decided to try to find a more elegant way.  Something from my college class on graph-theory must have stuck, because I remembered that you could represent a graph as an NxN matrix.  So, if you had a 6-node graph that looked like this:

ConnectedGraph

You could represent that as a matrix like this:

CompleteGraph-CompleteMatrix

The 1s here represent a connection between those two nodes, and 0s mean there is no direct connection between them.  When the engine originally lays out the city, and it creates an island, the graph might look something like this:

Graph with Islands

The matrix, then looks like this:

IslandGraph-CompleteMatrix

That doesn’t initially appear to really be easier to find the islands, until you look "below the fold".  Nodes in Congestion City don’t connect to themselves, to the diagonal will always be 0s.  This is what I refer to as the "fold":

IslandGraph-CompleteMatrix-FoldHighlit

Technically, the graph is represented twice in this matrix – once above the fold, and once below.  Since this is an undirected graph (where you can go from every node X to Y, and from Y to X), there’s no reason to include both sets.  What if we removed the one from above the fold?

IslandGraph-HalfMatrix - Nothing Highlit

Now the breaks in the graph stand out a bit better.  When the graph has an island, the half-matrix (here defined as below the fold, but you could just as easily look at the matrix above the fold) has at least 1 row and one column that has no 1s.  In our example, these are represented as row 3 and column 5:

IslandGraph-HalfMatrix - RowCol Highlit

Technically row 1 and column 6 also have no 1s in them, but I’m only interested in the ones below the fold.  All I have to do to work the islands out of the structure is check every row or column (as it turns out I don’t even have to check both – I only have to check in one direction to remove the islands) looking for the ones with only 0s in them.  Once I find those, I drop a 1 in a random cell, and move on.  Representing the structure as a matrix made it trivially easy to find and fix the islands.  So much so that that I decided to base the rest of the game engine on a edge-matrix instead of an edge-array as I had originally planned.

After completing in the rows, I then mirror the matrix so that the above-fold numbers match, re-completing it (that makes it easier to do the check of “is node X connected to node Y?).  My city is now islandless.

(And for the record, I find it hard to believe that I’m the first person to use a matrix in this manner to link up graph islands.  Given how developed graph theory is, I have to believe this already has someone’s name attached to it.  Unfortunately, I don’t remember THAT much from my graph theory class, so I don’t even know what questions to ask of the Google to find that person.  I’d love to hear from you if you know.)

Overall, I enjoyed writing Grand Theft Wumpus, and I think it’s a very playable game.  In fact, my older daughter played it a couple of times, and then requested that it be installed on her computer so she could play it whenever.  What do you know?  I have a fan!

Advertisements

February 7, 2012 - Posted by | F#

Sorry, the comment form is closed at this time.

%d bloggers like this: