Hi there everyone,
I’ve just done the Find Your Hat project (which I very much enjoyed) and am now trying to create a path solver to check if the randomly generated grid is solveable. Did a bit of research and decided to try to do a breadth-first search.
I got it to work beautifully if the path could be solved, but if it couldn’t, it would go into a crazy loop and make my computer sound like it was about to explode. I realised this was because it wasn’t correctly logging locations as having been ‘visited’. So, I’m trying to fix this and now running into a problem I just don’t understand. HALP
For some reason that I really can’t understand, when my function to find the neighbors of the space I’m investigating checks that the neighbors are a) within the grid and b) aren’t obstacles (‘x’ in the code I’m trying), it works 4 times perfectly (as I intended) and then for some reason continues and changes the input. I don’t understand why it does this, as there isn’t anything in the code to assign values to anything other than the array that isn’t being checked. I have got as far as my skill takes me with this one; I’ve tried logging everything to the console and checking it and just go “Yep, I know exactly where the problem is but I have no idea why it’s doing that”.
Here’s the code:
const area = [
['s', 'x', 'o'],
['o', 'o', 'e'],
['x', 'x', 'o']
];
area.forEach(row => console.log(row.join(" ")));
let start = [];
let end = [];
for (let i = 0; i < area.length; i++){
if (area[i].includes('s')){
start = [i, area[i].indexOf('s')];
};
if (area[i].includes('e')){
end = [i, area[i].indexOf('e')];
};
}
console.log("The start coordinates are " + start);
console.log("The end coordinates are " + end);
// BREADTH-FIRST SEARCH FUNCTION; TAKE A GRID, A START AND AN END POINT (AS A COORDINATE ARRAY [Y, X]) AS ARGUMENTS
function breadthSearch(grid, start, end){
// DETERMINE SIZE OF GRID
let width = grid.length;
let height = grid[0].length;
// SET NODE (LOCATION) TO BE THE START NODE TEMPORARILY
let location = [start[0], start[1]];
// CREATE QUEUE FOR UNVISITED NODES
let queue = [];
let visited = [];
let neighbors = [];
// ASSIGN LOCATION (AT FIRST, START NODE) TO THE QUEUE
queue.push(location);
// FIND VIABLE NEIGHBORS (NOT OUT OF AREA OR 'X')
function safeArea(c, r){
console.log("c: " + c);
console.log("r: " + r);
if (c < 0 || c > grid.length ){
console.log("failed test 1");
return false;
};
if ( r < 0 || r > grid[0].length ){
console.log("failed test 2");
return false;
};
if ( grid[c][r] === 'x' ){
console.log("failed test 3");
return false;
};
return true;
};
function findNeighbors(node){
console.log("1");
if (safeArea(node[0]-1, node[1])){
neighbors.push([node[0]-1, node[1]]);
};
console.log("2");
if (safeArea(node[0], node[1]-1)){
neighbors.push([node[0], node[1]-1]);
};
console.log("3");
if (safeArea(node[0]+1, node[1])){
neighbors.push([node[0]+1, node[1]]);
};
console.log("4");
if (safeArea(node[0], node[1]+1)){
neighbors.push([node[0], node[1]+1]);
};
};
while (queue.length){
// TAKE NODE FROM QUEUE; MARK IT AS 'VISITED' AND CHECK IF IT'S THE END POINT (IF SO, RETURN 'TRUE')
let currentLocation = queue.shift();
visited.push(currentLocation);
if (currentLocation[0] === end[0] && currentLocation[1] === end[1]){
return currentLocation;
};
findNeighbors(currentLocation);
for (neighbor in neighbors){
if (!visited.includes(neighbor)){
queue.push(neighbor);
};
};
// IF VIABLE NEIGHBORS ARE NOT VISITED, ADD THEM TO THE QUEUE AND REPEAT FOR EACH
};
// IF THE QUEUE IS EMPTY AND THE END HAS NOT BEEN REACHED, RETURN 'FALSE'
return false;
};
console.log(breadthSearch(area, start, end));
And here’s the output I get from that:
s x o
o o e
x x o
The start coordinates are 0,0
The end coordinates are 1,2
1
c: -1
r: 0
failed test 1
2
c: 0
r: -1
failed test 2
3
c: 1
r: 0
4
c: 0
r: 1
failed test 3
1
c: -1
r: undefined
failed test 1
2
c: 0
r: NaN
3
c: 01
r: undefined
/Users/jon/Documents/coding/training/bfs-test/main.js:58
if ( grid[c][r] === ‘x’ ){
^
TypeError: Cannot read property ‘undefined’ of undefined
at safeArea (/Users/jon/Documents/coding/training/bfs-test/main.js:58:21)
at findNeighbors (/Users/jon/Documents/coding/training/bfs-test/main.js:75:13)
at breadthSearch (/Users/jon/Documents/coding/training/bfs-test/main.js:99:9)
at Object. (/Users/jon/Documents/coding/training/bfs-test/main.js:117:13)
at Module._compile (internal/modules/cjs/loader.js:1063:30)
at Object.Module._extensions…js (internal/modules/cjs/loader.js:1092:10)
at Module.load (internal/modules/cjs/loader.js:928:32)
at Function.Module._load (internal/modules/cjs/loader.js:769:14)
at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main.js:72:12)
at internal/main/run_main_module.js:17:47