possibility0 possibility0 - 3 months ago 15
C++ Question

Breadth First Search with Path Tracing, some coordinates got "skipped"

I'm writing a Breadth First Search implementation on a grid with an added function to trace the path from the End Point back to the Start Point. The Breadth First Search algorithm worked as expected, though I have problems with tracing the path. It somehow "skipped" certain coordinates.

Consider this sample input:

3 3 //Grid Dimension (Row Column)
S|E //'S' = Start Point, 'E' = End Point
... //'.' = Empty Space, '|' = Wall
...


I expect the output would be:

Shortest Distance to the End Point: 4
Shortest Path Route:
X|X
XXX
...


But instead my program gives me:

Shortest Distance to the End Point: 4
Shortest Path Route:
S|X
XX.
...


I made sure the position and origin is correct. First, inside the BFS algorithm I printed out the origin of each point. Second, on the path tracing algorithm I printed out what is the current coordinate and what is the origin of that point. Here's what I printed out:

//First debug: Inside BFS
The origin for (1, 0) is (0, 0)
The origin for (1, 1) is (1, 0)
The origin for (2, 0) is (1, 0)
The origin for (1, 2) is (1, 1)
The origin for (2, 1) is (1, 1)
The origin for (0, 2) is (1, 2)
The origin for (2, 2) is (1, 2)

//Second Debug: Inside Path Trace
From (0, 2) going to the origin, which is (1, 2)
From (1, 1) going to the origin, which is (1, 0)
From (1, 0) going to the origin, which is (0, 0)


The thing is,
(1, 2)
got skipped on the path tracing. However, it recognized the origin of
(1, 2)
as the next point, which is
(1, 1)
.

I don't see anything wrong in my code (at least in the BFS it works correctly), so here's the path trace function that I code:

//On every point, I initially set the origin to be (-1, -1)
//Through the BFS, each point set its own origin
//If it is certain that there's a path from the Start Point to the End Point,
//Then from the End Point, I can traverse the origin until I reach (-1, -1)

coordinate currentPoint = endPoint;
while ((currentPoint.row != -1) && (currentPoint.col != -1)) {
map[currentPoint.row][currentPoint.col] = 'X';
currentPoint.row = mapData[currentPoint.row][currentPoint.col].origin.row;
currentPoint.col = mapData[currentPoint.row][currentPoint.col].origin.col;
}


Any insights on this one? Thanks

Answer

In these lines:

    currentPoint.row = mapData[currentPoint.row][currentPoint.col].origin.row;
    currentPoint.col = mapData[currentPoint.row][currentPoint.col].origin.col;

You are changing the value of currentPoint.row in the first line, then using it in the second line. This means that you are getting the col of (1,2) instead of (0,2)

Something like:

    int newRow = mapData[currentPoint.row][currentPoint.col].origin.row;
    int newCol = mapData[currentPoint.row][currentPoint.col].origin.col;
    mapData[currentPoint.row][currentPoint.col].origin.row = newRow;
    mapData[currentPoint.row][currentPoint.col].origin.col = newCol

will fix it.