0

I'm trying to get BFS working to find an optimal path on a grid system.

Currently, it works until the end node is found. But no path is sent out because I'm not sure how to do this. BFS How would I record the best node to take for the path?

Function for BFS algorithm (executed on button press):

public void BFS()
    {
        rq.Enqueue(start.X);
        cq.Enqueue(start.Y);
        gridmatrix[start.X, start.Y].VISITED = true;
        while (rq.Count() > 0)
        {
            int r = rq.Dequeue();
            int c = cq.Dequeue();
            if (r == end.X && c == end.Y)
            {
                endfound = true;
                break;
            }
            explore_neighbours(r,c);

            
            nodesleftinlayer--;
            if(nodesleftinlayer == 0)
            {
                nodesleftinlayer = nodesinnextlayer;
                nodesinnextlayer = 0;
                BFSMoveCount++;

            }
            if(endfound == true)
            {
                Console.WriteLine(BFSMoveCount);
               
            }
            else
            {
                Console.WriteLine(-1);
            }
            

           
        }
    }

Function for finding all adjacent nodes of the current one:

void explore_neighbours(int r, int c)
    {
 

        for (int i = 0; i < 4; i++) {
            int rr = r + dr[i]; //direction array
            int cc = c + dc[i];
            
            if(rr < 0 || cc < 0)
            {
                continue;
            }
            if(rr >= gridmatrix.GetLength(0) || cc >= gridmatrix.GetLength(1))
            {
                continue;
            }

            if(gridmatrix[rr,cc].VISITED == true)
            {
                continue;
            }
            if(gridmatrix[rr,cc].COLOUR == 1)
            {
                continue;
            }
            rq.Enqueue(rr);
            cq.Enqueue(cc);
            gridmatrix[rr, cc].VISITED = true;
            if(gridmatrix[rr, cc] == gridmatrix[end.X, end.Y])
            {
                endfound = true;
            }
            if(gridmatrix[rr,cc].COLOUR != 4 && gridmatrix[rr,cc].COLOUR != 1) //If grid tile has been checked
            {
                gridmatrix[rr, cc].COLOUR = 6; //set colour on the grid to pink
            }


            

            nodesinnextlayer++;

        }
    }
Loathing
  • 5,109
  • 3
  • 24
  • 35
Seitzy
  • 23
  • 1
  • 4

1 Answers1

0

There 2 common ways to get the path out:

  1. You remember the distance of every visited cell from the start, and then when you find the end you walk back to the start, along the path that decreases distance with every step. This method is memory-efficient when you can use a bit-packed representation for visited vertexes, since you only need to remember the lowest 2 bits of the distance.

  2. You directly remember the predecessor of every visited cell, and when you find the end you just follow all those links back to the start.

You should probably use method (1). Either of these methods would work fine for you. Instead of storing VISITED=true for every point you find, store either the distance from the start, or the coordinates of the preceding grid point.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • How would you suggest finding the preceding grid cell? – Seitzy Nov 26 '20 at 08:17
  • at the point where you set VISITED for the next cell (rr,cc), the preceding cell is (r,c) – Matt Timmermans Nov 26 '20 at 12:57
  • Hello Matt. Would you mind sharing your input on [this](https://stackoverflow.com/questions/65164220/do-not-understand-the-solution-for-the-binary-tree-maximum-path-sum-problem/65227353#65227353) question? – a_sid Dec 10 '20 at 03:13