javascript - 查找边界坐标内的坐标

Question

我有 x,y 4x5 仪表板。我有碰撞对象数组，它是:

const collisions = [{x: 1, y: 0}, {x: 2, y: 0}, {x: 0, y: 1}, {x: 0, y: 2}, {x: 1, y: 3}, {x: 2, y: 3}, {x: 3, y: 1}, {x: 3, y: 2}];

基本上形成一个没有边缘的正方形。我还有一系列目的地:

const destinations = [{x: 0, y: 0}, {x: 1, y: 1}, {x: 0, y: 4}];

图形表示为:

其中红色是碰撞，金色是目的地。

我需要能够找到被碰撞包围的目的地的算法。我不能斜着走，所以在上面的场景中我想找到 {x: 1, y:1}。

如何实现？

Answer 1

我可能会尝试使用经过充分测试的已建立(并且已经实现)的路径查找算法，例如A*(这基本上是 Dijkstra 算法的优化版本，请阅读更多内容)，而不是创建新算法关于路径查找算法 here )并调整您的场景，以便可以使用这些算法。我认为这种方法将为您节省相当多的时间并使您的代码更加可靠。

请注意，我将坐标对象转换为坐标数组，a)以这种方式表达坐标更常见，b)使用它们更容易(并且很可能更快 => 数组很快)。

对于您的示例，我们基本上希望找到从实际网格之外的某个点到每个目的地的路径。我们还需要确保目的地位于网格边缘，例如[0,0] 和 [0,4] 可以通过某种方式访问​​，例如有一条路可以通向他们。因此，我们在网格的每一侧扩展/“填充”一个节点。这意味着所有坐标都会移动 1 个节点。

从那里我们可以简单地检查是否存在到达目的地的路径。我正在从 [0,0] 进行检查，该节点现在位于实际网格之外，但只要该节点是“填充”节点之一，您就可以从任何地方进行检查:

const collisions = [[1, 0], [2, 0], [0, 1], [0, 2], [1, 3], [2, 3], [3, 1], [3, 2]];
const destinations = [[0, 0], [1, 1], [0, 4]];

// we expand the grid by one node on each side
// otherwise destinations at the edge might not be reachable!
const grid = new PF.Grid(4+2, 5+2);

// set up the blocked nodes
collisions.forEach(collision => {
	// +1 accounts for the grid "padding" of one node
	grid.setWalkableAt(collision[0]+1, collision[1]+1, false);
});

const paintGrid = grid => {
  const rects = [];
  const nodes = grid.nodes.flat();
  nodes.forEach(node => {
    rects.push(`
      <rect x="${node.x*24}" y="${node.y*24}" width="24" height="24" fill="${node.walkable ? '#FFF' : 'red'}" stroke="#000" stroke-opacity="0.2"></rect>
    `);
  });
  destinations.forEach(dest => {
    rects.push(`
      <rect x="${(dest[0]+1)*24}" y="${(dest[1]+1)*24}" width="24" height="24" fill="gold" stroke="#000" stroke-opacity="0.2"></rect>
    `);
  });
  document.querySelector('#grid').innerHTML = rects.join('');
};

const isTrapped = destination => {
	// make a working copy of the grid
	// as it will not be re-usable after processing
	const g = grid.clone();
	const finder = new PF.AStarFinder({
		allowDiagonal: false
	});
	
	// +1 accounts for the grid "padding" of one node
	return finder.findPath(0, 0, destination[0]+1, destination[1]+1, g).length === 0;
};

paintGrid(grid);

destinations.forEach(destination => {
	console.log(`is ${destination} trapped?`, isTrapped(destination));
});

<script src="https://cdn.jsdelivr.net/gh/qiao/PathFinding.js@0.4.18/visual/lib/pathfinding-browser.min.js"></script>

<svg id="grid" width="144" height="168" xmlns="http://www.w3.org/2000/svg">

</svg>

如果您确实需要完整的路径查找，当然取决于您的现实场景，如果您的网格和目的地的规模总是那么“小”，您可能会找到一个更简单的解决方案，例如@Yavuz建议的解决方案塔斯社