Implementing a tree for a maze to use in DFS, BFS

Question

My program is taking a char array as input from a file. The array looks like this:

"#########",
"# #     #",
"# ##  # #",
"#     # #",
"### # ###",
"#   # # #",
"# # #####",
"#   #   #",
"#########",

I am implementing DFS and BFS to solve this maze with starting from [1,1] and ending in [width - 1,height - 1].

I thought of making a tree representing the maze and then traversing the tree using each algorithm respectively.

I will start at each row and scan for empty cells, at each empty cell every cell that is to its right, left and bottom are going to be children of that cell. It looks something like this:

    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            if (isEmpty(maze[i][j]))
                    {
                         putChildren(maze[i-1][j], maze[i][j+1], maze[i+1][j]);
                         //this will check if it's a wall first
                    }       
    }

Is it a viable tactic to implement the tree like this and then use it to traverse the tree with DFS and BFS or I should I go at this another way?

Answer 1

Nice project, i love things like that. By the way Did you considered directional try algorithm (so called A* algorithm) I think that it will be better for you, especially while working on 2D array. It have better performance in usual cases than other methods, and you don't need to use linked cells. There are also some kind of improvements for this algorithm including memory linked with "try direction first" method. Of course there is no problem with your's method, but consider case when you have really gigantic matrix to process.

Answer 2

Your idea is good and pretty straightforward, but I think you misunderstood tree with a graph.

First of all, there is no need to create a tree from a maze graph - you can run BFS, DFS, A* , ... on a general graph.

Moreover, not every maze could be presented as a tree.

Let's look at the example:

"#####",
"#   #",
"# # #",
"#   #",
"#####",

Clearly there is a cycle in the maze, so it cannot be presented as a tree. Your example also has a few cycles.