The map of Congestion City will be an undirected graph with data associated with each node stored in the variable *congestion-city-nodes*. The possible data at each node will include the presence of the Wumpus, a Glowworm team, and various danger signs.
A set of edges stored in *congestion-city-edges* will connect the nodes, and data linked to these edges will alert us to the presence of any police roadblocks. We declare these and other global variables at the top of our program using defparameter:
(load "graph-util") (defparameter *congestion-city-nodes* nil) (defparameter *congestion-city-edges* nil) (defparameter *visited-nodes* nil)
(defparameter *node-num* 30)
(defparameter *edge-num* 45)
(defparameter *worm-num* 3)
(defparameter *cop-odds* 15)
We first load our graph utilities with the load command , which evaluates all the code in graph-util.lisp (which we created in the previous chapter) so the graph utility functions will be available. Notice that Congestion City will have 30 locations (nodes, defined with *node-num*), 45 edges (roads, defined with *edge-num*), and 3 worm teams (defined with *worm-num*). Each street will have a 1-in-15 chance of containing a roadblock (defined with *cop-odds*).
Next, we create a random list of edges to connect all the nodes:
First, we declare the random-node function , which returns a random node identifier. It uses the random function, which returns a random natural number less than the integer you pass to it. Since we’re going to be showing the node identifiers in our user interface, we use the 1+ function to number our nodes 1 through 30 (the upper limit because the *node-num* variable is set to 30), instead of 0 through 29.
The make-edge-list function generates the actual list of random edges. It uses the loop command to loop *edge-num* times , and then collects the requisite number of edges . We’ll take a closer look at the loop command in the next section. The graph of the city is undirected, so this function uses a helper function, edge-pair , to create two directed edges between the randomly selected nodes. This extra step makes sense once you remember that an undirected graph is the same as a directed graph, with two opposing directed edges mirroring each undirected edge. (When we build our edges into an alist later in this chapter, this step will ensure that the list is properly formed.)
Let’s try the make-edge-list function in the CLISP REPL:
> (make-edge-list)
((16 . 20) (20 . 16) (9 . 3) (3 . 9) (25 . 18) (18 . 25) (30 . 29)
(29 . 30) (26 . 13) (13 . 26) (12 . 25) (25 . 12) (26 . 22) (22 . 26)
(30 . 29) (29 . 30) (3 . 14) (14 . 3) (28 . 6) (6 . 28) (4 . 8) (8 . 4)
(27 . 8) (8 . 27) (3 . 30) (30 . 3) (25 . 16) (16 . 25) (5 . 21) (21 . 5)
(11 . 24) (24 . 11) (14 . 1) (1 . 14) (25 . 11) (11 . 25) (21 . 9) (9 . 21)
(12 . 22) (22 . 12) (21 . 11) (11 . 21) (11 . 17) (17 . 11) (30 . 21) (21 . 30)
(3 . 11) (11 . 3) (24 . 23) (23 . 24) (1 . 24) (24 . 1) (21 . 19) (19 . 21) (25 . 29)
(29 . 25) (1 . 26) (26 . 1) (28 . 24) (24 . 28) (20 . 15) (15 . 20)
(28 . 25) (25 . 28)
(2 . 11) (11 . 2) (11 . 24) (24 . 11) (29 . 24) (24 . 29)
(18 . 28) (28 . 18) (14 . 15)
(15 . 14) (16 . 10) (10 . 16) (3 . 26) (26 . 3) (18 . 9) (9 . 18) (5 . 12)
(12 . 5) (11 . 18) (18 . 11) (20 . 17) (17 . 20) (25 . 3) (3 . 25))You see the pairs of node numbers that make up the edges. This list of edge pairs will form the skeleton of the Congestion City road system.
Our make-edge-list function employs the powerful loop command, which can be used to loop over various types of data. We’ll be looking at loop in detail in Chapter 10. However, our game uses loop a few times, so let’s consider some simple examples to clarify how it works.
One handy thing you can do with loop is create a list of numbers. For instance, the following command will create a list of 10 ones:
>(loop repeat 10collect 1)(1 1 1 1 1 1 1 1 1 1)
Within the loop command, we specify how many times to repeat, and then specify an object to collect with every loop (in this case, the number 1).
Sometimes, we want to keep a running count as we’re looping. We can do this with the following syntax:
>(loop for n from 1 to 10collect n)(1 2 3 4 5 6 7 8 9 10)
In this example, we are saying that n should loop from 1 to 10. Then we collect each n and return it as a list.
Actually, we can put any Lisp code in the collect part of the loop. In the following example, we add 100 as we do our collecting:
>(loop for n from 1 to 10collect (+ 100 n))(101 102 103 104 105 106 107 108 109 110)
We now can generate random edges. Of course, if we just connect random nodes with random edges, there’s no guarantee that all of Congestion City will be connected because of all that randomness. For example, some parts of the city might form an island, with no connections to the main road system.
To prevent this, we’ll take our list of edges, find unconnected nodes, and connect these islands to the rest of the city network using this code:
(mapc (lambda (edge) (traverse (cdr edge))) (direct-edges node edge-list))))) (traverse node)) visited)) (defun find-islands (nodes 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 nodes)) 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))
First, we declare a utility function called direct-edges , which finds all the edges in an edge list that start from a given node. It does this by creating a new list with all edges removed (using remove-if-not ) that don’t have the current node in the car position.
To find islands, we write the get-connected function . This function takes an edge list and a source node and builds a list of all nodes connected to that node, even if it requires walking across multiple edges.
The usual way to find connected nodes is to start a visited list , and then perform a search along connected nodes, starting with the source node. Newly found nodes are added to the visited list with the push command . We also traverse all the children of this found node, using mapc .
If, on the other hand, we encounter a node that has already been visited, we know we can ignore it. Once the search is complete, the visited list will consist of all connected nodes.
Now that we have a function for finding nodes that are connected, we can use it to create a function that will find all the islands in our graph. The find-islands function first defines a local function, called find-island . This function checks which nodes are connected to the first node in our list of nodes using the connected function. It then subtracts these nodes from the full list of nodes using the set-difference function. (set-difference takes two lists, and returns all items that are in the first list but not the second.)
Any remaining nodes are deemed unconnected. If any unconnected node exists , we call the find-islands function again recursively to find additional islands.
Once we’ve found all the islands, we need a way of bridging them together. This is the job of the connect-with-bridges function. It returns a list of additional edges that join all the islands together. To do this, it takes the list of islands and checks if there is a cdr in this list . If there is, it means there are at least two land masses, which can be connected with a bridge. It uses the edge-pair function to create this bridge, and then calls itself recursively on the tail of the island list, in case additional bridges are needed.
Finally, we tie all of our island prevention functions together using the function connect-all-islands . It uses find-islands to find all the land masses, and then calls connect-with-bridges to build appropriate bridges. It then appends these bridges to the initial list of edges to produce a final, fully connected land mass.
To complete our edges for Congestion City, we need to convert the edges from an edge list into an alist. We also will add the police roadblocks, which will appear randomly on some of the edges. For these tasks, we will create the make-city-edges, edges-to-alist, and add-cops functions:
(defun make-city-edges ()
These are the most cumbersome functions in Grand Theft Wumpus. Let’s take a closer look at them.
First, the make-city-edges function creates a list of nodes, using a loop . (This is simply a list of numbers from 1 to *node-num*.) Next, it creates a random (but fully connected) edge list by calling the make-edge-list and connect-edge-list functions . This result is stored in the edge-list variable. It then creates a random list of edges that contains cops . We define these variables with the let* command, which allows us to reference previously defined variables.
The following example shows the difference between defining variables with let and let*:
>(let ((a 5)(b (+ a 2)))b)*** - EVAL: variable A has no value >(let* ((a 5)(b (+ a 2)))b)7
As you can see, let won’t allow you to refer to other defined variables (the variable b can’t reference the value of a). When defining variables with let*, on the other hand, this kind of reference is allowed. For our purposes, using let* allows our definition of cops to contain a reference to edge-list.
Once we’ve created the edge list and determined where the cops are, we need to convert our edge list into an alist and add the cops to it . The edges are converted to an alist with the edges-to-alist function, and the cops are added with the add-cops function.
The edges-to-alist function converts a list of edges into an alist of edges. For example, assume we have the following city, with only three locations and two edges connecting those locations:
We would describe this using an edge list as '((1 . 2) (2 . 1) (2 . 3) (3 . 2)). Remember that each of the edges is repeated, since the edges are undirected and can be used in both directions. If we described this same city as an alist, what would that look like?
Remember that an alist is a list that lets us look up a key (in this example, one of the three nodes in our city) and find the information associated with that key (in this case, a list of the roads connected to it). For this small city, the alist would be '((1 (2)) (2 (1) (3)) (3 (2))).
To build this alist, the edges-to-list function first mapcars over the nodes found in the edge list. To build the list of nodes, we use the remove-duplicates function, which removes duplicate items from a list. By default, remove-duplicates uses the eql function to check for equality, though it also allows you to choose a different test function using the :test keyword parameter. Since we’re checking for equality of cons pairs in our make-city-edges function, we set :test to #'equal .
Within this outer mapcar , we use another mapcar to map across all the direct-edges to this node. Together, these nested mapcar functions allow edges-to-alist to convert the edges of a city into an alist.
When we wrote the make-city-edges function, we randomly marked some of the edges to show that they have cops on them . We are now going to use this list of cop edges to mark the edges in our alist that contain cops. This is the job of the add-cops function.
To do this, we use nested mapcar commands to map across the edges within each node . We then check whether there are any cops on a given edge, using the intersection function . (The intersection function tells us which items are shared between two lists.)
To understand exactly what the add-cops function is doing, it will help to once again imagine our city with only three locations and two streets. In this example, one of the streets has cops on it:
The generated alist for this city, created by add-cops, would look like this:
((1 (2)) (2 (1) (3 COPS)) (3 (2 COPS)))
This is actually a nested alist. The outer alist is organized based on the first node, and the inner alists are organized based on the second node.
With the edges in this format, we can easily find all edges connected to a given node by calling (cdr (assoc node1 edges)). To see if a given edge contains cops, we can call (cdr (assoc node2 (cdr (assoc node1 edges)))), which goes down two levels to grab the actual data linked to a specific edge between two nodes. (One additional benefit of using this nested alist format is that it is fully compatible with our graph libraries—a feature that we’ll take advantage of shortly.)