0

I have created a pathfinding algorithm in C that uses a map.txt file with a maze written in 0s for walls and 1s for paths. Currently the path finding algorithm I'm using is a DFS with a stack to keep track of nodes but I'm trying to change it to a queue to utilize BFS so that I will be certain that the shortest path is always found. But when I try to print out the new path in BFS it seems like the rest of the path gets deleted somewhere but I can't find where. Here is the path-finding algorithm in question:

    struct node *BFS(struct graph* graph, int vertex, int endVertex, struct node* path_stack) {

  struct node* temp = graph->adjlist[vertex]; //This is the first neighbor to the vertex node
  struct node* temp2 = graph->adjlist[endVertex];// We use this temp to check if there exist a path at all (if the end node exist and has neighbours)

  graph->visited[vertex] = 1; // sets the self as visited
  static int done = 0;
  
  if(temp2 == NULL || temp == NULL)
    {
        printf("No Path can be found");
        return path_stack;
    }

  // if we havent arrived yet
    while (temp != NULL) { // checks if the current neighbor exists
      if(done == 1)
      {
        break;
        return path_stack;
      }

      if(temp->vertex == endVertex) // Check for when we have gotten to the goal
      {
        printStack(path_stack);
        done = 1;
        break;
      }
      path_stack = push(temp, path_stack); // we push the first neighbor to the stack
      if (graph->visited[temp->vertex] == 0) { //if the neighbor is not visited we run the algorithm again and now with the neighbors value as the vertex
        BFS(graph, temp->vertex, endVertex,path_stack);
      }
      else
      {
        if(graph->visited[temp->vertex] == 1)
        {
          path_stack = pop(path_stack);
        }
        temp = temp->next; // we go the next neighbor to the current node
      }
    }
  
  return path_stack;
}

Here is my push code that has been changed to push last like a queue:

    struct node* push(struct node* Node, struct node* head)// Push has now been altered to push like a queue, so we can use bfs instead of dfs
{
  struct node* temp = CreateNode(Node->vertex,Node->Y,Node->X); // We use a queue to keep track of visited nodes
  
  temp->next = NULL;
  if(head == NULL)
    head = temp;
  else
    {
    head->next = temp;
    head = temp;
    }
  return head;
}

and here is my function that prints the path but now it only prints the last node in the path and all the others are gone.

    void printStack(struct node* head)//Function that prints all the nodes in the stack
{
  struct node* tmp = head;
  //struct node* tmp2 = NULL;
  printf("(The Start)->");
  while(tmp != NULL)
  {
    //tmp2 = push_path(tmp, tmp2);
    printf("(%d,%d)->", tmp->X, tmp->Y);
    tmp = tmp->next;
  }

 /* while(tmp2 != NULL)
  {
    printf("(%d,%d)->", tmp2->X, tmp2->Y);
    
    tmp2 = tmp2->next;
  }
  */
  
  printf("(The End)\n");
}

The code for printing the path has also been changed a little because when using DFS the path would be printed reversed so the code that has been commented out was for when I needed to reverse it back but now it's not necessary to use it. Any help with why the path can't be printed is very much appreciated, I'm still quite new to C programming and path finding algorithms.

SimpaN
  • 1
  • Start with the smallest maze possible that causes the problem, then use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through your code statement by statement while monitoring variables and their values. This way it will be simpler to see when and where things start to go wrong. Also, break out the queue functions into their own test-program, so it's easier to debug that separately. – Some programmer dude May 15 '22 at 14:39

0 Answers0