In chapter 8 we build a Wumpus-style game. And if you recognize that reference then you must be at least as old as I am and allow me to reassure you that this will not be the basic Wumpus of yesteryear.
No, we're making Grand Theft Wumpus! Grand Theft Wumpus includes a few twists on the traditional Hunt the Wumpus game. The story is different but I'm not going to get into it. Buy the book for that. Suffice to say that you have one bullet, you're looking for the Wumpus, there are Glowworm Gangs that will mug you and ditch you elsewhere, and there are police checkpoints around town that end the game for you. Exciting!
The GlowWorm Gangs (GWG) are at random nodes in our game graph (yes, we're going to leverage that again) and the police blockade random edges. You can see GWG lights from one node away, you can hear sirens on the nodes to either side of a checkpoint, and the Wumpus has left a trail of blood that is visible in any node (bizarrely enough) up to 2 nodes away from himself. As the player you can move around town dodging checkpoints and exploring the randomized terrain and when you think you have the Wumpus pinpointed you charge in with your last bullet and win or lose based on your deductive reasoning.
That's the basic mechanics. Of course, the code involves rather more complexity than that so let's get started. First we have some basic parameters and helper functions.
The game's operating parameters appear first (the book helpfully forgets to include the *player-pos* parameter which made a nice troubleshooting exercise). random-node just returns a random number between 1 and the node max (*node-num*) inclusive. edge-pair returns a list of edges that describe a two way path. We'll use this because the game world is going to be an undirected graph meaning we need the edges defined in both directions. Finally we have make-edge-list which gets us to our first interesting (sort of) bit. Here we use a loop to collect a bunch of edge pairs between random nodes and then append them all into a single list.
Let's take a look at the structure of loop since it appears to be a bit awkward. The spec (google CLISP hyperspec) is dense with meaning and utility but in this chapter we only use it with two 'name clause's. We use a loop for and a loop repeat. loop for is your basic for loop with a defined index variable and a range for that variable over which the code block executes.
loop repeat just repeats the code block for the specified number of times.
You may have noticed the collect symbol in there. Based on my understanding of the spec (minimal I assure you) that's called the main-clause of the loop and in this case is an accumulation-clause, sub category list-accumulation, called collect. How that differs from append, collecting, or etc as referenced in the spec I wish I knew. Suffice that it will give us a list of edge pair lists, as in (((1 . 2) (2 . 1)) ((2 . 3) (3.2))), which is sort of what we want. Except that's nested deeper than is practical so we use apply to append all these sub lists into a single list like ((1 . 2) (2 . 1) (2 . 3) (3.2)) which is more readable to boot.
Now you might note that make-edge-list repeats the loop for *edge-num* iterations and creates a random path each time. The astute observer will note that this will likely leave many nodes inaccesible from some or all other nodes; in short it makes islands. It also creates some duplicate edges. We'll handle the duplicates in a later function. Right now we need to get the islands bridged.
First I'm going to blast a lot of code out in order to make what might be a philosophical point.
Our island prevention code:
That's a lot of pretty dense code. I'm discovering that when I read Lisp I have to read it from the inside out. But when coming up with the algorithm it has to be written from the outside in. Which, actually, puts me in mind of a time reversible process. Once the code is written if you want to understand it you have to perform the process in reverse. Maybe I'm just clueless. Moving along. Let's look at that again with some things brought out. Unfortunately I have yet to find a way to force custom highlights into a gist, so we're stuck with basic styles for this block.
[
(defun direct-edges (node edge-list)
(remove-if-not (lambda (x)
(eql (car x) node))
edge-list))
(defun get-connected (node edge-list)
(let ((visited nil))
(labels ((traverse (node)
(unless (member node visited)
(push node visited)
(mapc (lambda (edge)
(traverse (cdr edge)))
(direct-edges node edge-list)))))
(traverse node))
visited))
(defun find-islands (node edge-list)
(let ((islands nil))
(labels ((find-island (nodes)
(let* ((connected (get-connected (car nodes) edge-list))
(unconnected (set-difference nodes connected)))
(push connected islands)
(when unconnected
(find-island unconnected)))))
(find-island node))
islands))
(defun connect-with-bridges (islands)
(when (cdr islands)
(append (edge-pair (caar islands) (caadr islands))
(connect-with-bridges (cdr islands)))))
(defun connect-all-islands (nodes edge-list)
(append (connect-with-bridges (find-islands nodes edge-list)) edge-list))
]
Now first allow me to apologize for eyestrain. I tried to pick colors that weren't too garish or hard to read against the background without spending a lot of time on it. I'm not here to make beautiful copy. If you can get past that though you'll see the patterns. Each function has its color and every function scoped inside it has a washed out color in the same shade (I'm sure my use of terms would make any artist cringe, sorry). That lets me see recursion, as well as the flow of the code at a glance. I swear someone has to have put this kind of functionality in an IDE somewhere but I'll be boogered if I can find it (no; I'm not interested in learning emacs (which from all descriptions is the panacea of programs though I don't really know if it can do this); one heavy duty learning project at a time, go away). But to the point examining the code highlighted this way it's pretty easy to see what does what.
connect-all-islands is clearly top of the heap, it calls connect-with-bridges but that function doesn't go anywhere else (except itself ;) )so we follow find-islands. It creates a find-island function that calls get-connected. get-connected defines traverse which, in addition to being recursive, calls direct-edges which is the end of the line. direct-edges is the most interior function so we'll start there and work our way back up the heap. Perhaps I'm just bad at reading code or don't have enough practice with Lisp but this is the way my brain has to work in order to grok it for some reason. Turns out the order the functions appear in the book are inside to outside but I didn't know that when I first looked at the code and, if you've worked on enough code from other people, you can't expect that to be the case in any given set of code. Anyway.
In direct-edges we find all the edges in a list that start from a particular node. The lambda function compares the car of the given edge, x, and returns truth if it's the same as the node parameter the function was called with. remove-if-not deletes any item from edge-list that returns false from the lambda.
In get-connected we build a list of visited nodes. We define a function traverse which we the call recursively against each node linked to the node parameter in the edge-list parameter. At each node we first push it onto the visited list (which acts as progress tracking, return value, and recursion limiter because the unless form controls the recursion of traverse by testing the node against existence in visited) then we map traverse across the cdr of the list of edges provided by direct-edges for the given node. In the end we return everything we've accumulated in visited.
Allow a brief interlude here to define a few new language functions. let* works precisely like let except it allows references to other variables within the variable definition form. So
will run fine (returning 8) while
will cause a parse error (specifically that variable a has no value, though it's clearly defined right there). It's important to note that order in let* matters. The variable still has to be defined before you reference it.
We'll also use set-difference which simply takes two lists and returns what is in the first list but not the second.
Without further delay the find-islands function defines a function find-island. Allow me to make another aside. I deplore the use of plurality to differentiate the interior function from the outer function, even though it makes semantic sense, because it makes it damnably confusing to read properly at a glance unless they're highlighted like above. This gets even worse when you realize that the variables node and nodes act precisely the same here. node is one of the parameters of the outer function and nodes is the parameter of the inner function. Compounding your confusion would be the fact that node is fed to find-island in the body of the outer function causing significant (for me at least, maybe I'm a dunce) mental dissonance between giving a singular variable with a single node (assuming the semantics of the variable name are to be trusted! which in fact they aren't as we'll see shortly) in it to a plural variable which (semantically) should expect to receive a list of multiple nodes. Which taken together becomes a big jumbled mess of functions and variables that all look alike. Makes it a serious task to make sense of when it's not really that complicated. Now all this is probably just a failure of my intelligence. But for me, it reads a lot better like so:
Now we have, semantically, find-islands which defines explore-island which gets all the interconnected nodes in a given 'island' and then recurses on the nodes that aren't in that 'island' (thus 'exploring' the unexplored-nodes). This is perhaps a little sparser but I can grok it easier; in particular the differentiation of the names is critical to my understanding. Now, a more detailed deconstruction.
The find-islands function defines a function explore-island which uses get-connected to find the list of nodes that can be reached from the car of the parameter unexplored-nodes and put them in the connected variable. Then (using the magic of let*) we get the set-difference of unexplored-nodes and the nodes connected to this 'island'. Those nodes are still not 'explored' so we recurse them back into explore-island after pushing this 'island' (connected) onto the islands variable declared at the top of find-islands. In the end we have a list of lists of connected nodes. A list of islands, if you will, which we return.
Now the connect-with-bridges function which just takes a list of islands (notice a relationship there?) and builds a bridge between the first two. The logic is simple, even if the code looks a bit confusing at first. First look inside the append form at one of the two parameters. We'll start with the edge-pair since it's the easier one. It gets the first node in the first island in the input parameter and makes edges with the first node in the first island in the tail of the parameter. Confused? Read the c*r's backwards. (caadr islands) takes the tail (d) of islands (the second through nth term), gets the first (a) term (or island) and pulls the first (a) term, or node, off of it. Similarly for caar. The second term in append recurses into connect-with-bridges using the tail of the input parameter. Since we've recursed we need to look at that when form now. That just causes recursion to end when the function only gets a list of one island (there aren't any more islands to connect to, obviously). At which point we start returning the appended lists back up the recursion chain until at the end we have a list of bridge edges that will join all the islands given in the parameter.
Finally, the connect-all-islands function takes a list of nodes and their edges, uses find-islands to get the list of islands, gets a list of bridge edges by feeding that to connect-with-bridges, and then appends those bridges to the input edge list outputting a list of edges that will reliably connect every node together by at least one path. Phew. That feels a lot more complicated than it really is. But if you grok all that at once then I think we're well on our way to 'learning' Lisp (said by a raw neophyte so take it for what it's worth).
We are not, however, done with the hard work of the chapter. Next we need to convert our raw edge data into an alist. We'll also add the police roadblocks, since those exist along the edges rather than in the nodes. Here's another code dump.
This is somewhat less complicated than the last batch. Starting with edges-to-alist (which is the most interior function in this batch) we take a list of edge pairs and convert it to, apropo to the function name, an associative list of nodes and destinations. The last line in the function generates a list of the nodes that act as the starting point of each edge (which is effectively all nodes since the list is an undirected graph; so I'm not sure if there's a purpose to this as opposed to simply making a list of the integers from 1-*node-num*). Duplicates are removed (which is all remove-duplicates does by the way) and the resulting list is mapped by the lambda function. Within the lambda we find another mapcar which creates a list of the unique edges in the full edge list which start from the node given to the lambda. The mapping function for this interior mapcar is another lambda which creates a list of the destinations (the cdr) of the edge given to the lambda. The list result from the interior mapcar is then consed onto the original node. The reulsting list returned by the outermost mapcar (and thus the function) looks like ((1 (2) (4)) (2 (1) (3)) (3 (4) (1)) (4 (1) (3)) for a circular map with nodes 1, 2, 3, 4 in sequence.
The add-cops function takes an alist of edges (coincidentally of the type created by edges-to-alist ;) ) and a list of edges in which there will be cops (this list is generated by the outer make-city-edges function which we'll get to next, it's an edge in the format (x . y)). The outer mapcar just feeds the alist to the lambda and returns a list of the results. The logic all occurs within the lambda mapping function. First t declares node1 and node1-edges variables by breaking up the alist element it's given by the mapcar form. The interior mapcar then takes node1-edges and maps another lambda across it. This interior lambda first declares node2 as the car of the edges it's given (recall that our alist looks like ((1 (2) (4))... so the mapcar is looking at ((2) (4)...) and thus the interior lambda gets (2) which it needs to pull out of the list in order to operate on). The destination node (node2) and the start node from the outer lambda (node1, which is still in scope) are then converted via edge-pair (which you'll recall from earlier takes two nodes and creates an edge cons in both directions between them) and the intersection function is used to see if either of edge in the pair appears in the list of edges-with-cops (using the equal function as per the :test keyword since these we're comparing conses). if the intersection function returns anything at all then the node2 (the edge destination) is consed to 'cops to flag that destination. Otherwise the original edge (as it was given to the lambda in a list) is returned. In either case the resulting list (either of the destination or destination plus flag) is consed back onto the original node and the resulting alist returned to the outer mapcar. The result of the whole function looks like ((1 (2 'cops) (4)) (2 (1 'cops) (3)... which we can then parse for cops pretty easily by getting (cdr (assoc destination (cdr (assoc start edges)))). From the inside out that's getting the the current node from the edge list, getting the destinations from that node, getting a specific destination from from the list of destinations, then looking for a cdr in the destination's list (which would be our cop flag if it exists).
And now the outermost function in this clump of functionality, where we finally bring connect-all-islands and make-edge-list into the mix. The make-city-edges function uses let* to define a variable nodes as a sequential list of all nodes in the game, pass nodes to connect-all-islands to put a list of edges in edge-list and finally uses remove-if-not to generate a list of edges with cops using a lambda function that randomly returns true at a frequency modulated by *cop-odds*. Then it runs the edge-list through edges-to-alist which is returned to add-cops which returns the final output of the whole function. Basically, all this function does is figure out where the cops go and orchestrate the dance of other functions.
So now we have all the edges ready. We also need to put together the actual nodes since they'll have some context associated with them. What context? Well there's presence of the wumpus or GWG for starters but we also will need to indicate proximity to cops, GWGs, and the wumpus using sirens, lights, and blood respectively. While we could, technically, calculate proximity to these things at each move that would be an pointless load on processing since
1) Blood spreads out by two moves which increases the search range dramatically
2) The proximity search would either have to be completed at each move or a map kept up with in memory and if we're going to do that we might as well preload it all since...
3) It only takes a few bytes of memory and doesn't dramatically slow down game initialization.
So let's build an alist of nodes which includes all the localized context of each node. For starters we'll make a couple of helper functions.
neighbors just returns a list of the nodes neighboring the given node (isn't there another function that does this up there somewhere? I'm not sure now... Damn, this post is too long). It conveniently discards the COPS data. within-one just takes two nodes and checks for the second node in the neighbors of the first.
within-two first checks within-one. If that comes up false it gets all the neighbors of the first node and uses a lambda to check if the second node is within-one of them. If any of them are then some evaluates to true.
Now for the core of our node alist construction.
First a let form assigns the wumpus to a random node and as many GWGs as the game is configured to use are given random nodes and accumulated into a list. Now the guts of the make-city-nodes function is a loop that accumulates the output of two cond forms, and a when form. This is actually relatively easy to see from the code; the first cond returns '(wumpus) if you're in the same node with him, '(blood) if you're within two nodes, or nothing. The second returns '(glow-worm) if you're in a node with the GWG and '(lights!) if you're within one node of a GWG. Finally if there's a cdr in one of the destinations in the edges alist (which you'll recall from above will be our cops flag) the when will return '(sirens). All of this is appended into a list beginning with the node number.
Our play space is complete! Huzzah! Fire up the game and let's have a go at it! What's this? Where's the health bar? These graphics suck! Who wrote this piece of ... oh right. Derp! We seem to have forgotten the UI... back to the interpreter! The new-game function is quit basic.
First things first the find-empty-node utility function does just that. There's a risk here of infinite recursion though if there are too many GWGs or cops. Basically it looks for a node with no cdr in the node map so if every node has a flag of some sort then...
new-game itself simply uses the existing functions to set up some globals. It's mostly self explanatory. *visited-nodes* is just a list of nodes we've been in to save the state of the current game. draw-city just uses our existing Graphiz functions to draw the full map of the city. What's this? draw-known-city is undefined!
Ah, there it is. Glad to see it's back on the map. So the draw function here simply leverages Graphiz again. Of more import are the two helpers. known-city-nodes uses mapcan which appends the outputs of the mapping function together into a list. It maps across *visited-nodes* and the lambda function gets the edge destinations. So we end up appending together a list of all visited nodes and the destinations adjacent to them. The duplicates are removed and then this list is fed into the other lambda which gets the listed nodes directly from *congestion-city-nodes* and appends a * to the current player position or a ? to any node that hasn't been visited yet; this allows our map of the known city to include edges to places we haven't been because the nodes need to be there for the graphing utility while also being visually unambiguous. You could accurately call the ? the "Wumpus Fog of War™".
known-city-edges works similarly. The inner mapcar pulls the edge destinations for a visited node and if the destination is in the visited list it sends the whole thing to be consed to the original node. If it hasn't been visited then it makes a list of the destination's car and just sends that. This allows COPS flags to appear on edges that you've seen both sides of.
So much for our graphics (megatextures eat your heart out, these grafixs easily scale to any resolution!). Now we need to be able to control movements within the game world.
Three simple functions. They both call the same helper function, charge just sets a flag to indicate that we're going to charge instead of just walk.
handle-direction attempts to get the pos (the node we're going to) out of the possible destinations for the player's postion in *congestion-city-edges*. If it can't then edge is false and it outputs the error. Otherwise it calls this function:
The first thing that happens is we get the player's current position into node and then we check to see if 1. there's a GWG there and 2. we haven't been there before. If both of those are true then has-worm is true (even if there's a GWG, they only mug you once; you don't look that wealthy). With those variables set we pushnew the position onto *visited-nodes*, update the current position parameter, and redraw the map of the known city. Next we check for changes in the game status. The cond checks for cops on the edge you followed which ends the game, then for the wumpus (and prints a message based on the charging flag). If the wumpus wasn't there but you were charging then you waste your last bullet. Finally, if there is a GWG in the new node it moves us to a random new position. It should be pointed out that the recursive call to handle-new-place here sends nil for the edge parameter which, by nature, fails the cop and wumpus checks above.
Now ideally when the game is over we'd set some kind of ending condition but, in this case, we'll just print some messages and go on taking input. So technically winning and losing is a bit pointless. Hey, this isn't a triple A game we're making here; it's a language demo. As for playing, it's a bit fiddly. Open the known city map PNG file created by Graphiz in your browser. Yes, that's your graphics. Now enter (walk #) or (charge #) at the REPL and reload the image in your browser. Yeh, I said it's fiddly didn't I? I also said it isn't intended to be AAA right? I'm sure I said that somewhere...
That concludes this (rather long) post. If you think it took you forever to read I'm afraid it took me even longer to write it (week long interruptions are horrible). The code files are at...
grapher.lisp
GrandTheftWumpus.lisp
You'll want to do the following:
to get things running (using the correct paths of course).
