Ищете идеи, как реорганизовать мой алгоритм

Я пытаюсь написать свою Игру Жизни, со своим собственным набором правил. Первой "концепцией", которую я хотел бы применить, является социализация (что в основном означает, что клетка хочет быть одна или в группе с другими ячейками). Структура данных - это двумерный массив (на данный момент).

Чтобы иметь возможность перемещать ячейку в/из группы других ячеек, мне нужно определить, куда ее перемещать. Идея состоит в том, что я оцениваю все ячейки в области (соседей) и получаю вектор, который говорит мне, куда перемещать ячейку. Размер вектора равен 0 или 1 (не двигайтесь и не двигайтесь), а угол представляет собой массив направлений (вверх, вниз, вправо, влево).

Это изображение с изображением сил для клетки, как я себе это представлял (но охват может быть больше 5):

ForceAppliedToACell

Позвольте, например, сделать эту фотографию:

Example

Forces from lower left neighbour: down (0), up (2), right (2), left (0)
Forces from right neighbour     : down (0), up (0), right (0), left (2)
sum                             : down (0), up (2), right (0), left (0)

Так что клетка должна идти вверх.

Я мог бы написать алгоритм с большим количеством операторов if и проверить все ячейки по соседству. Конечно, этот алгоритм был бы самым простым, если бы параметр 'reach' был установлен в 1 (первый столбец на рисунке 1). Но что, если я изменю параметр досягаемости на 10, например? Мне нужно было бы заранее написать алгоритм для каждого параметра "достижения"... Как я могу избежать этого (обратите внимание, что сила возрастает (1, 2, 4, 8, 16, 32,...))? Могу ли я использовать конкретный шаблон дизайна для этой проблемы?

Кроме того: самое главное не скорость, а возможность расширить исходную логику.

Что следует принять во внимание:

  • досягаемость должна быть передана как параметр
  • Я хотел бы изменить функцию, которая рассчитывает силу (потенциал, Фибоначчи)
  • ячейка может перейти в новое место, только если это новое место не заселено
  • следите за углами (например, вы не можете оценить правых и верхних соседей в верхнем правом углу)

Ответы

Ответ 1

Нетрудно написать свой алгоритм для поиска всех ячеек в пределах досягаемости определенной ячейки C. Каждая ячейка, у которой есть житель, будет иметь особую силу отталкивания на ячейке C. Эта сила отталкивания основана на расстоянии от ячейки до ячейки C. В примере, который вы указали, эта сила отталкивания основана на расстоянии L-1 и составляет 2^(reach-distance). Затем каждая сила отталкивания складывается вместе, чтобы создать кумулятивную силу, которая диктует направление перемещения жителя в ячейку C.

Вам не нужно писать алгоритм для каждого разного охвата. Величину силы можно определить по простой формуле. Если вы измените эту формулу на что-то еще, например, на число Фибоначчи, вы все равно сможете вычислить величину по мере необходимости на основе расстояния и досягаемости.

Вот грубый код, написанный на псевдо-Java, показывающий основные идеи: http://codepad.org/K6zxnOAx

enum Direction {Left, Right, Up, Down, None};

Direction push(boolean board[][], int testX, int testY, int reach)
{
    int xWeight = 0;
    int yWeight = 0;
    for (int xDist=-reach; xDist<=+reach; ++xDist)
    {
        for (int yDist=-reach; yDist<=+reach; ++yDist)
        {
            int normDist = abs(xDist) + abs(yDist);
            if (0<normDist && normDist<reach)
            {
                int x = testX + xDist;
                int y = testY + yDist;
                if (0<=x && x<board.length && 0<=y && y<board[0].length)
                {
                   if (board[x][y])
                   {
                       int force = getForceMagnitude(reach, normDist);
                       xWeight += sign(xDist) * force;
                       yWeight += sign(yDist) * force;
                   }
                }
            }
        }
    }
    if (xWeight==0 && yWeight==0) return Direction.None;
    if (abs(xWeight) > abs(yWeight))
    {
        return xWeight<0 ? Direction.Left : Direction.Right;
    }
    else
    {
        return yWeight<0 ? Direction.Up : Direction.Down;
    }
}

int getForceMagnitude(int reach, int distance)
{
    return 1<<(reach-distance);
}

Ответ 2

Напишите функцию для циклического перехода по соседям:

  • Используйте min/max, чтобы закрепить границы матрицы.
  • Используйте цикл for для цикла по всем соседям.
  • Измените границы цикла для представления охвата.

:

def CalculateForceOnCell(x, y):
    force_on_x_y = [0,0,0,0]
    for i in range(max(0, x-reach), min(WIDTH, x+reach)+1):
        limited_reach = reach - abs(x-i)
        for j in range(max(0, y - limited_reach), min(HEIGHT, y + limited_reach + 1)):
            force_coefficient = limited_reach + 1
            AddNeighborForce(force_on_x_y, (x, y), (i, j), force_coefficient)
    return force_on_x_y