From: Garrett Mitchener <wgm2@duke.edu>
  To  : 
  Date: 22 Apr 1999 22:18:02 -0400

graph

Someone sent me this email:

Ok.  I wrote a generic graph class that uses an adjacency matrix 
implementation.  I thought about what you said yesterday, and I am rather 
confused as to how to incorporate my graph class into my maze class.  
Right now, my maze class uses a matrix of Room objects.  Basically, I 
perceive a Room object as a node in a graph with "pointers" to other 
nodes.  What I mean by a pointer is a Connection object which is really a 
glorified reference to another Room.  (If a connection is a wall, then 
the it points to the room that contains it.)  So, each 
Foursidedroom object contains four Connections to another Room object.

Hence, in light of this set up, it seems logical to use a maze generation 
algorithm to go through a matrix and set the Connection objects of each 
room  to refer to the room you want them to.  So, my question is how do I 
change this paradigm to use a graph?

Of course I could use the graph to store which nodes are connected to 
which, but in our design, a room contains its Connections, so keeping 
around a graph storing the information about how they are connected seems 
superfluous.  So, should I just use the graph to generate a 
model of the maze, and then go through and tell all of my Room objects 
contained in the Graph what their Connections are even though containing 
Graph also knows this information?

----------------

The idea is that if you store your maze as a bunch of rooms, each with
a list of connections, then you've basically done Graph (using lists
instead of an adjacency matrix, which is still fine).  So, if you
write a Graph class, your room class can just be a special kind of
node, and the rooms no longer have to keep up with where they connect,
just what's inside, etc.  It is redundant to have a graph and a list
of connections in each room.

One group I talked to needed a graph and a matrix because their maze
was laid out on a grid.  At first, they just had the matrix and
certain kinds of terrain were impassable.  Once we made the graph part
more required, they changed their design to have a graph as well. (At
least, this was their plan when I last talked to them.)  They're going
to still use the matrix for placing things, since graphs have no sense
of location, but now their game can be more flexible because you can
jump across the map, not just from square to square.  They ended up
with two matrices, one that stores adjacency information and is hidden
inside the graph class, and one that stores location information and
knows nothing about connections.

	Hope this helps,
	-- Garrett :-)