Обнаружение диапазона движения с массивом - PullRequest
Новая
       7

Обнаружение диапазона движения с массивом

0 голосов
/ 26 мая 2018

У меня есть один размерный массив, подобный этому: 

    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>

1 Ответ

0 голосов
/ 27 мая 2018

По сути, вы можете интегрировать массив масок и выходить раньше, если будет найдена ячейка, которую не следует использовать.

В этом предложении используются матрицы вместо линейных массивов, поскольку проверку соседних ячеек проще решать.

Затем он принимает массив для возможных направлений и проверку на ранний выход с помощью 

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);
...