Data Structure to Represent a Maze

Question

I'm writing a game of Dynamic maze in which after each time the structure of maze will change (Some doors will be closed and some doors will open. Something like Triwazard in HP4). Can anyone suggest me which data structure will be best suited to represent this?

Intermigration

1) What data structures have YOU considered? 2) Never assume people know all the little abbreviations you do. HP4 is not exactly a world known abbreviation for Harry Potter series' 4th book. – Tampon

Answer 1

Will the maze be a rectangular grid? Something else?

It also depends on how much of the map will contain useful information (passes or objects).

If it's a rectangular grid and most grid squares will contain SOMETHING, a good data structure is a 2D array (array of arrays), with each element of the array representing 1 row, each element of the inner arrays representing 1 cell in that row, which is an object containing data pertaining to that cell (which neighbor cells can be moved to, what does the cell contain, is there a character on it).

However, if the maze is not a rectangle, OR if a majority of the cells in a large maze don't actually contain any useful into (e.g. are un-passable blocks), a good data structure is a graph.

Every vertex of the graph is a cell that's passable. Edges represent the pairs of cells which you can move between (you can make it a directed graph if some doors are one-way only). Every vertex/cell is an object containing info on that cell (e.g. its location in the physical maze to be drawn, etc...).

The array-of-arrays structure benefit is that it's VERY easy to draw it, and fairly straight-forward to process (any move is just in/de-crement of an index). Adding/removing walls is as easy as changing data in 2 neighboring cells' array elements.

The graph structure benefit is that it takes up a lot less space if the maze passes are very sparse (e.g. only 1/100th of the field is passes); it's the only structure which can represent random (e.g. non-rectangular-grid) geometry, and the processing is fairly straightforward. Adding/removing walls is easy as it's just adding an edge to a graph.

Tampon