javascript - 具有寻路网格生成的边缘情况的困难
问题描述
我正在尝试开发此答案的实现,以支持可能大于单个单元的单元的 A-star 寻路。
我遇到的问题是目前我的输出中有一个小错误,我不确定我是否执行不当,或者算法是否没有正确处理这种边缘情况。
这是演示该问题的完整复制品:
function createThickGrid(inputGrid, width, height) {
let outputGrid = [];
let largeInteger = 100000000;
for (let i = 0; i < width * height; i++) {
if (inputGrid[i] === 0) { // wall
outputGrid[i] = -1;
} else {
outputGrid[i] = largeInteger;
}
}
for (let i = 0; i < width * height; i++) {
if (outputGrid[i] > 0) {
outputGrid[i] = getSmallestNeighbor(outputGrid, i, width, height) + 2;
}
}
return outputGrid;
}
function getSmallestNeighbor(grid, idx, width, height) {
let col = idx % width;
let row = Math.floor(idx / width);
let smallest = 99999999999999;
if (row <= 0 || row >= height - 1 || col <= 0 || col >= width - 1) {
return -1;
}
let northValue = grid[idx - width];
if (northValue < smallest) {
smallest = northValue;
}
let northWestValue = grid[idx - width - 1];
if (northWestValue < smallest) {
smallest = northWestValue;
}
let northEastValue = grid[idx - width + 1];
if (northEastValue < smallest) {
smallest = northEastValue;
}
let southValue = grid[idx + width];
if (southValue < smallest) {
smallest = southValue;
}
let southWestValue = grid[idx + width - 1];
if (southWestValue < smallest) {
smallest = southWestValue;
}
let southEastValue = grid[idx + width + 1];
if (southEastValue < smallest) {
smallest = southEastValue;
}
let westValue = grid[idx - 1];
if (westValue < smallest) {
smallest = westValue;
}
let eastValue = grid[idx + 1];
if (eastValue < smallest) {
smallest = eastValue;
}
return smallest;
}
// You can ignore this, it's just for pretty printing
function convert1DTo2D(grid, width, height) {
let arr = [];
for (let row = 0; row < height; row++) {
let newRow = [];
for (let col = 0; col < width; col++) {
newRow.push(grid[row * width + col]);
}
arr.push(newRow);
}
return arr;
}
let width = 5;
let height = 5;
// 0 == wall and 1 == free space
grid = [1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1];
let thickGrid = createThickGrid(grid, width, height);
// console table works better but I don't know if Stackoverflow supports it
// console.table(convert1DTo2D(thickGrid, width, height));
console.log(convert1DTo2D(thickGrid, width, height));
如您所见,以下输出是这样的:
[1, 1, 1, 1, 1]
[1, 3, 3, 3, 1]
[1, 3, 5, 3, 1]
[1, 3, 5, 3, 1]
[1, 1, 1, 1, 1]
除了倒数第二行的中间值之外,这似乎几乎完全正确。我认为应该是 a3
而不是 a 5
。
这些数字是指它们与最近的墙之间的半瓦距离(在这种情况下,最近的墙是阵列的边缘)。我相信它应该是以下内容:
[1, 1, 1, 1, 1]
[1, 3, 3, 3, 1]
[1, 3, 5, 3, 1]
[1, 3, 3, 3, 1]
[1, 1, 1, 1, 1]
但我不确定为什么现在还不是这样。算法是错误的还是我的实现有缺陷?
解决方案
确实,您的算法不会那样工作。更新距离时,这可能会影响您已经处理过的单元格的距离(北),应根据当前单元格刚刚获得的距离来减少该距离。
解决此问题的算法是面包优先遍历:这将使您按距离顺序访问一个单元格。所以你从墙开始,找到他们的邻居,然后把他们排在队列的最后。从队列的开头处理单元格。这样,您将找到从墙壁到任何单元的最短路径,并且可以正确确定它们的距离。
有几种方法可以实现这种广度优先遍历。我个人喜欢用两个普通数组而不是一个队列来做到这一点。每次将所有邻居添加到数组时,都会将该数组作为下一次迭代的基础,其中距离将大 2。下一次迭代将用邻居填充一个新数组。在该迭代结束时,新数组被视为旧数组,并且一切都重复,直到找不到更多邻居:
function createThickGrid(inputGrid, width) {
let height = inputGrid.length / width; // height can be derived...
let outputGrid = [];
// Add all walls to a list
let wave = [-1]; // special wall value to denote the "wall" outside the grid
for (let i = 0; i < width * height; i++) {
if (inputGrid[i] === 0) { // Wall
outputGrid[i] = -1; // Mark wall in the output
wave.push(i);
}
}
let distance = 1;
while (wave.length) { // Each iteration we deal with the next distance
let nextWave = [];
for (let i of wave) {
// Collect unvisited neighbors of a cell
let neighbors = getNeighbors(i);
// Mark their distance
for (let i of neighbors) outputGrid[i] = distance;
// Schedule their treatment for next outer iteration
nextWave.push(...neighbors);
}
// Prepare next iteration
wave = nextWave;
distance += 2;
}
return outputGrid;
function getNeighbors(i) {
let neighbors = [];
if (i >= 0) { // normal case
if (i % width) neighbors.push(i - 1 - width, i - 1, i - 1 + width);
neighbors.push(i - width, i + width);
if ((i+1) % width) neighbors.push(i + 1 - width, i + 1, i + 1 + width);
} else { // all edge cells neighbor a "wall"
neighbors = [...Array(width).keys(),
...Array.from({length: height-2}, (_,i) => (i + 1) * width),
...Array.from({length: height-2}, (_,i) => (i + 2) * width - 1),
...Array.from({length: width}, (_, i) => (height - 1) * width + i)
];
}
return neighbors.filter(i =>
i >= 0 && i < width * height && outputGrid[i] === undefined
);
}
}
function convert1DTo2D(grid, width) {
return Array.from({length: grid.length / width}, (_, i) =>
grid.slice(i*width, (i+1)*width)
);
}
let width = 5;
// 0 == wall and 1 == free space
let grid = [
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
];
let thickGrid = createThickGrid(grid, width);
for (let row of convert1DTo2D(thickGrid, width)) {
console.log(JSON.stringify(row));
}
推荐阅读
- matplotlib - 禁止在metpy中打印轴标签
- java - jlink不使用自动模块
- javascript - 反应 API 项目:类型错误:无法读取未定义的属性“小”
- java - 需要关于我做错了什么的建议
- c# - 了解将数据从页面传递到用户控件
- python - 将正整数表示为三个数字的和
- r - 基于多个条件的 if else 语句
- python - 为 Pandas Dataframe Columns 中两个列表中的每个元素运行一个函数
- python - 如何在 Mitmproxy 中突出显示文本?
- react-native - TypeError: Cannot read proper 'navigate' of undefined