Maze tree implementation for use in DFS, BFS

Question

My program accepts a char array as input file. The array is as follows:

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

I use DFS and BFS to solve this maze, starting with [1,1] and ending with [width - 1, height - 1].

I was thinking of creating a tree representing the maze, and then traversing the tree using each algorithm, respectively.

I will start from each line and scan empty cells, in each empty cell each cell that is on the right, left and bottom will be a child of this 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 a wall first } } 

Is it a viable tactic to implement a tree like this and then use it to cross the tree using DFS and BFS, or should I go this other way?

Answer 1

Good project, I love such things. By the way, you considered a directed attempt algorithm (the so-called A * algorithm), I think it will be better for you, especially when working on a 2D array. It has better performance in ordinary cases than other methods, and you do not need to use linked cells. There are also some improvements for this algorithm, including memory associated with the "try the direction first" method. Of course, there is no problem with your method, but consider the case when you have a really giant processing matrix.

Answer 2

Your idea is good and quite simple, but I think you misunderstood the tree with the graph.

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

In addition, not every maze can be represented as a tree.

Let's look at an example:

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

It is clear that there is a cycle in the labyrinth, therefore it cannot be represented as a tree. Your example also has several loops.