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(class Tile pBoard[pBoard.GetRows][pBoard.GetColumns].itsCheck,[])
{
//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

1
Contributor
2
Replies
3
Views
8 Years
Discussion Span
Last Post by zoner7

bool GenBoard(w,[])

accidentally messed up the function arguments. here is a modified version

I guess I'll post what I've done so far. The last bit is psuedocode. I just need someone to tell me if I'm on the right track or not.

``````bool GenBoard(class Tile *pBoard[pBoard.GetRows()][pBoard.GetColumns()])
{
// 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;
}