Member Avatar for techie929

Hi,

I have to create a maze in C++.

// Below is the problem Statement

Let's use a simple case of a w=4 (columns) by h=3 (rows) maze to illustrate the maze-generation algorithm.

We will start with 4 × 3 = 12 closed rooms, arranged in a 4 by 3 grid:

+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

The rows are numbered 1 through h and the columns are numbered 1 through w.

Between adjoining rooms, there is either a removable vertical wall or a removable horizontal wall. There are a total of (w-1) × h removable vertical walls and w × (h-1) removable horizontal walls. Let's number these removable walls in sequencial order from top to bottom and from left to right within a row (i.e., row-major order). Some of the removable wall numbers are depicted below.

+-+-+-+-+
| 0 1 2 |
+3+4+5+6+
| 7 8 9 |
+-+-+-+-+
| | | | |
+-+-+-+-+

//Please Suggest how should I start creating the maze.How do I save the walls in the maze??

  • 2 Contributors
  • 1 Reply
  • 116 Views
  • 13 Hours Discussion Span
  • Latest Post Latest Post by Lerner

Dani AI

Generated

A compact, practical plan that builds on ’s advice: decide a representation (how to save walls) first, then pick an algorithm (how to remove them). Two common, easy-to-use representations work well for C++ and match the numbering you described.

Representations

  • Per-cell bitmask (recommended): each cell stores 4 bits (N,E,S,W). It is simple to visualize and ensures removing a wall is symmetrical (toggle the bit in both adjacent cells).
  • Separate wall arrays: keep a vector for vertical removable walls (size = h(w-1)) and one for horizontal removable walls (size = (h-1)w). Row-major indexing formulas:
    • vertical at row r, col c (0-based): index = r*(w-1) + c
    • horizontal at row r, col c: index = r*w + c
      If you need a single sequential ID for all removable walls, place the vertical block first and use an offset to map to horizontals.

Small C++ sketch (concept only):

enum Wall : uint8_t { N=1, E=2, S=4, W=8 };

struct Cell {
  uint8_t walls = N|E|S|W; // bit set = wall present
};

// helpers:
inline int cellIndex(int r,int c,int W){ return r*W + c; }
inline int vertIndex(int r,int c,int W){ return r*(W-1) + c; }
inline int horizIndex(int r,int c,int W){ return r*W + c; }

Algorithm notes

  • For a simple perfect maze use the recursive backtracker (depth-first carve). It’s easy and fast.
  • For guaranteed acyclic connection via removable-wall list, use Kruskal with a disjoint-set (union-find): shuffle all removable walls and remove one if it connects two different sets.
  • Important gotchas: always update both adjacent cells when removing a wall; pick a coordinate convention (0-based row/col) and stick to it; seed RNG for reproducibility when testing.

For comparisons of algorithms and details see the overview at Maze generation algorithms.

Member Avatar for Lerner

Always start with a plan on paper that you write out with pen/pencil. For example, in this case you might try something like this:

Determine mazeHeight
Determine mazeWidth
Use an array of type char to represent the removeable walls.
Using dynamic memory and the formulas you described declare the memory needed to store the information regarding the walls and assign each element a default value.
Determine which walls will be present and which will be absent (randomly remove or place a random number of removable walls.
Use the index of the array to access the walls
Declare a room class
Each room has 4 walls, some or all of which may be removable.
Determine which type of walls each cell has, where.
Declare a display function to show each cells walls.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.