Search code examples
c++calgorithmdepth-first-searchmaze

Maze Backtracking Algorithm in C++ DFS?

I am new to C++ and I am currently on a project to create a maze that generates out using the DFS algorithm.

I've already successfully managed to generate out a single path, which is for example

0 , 0 , 0 , 0,  0
0 , 1 , 1 , S,  0
0 , 1 , 0 , 0,  0
0 , 1 , 0 , 0,  0
0 , D , 0 , 0,  0
0 , 0 , 0 , 0,  0

As above,

Source is the initial cell, and 1 is the path that I created based on random neighbor, the thing is, D is "dead end". So, if possible I will like to backtrack to S and start from the other direction. How am I supposed to do that with queue and stack? Can anyone shed some light on this? Thank you so much?

Solution

  • It's better if we used basic AI knowledge. Define a set of valid operations for this specific problem, an initial state, a final state and let your program use a search tree of states with the defined operations to find the solution.