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