用数组检测运动范围

Question

我有这样的一维数组：

    0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 1, 1, 0,
    0, 0, 0, 0, 0, 1, 1,
    0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 0, 1, 1,
    0, 1, 0, 1, 1, 1, 0,
    0, 1, 0, 1, 0, 0, 0,

图例：0 = 空楼层，1 = 挡路的墙，2 = 起点，3 = 从起点可以到达的楼层。如果值为 0，则可以水平、垂直和对角线移动。示例地图数组为 7x7，示例移动范围为 3，但这些参数甚至可能为 15x9 和 6。我想要做的是获取一维数组，显示从所选点开始的可能移动范围（示例范围为 3 步，如果位置为 0，对角线可以在墙之间穿过，如您在左下角所见）：

    0, 0, 0, 0, 0, 0, 0,
    3, 1, 1, 1, 1, 1, 0,
    3, 3, 3, 3, 3, 1, 1,
    3, 3, 3, 2, 3, 3, 3,
    1, 3, 3, 3, 3, 1, 1,
    3, 1, 3, 1, 1, 1, 0,
    0, 1, 3, 1, 0, 0, 0,

这是一个更简单的版本，因为如果可以将范围限制为在一维掩码数组中可以不同的指定形状，就像这个例子（0 = 超出范围）：

    0, 0, 0, 1, 0, 0, 0,
    0, 0, 1, 1, 1, 0, 0,
    0, 1, 1, 1, 1, 1, 0,
    1, 1, 1, 1, 1, 1, 1,
    0, 1, 1, 1, 1, 1, 0,
    0, 0, 1, 1, 1, 0, 0,
    0, 0, 0, 1, 0, 0, 0,

在这种情况下，结果将是这样的：

    0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 1, 1, 0,
    0, 3, 3, 3, 3, 1, 1,
    3, 3, 3, 2, 3, 3, 3,
    1, 3, 3, 3, 3, 1, 1,
    0, 1, 3, 1, 1, 1, 0,
    0, 1, 0, 1, 0, 0, 0,

代码：

<div id="results" style="font-family: monospace; font-weight: bold; font-size: 24pt; background-color: #000000; color: #FFFFFF;">
</div>
<script>
var map=[0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,1,1,0,0,1,0,1,0,0,0,];
var mask=[0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0,];

function path_create(map,width,height,point,range,mask)
{
// map = pure map with 0 as floor and 1 as wall
// width, height = size of map
// point = starting point to calculate movement range
// range = number of moves from starting point to each direction of horizontal, vertical, and diagonal
// mask = (optional) if possible to do, array mask (0 is not in range) can change range for diagonal moves with special shapes like circle or rhombus
var matrix=[];
return matrix;
// one dimension array where 0 is no range, and 1 is ok
}

function path_show(matrix,width,height)
{
var v="";
for(var i=0; i<matrix.length; i++)
{
if(i!=0 && i%7==0){v=v+"<br>";}
v=v+matrix[i]+" ";
}
document.getElementById('results').innerHTML=v;
}

path_show(path_create(map,7,7,25,3,mask));
//path_show(path_create(map,7,7,16,3,mask));
</script>

Answer 1

基本上你可以集成掩码数组并在发现不应该使用的单元格时提前退出。

此提议使用矩阵而不是线性数组，因为对相邻单元格的检查更容易解决。

然后它需要一个数组来表示可能的方向，并使用

检查提前退出

if (!mask[i][j] || array[i][j] === 1 || !steps || reach[i][j] >= steps) {
    return;
}

哪里

!mask[i][j] 检查掩码，
array[i][j] === 1翻墙，
!steps 检查剩下的步骤或
reach[i][j] >= steps 当一个单元格的步数大于剩余步数时，这会阻止检查已检查的步数并尽可能地阻止采取更短的剩余步数。

在所有上述情况下，进一步处理停止。

function check(i, j, steps) {
    var directions = [{ x: 0, y: -1 }, { x: -1, y: -1 }, { x: -1, y: 0 }, { x: -1, y: 1 }, { x: 0, y: 1 }, { x: 1, y: 1 }, { x: 1, y: 0 }, { x: 1, y: -1 }];

    if (!mask[i][j] || array[i][j] === 1 || !steps || reach[i][j] >= steps) {
        return;
    }

    reach[i][j] = steps;
    directions.forEach(({ x, y }) => {
        x += i;
        y += j;
        if (x < 0 || x >= width || y < 0 || y >= height) {
            return;
        }
        check(x, y, steps - 1);
    });
}

function out(array) {
    document.getElementById('out').innerHTML += array.map(a => a.join('  ')).join('\n') + '\n\n';
}

function getMatrix(raw, width) {
    var array = [],
        i = 0;

    while (i < raw.length) {
        array.push(raw.slice(i, i += width));
    }
    return array;
}

var width = 7,
    height = 7,
    rawData = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0],
    rawMask = [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    array = getMatrix(rawData, width),
    mask = getMatrix(rawMask, width),
    reach = Array.from({ length: height }, _ => Array.from({ length: width }).fill(0)),
    max = 3,
    result;

array[3][3] = 2;
check(3, 3, max + 1);
result = reach.map((a, i) => a.map((b, j) => b === max + 1 ? 2 : b ? 3 : array[i][j]));

out(array);
out(reach);
out(result);

<pre id="out"></pre>

用数组检测运动范围

Detecting movement range with array

javascript

arrays

html

path-finding