Поиск идей, как осуществить рефакторинг мой алгоритм
Я пытаюсь записать свою собственную Игру Жизни с моим собственным подшипником. Первое 'понятие', которое я хотел бы применить, является национализацией (который в основном означает, хочет ли ячейка быть одной или в группе с другими ячейками). Структура данных является 2-мерным массивом (на данный момент).
Чтобы смочь переместить ячейку в от группы другого ячейки, я должен определить, куда переместить ее. Идея, что я оцениваю все ячейки в области (соседи) и получаю вектор, который говорит мне, куда переместить ячейку. Размер вектора 0, или 1 (не перемещайтесь или перемещайтесь), и угол является массивом направлений (вниз, право, оставленное).
Это - изображение с представлением сил к ячейке, как я вообразил это (но досягаемость могла быть больше чем 5):
Давайте, например, сделаем этот снимок:
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)
Таким образом, ячейка должна повыситься.
Я мог записать алгоритм, с большим количеством из если операторы и проверяют все ячейки в район. Конечно, этот алгоритм был бы самым легким, если параметр 'досягаемости' устанавливается на 1 (первый столбец на изображении 1). Но что, если я изменяюсь, достигают параметра к 10, например? Я должен был бы записать, что алгоритм для каждого 'достигает' параметра заранее... Как я могу избежать этого (уведомление, что сила растет потенциально (1, 2, 4, 8, 16, 32...))? Я могу использовать определенный шаблон разработки для этой проблемы?
Также: самой важной вещью не является скорость, но смочь расширить начальную логику.
Вещи учесть:
- досягаемость должна быть передана в качестве параметра
- я хотел бы изменить функцию, которая вычисляет силу (потенциал, fibonacci)
- ячейка может перейти к новому месту, только если это новое место не заполняется
- наблюдайте за углами (Вы не можете оценить правильных и главных соседей в верхнем правом углу, например),
2 ответа
Нетрудно написать свой алгоритм для поиска всех ячеек в пределах досягаемости конкретной ячейки. C . Каждая клетка, в которой есть обитатель, будет иметь определенную силу отталкивания на клетку C . Эта сила отталкивания основана на расстоянии от клетки до клетки C . В приведенном вами примере сила отталкивания основана на расстоянии L-1 и составляет 2 ^ (расстояние досягаемости) . Затем каждая сила отталкивания складывается, чтобы создать кумулятивную силу, которая определяет направление, в котором перемещается обитатель клетки 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);
}
Напишите функцию для обхода соседей:
- Используйте min / max, чтобы ограничить границы матрицы.
- Используйте цикл for для перебора всех соседей.
- Измените границы цикла 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