Currently with the following algorithm I'm trying to generate a maze:
// m_maze is a m_dim*m_dim matrix filled which '#' which means a wall and ' ' means a free cell
// const int dxdy[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; // {UP, LEFT, DOWN, RIGHT}
void Maze::generate() {
std::queue<std::pair<int, int>>neighbours;
neighbours.emplace(0, 0);
m_maze[0][0] = ' '; // marking a free cell
while (!neighbours.empty()) {
std::pair<int, int> currentCell = neighbours.front();
for (int d = 0; d < 4; d++) {
const int newX = currentCell.first + 2*dxdy[d][0];
const int newY = currentCell.second + 2*dxdy[d][1];
if (newX >= 0 && newY >= 0 && newX <= m_dim && newY <= m_dim && m_maze[newX][newY] && m_maze[newX][newY] == '#') {
m_maze[currentCell.first + dxdy[d][0]][currentCell.second + dxdy[d][1]] = ' ';
m_maze[newX][newY] = ' ';
neighbours.emplace(newX, newY);
}
}
neighbours.pop();
}
}
The problem is that the output looks like this:
#
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # # #
##########################
I was thinking that this problem comes from the instructions inside if() statement, but I am not sure. The way I tought those instructions is: I'm removing a wall and then mark the next cell as free. Any tips?
Why your algorithm produces such regular results is that there is no randomness. Think the algorithm's work step by step.
At Starting point (0,0) : maze becomes to
@__#####
_#######
_#######
########
########
########
where, '@' is current position, and "free space" is shown with '_'
Next,
___#####
_#######
@__#####
_#######
_#######
########
Then
___#####
_#######
___#####
_#######
@__#####
########
And at the next step, downside position of '@' is already '_', can be step to right only. So it becomes to
__@__###
_#######
___#####
_#######
___#####
########
Since all subsequent steps are the same, the result will be as follows.
_______#
_#######
_______#
_#######
_______#
########
The directions are different between this example and your result, but this depends on how the index of the array is used.
You are digging all possible direction from current position at same time.
Changing this to "digging only one direction, and select this direction with random" will cause maze like result.