寻找二维数组中两点之间的最短路径 [英] Finding the shortest path between two points in 2D Array

问题描述

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

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

class 节点{指数: {x:数字，y:数字},isAvailable: 布尔值}

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

例如树被标记为不可用 node.isAvailable = false

我一直在为这个矩阵实现算法

我尝试使用

export class PathFinder {网格:瓷砖[][];网格高度:数字；网格宽度:数量；startTile:瓷砖；endTile:瓷砖；/** 已经检查过的瓦片数组.*/关闭列表:列表<平铺>= new List();openList: List= new List();构造函数(网格:Tile[][]，gridHeight:数字，gridWidth:数字){this.grid = 网格；this.gridHeight = gridHeight;this.gridWidth = gridWidth;}searchPath(start: Tile, end: Tile): Tile[] {this.startTile = 开始；this.endTile = 结束；/** 路径验证 */如果 (!start.walkable) {console.log('不能行走的起始瓦片，选择不同的瓦片', start.index);返回 [];}如果(！end.walkable){console.log('不可行走的结束瓷砖，选择不同的瓷砖', end.index);返回 [];}/** 启动 A* 算法 *//** 将起始图块添加到 openList */this.openList.push(start);让 currentTile;/** 当 openList 不为空时 */而(this.openList.length){//当前节点=成本最低的开放列表节点.currentTile = this.getTileWithLowestTotal(this.openList);//如果currentTile是endTile，那么我们可以停止搜索if(JSON.stringify(currentTile.index) === JSON.stringify(end.index)){this.startTile.setBackgroundColor("rgba(255, 45, 45, .8)");this.endTile.setBackgroundColor("rgba(255, 45, 45, .8)");返回 this.shortestPath();}别的 {//将当前图块移动到关闭列表并将其从打开列表中删除.this.openList.remove(currentTile);this.closedList.push(currentTile);////获取所有相邻的瓷砖让相邻瓷砖 = this.getAdjacentTiles(currentTile);对于(让相邻瓷砖的相邻瓷砖){//获取不在打开列表中的tile如果(！this.openList.contains(adjacentTile)){//获取不在关闭列表中的tile如果(！this.closedList.contains(adjacentTile)){//将其移动到打开列表并计算成本this.openList.push(adjacentTile);//计算成本nextTile.cost = currentTile.cost + 1;//计算曼哈顿距离相邻Tile.heuristic = this.manhattanDistance(adjacentTile);//计算总金额相邻瓷砖.total = 相邻瓷砖.成本 + 相邻瓷砖.启发式；currentTile.setBackgroundColor('rgba(0, 181, 93, 0.8)');}}}}}}getTileWithLowestTotal(openList: Tile[]): Tile {让 tileWithLowestTotal = new Tile();让最低总:数字 = 999999999；/** 搜索打开的瓷砖，得到总成本最低的瓷砖 */for (let openTile of openList) {如果(openTile.total <= minimumTotal){//克隆最低总minimumTotal = openTile.total;tileWithLowestTotal = openTile;}}返回 tileWithLowestTotal;}getAdjacentTiles(current: Tile): Tile[] {让相邻瓷砖:瓷砖[] = [];让相邻瓷砖:瓷砖;//向左平铺如果 (current.index.x - 1 >= 0) {相邻瓷砖 = this.grid[current.index.x - 1][current.index.y];if (adjacentTile &&相邻Tile.walkable) {相邻瓷砖推(相邻瓷砖)；}}//向右平铺if (current.index.x + 1 < this.gridWidth) {相邻瓷砖 = this.grid[current.index.x + 1][current.index.y];如果(相邻瓷砖&&&&相邻瓷砖.walkable){相邻瓷砖推(相邻瓷砖)；}}//平铺到下方if (current.index.y + 1 < this.gridHeight) {相邻瓷砖 = this.grid[current.index.x][current.index.y + 1];if (adjacentTile &&相邻Tile.walkable) {相邻瓷砖推(相邻瓷砖)；}}//平铺到上方如果 (current.index.y - 1 >= 0) {相邻瓷砖 = this.grid[current.index.x][current.index.y - 1];如果(相邻瓷砖&&&&相邻瓷砖.walkable){相邻瓷砖推(相邻瓷砖)；}}/** 待办事项:对角线移动 */返回相邻的瓷砖；}/** 计算曼哈顿距离 */manhattanDistance(adjacentTile: Tile): number {返回 Math.abs((this.endTile.index.x - nextTile.index.x) +(this.endTile.index.y - nextTile.index.y));}最短路径() {让 startFound:boolean = false;让 currentTile = this.endTile;让 pathTiles = [];//包括路径中的结束瓦片pathTiles.push(this.endTile);this.endTile.ball = true;而 (!startFound) {让相邻瓷砖 = this.getAdjacentTiles(currentTile);//检查当前最新的瓷砖.对于(让相邻瓷砖的相邻瓷砖){//检查它是否是起始图块if (JSON.stringify(adjacentTile.index) === JSON.stringify(this.startTile.index)){返回路径瓦片；}//它必须在closedList或openList内if (this.closedList.contains(adjacentTile) || this.openList.contains(adjacentTile)) {if (adjacentTile.cost <= currentTile.cost &&nextTile.cost > 0) {//改变当前的瓷砖.当前瓦片 = 相邻瓦片；//将此相邻的Tile添加到路径列表中pathTiles.push(adjacentTile);//用黄色球突出显示方式相邻瓷砖球 = 真；休息;}}}}}}

I have a simple game, I'm trying to get the shortest route between 2 points

The map consists of 2d array matrix: Node[][],

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

The algorithm should return the shortest path with respect to node availability.

e.g. Trees are marked as unavailable node.isAvailable = false

I'm stuck on implementing the algorithm for this matrix

I tried to use Dijkstras algorithm from here, but I couldn't figure out how to apply it, I did

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)

How can I apply the algorithm on this matrix?

P.S here is my full code

解决方案

I had to implement the A* algorithm

export class PathFinder {

