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

Question

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

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

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

ForceAppliedToACell http://img293.imageshack.us/img293/2852/29186643.png

Давайте, например, возьмем эту картинку:

Пример http://img683.imageshack.us/img683/7357/70002678.png

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, ...)) ? Могу ли я использовать конкретный шаблон дизайна для этой проблемы?

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

Что нужно учитывать:

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

Answer 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);
}

Answer 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