寻找重构算法的想法

Question

寻找重构算法的想法

c#.netalgorithmdesign-patterns

13

我正在尝试编写自己的生命游戏，并使用自己的规则。首先要应用的“概念”是社交（基本上意味着单独或与其他细胞一起组成群体）。数据结构是二维数组（目前为止）。

为了能够将一个细胞移动到/离开另一组细胞，我需要确定移动位置。我的想法是，评估周围所有的细胞（邻居），并获得一个向量，告诉我该如何移动细胞。向量的大小为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)

因此，单元格应该上移。

我可以编写一个带有许多if语句的算法，并检查所有邻近的单元格。当然，如果将“reach”参数设置为1（第一列在图片1中），则此算法最简单。但是，如果我将reach参数更改为10呢？我需要事先为每个'reach'参数编写算法...如何避免这种情况（请注意，力量是潜在增长的（1,2,4,8,16,32，...））？我能用特定的设计模式来解决这个问题吗？

另外：最重要的不是速度，而是能够扩展初始逻辑。

需要考虑以下几点：

reach应作为参数传递
我想更改计算力量（potential，fibonacci）的函数
仅当新位置未被占用时，单元格才能移动到新位置
注意角落处（例如，在右上角无法评估右侧和顶部邻居）

- sventevit

@Ikaso：右边两个加左边两个等于零。 - Eric Lippert

2

这是一个有趣的问题和需要解决的问题，但您的问题与您正在寻找的东西根本不接近。您需要代码来重构。您真正要求的是在编写算法时寻求帮助。 - John

@lkaso：红色的细胞是其他生命体居住的地方。每个生命体都试图与其他生命体保持距离。 - Matthew T. Staebler

@John - 我有代码，但它是“意大利面条式代码”，有很多if语句。而且它只适用于一个特定的参数 - 如果我想改变这个参数，那么我就必须编写新的算法。但是，也许这是一个太广泛的问题... :( - sventevit

你有了解元胞自动机吗？生命游戏就属于这一类“游戏”。似乎你所想实现的并不能作为元胞自动机来实现，但它可能会提供有用的灵感。 - Nick Johnson

显示剩余3条评论

2个回答

0

编写一个函数来循环遍历邻居：

使用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

- Stephen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew T. Staebler · Accepted Answer

不难编写算法以搜索特定单元格 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);
}