Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm not actually sure that "maze" is the correct term. Basically users start in a single Room that has 4 doors (N, S, E, and W). They can go in any direction, and each subsequent room is contains another room with anywhere from 1 to 4 doorways that go to other rooms.

The "maze" is supposed to be unlimited in size, and to grow as you move rooms. There is a limited number of Rooms available, however the available number is dynamic and can change.

My problem is, I'm not sure of the best data structure for this type of pattern

I first thought about just using a [X][X] array of Room objects, but I'd really rather avoid that since the thing is supposed to grow in any direction, and only rooms that are "visited" should be built.

The other thought was to have each Room class contain 4 linked Room properties for N, S, E, and W, and just link to the previous Room, but the problem with that I don't know how to identify if a user goes into a room that has an adjacent room already "built"

For example,

---    ---            ----------
|        |            |        |
   Start        5          4
|        |            |        |
---    ---            ---    ---
---    --- ---------- ---    ---
|        | |        | |        |
|    1          2          3
|        | |        | |        |
---    --- ---    --- ----------

If the user moves from Start > 1 > 2 > 3 > 4 > 5, then Room #5 needs to know that W contains the starting room, S is room #2 and in this case should not be available, and N can be either a new Room or a wall (nothing).

Perhaps I need a mix of the array and the linked rooms, or maybe I'm just looking at this the wrong way.

Is there a better way of building the data structure for this type of "maze"? Or am I on the right track with my current thought process, and am just missing a few pieces of information?

(In case you're interested, the project is a game very similar to Munchkin Quest)

share|improve this question
    
I don't think any kind of array would work since the rooms would grow in any directions... So if you start at [0,0] and move left? it would try [-1, 0]. –  Paul May 11 '12 at 16:52
    
@Paul Append a row/column, shift all the array data over, then shift all the player positions as well to match the new map array. Slow and can be difficult depending on how much has to be shifted, but possible. Still, Bubblewrap's answer is much better. –  Izkata May 11 '12 at 18:11
    
I'm probably wrong, but wouldn't this be better off on GameDev.SE? –  Dynamic May 12 '12 at 0:35
    
@Dynamic This is a data structure question, so it fits in just fine here. –  Izkata May 12 '12 at 4:20
add comment

8 Answers 8

up vote 41 down vote accepted

Give each Room coordinates (start would be (0,0)) and store each generated Room in a dictionary/hashmap by coordinates.

It's trivial to determine the adjacent coordinates for each Room, which you can use to check if a Room already exists. You could insert null values to represent locations where it is already determined that no Room exists. (or if that's not possible, i'm not sure atm, a seperate dictionary/hasmap for coordinates that do not contain a Room)

share|improve this answer
2  
@Paul I think the idea is to create a dictionary of rooms, and when building a new Room, look for adjacent rooms in the dictionary and add their links to the Room object before adding new rooms to the remaining sides. So the only time the dictionary lookup would occur is when creating a new Room object, not when travelling between Rooms –  Rachel May 11 '12 at 17:01
6  
There's no reason to store links to other rooms inside of a Room object at all. If you're in room (x,y) and want to travel North, you look up room (x,y+1) in the dictionary, creating it if it doesn't exist. Dictionary lookups are very fast, O(1). –  Karl Bielefeldt May 11 '12 at 17:28
3  
@KarlBielefeldt: The room @(x,y+1) may exist, but not be navigable from (x,y) going North. That is to say, that an edge may not go directly from (x,y) to (x,y+1). –  Steve Evers May 11 '12 at 17:39
1  
You guys are making this complicated. This is basically the same as an array.. except you're looking it up in a dictionary rather than a two dimensional array. Any issues you come across with an array will also be there... but he was going to use an array anyway. –  user606723 May 11 '12 at 18:31
1  
@user606723 See my comment on the question. The hash version avoids some horrible O(N^2) data shifting when you try and extend the map in 2 of the 4 directions. –  Izkata May 11 '12 at 20:03
show 8 more comments

In most cases, what you're describing sounds like a graph. Given some of your requirements (the growing aspect) I'd probably choose an adjacency list as the implementation (the other common option would be an adjacency matrix).

I'm not sure what language you're using, but a good tutorial/explanation with implementation details for a graph implemented with an adjacency list in .NET is here.

share|improve this answer
1  
Not sure a graph is sufficient to describe this since N/E/S/W aren't really part of the graph concept; there's only connected and possibly in/out. –  Crazy Eddie May 11 '12 at 15:25
3  
@CrazyEddie: Keep in mind that the/a data structure is not intended to map directly to any particular domain (indeed, that is their benefit). In this particular example, the graph would be directional and the edges can be trivially annotated with an enum. –  Steve Evers May 11 '12 at 15:31
    
The Annotation could trivially enforce the east-west,north-south relationship even. This would eliminate problems of going west from room A to room B and then going east from room B to room C (instead of room A) due to a bad link. –  Peter Smith May 11 '12 at 15:33
3  
Lets say that we wanted to implement a room populated by a wizard who protects himself by teleporting the player ten squares in a random direction. Finding that point in a graph based data structure would be very expensive, especially if that room didn't exist and you had to generate all of the rooms linking that room to another room in the graph (since the structure wouldn't allow multiple, mutually disconnected sections of dungeon). –  Mark Booth May 11 '12 at 17:51
2  
@MarkBooth but then we've changed the requirements, no? –  Joshua Drake May 11 '12 at 18:48
show 5 more comments

