UM EECS 489 Fall 1999

Programming Assignment 3

DUE DATE 12/02/1999, Midnight
Note: All the files mentioned in this handout can be found in the assignment directory: /afs/engin.umich.edu/class/f99/eecs489/assignments/pa3 on CAEN's machines. It is possible that there may be bugs in our code. Please let us know asap if you suspect a bug. Recently, we have not been able to get multicasting to work between labs. When testing your code you may want to use machines that are all in the same lab.

The Game

On a web site sits a file named wumpus.c. Attached is the following note;
wumpus.c -- a faithful translation of the classic "Hunt The Wumpus" game.
Translator: Eric S. Raymond <esr@snark.thyrsus.com>
This was the state of the art 20 years ago, in 1972.
We've come a long way, baby.
The BASIC source is that posted by Magnus Olsson in USENET article
<9207071854.AA21847@thep.lu.se>: he wrote
> Below is the source code for _one_ (rather simple) Wumpus version,
> which I found in the PC-BLUE collection on SIMTEL20. I believe this is
> pretty much the same version that was published in David Ahl's ``101
> Basic Computer Games'' (or, possibly, in the sequel).
I have staunchly resisted the temptation to ``improve'' this game. It is functionally identical to the BASIC version. So, pretend for a little while that your workstation is an ASR-33 and limber up your fingers for a trip to nostalgia-land...
We have retained the text-based interface of the game, by necessity; but the rules have changed a bit. Hunt the Wumpi is a multi-player game. Each player must choose to be a wumpus or a human. To see each other, each player must play on a separate machine. A human or wumpus wakes up in 1 of 20 caverns that make up a statically configured subterranean dodecahedron. Each cavern has 3 tunnels leading to other caverns.

The True Nature of Humans

Humans (pronounced with a long aa) carry crooked arrows. An individual human is born with a certain energy level. Humans can move around the maze one cavern at a time. When a human smells a wumpus, the human may shoot it using one of its crooked arrows. Each crooked arrow can go from 1 to 5 caverns (hence the adjective crooked). To shoot an arrow, humans specifiy how many (up to 5) caverns they want the arrow to travel through, and then give the number of each cavern along the path. It takes energy to fire a shot. If a human's aim is not good, the crooked arrow travels at random and the human may die of friendly fire. If the arrow hits a wumpus, the human's energy level increases by the energy level of that wumpus. If the arrow hits another human, the shooter's energy level also increases by the the energy level of the shot human. In the end, there can be only one. If a target is killed by more than one attacker, each attacker gets an equal fraction of the target's strength. An idle human loses energy. A human that does not make a kill loses energy. An energy-less human dies of boredom. In the end it's still a zero sum game.
Hazards of life in the caverns
Two hazards complicate the lifes of humans:
1.
Bottomless pits: Two caverns have bottomless pits in them. If you go there, you fall into the pit (and die!).
2.
Wombats: Two other caverns have wombats. If you go there, the wombat grabs you and takes you to some other cavern at random (which may be troublesome).
Being a human, when you are in a cavern with, or one cavern away from, a wumpus or another human, you can smell it. Wombats are also smelly. You will feel a draft if there is a pit in an adjacent cavern. The placement of wombats and pits may be different for each human, as Fate would have it.

The True Nature of Wumpi

Wumpi (the plural form of wumpus that rhymes with wimpy--think them wimps at your own peril) are not bothered by hazards (they have sucker feet and are too big for a wombat to lift). Each wumpus is born with a different strength (energy level). A wumpus at rest gains strength. A wumpus at rest makes for an easy target. Wumpi forage for food (i.e. humans), consuming energy as they do so. A wumpus does not another wumpus eat, unless there are no humans left. Having eaten, a wumpus (not the eaten one) gains the energy level of its meal. If a victim is killed by more than one attacker, each attacker gets an equal fraction of the victim's strength. To eat its victim, a wumpus must attack it from another cavern. A wumpus can eat any human it runs into, but it can only eat another wumpus weaker than itself. If a wumpus runs out of energy without finding food, it dies of hunger. An idle but otherwise not restful wumpus also dies of hunger. Life is futile for a lonesome wumpus, but it must still live it to live.

The Wumpi Communication Protocol

Each player communicates with the other using multicasting. Fig. 1 shows the format of the packet used in this communication.
Figure 1: Wumpi Packet Format.
\begin{figure}\centerline{\epsfig {file=wumpi.eps,width=.3\linewidth}}\end{figure}

