Efficient data structure for a maze

You can write a piece of code in the editor that can cope with this issue for you. I am using a similar layout at geometry generation time for a 3D maze creation and the physics in that particular app is using a grid of cells that store a bool area of size 6 for each cell thats in use in the grid.

Best is to keep it simple in the beginning and optimise later on when certain things are proven to be slow or unwieldable.

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

Too lazy to read whole thread, but i would just make it so that the "corners" of the walls would be at the centers of the cells instead at corners of cells, and each cell could either be +,| or -

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 idea of storing n-s and e-w walls in 2 separate 2D arrays is interesting!

Even with graphs there still seems to be the problem of having to store each wall twice (or pointers back and forth between neighbours). I think this method will avoid that.

Cheers!

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

The game I'm making is a simple, no-frills perfect maze game so I think graphs may indeed be overkill.

I think they may be useful for something like a rogue-like, which is something I'd definitely like to program in the future but for now I'll keep it simple.

[quote name='Expert Novice' timestamp='1333001932' post='4926230']
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 idea of storing n-s and e-w walls in 2 separate 2D arrays is interesting!

Even with graphs there still seems to be the problem of having to store each wall twice (or pointers back and forth between neighbours). I think this method will avoid that.

Cheers!
[/quote]

The original two X-Com games use a 2D array where each 'cell' contains 4 members: IDs for floor, north-edge wall, east-edge wall, and object tiles. It works pretty well. However, it means that the southernmost and westernmost edges of the map cannot have walls on their outer edges (which is not really a problem since they design their maps with that in mind)

Success!

Amazing!

Nice work!