Sign in to follow this  

Strange problem with maze generation algorithm.

Recommended Posts

Posted (edited)
I'm having a strange issue with my recursive backtracker code. It works great, so long as the maze is defined as NxN cells. If I try to define a maze as MxN cells, I get a crash at the line noted in the code. After a few iterations through the code, but before the maze is complete, the stack seems to screw up.

Trying to understand why this happens, I wrote a little ASCII art bit of code. Every time the current cell is pushed on the stack, it generates the maze in the console. This shows an interesting problem. In the 5x5 maze, the maze generates correctly, cell by cell. In the 3x5 maze, the cell being generated is generated twice, but on opposite sides of the maze. Nothing in my code allows for this. This isn't too big of a concern, since the game I have in mind will always have NxN cells, but the error is there... somewhere... I'd rather fix this now than get a surprise later.

(3x5 maze error:)
maze_error.jpg

(5x5 maze correct:)
maze_correct.jpg

maze.h:
enum{
	NORTH = 1,
	EAST = 2,
	SOUTH = 4,
	WEST = 8
};

class Maze{
public:
	Maze(long rows,long columns);
	~Maze();

	void FillMaze();

private:
	std::vector<char>	cells;

	long			num_rows;
	long			num_columns;

	long			cell_width;
	long			cell_height;

	bool IsGoodMove(long row,long column,long direction);
};
maze.cpp
#include <stack>
#include <utility>

#include "maze.h"

Maze::Maze(long rows,long columns)
{
	for(auto i = 0;i < rows * columns;++i)
		cells.push_back(0xF);

	num_rows = rows;
	num_columns = columns;

	cell_width = 8;
	cell_height = 8;	
}

bool Maze::IsGoodMove(long row, long column,long direction)
{
	std::pair<long,long>	move_dir[4];

	if(direction < 0 || direction > 3)
		return(false);

	move_dir[0] = std::make_pair(-1, 0); // Move North.
	move_dir[1] = std::make_pair(1, 0); // Move South.
	move_dir[2] = std::make_pair(0, 1); // Move East.
	move_dir[3] = std::make_pair(0, -1); // Move West.

	row += move_dir[direction].first;
	column += move_dir[direction].second;
	if (((row >= 0) && (row < num_rows)) && ((column >= 0) && (column < num_columns)))
	{
		if (cells[(row * num_rows) + column] == 0xF)
			return(true);
		return(false);
	}
	return(false);
}

void Maze::FillMaze()
{
	std::stack<std::pair<long,long>>	cell_stack;
	std::pair<long,long>			curr_cell;
	std::pair<long,long>			next_cell;
	std::pair<long,long>			move_dir[4];
	long					visited;
	long					total;
	long					i,j,unvisited,row,column;

	// Used for pretty ASCII art.
	char					cell_num[16] = { 0xCE,0xCB,0xB9,0xBB,0xCA,0xCD,0xBC,0xFE,0xCC,0xC9,0xBA,0xFE,0xC8,0xFE,0xFE,0xDB };

	total = num_rows * num_columns;

	//srand(clock());
	srand(0);

	curr_cell = std::make_pair(rand() % num_rows, rand() % num_columns);

	visited = 1;

	// Clear maze
	for (i = 0; i < total; i++)
		cells[i] = 0xF;

	move_dir[0] = std::make_pair(-1,0); // Move North.
	move_dir[1] = std::make_pair(1,0); // Move South.
	move_dir[2] = std::make_pair(0,1); // Move East.
	move_dir[3] = std::make_pair(0,-1); // Move West.

	// Pretty debug ASCII art showing the maze being built in stages.
	for (i = 0; i < num_rows; ++i)
	{
		for (j = 0; j < num_columns; ++j)
		{
			std::cout << cell_num[cells[(i * num_rows) + j]];
		}
		std::cout << std::endl;
	}
	std::cout << std::endl;

	while (visited < total)
	{
		// find all neighbors of current cell with all walls intact
		unvisited = 0;
		for (i = 0; i < 4; i++)
		{
			if (IsGoodMove(curr_cell.first, curr_cell.second, i))
				unvisited++;
		}

		if (unvisited >= 1)
		{
			long	direction;

			do {
				direction = rand() % 4;
			}while(!IsGoodMove(curr_cell.first, curr_cell.second, direction));

			next_cell = std::make_pair(curr_cell.first + move_dir[direction].first, curr_cell.second + move_dir[direction].second);

			if (direction == 0)
			{
				column = curr_cell.second;

				row = curr_cell.first;
				cells[(row * num_rows) + column] &= ~NORTH;
				row = next_cell.first;
				cells[(row * num_rows) + column] &= ~SOUTH;
			}
			else if (direction == 1)
			{
				column = curr_cell.second;

				row = curr_cell.first;
				cells[(row * num_rows) + column] &= ~SOUTH;
				row = next_cell.first;
				cells[(row * num_rows) + column] &= ~NORTH;
			}
			else if (direction == 2)
			{
				row = curr_cell.first;

				column = curr_cell.second;
				cells[(row * num_rows) + column] &= ~EAST;
				column = next_cell.second;
				cells[(row * num_rows) + column] &= ~WEST;
			}
			else if (direction == 3)
			{
				row = curr_cell.first;

				column = curr_cell.second;
				cells[(row * num_rows) + column] &= ~WEST;
				column = next_cell.second;
				cells[(row * num_rows) + column] &= ~EAST;
			}

			cell_stack.push(curr_cell);
			curr_cell = next_cell;

			// Pretty debug ASCII art showing the maze being built in stages.
			std::cout << std::endl;
			for (i = 0; i < num_rows; ++i)
			{
				for (j = 0; j < num_columns; ++j)
				{
					std::cout << cell_num[cells[(i * num_rows) + j]];
				}
				std::cout << std::endl;
			}
			std::cout << std::endl;

			visited++;
		}else {
			curr_cell = cell_stack.top(); // <- Error happens here. cell_stack.size() indicates a size of zero.
			cell_stack.pop();
		}
	}
}
Edited by MarkS

