I am having difficulties to rewrite the path from the start to the end point after finding a BFS solution.
I have found other questions similars to mine, but still couldnt understand what to do. I am saving the visited notes on nodeTable, but it only returns all visited nodes, not the optimal path.
The idea is to find the shortest path on a binary matrix, where the only paths possible are through cells marked with 1.
https://github.com/gabrielgcosta83/Commander
const C = Map.width;
const R = Map.height;
const startPoint = [308,863];
const endPoint = [473,894];
const rowQ = [];
const colQ = [];
let reachedEnd = false;
let nodeTable = [];
let dr = [1,-1,0,0,1,-1,1,-1];
let dc = [0,0,-1,1,1,-1,-1,1];
function solve() {
rowQ.push(startPoint[0]);
colQ.push(startPoint[1]);
visitedMap[startPoint[0],startPoint[1]] = true;
while ( rowQ.length > 0 ) {
const r = rowQ[0];
const c = colQ[0];
rowQ.splice(0,1);
colQ.splice(0,1);
if (endPoint[0] == r && endPoint[1] == c) {
reachedEnd = true;
break;
}
explore_neighbors(r,c);
}
if (reachedEnd) {
console.log("Solucao encontrada: ", endPoint);
return;
} else {
console.log("Solucao nao encontrada");
return;
}
}
function explore_neighbors(r,c) {
for (let i = 0; i < 8 ; i++) {
let rr = r + dr[i];
let cc = c + dc[i];
if (rr < 0 || cc < 0) { continue }
if (rr > R || cc > C) { continue }
if (visitedMap[rr][cc] == true ) { continue }
if (roadMap[rr][cc] == 0) { continue }
addPointToTable([rr,cc],"yellow");
rowQ.push(rr);
colQ.push(cc);
visitedMap[rr][cc] = true;
nodeTable.push([rr,cc]);
}
}