Maze Solving using DFS

Question

In a school project, we got to solve a maze given through program parameter. To achieve this, we need to use Depth First Search algorithm.

I have been able to find the pseudo code of a DFS algorithm, and even recode it using C. The algorithm is able to find the exit, however now I'm looking for a way to get the path from the beginning to the end of the maze.

The beginning of each maze is the upper left corner, and the end is the bottom right corner.

Initial Maze (X = Walls ; * = Free Space):

*****XX****X********XXXX
XX******XX***XXXXX***XXX
XX***XXXX**XXXXX****XXXX
XX***XXXXXXXXXXXXXX****X
*****XXXXXX****XX***XXXX
XX*************XXXX*****

Solved Maze (o = Path from begining to end):

oooooXXooooXooooooooXXXX
XX**ooooXXoooXXXXX*o*XXX
XX***XXXX**XXXXX***oXXXX
XX***XXXXXXXXXXXXXXo***X
*****XXXXXX****XX**oXXXX
XX*************XXXXooooo

Here is the code I have been able to produce so far:

#include "../include/depth.h"

static t_bool   stack_push(t_list **stack, int x, int y)
{
  t_cell    *cell;

  if (!(cell = malloc(sizeof(t_cell))))
    return (FALSE);
  cell->coord.x = x;
  cell->coord.y = y;
  if (!my_list_push(stack, cell))
    {
      free(cell);
      return (FALSE);
    }
  return (TRUE);
}

static t_bool   is_colored(const t_list *colored, int x, int y)
{
  while (colored != NULL)
    {
      if (((t_cell *) colored->elm)->coord.x == x &&
      ((t_cell *) colored->elm)->coord.y == y)
    return (TRUE);
      colored = colored->next;
    }
  return (FALSE);
}

static t_bool   push_edges(t_map *map, t_stack *stack, int x, int y)
{
  if (x - 1 >= 0 && !is_colored(stack->colored, x - 1, y))
    stack_push(&stack->stack, x - 1, y);
  if (x + 1 < map->sz.x && !is_colored(stack->colored, x + 1, y))
    stack_push(&stack->stack, x + 1, y);
  if (y - 1 >= 0 && !is_colored(stack->colored, x, y - 1))
    stack_push(&stack->stack, x, y - 1);
  if (y + 1 < map->sz.y && !is_colored(stack->colored, x, y +1))
    stack_push(&stack->stack, x, y + 1);
  return (TRUE);
}

static t_bool   exit_properly(t_stack *stack, void *curr)
{
  my_list_destroy(&stack->stack, LIST_FREE_PTR, NULL);
  my_list_destroy(&stack->colored, LIST_FREE_PTR, NULL);
  free(curr);
  return (TRUE);
}

t_bool      depth(t_map *map)
{
  t_stack   stack;
  t_cell    *curr;

  stack.colored = stack.stack = NULL;
  stack_push(&stack.stack, MAP_START_X, MAP_START_Y);
  while (stack.stack != NULL)
    {
      curr = stack.stack->elm;
      my_list_pop(&stack.stack, &stack.stack);
      if (curr->coord.x == map->sz.x - 1 &&
      curr->coord.y == map->sz.y - 1)
    return (exit_properly(&stack, curr));
      if (!is_colored(stack.colored, curr->coord.x, curr->coord.y))
    {
      stack_push(&stack.colored, curr->coord.x, curr->coord.y);
      push_edges(map, &stack, curr->coord.x, curr->coord.y);
    }
      free(curr);
    }
  return (TRUE);
}

The initial algorithm:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do 
9                  S.push(w)

Thanks.

Note: t_list types holds a generic linked list.

When you reach the target, all the nodes you visited along the way should be on the stack. Just pull them off one by one and then return the list in reverse order. — r3mainer
Unfortunately not, as as given in the pseudo code line 5, the element is pop'd from the stack. The only element left in the list is the last one containing the end of the maze. — Ra'Jiska

Ashish kulkarni Ashish kulkarni · Accepted Answer · 2017-05-13T09:41:06

Assuming that your input data is in the form of a matrix:

Create a structure with the following definition

struct parent {
    int x, y;
};

Create a two-dimensional matrix with the above struct as its data type and of the same dimesions as of the input matrix.

struct parent ** parent_info = (struct parent **)malloc(ROW_SIZE * sizeof(struct parent* ));
int i = 0;
for (i = 0; i < ROW_SIZE; i++) {
    parent_info[i] = (struct parent *)malloc(COLUMN_SIZE * sizeof(struct parent));
}

where ROW)_SIZE and COLUMN_SIZE are the number of rows and columns respectively in your input matrix.

Now each time you push a new graph node (matrix cell) in your stack (pseudo code line 9), set the parent details in the parent_info matrix (e.g. in pseudo code, set 'v' as the parent of 'w').

For example, you move from (0,0) to (0,1) then set

parent_info[0][1].x = 0;
parent_info[0][1].y = 0;

Finally, to retrieve the path, recursively follow the co-ordinates in the parent_info matrix, starting from the parent co-ordinates of the end point of the maze.

Maze Solving using DFS

1 Answers