How can I create cells or grids in C++ for a randomized maze?

Question

I'm trying to create a randomized maze in C++, but I can't start because I don't know how to create grids or cells. How could I create it? And I also want to create it using ASCII characters. how can i store it in array? (can any one give a sample code and some explanation so i can understand it better)

Another question: What data stuctures should I need to learn and use? I'm planning to use Eller's algorithm or Kruskal's algorithm.

Thank you guys for helping me! im a begginer programmer, and i want to learn about this, because this is a part of my project, thank you vary much!

Answer 1

Are you looking for Maze generation algorithms (more)? Is your problem with the algorithms, or graphics?

The typical algorithms work by considering each "cell" in the maze as a vertex of a graph, start with all "walls", and remove a set of walls that corresponds to a spanning tree. (So in order to randomize it, many of them start with random weights and find the minimum spanning tree.) For small mazes at least, you don't need any special data structure to represent the cells; you can just think of each cell as a pair (x,y) (its coördinates). And you don't need any data structure (adjacency matrix / adjacency list) to store the edges of the graph either, because the neighbours of (x,y) are just (x,y±1) and (x±1,y) (ignoring those that fall outside the boundaries).

In any case, once you have the spanning tree, you know exactly which of the walls "exist" and which do not, so you have a complete description of the maze. If you're going to draw the maze, you know which ones to draw.

To draw with ASCII characters, you just pass through each row one by one: draw the "upper walls" (put a "--" if the wall between (x,y) and (x,y+1) exists), then draw the actual row (put a "|" if the wall between (x,y) and (x+1,y) exists). Finally draw the bottom boundary.

Answer 2

Vertical Wall: | Horiz. Wall: _

If you're using fixed-width fonts:

 _____
| |  _
|_  | |
 __ | |
|_____|

I'm not sure exactly what to do, but here's where I'd start.

Determine where on your grid the start and end points will be. Then, create a single path, with whatever squiggles you want. Basically, it should be random movement, checking each time that there is still a way for this path to reach the end. Then, remove a certain amount of walls from this path, and create other paths from these holes. Continue this until you run out of empty space. Then, perhaps, ensure that no shorter paths have been created. If they have, block those up.

Answer 3

You probably want to store your maze in a 2-dimension char array. You can declare an array with or without initializing it in C++.

char a[30][10];  // declares a char array of 30 rows and 10 columns.

// declare an array with 3 rows and 3 columns, and provide initial values
char ticTacToeBoard[3][3] = {{'x', 'x', 'o'},
                             {'o', 'o', 'x'},
                             {'x', 'o', ' '}
                            };

You could change the initial values to '|' and '-' for walls in your maze, and use a space character, ' ', for the passageways. Either initialization method works, but you always use the elements the same way. Here's how you clear the board in the initialized array above.

// clear the board
for (int row=0; row<3; row++) {
    for (int col=0; col<3; col++) {
        ticTacToeBoard[row][col] = ' ';
    }
}

If you want to read the value of an element (useful when you're trying to navigate a maze), you use the same subscript notation as when you're setting its value.

char y = a[2][2]; // reads the character in row 2, column 2