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.
|
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:
-
WPI_HURT: The individual is being killed by another.
-
WPI_DEAD: The individual is dead and the packet contains the individual's
obituary.
-
A cavern number, which indicates where the individual is currently located.
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:
-
mcast_bind: creates a socket and binds it to the multicast address
and port number of your choice. This socket is used in calls to wpi_recv.
All members of your multicast group must use the same multicast address
and port number to communicate with each other. Conversely, to avoid receiving
or sending packets belonging to others in the course, pick a multicast
address and port number that no one else is using. You will have a hard
time debugging if you use the default multicast address WPI_ADDR
and port number WPI_PORT when someone else is also using same.
-
mcast_connect: creates a socket and connects it to the multicast
address and port. This socket is used in calls to wpi_send. In
wumpi,
mcast_connect
is called with looping turned off to avoid making each player deal with
its own packets. You must also set the ttl of your multicast communication
to the ttl value supplied by the caller of mcast_connect.
-
wpi_recv: receives a wumpi packet. Don't forget to do byte-ordering
conversion.
-
wpi_send: sends a wumpi packet. Don't forget to do byte-ordering
conversion.
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.
|
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.
|
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.
|
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.
|
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
-
Study the files mrecv.c and msend.c and play with the
programs mrecv and msend before you start working on this
assignment. This will at least help you write the functions in mcast.c.
Fire up mrecv on a couple of machines and then fire up msend
to send a message to all of the mrecv's you have started. This will
help you see the power of multicasting. To avoid conflicts with others
in the course, you may want to use a different multicast address than the
one hard coded into mrecv.c and msend.c.
-
Use wumpi -g mcast_address option to specify your own multicast
address when debugging. This will prevent you from interfering with each
other's session.
-
As noted above, multicasting does not seem to be working between labs.
Use machines that are in the same lab to test your code.
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).