maze solver in C++ [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I have made a maze generator using Depth First Search which returns an array of pounds and spaces to indicate a maze. Example:

char maze[height][width] =
{
    "#########",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "#########",
};

The agent will always start at the top left corner (maze[1][1]) and exit at the bottom right corner (maze[7][7]).

I am trying to make the solver now using Depth First Search.

The problem is I am quite a beginner to intermediate programmer so I am having a hard time understanding how to implement the Depth First Search in C++ and I'm having an even harder time implementing it for the maze.

I have a basic knowledge of stacks, queues etc. I also know how DFS works in a tree (pretty much in theory) but my main problem is how I would go to implement this in a maze which is stored in a 2D array.

I want to learn specifically DFS so I can get started and then I'll implement other search tactics (like BFS for example) to start getting a hand on AI.

EDIT: I don't want ready code!!! I want you to help me understand how to transfer pseudocode to C++ for a maze!

Answer 1

So the basic operation of a depth first search is:

This works the same for any arbitrary graph as for a tree. A tree is just a special case. You can even visualize your maze as a tree:

#########
#123#   #
#4### # #
#5#   # #
# # # ###
#   # # #
# ### # #
#   #   #
#########

The only difference between using this algorithm on a tree vs. an arbitrary graph is that it's implicitly known which nodes in a tree have been visited, due to the hierarchical structure of a tree. With an arbitrary graph you might have a structure like:

#####
#187#
#2#6#
#345#
#####

And when examining node eight you don't want to treat node one as a new place to visit.

With your maze one way to remember which nodes have been visited would be to fill them in with '#' as soon as you encounter them.

---

I have pretty much figured out how to represent the position of the agent, how to move him around and such but my problem mostly is in how to use the stack for keeping track of which places the agent has been. By what I've found in google some keep a stack of the visited places but I never really understood when to remove positions from the stack, that's my biggest confusion

The stack itself is not used to keep track of which places are visited. It only keeps track of the current 'path' taken through the maze. When you reach a dead end nodes get removed from the stack; Those nodes must remain marked as visited even though they are removed from the stack. If removing those nodes also causes those nodes to be 'unvisited' then your search may continually try and retry dead ends.

---

I recommend that you first draw out a few little mazes and walk through them by hand using the flow chart above. This will give you a better understanding of the algorithm. Here are some example mazes:

Start at O, finish at X

####    #####      #####     #####
#OX#    #O X#      #O#X#     #O  #
####    #####      #####     # #X#
                             #####

Then consider each box in the flow chart and think about what data it uses, how to represent that data, and how to implement the box's action in code using that data.