How to implement connected rooms?

This may be a duplicate question as I don't know to phrase the search query. I'm creati开发者_运维技巧ng a Zork-like text based game in Java where the character moves to different rooms which are connected to each other. I want to be able to list all options a player has available for this room.

For example, Room A is connected east to B, and B is connected west to A, south to C, north to D and so forth.

What data structure should I use or how should I implement this as efficiently as possible?

The first thing to decide is what constitutes a valid direction: is it from a fixed list or can it be freeform text? The simplest solution is to have the four cardinal directions. Some have suggested doing this as an int array. That might be a valid solution in C/C++/C# (enums in all of them are just int constants) but there is no reason to do it in Java.

In Java you can use a (typesafe) enum—which incidentally can have state and behaviour—and use an EnumMap, which is highly efficient. Internally it's just an array indexed by enum ordinal value. You might argue what's the difference between that and an int array? The answer is that the int array inside EnumMap is an internal implementation detail for a typesafe random access collection.

If you allow freeform text for the exit direction, your structure will look something like this:

Map<String, Direction> exits;

I don't recommend this however. I recommend enumerating possible directions:

public enum Direction {
  NORTH("north", "n"),
  NORTHWEST("northwest", "nw"),
  ...
  IN("in"),
  OUT("out");

  private final static Map<String, Direction> INSTANCES;

  static {
    Map<String, Direction> map = new HashMap<String, Direction>();
    for (Direction direction : values()) {
      for (String exit : direction.exits) {
        if (map.containsKey(exit)) {
          throw new IllegalStateException("Exit '" + exit + "' duplicated");
        }
        map.put(exit, direction);
      }
    }
    INSTANCES = Collections.unmodifiableMap(map);
  }

  private final List<String> exits;

  Direction(String... exits) {
    this.exits = Collections.unmodifiableList(Arrays.asList(exits));
  }

  public List<String> getExits() { return exits; }
  public String getName() { return exits.get(0); }
  public static Map<String, Direction> getInstances() { return INSTANCES; }
  public static Direction getDirection(String exit) { return INSTANCES.get(exit); }
}

which you then store with:

private final Map<Direction, Exit> exits =
  new EnumMap<Direction, Exit>(Direction.class);

That gives you type-safety, performance and extensibility.

The first way to think about this is as a Map:

Map<String, Room> exits;

where the key is a freeform direction (north, east, south, etc).

Next question: what is an Exit? In the simplest case, an Exit is simply what Room you end up in but then you start asking all sorts of questions like:

• Can the player see the exit?
• Is the exit closed or open?
• Can the exit be closed, opened, locked, unlocked, pushed open, etc?
• Can use of the exit be programmatic (eg you have to be carrying a certain amulet)?
• Can where you end up be programmatic (eg you could fall down a pit-trap and end up somewhere else entirely)?
• Can using an exit trigger some other action (eg setting off an alarm)?

It is necessary to consider the interface for a text adventure game. A player types in commands in the following form:

Verb [[preposition1] object1 [[preposition2] object2]] 

That's one possibility at least. Examples would include:

• sit (verb = sit);
• open door (verb = open, object1 = door)
• look at book;
• lock chest with iron key (verb = lock, object1 = chest, preposition2 = with, object2 = iron key);
• cast fireball at orc;
• etc.

So the above covers a fairly comprehensive set of behaviour. The point of all this is:

• Exits will support a number of Verbs or Commands (eg you can open/close a door but not a passageway);
• Monsters and items also will support commands (a wand can be "waved" and an orc can be "hit");
• Exits, monsters and items are then all types of Objects (being things in game that can be interacted with in some way).

so:

public enum Command { LOOK, HIT, WAVE, OPEN, CLOSE, ... };

(and there will no doubt be behaviour associated with those instances) and:

public class GameObject {
  boolean isSupported(Command command);
  boolean trigger(Command command);
}

public class Exit extends GameObject {
  ...
}

GameObjects may also have other state such as whether they can be seen or not. Interestingly, the Direction enum instances are also arguably Commands, which again changes the abstraction.

So hopefully that should help point you in the right direction. There is no "right" answer for the abstraction because it all depends on what you need to model and support. This should hopefully give you a starting point however.

An array of rooms, and for each room a list of exits, with reference to the room that it leads to.

You can store your Room objects in a List or a Set or (as Lars D suggested) an array.

Within Room, I think a nice way to store exits (considering they could be other than just the 4 cardinal directions) would be in a Map, with an Enum for the direction and the adjoining Room as the value.

That's pretty efficient in storage space and should also be quick enough to navigate through.

It sounds to me like you need a data structure known as a multimap.

This is a collection like a hash but where keys can have multiple values. There isn't one as such in Java but it is easily constructed by using an ordinary collection with two levels: store a list in a map. The key is a unique token for the door and the list contains all the rooms to which the door connects. Usually this will be just two rooms, but perhaps the door has some level of magic to it.

Approximately the same thing is to have your own class Door, which contains anything you want plus a reference to both connecting rooms. This then only needs a normal map.

In either case, the Room class then just has door keys in it that can be looked up in the collection.

You certainly could put the topology of the rooms directly into the room objects, having door structures that directly reference other rooms, but I suspect that doors will have state of their own (open, closed, locked, ...) and in any case you have a chicken-and-egg problem of how to create all those links in the first place. Using a library collection solves all of these problems.

You could implement this using an array:

class Room {
    private Room[] exits = new Room[4];
}

In this example, exits[0] could contain a reference to the room to the north, exits[1] the room to the east, and so on. If an element contains null then that might represent no exit in that direction.

Note that you can create nonlinear data structures using this method, such as A -> B -> C -> A.

The first thing that came to mind when I saw the question was a making a Graph data structure, but reading these other comments, a Map is probably a lot better. Graphs are too complicated.

Using a proper graph library would be more powerful and flexible than most of the Map approaches here. The Jung library (http://jung.sourceforge.net/) provides a lot of graph based functionality in Java. Although it might look a little complicated, it's probably worth the time investment in the long run.