Thread: Shortest path between two points

Originally Posted by algorism

BFS is actually not that hard. The basic idea is to use a queue to hold the adjacent positions that you haven't visited yet. (Do you know how to make a queue?)

Initialize the queue with the start position and then enter a loop. If the queue becomes empty, no path was found. Otherwise, pop the front of the queue (initially the start position) and mark that position as visited. If that position is the goal position, success! Otherwise, push all that position's neighbors that haven't been visited yet onto the queue. Repeat the loop.

In order to find the shortest path once the goal position has been reached by the BFS, you need to save which position added each new position to the queue. One way to do that is to store symbols into the character array itself, which might end up looking something like this:

Code:

` 0 1 2 3 4 5 6 
0 @ @ @ @ @ @ @ 
1 @ v < < < v @ 
2 @ v @ @ @ v < 
3 S < < < < < @ 
4 @ ^ ^ @ ^ @ @ 
5 @ ^ ^ < ^ @ @ 
6 @ @ @ @ @ @ @

This obviates the "mark that position as visited" step since that would erase this information and also doesn't seem to be necessary. Alternatively if you didn't want to mess up the original maze array you could use a secondary copy.

Anyway, to find the shortest path, begin at the goal and follow the arrows to the start.

I'm..actually not too sure how I can go about doing that :/
I've already made a secondary copy of the maze via an arrCopy function. I think I understand the logic behind the BFS algorithm based on this website Maze Solver (shortest path finder) - CodeProject, but I have difficulty translating it into C. Especially on the part where we have to make this a sort of a loop and then somehow have the queue array correspond to the origin array in a lowest to highest order.

Do you mind guiding me along..? I know now that, if I have a 30-by-30 maze, I probably need an array that can hold the nodes for 900 cells, but since this node[900] is a 1d array, does that mean I should have a structure containing row and col, and insert that structure into each element to point to the corresponding cell for each node? Then, if my nodes[900] contains the position of the nodes, and I know that the node numbers from 1 to N corresponds to a position in the cell, my queue[900] and origin[900] would just need to hold the sequence of nodes (int) rather than the structure containing the position, am I right?

I removed the parts related to reading the input and the left-hand-rule for simplicity.

Code:

#include <stdio.h>
#define SIZE 10


typedef struct{
   int row, col;
} Pos;


void setNodes(Pos node[SIZE*SIZE]);


int main(void) {
   char map[SIZE][SIZE+1]={{""}};
   int n = SIZE, queue[SIZE*SIZE], origin[SIZE*SIZE], status[SIZE*SIZE];
   Pos node[SIZE*SIZE]={0};

   setNodes(node);

   return 0;
}


void setNodes(Pos node[SIZE*SIZE]){
   int row, col, cur=0;
   for(row = 0; row < SIZE; row++){
      for(col = 0; col < SIZE; col++){
          node[cur].row = row;
          node[cur].col = col;
         cur++;
      }
   }
   return;
}