I'm building a simple 2D maze game using pygame.  I'm not sure what would be the best data structure to represent the maze itself.

So far I'm using 2 classes, Cell and Grid.  The Grid class is a 2D array of Cells.  Each Cell contains 4 variables: w_n w_s w_e w_w, which are boolean flags indicating whether there is a wall in that direction.

One problem I can see is that each wall is stored twice e.g. one Cell with w_e set true requires a neighbour with w_w set true.  This makes setting the walls up inefficient as when I remove a wall in one cell I have to remove it in its neighbour's as well.

Is there a better way to represent the maze?  (I'm sure there is...)

You could set it up as a graph. Each node would have a N/S/E/W neighbor pointer, and anytime a pointer is null there would be a wall there. You could extend it to have any number of neighbors and then you could generate mazes with very odd geometries, but that might not really be useful atm.

You could check out the Boost Graph Library in C++ if that sounds interesting to you.

You could set it up as a graph. Each node would have a N/S/E/W neighbor pointer, and anytime a pointer is null there would be a wall there. You could extend it to have any number of neighbors and then you could generate mazes with very odd geometries, but that might not really be useful atm.

You could check out the Boost Graph Library in C++ if that sounds interesting to you.

I've read about graphs, and it does sound like a good solution.

One thing I don't understand is how to prevent cells from overlapping.  I want to make a simple 2D maze.

Perhaps there's some way to combine the grid method and the graph method?

Rather than a 2D array of cells, I'd make a 2D array of walls. Then, when you query about a cell, you construct the cell using data from the array of walls. You can further optimize if you want, breaking your array into an array of smaller arrays to ensure spacial locality of memory.

That said, what you have now sounds fine to me. Unless performance is a problem, why optimize? Anything you do will have trade-offs, and unless you understand what resources are abundant and what resources are scarce in your program, you're going to be unable to make an informed decision.

[quote name='way2lazy2care' timestamp='1332964307' post='4926095']
You could set it up as a graph. Each node would have a N/S/E/W neighbor pointer, and anytime a pointer is null there would be a wall there. You could extend it to have any number of neighbors and then you could generate mazes with very odd geometries, but that might not really be useful atm.

You could check out the Boost Graph Library in C++ if that sounds interesting to you.

I've read about graphs, and it does sound like a good solution.

One thing I don't understand is how to prevent cells from overlapping. I want to make a simple 2D maze.

Perhaps there's some way to combine the grid method and the graph method?
[/quote]

If you have all the nodes in your graph only having 4 possible neighbors it should align to the grid naturally as long as you're controlling the initialization. Maybe to enforce it a little more you make a grid of nodes and set all their neighbors but store a boolean or bitfield or some such that says which neighbors it shares a connection with.
[source]
Nodes Maze
|1|2|3| |_ | |
|4|5|6| | ___|
|7|8|9| |____|
[/source]

So let's say you have this as your grid, 1 would store 2 and 4 as it's east and south neighbors, and bools for both; 2 would be true, since it's an open path, and 4 would be false since it's got a wall in the way.

5 would store 2, 5, 8, and 4 as it's NESW neighbors respectively. N=true, E=true, S=false, W=true.

@slavik: Premature performance optimization is bad, but this is a design decision that will affect the capabilities of his whole game; I don't think it's too soon for this kind of design.

Why not use the classic 2D array of booleans, where false = empty, true = wall?

A graph seems overkill, especially if each node represents one cell on a grid anyway.

A graph where long straight hallways are a single edge may be respectable (especially for solving), if your maze contains lots of long straight hallways.

Um I don't know why anyone hasn't mentioned to use one 2d array of tilegraphics, one 2d array of N-S walls, and one 2d array of E-W walls.
The walls should be one more or one less than the tiles, depending on if you want to store the outermost walls in the arrays or just assume they are there in the code.

ABABA
C..C..C
ABABA
C..C..C
ABABA

Then do something like check n for South or East and n-1 for North or West in the relevant array (assuming 0,0 is in the upper-left quadrant).

EDIT:
You probably don't need tilegraphics, you could just assume that if a tile is surrounded by walls on all sides make it black, otherwise make it white. Then draw the walls in.

Like the other guy said though, most people just do one array of walls and tiles, where the walls are a type of tile that you can't access ever, from any side. Not like PacMan but more like Rogue. Although I think PacMan just uses 16x16 tiles and says that an empty tile is the background color and usually sticks two of them together at once to make a pathway big enough for PacMan's fatness to squeeze through. Maybe he shouldn't eat so much.

If you want to really compress things, maybe for tons of levels, just assume either wall or path and draw lines of the other kind connecting everything. Should end up a bit more compact. You could also add a boolean to split the level into two mirrored arrangements. Many PacMan levels are mirrored. You'll need an empty array to store the current level data, but you can store the rest as algorithms or parameters.

Why not use the classic 2D array of booleans, where false = empty, true = wall?

For this wouldn't your walls end up having to be the thickness of an open cell? I do think this was the way pacman did it originally though.

A graph seems overkill, especially if each node represents one cell on a grid anyway.
[/quote]
The biggest reason I'd use a graph is because you get access to a lot of extra features that may or may not be tied to the maze itself. A bunch of AI stuff would become pretty trivial.

With the scope of what we know about the project, a graph may be overkill. It would be more fun to implement imo though :X