查找边界坐标内的坐标
Find coordinates inside borders coordinates
我有 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}];
图示为:
红色是 collisions
,金色是 destinations
。
我需要算法来找到被碰撞包围的目的地。我不能走对角线,所以在上面的场景中我想找到 {x: 1, y:1}.
如何实现?
可能有更有效的算法来计算这个,但起初想到,您可以简单地迭代所有目的地并逐个检查所有 4 个方向(左、右、上、下)的相邻方块。
这是一个实现。它有点冗长,但你可以通过分离功能来简化它:
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}];
const surrounded = [];
// boundaries
var minX = 0, minY = 0;
var maxX = 3, maxY = 4;
var point = {x: 0, y: 0};
for(dest of destinations){
var left = false;
var right = false;
var up = false;
var down = false;
point.x = dest.x;
point.y = dest.y;
// left check
while(point.x--){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("left hit for point:")
// console.log(dest)
left = true;
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!left)
continue;
point.x = dest.x;
point.y = dest.y;
// right check
while(point.x++){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("right hit for point:")
// console.log(dest)
right = true;
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!right)
continue;
point.x = dest.x;
point.y = dest.y;
// up check
while(point.y--){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("up hit for point:")
// console.log(dest)
up = true
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!up)
continue;
point.x = dest.x;
point.y = dest.y;
// down check
while(point.y++){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("down hit for point:")
// console.log(dest)
down = true
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!down)
continue;
if(left && right && up && down){
surrounded.push(dest)
}
}
console.log("Surrounded found: " + surrounded.length);
console.log(surrounded);
这是 jsbin。
我可能会尝试使用 well-tested 已建立(并且已经实施)的路径查找算法,而不是创建新算法,例如 A*(这基本上是一个优化的Dijkstra 算法的版本,阅读更多关于寻路算法 here) 并调整您的场景以便可以使用这些算法。我认为这种方法会为您节省不少时间并使您的代码更可靠。
请注意,我将您的坐标对象转换为坐标数组,a) 以这种方式表达坐标更常见,b) 使用它们更容易(而且很可能更快 => 数组很快)。
对于您的示例,我们基本上想找到从实际网格外部的某个点到每个目的地的路径。我们还需要确保位于网格边缘的目的地,例如[0,0]
和 [0,4]
可以通过某种方式到达,例如一条路可以通向他们。出于这个原因,我们扩展/"pad" 网格,每侧有一个节点。这意味着您的所有坐标都移动了 1 个节点。
从那里我们可以简单地检查是否存在通往目的地的路径。我正在从 [0,0]
检查,它现在位于您的实际网格之外,但您可以从任何地方检查,只要该节点是 "padding" 节点之一:
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>
如果你真的需要完整的路径查找当然取决于你的 real-world 场景,如果你的网格和目的地总是 "small" 的规模,你可能会找到一个更简单的解决方案,比如@Yavuz Tas
建议的那个
我有 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}];
图示为:
红色是 collisions
,金色是 destinations
。
我需要算法来找到被碰撞包围的目的地。我不能走对角线,所以在上面的场景中我想找到 {x: 1, y:1}.
如何实现?
可能有更有效的算法来计算这个,但起初想到,您可以简单地迭代所有目的地并逐个检查所有 4 个方向(左、右、上、下)的相邻方块。
这是一个实现。它有点冗长,但你可以通过分离功能来简化它:
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}];
const surrounded = [];
// boundaries
var minX = 0, minY = 0;
var maxX = 3, maxY = 4;
var point = {x: 0, y: 0};
for(dest of destinations){
var left = false;
var right = false;
var up = false;
var down = false;
point.x = dest.x;
point.y = dest.y;
// left check
while(point.x--){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("left hit for point:")
// console.log(dest)
left = true;
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!left)
continue;
point.x = dest.x;
point.y = dest.y;
// right check
while(point.x++){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("right hit for point:")
// console.log(dest)
right = true;
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!right)
continue;
point.x = dest.x;
point.y = dest.y;
// up check
while(point.y--){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("up hit for point:")
// console.log(dest)
up = true
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!up)
continue;
point.x = dest.x;
point.y = dest.y;
// down check
while(point.y++){
// hit check
if(collisions.findIndex(e => e.x==point.x&&e.y==point.y) > -1){
// console.log("down hit for point:")
// console.log(dest)
down = true
break;
}
if(point.x <= minX || point.x >= maxX || point.y <= minY || point.y >= maxY){
break;
}
}
if(!down)
continue;
if(left && right && up && down){
surrounded.push(dest)
}
}
console.log("Surrounded found: " + surrounded.length);
console.log(surrounded);
这是 jsbin。
我可能会尝试使用 well-tested 已建立(并且已经实施)的路径查找算法,而不是创建新算法,例如 A*(这基本上是一个优化的Dijkstra 算法的版本,阅读更多关于寻路算法 here) 并调整您的场景以便可以使用这些算法。我认为这种方法会为您节省不少时间并使您的代码更可靠。
请注意,我将您的坐标对象转换为坐标数组,a) 以这种方式表达坐标更常见,b) 使用它们更容易(而且很可能更快 => 数组很快)。
对于您的示例,我们基本上想找到从实际网格外部的某个点到每个目的地的路径。我们还需要确保位于网格边缘的目的地,例如[0,0]
和 [0,4]
可以通过某种方式到达,例如一条路可以通向他们。出于这个原因,我们扩展/"pad" 网格,每侧有一个节点。这意味着您的所有坐标都移动了 1 个节点。
从那里我们可以简单地检查是否存在通往目的地的路径。我正在从 [0,0]
检查,它现在位于您的实际网格之外,但您可以从任何地方检查,只要该节点是 "padding" 节点之一:
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>
如果你真的需要完整的路径查找当然取决于你的 real-world 场景,如果你的网格和目的地总是 "small" 的规模,你可能会找到一个更简单的解决方案,比如@Yavuz Tas
建议的那个