Which data structure to use?

John

17y3.5kSoftware Architecture/Engineering

Hello all. I'm a student in a data structures class, and our professor just assigned us our 3rd project of the semester. I'll copy/paste a section of the project to give you an idea of what I'm supposed to do:

"Adventure is a game based on an imaginary world that can be envisioned as a series of connected
rooms. These rooms can be thought of as vertices of a large graph. In this text-based game, when
you enter each room, the computer produces a description, such as the following:

You are standing in a large dining hall. In front of you
is a table on which there sits a candelabra. Next to the
candelabra is a key resting on top of a folded piece of
paper. To the left is an open window. To the right is a
wooden door. Across from you, behind the table, is a
large curtain.

Users are allowed to enter simple commands, such as "pick up key," "read paper," or "exit
through window." In response, the computer will tell you the contents of the next room, the
contents of your pockets, or various other bits of information. Design an adventure game that has
at least ten rooms and seven types of objects. Observe that the rooms and their connections can
be modeled by a graph."

When I was first reading this, I saw the "connected rooms" part and immediately thought Linked List. However, when I noticed that there were possibly multiple exits to the room, linked lists suddenly didn't seem like a good idea. I've given it some more thought, but I can't really figure out which data structure would be appropriate for holding the rooms and items they could hold (keys, etc). Any help or suggestions would be greatly appreciated.

BTW, I had no clue which category this falls under so I just clicked Design and Architecture.

2 Replies

Know the answer? Post it — somebody with the same question will find it here.

Sam Hobbs17y ago
I think linked lists are not inconsistent with multiple connected rooms. You simply have a list of doors for each room that links to the room the door goes to. I am not sure what a window is but I assume a window is a way to get outside so that would be a different list. You could have separate lists for each type of item, such as a list of ddors and a separate list of windows if any and a separate list of other itmems in the room or you could have one big list of contents for each room and use a list capable of many types of objects. If it were me I would try to make a base class for all types of objects and then derive the vairous types such as doors and windows from the base class.

The following comment does not help much with your question but I want to include this comment anyway. A linked list could be more complicated if you needed to provide the ability to update the data, such as a parts list for something such as a bicycle or car or airplane because you must ensure that a component is not accidentally entered as containing a component that is also an assembly that the component is in, but since the components will not change after design time, and since a room will never have a room in it, it makes things much easier than data you are likely to encounter later in your education or career.
0
Serban Cosmin17y ago
For startes you can consider using graphs. Each room is a node in the graph and from it you can navigate to other nodes by following node links. Graphs is a to broader project to be discussed in a forum post, but here is a link with some code examples that you can download. http://msdn.microsoft.com/en-us/library/ms379574(VS.80).aspx Hope this helps.
0