search - 寻找二维数组中两点之间的最短路径

Question

我有一个简单的游戏，我试图获得两点之间的最短路线



map 由二维数组 matrix: Node[][] 组成,

class Node{
   index: {
     x: number,
     y: number
   },
   isAvailable: boolean
}

该算法应返回关于节点可用性的最短路径。

例如树被标记为不可用 node.isAvailable = false
我坚持为这个矩阵实现算法

我尝试使用 迪杰斯特拉斯 算法来自 here ，但我不知道如何应用它，我做到了

const graph = new Dijkstra();

//convert the matrix (2d array) to graph
matrix.map((row) => {
  row.map((node: Node) => {
    let x = node.index.x;
    let y = node.index.y;
    graph.addVertex(x + ":" + y, {x: x, y: y});

  });
});

console.log(graph.shortestPath('0:0', '5:5'));
//the output was ['0:0'] (definitly not the answer)

如何在这个矩阵上应用算法？

P.S 这是我的全部 code

Answer 1

我使用了一种最好描述为将油漆泼洒在目标上的方法:

你用 0 标记目标方块，然后遍历邻居并将它们标记为 1，代表到目标的距离，然后遍历邻居的邻居，等等。重复这个过程，直到油漆到达你的巨魔。巨魔要做的就是开始移动到潜力最低的方格。

一旦你有多个角色需要在每个人都在移动时互相绕行，它就会变得更有趣。