В текущей реализации функция находит правильный путь до препятствия, но когда она начинает обходить его f следующего шага в правильном направлении становиться больше чем f предыдущих просмотренных нод. Тогда из открытого списка начинают выбираться неправильные ноды. Не могу понять как это исправить.
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 (a.x == b.x && a.y == b.y) 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(a.x - b.x) + Math.abs(a.y - b.y);
}
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]);
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Подскажите, почему может быть такая проблема с кодировкой при наведении и черные точки?
Есть потребность в создание запроса который возвращал бы таблицу с полями