Constructing a tree from an array for a DFS solver

Question

I am making a maze solver using DFS and I want to implement the search tree for it but I am a bit new to artificial intelligence and I want a little bit of help on this matter.

Let me give a maze example first:

char maze[5][9] = 
    "#########",
    "#  #    #",
    "# ##  # #",
    "#     # #",
    "#########",

So my search tree for DFS should be something like this:

    "#########",
    "#12#15 10 11 #",
    "#3##14 9 #12 #",
    "#456 7 8 #13 #",
    "#########",

1st child of parent -> Right Cell if it is empty

2nd child of parent -> Bottom Cell if it is empty

3rd child of parent -> Left Cell if it is empty

4th child of parent -> Top Cell if it is empty

My solver will receive as an argument my maze array. My questions are these:

1st question: Is this actually the way the nodes are going to get visited by my actor?

2nd question: In the code do I need to declare 15 as child of 10? (also in other cases like 9 with 14)

3rd question: When my solver receives the array do I need to make a pre-process on the array and construct the tree from the array or will my actor construct it as he goes?

Answer 1

I also assume the rule of "do not include a node in the solution tree if it was already in the tree"? Because that sure helps.

Typically the tree is implicit, and you only construct the parts of the tree you actually visit, often tearing things down as you roll it back.

Your solver keeps track of the current steps along the tree. You probably also want to keep track of what cells you have explored in the maze. If the maze has only # and characters, use * to indicate you have visited the cell in this solver.

You start at some location. If that location is valid, you mark it with a * so you don't come back to it, and add that location (say, (1,1))to your "stack" of your path.

Now, you follow the rules you wrote above. Check the cell under your current location. Is it empty? (not a # or a *) If so, recurse, asking if that finds the way out.

If it finds the way out, take the path it found, prepend your current node, and return that path as the way out.

If it does not, search in the next adjacent cell (by the order above).

Finally, wrap the above recursive routine with a function that calls it, then removes the * marks from the map.

The tree you walk is implicitly coded. Building the tree forces you to visit every node, and you only want to build the parts that you have to.

This can be optimized in a number of ways. You can avoid writing to the map by working on a "ghost" copy of it. You can avoid prepending by passing the stack to the recursive versions, which carefully remove any extra nodes if they fail, and leave them on if they succeed. Or you can use a real stack, and encode the path backwards, with a wrapping function that (after all the work is done) reverses the path so it is in a more conventional order.