In the current implementation, the function finds the right path to the obstacle, but when it starts to bypass it, the next step in the right direction becomes larger than the previous nodes viewed f. Then the wrong nodes start to be selected from the open list. I can not understand how to fix it.
var mapSize = { x: 10, y: 10, }; var graph = []; function graphToString(graph) { var stringGraph = []; for (var x = 0; x < mapSize.x; x++) { var row = []; for(var y = 0; y < mapSize.y; y++) { var node = 'x:' + graph[x][y].x + '_y:' + graph[x][y].y + '_f:' + graph[x][y].f + '_g:' + graph[x][y].g; if (graph[x][y].parrent) { node += '_p:' + graph[x][y].parrent.x + '_' + graph[x][y].parrent.y; } node += '_weight:' + graph[x][y].weight; row.push(node) } stringGraph.push(row); } return stringGraph; } function compareNode(a, b) { if (ax == bx && ay == by) return true; return false; } function neighbors(graph, node) { var dirs = [[0,1], [1, 0], [-1, 0], [0, -1]]; var res = []; dirs.map(function(item, i) { var x = node.x + item[0]; var y = node.y + item[1]; if (graph[x] && graph[x][y] ) res.push(graph[x][y]); }) return res; } for (var x = 0; x < mapSize.x; x++) { var row = []; for(var y = 0; y < mapSize.y; y++) { var node = { x: x, y: y, f: 0, g: 0, weight: 0, parrent: null, }; row.push(node); } graph.push(row); } function minF(list) { var min = Infinity; var minIndex = -1; if (list.length == 1) return list[0]; list.map(function(item, i) { if (item.f <= min) { min = item.f; minIndex = i; } }); return list[minIndex]; } function remove(list, node) { var deleteIndex = -1; list.map(function(item, i) { if (item.x == node.x && item.y == node.y) deleteIndex = i; }); list.splice(deleteIndex, 1); } function inList(list, node) { var res = false; list.map(function(item) { if (item.x == node.x && item.y == node.y) res = true; }); return res; } function heuristic(a, b) { return Math.abs(ax - bx) + Math.abs(ay - by); } function moveNodeCost(a, b) { if (b.weight === 1) return Infinity; else return 1; } function astar(map, start, end) { var open = [] var closed = []; var from = []; open.push(start); while(open.length) { var cur = minF(open); console.log('min f', cur); if (compareNode(cur, end)){ break; } remove(open, cur); closed.push(cur); var neighborsList = neighbors(map, cur); for( var i = 0; i < neighborsList.length; i++) { var neighbor = neighborsList[i]; if (inList(closed, neighbor)) continue; var tempG = cur.g + moveNodeCost(cur, neighbor); //???????? if (!inList(open, neighbor)) open.push(neighbor); else if (tempG >= neighbor.g) continue; from.push(cur); neighbor.g = tempG; neighbor.f = neighbor.g + heuristic(neighbor, end); } } } graph[5][3].weight = 1; graph[5][4].weight = 1; graph[5][5].weight = 1; astar(graph, graph[2][4], graph[7][4]); 
