This may be a duplicate question as I don't know to phrase the search query. I'm creating 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?
An array of rooms, and for each room a list of exits, with reference to the room that it leads to.
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.
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.
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.
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.