A* не может обойти препятствие (JS)

182
26 декабря 2018, 15:40

В текущей реализации функция находит правильный путь до препятствия, но когда она начинает обходить его 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]);
READ ALSO
JSON для TreeTable в PRIME NG

JSON для TreeTable в PRIME NG

Как лучше сгенерить такой JSON?

186
Проблемы при использовании SCORM-курсов

Проблемы при использовании SCORM-курсов

Пытаюсь разобраться с курсами SCORM

187
Проблема с кодировкой виджета

Проблема с кодировкой виджета

Подскажите, почему может быть такая проблема с кодировкой при наведении и черные точки?

142
MySQL сборка 2 запросов в таблицу

MySQL сборка 2 запросов в таблицу

Есть потребность в создание запроса который возвращал бы таблицу с полями

269