Sign in to follow this  

A Beginners DFS Maze Problem

This topic is 827 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

Hi,
 
I have been using this site www.migapro.com/depth-first-search/ to learn about how to do mazes
 
I have got it setup and it works ok but I have a problem. Sometimes when the map is created it doesn't find every possible path to create a maze.

I have been able to work out a formula based on the size of the maze to determine how many grid tiles should be used to make the map, and if that size is not correct, then redo the map.

 

I'd like not to have to redo the whole map, or understand why it fails to fill all possible grid positions.

 

I'm still a beginner and am starting to understand how the recursion works. If you could have a look over my code and point out what I should be looking at to find the error. It only happens like 1 in 10 times. I think it is in the direction it randomly chooses to travel in....( in this case it didn't go "up" at all.

 

Here is a picture of one of the bad maps.

 

[attachment=29068:badmaze.jpg]

 

and here is the code:

GenerateMaze::GenerateMaze(int mazex, int mazey)
{
	numberofcells = mazesize*mazesize;
	mazesizex = mazex;
	mazesizey = mazey;
	Directiontotravel.push_back(Direction::Up);
	Directiontotravel.push_back(Direction::Down);
	Directiontotravel.push_back(Direction::Left);
	Directiontotravel.push_back(Direction::Right);

}
bool GenerateMaze::GenerateNewMaze(int mazearray[], int mazexsize, int mazeysize)
{
	system("CLS");
	// maze maker magic
	// use recursion rather than a stack.
	ClearMaze(mazearray);
	int startpoint = mazesize+1; 
	Visited[startpoint] = true;
	mazearray[startpoint] = 1;

	int xposcell = startpoint % mazesizex; // x pos in tiles
	int yposcell = startpoint / mazesizey; // y pos in tiles
	// reduce number of cells by 1 for starting location aswell
	numberofcells--;

	// call recursion function
	bool succeeded = Generate(mazearray, xposcell, yposcell);
	return succeeded;
}
bool GenerateMaze::Generate(int mazearray[], int x, int y)
{
	int newtile = -1;
	int betweentile = -1;
	std::random_shuffle(Directiontotravel.begin(), Directiontotravel.end());
	for (int a = 0; a < (int)Directiontotravel.size(); a++)
	{
		switch (Directiontotravel[a])
		{
		case Direction::Up:
			if (y - 2 <= 0)
				continue;
			 newtile = x + ((y-2) * mazesizex);
			 betweentile = x + ((y - 1) * mazesizex);
			if (!Visited[newtile] && !Visited[betweentile]) // tiles have not been visited
			{
				Visited[newtile] = true;
				Visited[betweentile] = true;
				mazearray[newtile] = 1;
				mazearray[betweentile] = 1;
				numberofcells -= 2;
				int newx = newtile % mazesizex;
				int newy = newtile / mazesizey;
				Generate(mazearray, newx, newy);
			}
			break;
		case Direction::Down:
			if (y + 2 >= mazesizey - 1)
				continue;
			newtile = x + ((y + 2) * mazesizex);
			betweentile = x + ((y + 1) * mazesizex);
			if (!Visited[newtile] && !Visited[betweentile]) // tiles have not been visited
			{
				Visited[newtile] = true;
				Visited[betweentile] = true;
				mazearray[newtile] = 1;
				mazearray[betweentile] = 1;
				numberofcells -= 2;
				int newx = newtile % mazesizex;
				int newy = newtile / mazesizey;
				Generate(mazearray, newx, newy);
			}
			break;
		case Direction::Left:
			if (x - 2 <= 0)
				continue;
			newtile = (x - 2) + (y * mazesizex);
			betweentile = (x - 1) + (y * mazesizex);
			if (!Visited[newtile] && !Visited[betweentile]) // tiles have not been visited
			{
				Visited[newtile] = true;
				Visited[betweentile] = true;
				mazearray[newtile] = 1;
				mazearray[betweentile] = 1;
				numberofcells -= 2;
				int newx = newtile % mazesizex;
				int newy = newtile / mazesizex;
				Generate(mazearray, newx, newy);
			}
			break;
		case Direction::Right:
			if (x + 2 >= mazesizex - 1)
			continue;

			newtile = (x + 2) + (y * mazesizex);
			betweentile = (x + 1) + (y * mazesizex);
			if (!Visited[newtile] && !Visited[betweentile]) // tiles have not been visited
			{
				Visited[newtile] = true;
				Visited[betweentile] = true;
				mazearray[newtile] = 1;
				mazearray[betweentile] = 1;
				numberofcells -= 2;
				int newx = newtile % mazesizex;
				int newy = newtile / mazesizex;
				Generate(mazearray, newx, newy);
			}
			break;

		}

	}
	return true;

}
bool GenerateMaze::ClearMaze(int mazearray[])
{
	for (auto &a : Visited)
	{
		a = false;
	}
	for (int x = 0; x < mazesizex*mazesizey; x++)
	{
		mazearray[x] = 0;
	}
	return true;
}

Thanks for reading ph34r.png

 

werdy666biggrin.png

Share this post


Link to post
Share on other sites

I'm going to tell the solution because it is not an easy one and would take some time to figure it out even with a gentle nudge in the right direction (it took me some time to actually figure it out too, it is somewhat hidden laugh.png), but you have to promise me, that you are going to look into debugging wink.png!