  grid: Tile[][];
  gridHeight: number;
  gridWidth: number;
  startTile: Tile;
  endTile: Tile;

  /** Array of the already checked tiles. */
  closedList: List<Tile> = new List<Tile>();
  openList: List<Tile> = new List<Tile>();

  constructor(grid: Tile[][], gridHeight: number, gridWidth: number) {

    this.grid = grid;
    this.gridHeight = gridHeight;
    this.gridWidth = gridWidth;
  }

  searchPath(start: Tile, end: Tile): Tile[] {
    this.startTile = start;
    this.endTile = end;

    /** Path validation */
    if (!start.walkable) {
      console.log('The start tile in not walkable, choose different tile than', start.index);
      return [];
    }
    if (!end.walkable) {
      console.log('The end tile in not walkable, choose different tile than', end.index);
      return [];
    }
    /** Start A* Algorithm */

    /** Add the starting tile to the openList */
    this.openList.push(start);
    let currentTile;

    /** While openList is not empty */
    while (this.openList.length) {
      //current node = node for open list with the lowest cost.
      currentTile = this.getTileWithLowestTotal(this.openList);

      //if the currentTile is the endTile, then we can stop searching
      if(JSON.stringify(currentTile.index) === JSON.stringify(end.index)){

        this.startTile.setBackgroundColor("rgba(255, 45, 45, .8)");
        this.endTile.setBackgroundColor("rgba(255, 45, 45, .8)");
        return this.shortestPath();
      }
      else {
        //move the current tile to the closed list and remove it from the open list.
        this.openList.remove(currentTile);
        this.closedList.push(currentTile);

        // //Get all adjacent Tiles
        let adjacentTiles = this.getAdjacentTiles(currentTile);

        for (let adjacentTile of adjacentTiles) {
          //Get tile is not in the open list
          if (!this.openList.contains(adjacentTile)) {
            //Get tile is not in the closed list
            if (!this.closedList.contains(adjacentTile)) {
              //move it to the open list and calculate cost
              this.openList.push(adjacentTile);

              //calculate the cost
              adjacentTile.cost = currentTile.cost + 1;

              //calculate the manhattan distance
              adjacentTile.heuristic = this.manhattanDistance(adjacentTile);

              // calculate the total amount
              adjacentTile.total = adjacentTile.cost + adjacentTile.heuristic;

              currentTile.setBackgroundColor('rgba(0, 181, 93, 0.8)');
            }
          }
        }
      }
    }
  }

  getTileWithLowestTotal(openList: Tile[]): Tile {
    let tileWithLowestTotal = new Tile();
    let lowestTotal: number = 999999999;
    /** Search open tiles and get the tile with the lowest total cost */
    for (let openTile of openList) {
      if (openTile.total <= lowestTotal) {
        //clone lowestTotal
        lowestTotal = openTile.total;
        tileWithLowestTotal = openTile;
      }
    }
    return tileWithLowestTotal;
  }

  getAdjacentTiles(current: Tile): Tile[] {
    let adjacentTiles: Tile[] = [];
    let adjacentTile: Tile;

    //Tile to left
    if (current.index.x - 1 >= 0) {
      adjacentTile = this.grid[current.index.x - 1][current.index.y];
      if (adjacentTile && adjacentTile.walkable) {
        adjacentTiles.push(adjacentTile);
      }
    }

    //Tile to right
    if (current.index.x + 1 < this.gridWidth) {
      adjacentTile = this.grid[current.index.x + 1][current.index.y];
      if (adjacentTile && adjacentTile.walkable) {
        adjacentTiles.push(adjacentTile);
      }
    }

    //Tile to Under
    if (current.index.y + 1 < this.gridHeight) {
      adjacentTile = this.grid[current.index.x][current.index.y + 1];
      if (adjacentTile && adjacentTile.walkable) {
        adjacentTiles.push(adjacentTile);
      }
    }

    //Tile to Above
    if (current.index.y - 1 >= 0) {
      adjacentTile = this.grid[current.index.x][current.index.y - 1];
      if (adjacentTile && adjacentTile.walkable) {
        adjacentTiles.push(adjacentTile);
      }
    }
    /** TODO: Diagonal moves  */
    return adjacentTiles;
  }

  /** Calculate the manhattan distance */
  manhattanDistance(adjacentTile: Tile): number {
    return Math.abs((this.endTile.index.x - adjacentTile.index.x) +
      (this.endTile.index.y - adjacentTile.index.y));
  }

  shortestPath() {
    let startFound: boolean = false;
    let currentTile = this.endTile;
    let pathTiles = [];

    //includes the end tile in the path
    pathTiles.push(this.endTile);
    this.endTile.ball = true;

    while (!startFound) {
      let adjacentTiles = this.getAdjacentTiles(currentTile);

      //check to see what newest current tile.
      for (let adjacentTile of adjacentTiles) {
        //check if it is the start tile
        if (JSON.stringify(adjacentTile.index) === JSON.stringify(this.startTile.index)){
          return pathTiles;
        }

        //it has to be inside the closedList or openList
        if (this.closedList.contains(adjacentTile) || this.openList.contains(adjacentTile)) {
          if (adjacentTile.cost <= currentTile.cost && adjacentTile.cost > 0) {
            //change the current tile.
            currentTile = adjacentTile;
            //Add this adjacentTile to the path list
            pathTiles.push(adjacentTile);
            //highlight way with yellow balls
            adjacentTile.ball = true;
            break;
          }
        }
      }
    }
  }
}

这篇关于寻找二维数组中两点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！