Matlab - получить соседние ячейки с функцией условия/перемещения

У меня есть большая квадратная матрица структур, которая представляет существ. Каждое существо может двигаться влево, вверх, вправо или вниз. Я проверяю соседние позиции матрицы на наличие пустых ячеек и выполняю следующие вычисления для новых координат:

function res = Move2(worldDimension,row,col,left,up,right,down)

%In the following matrices, good moves are > 0.

%Directions pattern:
patternMatrix = [0 2 0;
                 1 5 3;
                 0 4 0];
%Possible border moves:             
borderMatrix = [0 (row>1) 0;
                (col>1) 1 (col<worldDimension);
                 0 (row<worldDimension) 0;];
%Possible neighbor moves:              
neighborsMatrix = [0 (up==0) 0 ;
                (left==0) 1 (right==0);
                 0 (down==0) 0;];             

%Matrix of possible directions including neighbors and borders
possibleMovesMatrix = ((borderMatrix).*(neighborsMatrix)).*(patternMatrix);

%Vector of possible directions:
possibleMovesVector = sort(possibleMovesMatrix(possibleMovesMatrix(:) > 0));

%Random direction:
randomDirection = possibleMovesVector(randi(length(possibleMovesVector)));

directionCoordsVector = [[row (col-1)];[(row-1) col];[row (col+1)];[(row+1) col];[row col]];                         
res = [directionCoordsVector(randomDirection,1) directionCoordsVector(randomDirection,2)];
end

Эта функция довольно медленная, когда я запускаю профилировщик, он говорит мне, что:

borderMatrix = [0 (row>1) 0;
(col>1) 1 (col<worldDimension);
0 (row<worldDimension) 0;];

занимает 36% времени, а вот это: randomDirection = PossibleMove... занимает 15% времени. Можно ли как-то ускорить процесс?

Может быть, я могу использовать другой подход, немедленно беря с основного игрового поля свободные места вокруг координаты существа? Если да, то как мне взять подматрицу, если существо находится рядом с границей доски, не имея дело с индексами за границей?

Спасибо, Гай.


person Guy Wald    schedule 22.01.2013    source источник
comment
Я не понимаю, зачем вам нужна матрица для обработки ваших данных. Я знаю, что это менее интуитивно понятно, но у вас действительно есть только 4 возможных хода, поэтому вам действительно нужен только вектор длины 4. Это должно ускорить работу.   -  person Squazic    schedule 22.01.2013


Ответы (2)


Итак, у вас есть массив структур и вы перемещаете структуры внутри массива? Мне это кажется крайне неэффективным.

Кроме того, причина, по которой borderMatrix-строка занимает так много времени, заключается в том, что вы строите, возможно, большой массив.

Вот предложение по обращению с движущимися существами:

Храните своих существ в виде числового массива nCreatures-by-mProperties. Гораздо проще применять функции к столбцу массива, чем сканировать отдельные поля. Например creatures = [x,y,prop1,prop2];

Перемещайте своих существ по одному:

for iCreature = 1:nCreatures
    currentPos = creatures(iCreature,1:2);

    %# initialize array of allowed moves with border conditions
    goodMoves = [currentPos(1) > 1, currentPos(2) > 1, currentPos(1) < maxX, currentPos(2) < maxY, true];

    %# check for neighbors
    if any(creatures(:,1) == currentPos(1) - 1 & creatures(:,2) == currentPos(2))
       goodMoves(1) = false;
    end
    %# etc

    %# identify remaining good moves
    if any(goodMoves(1:4))
       goodMoveIdx = find(goodMoves);
       move = goodMoveIdx(randi(length(goodMoveIdx)));
    else
       move = 5; %# remain stationary
    end
end
person Jonas    schedule 22.01.2013
comment
Когда я проверяю соседей, могут ли условия в примере фальсифицировать движение в определенном направлении, даже если квадрат в этом направлении свободен? Я имею в виду, что if выше проверяет x и фальсифицирует левое движение, даже если y поместит существо далеко от текущего существа. Могу ли я и x и y вместе? - person Guy Wald; 22.01.2013
comment
@Guy: Я предполагал, что вы можете двигаться только влево/вправо/вверх/вниз, а не влево+вверх, и что шаг будет только первого размера. Если могут быть многошаговые движения, я предлагаю вам просто зациклить один шаг несколько раз. Если могут быть диагональные движения (только одношаговые), то нужно иметь больше хорошихMove-вариантов, и нужно проверять обе координаты одновременно, например. слева проверяется как creatures(:,1) == currentPos(1)-1 & creatures(:,2) == currentPos(2) - person Jonas; 22.01.2013
comment
Вы предположили правильно. Может я не понимаю логики. Существа имеют 2d позицию. Насколько я понял, проверка 'any(creatures(:,1) == currentPos(1) - 1)' проверяет, существует ли другое существо в строке выше меня. Это существо может быть рядом выше, но где-то слева или справа. Тем не менее, квадрат точно надо мной может быть свободен. - person Guy Wald; 22.01.2013
comment
Мое решение: goodMoves(left) = sum((creatures(:,row)==currentPos(1)).*(creatures(:,col)==currentPos(2)-1)) == 0; - person Guy Wald; 22.01.2013
comment
Кажется, что использование n-существ по m-свойствам с for iCreatire=1:nCreatures приведет меня к решению O(n^2), а использование матрицы равно O(n), потому что с матрицей я проверяю точно клетки вокруг, в то время как с этим решением я проверяю каждое движение всех остальных существ. Нет? - person Guy Wald; 23.01.2013
comment
@Guy: Вы правы - вам нужно выполнить проверку, которую я предлагаю в моем комментарии выше. Я отредактирую свой ответ. Логические проверки в целом выполняются быстро по сравнению с большинством других решений, даже если вы в конечном итоге проверяете все против всех. Таким образом, я также предлагаю использовать any и & вместо sum и .*. В любом случае, для возможно более быстрого решения вы можете рассчитать расстояние, используя быстрый алгоритм mex, который позволяет вам пропустить расчеты расстояния для дальних соседей - вверх/вниз/влево/вправо всего один шаг. - person Jonas; 23.01.2013
comment
Вы также можете пропустить проверку соседей, если для этой проверки нет goodMove, чтобы сэкономить дополнительное время. В любом случае, вы должны снова профилировать, чтобы убедиться, что именно эта часть действительно вредит вам с точки зрения производительности. - person Jonas; 23.01.2013
comment
Йонас: Спасибо. Это значительно улучшило скорость кода, и я многому научился у вас о Matlab!! - person Guy Wald; 23.01.2013

На самом деле не ясно, есть ли несколько сильно зависимых существ, но в остальном это был бы эффективный рабочий процесс:

  1. Генерировать 1 случайное число для каждого существа
  2. Определить для каждого существа, сколько у него возможных ходов
  3. Используйте соответствующее случайное число, чтобы сделать выбор

Если они зависимы, но не слишком сильно, вы можете сделать это несколько раз, пока не найдете приемлемое значение или включите зависимость на шаге 2.

person Dennis Jaheruddin    schedule 22.01.2013