The Version field must be WPI_VERS. The Identification field identifies the individual to which the operation in the Operation field applies. The Operation field can be one of:

The Species field specifies the species of the individual. The Strength field carries the strength of the individual. All the constants mentioned above are defined in the file wumpi.h. The packet format depicted in Fig. 1 is also defined in the file wumpi.h. The file wumpi.c handles the map initialization, setting up the communication channels, and waits for user or network inputs.

When an individual entity moves, its new location is multicasted to the whole group. When an individual kills another, the act is multicasted to the whole group. When an individual dies, its obituary is multicasted to the whole group. Parts of these functionalities are implemented in the local.c file.

Your Mission

Your mission is divided into two parts. The first is really simple and should be do-able in one hour, at most. The second requires some distributed thinking. Object code for our implementation of both parts, along with a Makefile, are available in the assignment directory.

Part I: Programming for Multicast

You are to write the functions mcast_bind, mcast_connect, wpi_recv, and wpi_send: Skeletons of these functions are in the file mcast.c and wumpi.c. They make calls to our version in _mcast.o and _wumpi.o.

Part II: Distributed Computing

For this part, you are to write the functions local_wumpus, local_human, local_keepalive, local_obtr, and remote_parse.

On receiving keyboard input, the main function of wumpi calls either local_wumpus or local_human depending on whether the player is playing as a wumpus or a human, respectively. See the comments in local.c for descriptions of these functions. Periodically, local_keepalive is called to decrease the energy level of idle player. When the energy level reaches 0, the player is declared dead. When a player is dead, either of boredom, idleness, sloth, or being killed, the function local_obtr is called to release its soul and to send out its obituary.

The function remote_parse is called whenever the wumpi process detects that the receive socket has something waiting. You are to pull up a wumpi packet (wpiop_t defined in wumpi.h) by calling mcast_recv and then apply the operation encoded in the packet on the individual named in the packet. You may find one or more of the functions wpi_locate, wpi_identify, wpi_new, and wpi_neighbor defined in wumpi.c helpful.
 
 



Figure 2: Wumpi packet with the location and strength of golum@grinch.
\begin{figure}\centerline{\epsfig {file=move.eps,width=.3\linewidth}}\end{figure}

Fig. 2 provides an example of a wumpi packet informing group members of the location (cavern #6) and strength (23) of the wumpus golum@grinch. On receiving such a packet, you are to check if you have previously heard from the wumpus golum@grinch. If so, update its information. If not, allocate some memory to store its state (you may want to use the function wpi_new).
 
 



Figure 3: Wumpi packet stating that golum@grinch is being killed.
\begin{figure}\centerline{\epsfig {file=kill.eps,width=.3\linewidth}}\end{figure}

Fig. 3 provides an example of a wumpi packet informing group members that golum@grinch is being killed. On receiving such a packet, you are to locate golum@grinch's state. If you found it, kill it (see the comments in wumpi.h on how to kill an individual). If you yourself are golum@grinch, you must also send out an obituary informing group members of your demise.
 
 



Figure 4: Wumpi packet containing the obituary for golum@grinch.
\begin{figure}\centerline{\epsfig {file=obtr.eps,width=.3\linewidth}}\end{figure}

Fig. 4 provides an example of a wumpi packet carrying an obituary for wumpus golum@grinch. On receiving such a packet, you are to locate golum@grinch's state. If you found it, check if you are one of its killers (its location field says WPI_HURT). If so, reward yourself with its energy. If there are more than one killers, you should divide up the energy and reward yourself only your portion. If you are not the killer, free the state for future use (again, see the comments in wumpi.h on how to recycle state, namely you have to update the variables ind_loc and ind_name of the individual_t).
 
 



Figure 5: Sample flow chart for remote_parse function.
\begin{figure}\centerline{\epsfig {file=flow.eps,width=\linewidth}}\end{figure}

Fig. 5 provides a sample flow chart you can use in remote_parse to apply the operations encoded in wumpi packets. Remember this: you are using unreliable UDP for communication. Packets you sent may not get to the destinations, packets you expect may never arrive. Don't let this cause your program to hang, crash, or otherwise get confused.

Instead of doing all the above processing in remote_parse, you may wish to split them up into smaller functions that you call from remote_parse. A skeleton of remote_parse is available in remote.c. It calls our version in _remote.o

Hints

What to Turn in

Use your turnin client from HW1 to turn in all the files, and only the files, you modified or created. Same server name (kailash), same port number (4898).