Data Structures – How to Build a Data Structure for a Dynamic, Unlimited-Size Maze

data structuresgame development

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)

Best Answer

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)

Related Topic