Share this post


Link to post
Share on other sites

It's also worth noting that if you implement this algorithm correctly you should not need to count the number of cells visited. When you hit a dead end you pop the stack until you reach a node with an open neighbor. When there are no such nodes it indicates that the maze is complete.

Share this post


Link to post
Share on other sites
Posted (edited)

It's also worth noting that if you implement this algorithm correctly you should not need to count the number of cells visited. When you hit a dead end you pop the stack until you reach a node with an open neighbor. When there are no such nodes it indicates that the maze is complete.


Thanks for that! I'll make the adjustments.

I wish there was a way to eliminate the stack. I'm currently generating a 10000x10000 cell maze to stress test the algorithm and the current process memory is at 748 MB and rising... Edited by MarkS

Share this post


Link to post
Share on other sites

Is 10k^2 really realistic for your use?

 

You can work this out mathematically in any case. The element is a std::pair<long, long>, which is probably 8 bytes. The stack can't get larger than the number of cells in the maze (which would be a very rare condition) so:

 

10,000 * 10,000 * 8 = 800,000,000 bytes = Just under 763 MB

Share this post


Link to post
Share on other sites

Is 10k^2 really realistic for your use?

Absolutely not!  :lol: It took 38 minutes to generate that and topped out at 891 MB. I just wanted to see if it was stable enough to manage this. It was.

Share this post


Link to post
Share on other sites
Posted (edited)

Wow, I'm stupid! Or forgetful! I'm reviving an old project. I dug around for the code, found I was doing stupid things like allocating pointers of std::vectors with new and other oddities, and rewrote the code.

 

Today I'm digging around and found that I had already restarted this project a year or two ago and already fixed this issue. Turns out I used a MUCH older bit of code and forgot that I've been down this road before. I need a triple facepalm meme...

Edited by MarkS

Share this post


Link to post
Share on other sites
Posted (edited)

I will say that I like my current revision much better. Far cleaner and easier to read.

 

Seriously, I was doing:
 

std::stack<Cell> *cell_stack;
.
.
cell_stack = new std::stack<Cell>;
.
.
delete cell_stack;

with pretty much ever type of container. It must have been while I was learning how to use them. :unsure:

Edited by MarkS

Share this post


Link to post
Share on other sites
Posted (edited)

Reading old code tends to clearly show you how much progress you have made in the art of programming :)

When I originally wrote that I had a very negative view of C++ (still not 100% positive), but was dabbling in OOP. My understanding of smart pointers and containers was not all that clear. A std::vector is a dynamic array and you allocate dynamic arrays with malloc/new, so clearly...

Edited by MarkS

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this