Since I have been searching for the best algo for maze generation in c++. I could found its implementation in Ruby from the link
Here is the code in Raw form
# --------------------------------------------------------------------
# An implementation of the "Binary Tree" algorithm. This is perhaps
# the simplest of the maze generation algorithms to implement, and the
# fastest to run, but it creates heavily biased mazes.
#
# It is novel in that it can operate without any state at all; it only
# needs to look at the current cell, without regard for the rest of
# the maze (or even the rest of the row). Thus, like Eller's algorithm
# it can be used to generate mazes of infinite size.
# --------------------------------------------------------------------
# --------------------------------------------------------------------
# 1. Allow the maze to be customized via command-line parameters
# --------------------------------------------------------------------
width = (ARGV[0] || 10).to_i
height = (ARGV[1] || width).to_i
seed = (ARGV[2] || rand(0xFFFF_FFFF)).to_i
srand(seed)
# --------------------------------------------------------------------
# 2. Set up constants to aid with describing the passage directions
# --------------------------------------------------------------------
N, S, E, W = 1, 2, 4, 8
DX = { E => 1, W => -1, N => 0, S => 0 }
DY = { E => 0, W => 0, N => -1, S => 1 }
OPPOSITE = { E => W, W => E, N => S, S => N }
# --------------------------------------------------------------------
# 3. Data structures to assist the algorithm
# --------------------------------------------------------------------
grid = Array.new(height) { Array.new(width, 0) }
# --------------------------------------------------------------------
# 4. A simple routine to emit the maze as ASCII
# --------------------------------------------------------------------
def display_maze(grid)
print "\e[H" # move to upper-left
puts " " + "_" * (grid[0].length * 2 - 1)
grid.each_with_index do |row, y|
print "|"
row.each_with_index do |cell, x|
if cell == 0 && y+1 < grid.length && grid[y+1][x] == 0
print " "
else
print((cell & S != 0) ? " " : "_")
end
if cell == 0 && x+1 < row.length && row[x+1] == 0
print((y+1 < grid.length && (grid[y+1][x] == 0 || grid[y+1][x+1] == 0)) ? " " : "_")
elsif cell & E != 0
print(((cell | row[x+1]) & S != 0) ? " " : "_")
else
print "|"
end
end
puts
end
end
# --------------------------------------------------------------------
# 5. Binary Tree algorithm
# --------------------------------------------------------------------
print "\e[2J" # clear the screen
height.times do |y|
width.times do |x|
display_maze(grid)
sleep 0.02
dirs = []
dirs << N if y > 0
dirs << W if x > 0
if (dir = dirs[rand(dirs.length)])
nx, ny = x + DX[dir], y + DY[dir]
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
end
end
end
display_maze(grid)
# --------------------------------------------------------------------
# 6. Show the parameters used to build this maze, for repeatability
# --------------------------------------------------------------------
puts "#{$0} #{width} #{height} #{seed}"
I have converted this code in cpp as:
#include "iostream"
#include<cstdlib>
#include"time.h"
#include<vector>
using namespace std;
struct Point{
int E;
int W;
int N;
int S;
int getElementAt(int i)
{
if (i == 4)
return E;
else if (i == 8)
return W;
else if (i == 1)
return N;
else if (i == 2)
return S;
}
};
class Maze
{
private:
int width, height, seed;
int N, S, E, W;
Point DX, DY, OPPOSITE;
int **grid;
public:
Maze()
{
width = 10; //maze height
height = 10; //maze width
//seed = rand() % RAND_MAX + 1; //random number assignment to seed
srand(time(NULL));
E = 4, W = 8, N = 1, S = 2;
DX = { 1, -1, 0, 0 }; //it will keep the directions of each point on X
DY = { 0, 0, -1, 1 }; //it will keep the directions of each point on Y
OPPOSITE = { W, E, S, N };
grid = new int*[height];
for (int i = 0; i < height; i++)
{
grid[i] = new int[width];
for (int ini = 0; ini < width; ini++)
{
grid[i][ini] = 0;
}
}
}
void display_maze()
{
cout << "[H";
for (int i = 0; i < width * 2 - 1; i++)
{
cout << "_";
}
cout << endl;
for (int y = 0; y < height; y++)
{
cout << "|";
for (int x = 0; x < width; x++)
{
if (grid[y][x] == 0 && y + 1 < height && grid[y + 1][x] == 0)
cout << " ";
else
cout << ((grid[y][x] & S != 0) ? " " : "_");
if (grid[y][x] == 0 && x + 1 < height && grid[y][x + 1] == 0)
cout << ((y + 1 < height && (grid[y + 1][x] == 0 || grid[y + 1][x + 1] == 0)) ? " " : "_");
else if (grid[y][x] & E != 0)
cout << (((grid[y][x] | grid[y][x + 1]) & S != 0) ? " " : "_");
else
cout << "|";
}
cout << "\n";
}
}
void generate()
{
int y = 0;
while (y < height)
{
int x = 0;
while (x < width)
{
display_maze();
vector<int> dirs;;
if (y > 0)
dirs.push_back(N);
if (x > 0)
dirs.push_back(W);
srand(time(NULL));
int zz = rand() % (dirs.size() - 0 + 1) + 0;
if (zz < dirs.size())
{
int dir = dirs[zz];
int nx = x + DX.getElementAt(dir);
int ny = y + DY.getElementAt(dir);
grid[y][x] |= dir;
grid[ny][nx] |= OPPOSITE.getElementAt(dir);
}
x++;
}
y++;
}
}
};
void main()
{
Maze maze;
//maze.display_maze();
maze.generate();
//maze.display_maze();
}
I have converted the ruby script below display_maze to generate() function. I have also converted DX,DY,OPPOSITE to struct to reuse them easily.
The problem occurs in generate() of cpp since if (dir = dirs[rand(dirs.length)]) If i use this thing in c++ it throw index out of bound exception. I have checked through if statement.
But both of my codes generate different outputs. Please run both seperately. The display function seems to work fine. Problem is with generate() method only!
Edit:
Code is working fine but I cannot figure out the problem why maze generates differently. My ruby code give exact output but c++ code does not generate output correctly. I am unable to get the issue!