Public Group

# backtracking recursive algorithm

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

## 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 on other sites
Quote:
 my first conundrum is will this strategy even work

Sure it will work, What work was it supposed to do again?

##### Share on other sites
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 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 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 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 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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
khawk
15
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013645
×