Jump to content
  • Advertisement
Sign in to follow this  
zoner7

backtracking recursive algorithm

This topic is 3409 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 trying to write my first game, and in order to do so, I need to design a recursive algorithm with backtracking capabilities. In the game, there is a grid of tiles. Some of these tiles back be moved to; however, a few of them are impassable. The goal of the player is to travel to each open tile once, which means that he must travel to every tile without crossing his path. At any given point, a player may have a maximum of 3 choices of direction to move, except on the first move, during which the player will have 4 choices, and a minimum of 1 choice. Since the player travels from one block to the next but is unable to cross his path, he cannot travel backwards. So, in essence, the player can travel up, down, left or right minus one possibility (the direction you came from). here is some psuedo code I wrote
bool GenBoard(w,[])
{
	//base case
	 if (w == []){ 
		return true;
	 }
	 for all a in w{
		 if OK(a) //if the player has not moved to this tile
			 GenBoard(w-{a}, p + {a});  //(w - {a}) removes a from boolean set w | (p + a) = append a to list p.
				return true;
	 }
	 //backtrack
	 return false
 }


I figured I would have 2 sets, w and p. w holds all possible tiles that have not been traveled to and that are not impassable. p is a list of those tiles that have been traveled to. a is the element of the set that the player is considering to move to once set w is empty, then a solvable maze has been generated (the base case). ...my first conundrum is will this strategy even work. And if it will, how in the world do I even go about implementing it? Thanks for the help

Share this post


Link to post
Share on other sites
Advertisement
It generates a grid that is ensured to be solvable by the player; that is, it is possible for the player to move through every tile without crossing his path

Share this post


Link to post
Share on other sites
When you write pseudocode, there's no reason to use short variable names. Keep it clear what everything is supposed to be. In fact, do that in your real code, too. :)

I get something like:


# The initial value of "unvisitedLocations" should hold every location minus
# the start location, which is the initial "currentLocation".

to checkIfSolvable(currentLocation, unvisitedLocations):
if empty(unvisitedLocations): return true # everything was visited
# See if we were forced to re-visit a location.
if currentLocation in unvisitedLocations: return false

for location in adjacentTo(currentLocation):
if checkIfSolvable(location, unvisitedLocations - location):
return true

return false # no step from here leads to a solution.




You don't have to provide for the "can't move backwards" condition explicitly, because it's already covered by the "can't re-visit a tile" condition. And you don't want to search through already-visited locations to find the next step; you want to look at the locations adjacent to the current position.

Share this post


Link to post
Share on other sites
Alright. So here is what I've written for the function so far. The end is still the psuedocode that you gave me.

Tell me if I'm on the right track here.

[source=c++]
bool GenBoard(itsCurrentLocation, UnvisitedLocations)
{
// Base case
//Check to see if every cell has been visited yet
for (int i = 0; i < pBoard.GetRows(); i++)
{
for (int j = 0; i < pBoard.GetColumns(); i++)
{
if (pBoard.GetUnvisted()) == true)
break;
else return true; //Everything was visited. Board is complete
}
}

// See if we were forced to re-visit a location. That means that the current location has been visited
if (pBoard.GetUnvisited() == pBoard.GetCurrentPosition())
return false;
}

for location in adjacentTo(currentLocation)
{
if checkIfSolvable(location, unvisitedLocations - location)
return true;
}
return false // a solution cannot be reached by moving somewhere from this point
}



I'm not exactly sure what the return true and false does. What do I even do with it when it returns to main?

and why is there a return true (or, rather, a return anything at all after

[source=c++]
if checkIfSolvable(location, unvisitedLocations - location)
return true;



Shouldn't this point never even be reached?

Share this post


Link to post
Share on other sites
The method that Zahlman wrote, and apparently the one you adapted as well, checks whether an already-generated board is solvable, it doesn't generate the board in the first place. That's why it returns true or false.

How big are your boards going to be? If they're relatively small, 10x10 or 20x20 or so, it might be possible to just randomly generate a board, check whether it's solvable, and if not generate another random one (looping until you generate a solvable one). That depends on a number of factors, though...

Share this post


Link to post
Share on other sites
yea the boards would be about that small. But I think it would be A LOT faster to use some sort of recursive backtracking algorithm. I wrote a sudoku generator a while back that didn't backtrack, and it took nearly 10 minutes to generate a board.

the actually board generation part would be really easy after getting this algorithm to work. I would just randomly place impassable tiles, run the verification algorithm, and if it worked I would save the board, otherwise I would throw it out and try a new one.

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!