A couple thoughts on the implementation (I've thought of Carcassonne which has a number of other challenging aspects to building the matrix - it was even an interview question I once was asked).

There are some questions that are asked of this structure:

  1. is there a room at X,Y?
  2. is there a room [N/S/E/W] of the empty location X,Y?

The problem with simple lists and graphs

The difficulty with simple lists is that one has to walk the structure in order to test if something can be placed at a given location. The system needs a way of accessing an arbitrary location O(1).

Consider:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

To find the information the possible location '?', when at 3, one has to walk all the way around to get to 4. The answer of link with extra information on how many nodes it jumps (so that 3 would be linked to 4 with a 'jump 1' extra info) still requires walks when finding the adjacency of '*' from 6 or A.

Simple, big, arrays

There is a limited number of Rooms available

If this is a not large number, just create a 2N x 2N array and leave it there. A 100 x 100 array is 'only' 10,000 pointers and 50 objects. Index directly into the array.

This could be reduced to just NxN if out of bounds activities shifted the array around to always be within the constraints. For example, if a room was to be added that would underflow the array, have the grid to shift every element one position so that there would be no underflow anymore. At this point, the size of the world for 50 rooms would be 2500 pointers and 50 objects.

Sparse arrays and matrices

To more optimally create this, look into a sparse array in which the majority of the elements are 0 or null. For two dimensions, this is known as a sparse matrix. Many programming languages have various libraries for working with this structure. If the library restricts to integers, one could use this integer as an index into a fixed array of rooms.

My preferred approach would be to have the rooms as a structure (pointers to adjacent rooms, and coordinates) and have the room also a pointer from a hash table which is hashed on coordinate. In this situation to ask what room is [N/S/E/W] from a null room, one would query the hash table. This, incidentally, is the 'DOK' format for storing a sparse matrix.

share|improve this answer
1  
Nice answer, as Bubblewrap suggests though, a dictionary with a position tuple as key is a reasonable structure to use to implement a sparse matrix. –  Mark Booth May 11 '12 at 17:39
add comment

How about this..

Give each cell a link to each of it's neighbors. Give each cell some sort of name (ie "0/0", "-10/0" (Assume you start at 0,0)). Add a HashSet with all the names in it. As you try to move to another cell, just check that the neighbor does not already exist in the HashSet.

Also, if you create an opening to another room, does that imply that the rooms exists? So you'd create a link to an empty room with no links to any rooms. You'd probably also want to check the new rooms neighbors. If one exists, and would open to your new room, add a door to that room.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = { 0|0, 1|0, 2|0, 3|0, 0|-1, 1|-1 .... } 1,0 : W = 0,0/Door ; 1,0 : N = 1,1/Empty ; E = 2,0/Door ; S = 1,-1/Wall

You'd also have to make sure that you give each new room at least one non-adjacent (to another room) door so that the maze can grow in that direction.

share|improve this answer
add comment

What you're designing sounds a lot like a graph.

A graph of the labyrinth

These are often represented as a set of states Q, an initial state q0Q, and some transitions Δ. So, I'd suggest you store it like this.

  • A set Q: {s, 1, 2, 3, 5, 6}
  • An initial state q0: s
  • A map of transition relations Δ: {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

Most reasonable languages have both maps and sets.

share|improve this answer
add comment

You could consider a 4 way linked list...

I first thought about just using a [X][X] array of Room objects, but I'd really rather avoid that since the thing is supposed to grow in any direction, and only rooms that are "visited" should be built.

You can still use a [][] for that. The dynamic growing might be slow, especially when adding at the beginning, but maybe not all that bad. You should profile to check. Trying to manipulate some linked list or map might actually be worse, and on a constant level rather than occasional.

You can build only visited rooms by implementing lazy evaluation. An object can be in place that contains a room, and doesn't build that room until room() is called on it. Then it just returns the same one every time after that. Not hard to do.

share|improve this answer
1  
Could you expand on what you mean by a "4 way linked list"? The only thing I could find was a CodeProject article, which boild down to being an adjacency list. –  Steve Evers May 11 '12 at 15:38
add comment

I learned to do this via the book "Creating Adventure Games On Your Computer". If you are willing to dig through BASIC code (the book is that old) go read here:

http://www.atariarchives.org/adventure/chapter1.php

For the shortcut, what they do is have an array of rooms, with an element in each array being a pointer to another room that you can go to, with 0 (I would use -1 these days) to indicate that you can't go that way. For example, you'd make a room structure (or class or what-have-you)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Then you could have an array or linked list structure or however else you want to manage your rooms. For array-style (or C++ vectors) I'd use that code and the directions would hold the index of the room they link to; for a linked list, you could use pointers to the next room.

As others have said, if you need to dynamically generate new rooms when people enter them, you can also do that.

share|improve this answer
add comment

Don't try and solve all problems with one structure.

Define your room object to store things about the room, not its relations to other rooms. Then a 1D array, list etc can grow as you like.

A separate structure can hold "reachability" - which rooms are accessible from the room I'm in. Then decide if transitive reachability needs to be a quick calculation or not. You might want a brute force calculation and a cache.

Avoid early optimisation. Use really simple structures and dumb easily understood algorithms then optimise the ones that get used.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.