As you said you are a beginner, and you most likely have yet to use a debugger. I suspect based on the screenshot, that you are on a windows machine, so you are probably using Visual Studio or Code Blocks or Eclipse as your IDE, and all of them is equipped with a capable one.
In the future you are going to be using it a lot to figure out what is causing a problem.

In one sentence it is a tool helping you step over your code and inspect the instruction flow and data of your program as it is running, to capture nasty bugs.

Now about the exact problem you are facing. It is happening somewhat due to recursion.

// use recursion rather than a stack.

I guess you may know that, but you are actually using a stack tongue.png. The call stack holding the called functions and their local variables, so the last called function with it's local variables are on the top and as you return you are popping that stack.
If you use memory/data which is in reach of each call of the "Generate" function, than you are having non-local variables used in "Generate" (non local to the function), and this in case of recursive functions can cause ~serious mess~ and elusive/hideous bugs.
If you inspect your variables closely "Directiontotravel" is not local to the "Generate" function, thus whenever you enter the function you reshuffle that list, so when you return from a bunch of calls and start to continue the for loop you may have a totally different direction order (due to being reshuffled by the consecutive "Generate" calls) and you may leave out checking some directions due to this.

NOW GO AND CHECK THIS OUT WITH A DEBUGGER!!! biggrin.png

Simple solution is to move the following code, to the "Generate" function and get rid of the class member variable:

std::vector<Direction> Directiontotravel;
Directiontotravel.push_back(Direction::Up);
Directiontotravel.push_back(Direction::Down);
Directiontotravel.push_back(Direction::Left);
Directiontotravel.push_back(Direction::Right);

Also a couple of suggestions for your code. I know you are beginner, these are just suggestions, so that you don't end up running into common mistakes in the future.

#1:
Never be lazy to put out brackets, even with having only one instruction in the scope of an if/for/while etc... Some programmers will say, that this is only opinion and preference stuff, and it is not necessary, and they are right, it is not necessary. But these are the programmers who mistakenly cause problems like the last famous iOS security problem. You can inject nasty bugs so easily at these locations so I suggest to do not fall to laziness in this case:

if (y - 2 <= 0)
{
    continue;
}

#2:
Use a consistent naming style all over your code base. As I see, you are using camel casing, but some of the variables are not cased correctly and it is hard to read them. Casing in camel format is important, because it lets you easily read out words even without spaces.

GenerateMaze <= easy to read
maze array <= easy to read (can't be used as identifier due to space)
maze x size <= easy to read (can't be used as identifier due to space)

mazearray <= hard to read, use: mazeArray
mazexsize <= hard to read, use: mazeSizeX

Also use verbs for functions (Generate is good), and nouns for classes/types (GenerateMaze is not so good, use MazeGenerator instead). It makes your code easier to understand when reading it.

#3:
Regularly clean up your code and refactor messy parts:

bool GenerateMaze::GenerateNewMaze(int mazearray[], int mazexsize, int mazeysize)

Here the "mazexsize" and "mazeysize" variables are not even used, get rid of them!

#4:
Functions, structures, classes, polymorphism, are all tools to generalize problems and get rid of duplicated code (solving the same problem multiple times at different locations in the code-base with the same logic/snippet). Your code is small, yet it is crawling with duplication already. Code duplication is a certain way for unnecessarily lengthy code which is full of copy paste bugs...

Visited[newtile] = true;
Visited[betweentile] = true;
mazearray[newtile] = 1;
mazearray[betweentile] = 1;
numberofcells -= 2;
int newx = newtile % mazesizex;
int newy = newtile / mazesizey;
Generate(mazearray, newx, newy);

100% of this code part is copied four times to every case branch, move this to a function. You don't have to be overzealous of course with this. Sometimes it takes a lot of hacky code to get rid of a small duplication. Don't do that, but always refactor and move replicating code parts into more generalized constructs.

Classes and structs can help you out even more with this problem. For example you have a lot a places where you pass an x and a y integer as a means of sharing a coordinate value with other parts of the code. You could create a Coordinate structure for that, if your standard library does not already provide something similar. Also you could add helper functions to this structure, so you can safely do these logic and there is no need to copy it around to multiple places:

int tile = x + (y * mazesizex);

int x = tile % mazesizex;
int y = tile / mazesizey;

Br. and good luck with the debugger wink.png...

Edited by Spidi

Share this post


Link to post
Share on other sites

Thanks Spidi. - And Eck, I will take your recommendation too!smile.png

 

1. I do see tutorials that will not use them and some that use brackets even if it is one command. I personally like that brackets cause I find it easier to read myself.

 

2. My naming convention does need work. The more I code the more I will get it right. Practice makes perfect. You should see my class member names. Gotta remember to use m_ for them!

 

3. Yeah I kinda put that in ready for when I can start using mazes of a different height to width. Also I will use a vector rather than an array so I can decide at run time the size of the maps.

 

4. Yeah I have since cleaned up my code a little, I haven't yet put that into a function but I will. Just gotta work out the logistics of it all. Any problems with it I know where to ask for help! smile.png

 

I knew it would be something simple. I have used the debugger in VS 2013 and even watched the directions change each time.....

I do like the debugger, it does come in handy when I want to make sure a variable has a value and when it has one I did not think it should, I go straight to my code and work it out from there. I think being fairly rusty( haven't touched any programming for like 4 years now) I think I assumed that the Directions vector was not global casue it was in a class. Didn't cross my mind that it was global to the class itself!

Edited by werdy666

Share this post


Link to post
Share on other sites

This topic is 827 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.

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