Jump to content
  • Advertisement
Sign in to follow this  
MarkS

Strange problem with maze generation algorithm.

This topic is 649 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement

cells[(row * num_rows) + column]

 
Bench-check that.


I have. Am I missing something?


row * num_columns

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

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

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!