44

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)

Rachel
  • 23,979
  • 16
  • 91
  • 159
  • 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 00:35
  • 1
    @Dynamic This is a data structure question, so it fits in just fine here. – Izkata May 12 '12 at 04:20

8 Answers8

45

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)

Bubblewrap
  • 1,049
  • 9
  • 9
  • 2
    Make each Room object contain north-east-south-west information to other Room objects, so you can both use the dictionary/hashmap as well as the Room cardinal directions to navigate the maze (sometimes you'll want to find with absolute coordinates and sometimes you'll want to know what's north of Room object X). – Neil May 11 '12 at 16:14
  • I'm not convinced this idea would work.. But maybe I'm not reading it correctly. I would see that some room to room would be easy, but others would require looping thru the dictionary... – Paul May 11 '12 at 16:55
  • 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
  • 7
    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
  • I like this option, it is the highest level of abstraction of any of the answers here and reduces the *adjacent rooms* problem to three dictionary lookups (presumably you already know about the room you came from). The only real problem will be ensuring that the door/wall flags match up (i.e. if (0,0)E is a *wall* then (0,1)W can't be a *door*) though I guess a mismatch could be used to denote *secret doors*. *8') – Mark Booth May 11 '12 at 17:34
  • 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)`. – Steven Evers May 11 '12 at 17:39
  • @MarkBooth That's handled by Rachel's comment. When creating a new room, check all four adjacent ones to see if they exist, then copy the door/wall setting from that room. Otherwise, generate something new. – Izkata May 11 '12 at 18:13
  • 2
    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
  • @Izkata, sorry, you misunderstood my comment. I'm trying to say that there is no reason to try to compensate for edges like the other comments are. This is as good or better than the array and solves expansion, and therefore should be good enough as the solution. – user606723 May 11 '12 at 20:23
  • Why not simply expand this for "Boundaries"? @(x,y+.5) would contain the description of the boundary for the wall/door/ponies north of @(x,y) and south of @(x,y+1). Halves would contain the boundary information... – WernerCD May 11 '12 at 20:55
  • @user606723 The other comments are trying to compensate for edges because the next highest rated answer (SnOrfus's, if the answer ranking changes) has doors-vs-walls built in. – Izkata May 11 '12 at 20:55
  • Wow. Just have to say this answer is beautiful in its simplicity and functionality. + 10 if I could. – emragins May 12 '12 at 17:01
15

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.

Steven Evers
  • 28,200
  • 10
  • 75
  • 159
  • 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. – Edward Strange 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. – Steven 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
  • @CrazyEddie wouldn't a [Directed Graph](http://en.wikipedia.org/wiki/Directed_graph) do that? – Joshua Drake May 11 '12 at 18:50
  • @MarkBooth: Depends a bit on the data. *Worst* case scenario is `O(n)` if rooms are centered on `(x,y)` co-ords with 1 unit between them (that is to say that room A is at `(1,1)` and room B is at `(1,2)` for instance). If that's not the case, then yes, it gets expensive calculating Euclidean distances in `O(n)` worst-case (I am pretty sure that there's faster ways, but I personally don't know them off-hand) - but there's no solution that I know of that solves that trivially. And it's outside the scope of this problem as @JoshuaDrake noted. – Steven Evers May 12 '12 at 05:02
  • @JoshuaDrake - I was just trying to point out that finding an arbitrary point on the graph is very expensive. If you've ever played [Carcasonne](http://en.wikipedia.org/wiki/Carcassonne_%28board_game%29) you will know that you often end up with blank spaces in the graph and matching up the edges for new tile placement can force the game to expand in unexpected ways. – Mark Booth May 12 '12 at 10:41
  • @SnOrfus - But the only valid path between (1,1) and (1,2) **might** take you by a long and circuitous route via (-56,132)! – Mark Booth May 12 '12 at 10:45
  • @MarkBooth: Certainly. A* and Dijkstra's algos both are designed to work on graphs, have lots of material for writing against graph data structures and the former is guaranteed (with a pessimistic heuristic) to find an optimal path. All of which strengthens the case for using a graph. Anything beyond the most trivial of cases just ends up re-inventing a graph. – Steven Evers May 15 '12 at 22:16
9

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.

Community
  • 1
  • 1
    Nice answer, as [Bubblewrap](http://programmers.stackexchange.com/a/148251/22493) 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
2

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.

Paul
  • 730
  • 3
  • 13
1

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 q0 ∈ Q, 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.

Community
  • 1
kba
  • 976
  • 2
  • 10
  • 19
0

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.

Edward Strange
  • 9,172
  • 2
  • 36
  • 48
  • 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. – Steven Evers May 11 '12 at 15:38
0

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.

laaph
  • 151
  • 4
0

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.

Julian
  • 101
  • 2