一千萬個為什麽

搜索

尋找如何重構我的算法的想法


我正在嘗試使用自己的一套規則編寫自己的 Game of Life 。我想申請的第一個“概念”是社會化(基本上意味著細胞想要獨處或與其他細胞組成)。數據結構是二維數組(現在)。

為了能夠將一個細胞移動到一組另一個細胞,我需要確定移動細胞的位置。我的想法是,我評估區域中的所有單元格(鄰居)並獲得一個向量,它告訴我在哪裏移動單元格。矢量的大小為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 ......)) ?我可以針對此問題使用特定的設計模式嗎?

另外:最重要的不是速度,而是能夠擴展初始邏輯。

需要考慮的事項:

  • 到達應作為參數傳遞
  • 我想改變函數,它計算力(潛力,斐波那契)
  • 只有在未填充此新地點時,單元格才能轉到新地點
  • 註意角落(例如,您無法評估右上角的右鄰居和頂級鄰居)

最佳答案

編寫算法來搜索特定單元格 C 的到達距離內的所有單元格並不困難。每個擁有居民的細胞都會在細胞 C 上產生特定的排斥力。這種排斥力基於從細胞到細胞 C 的距離。在您給出的示例中,排斥力基於L-1距離並且是 2 ^(到達距離)。然後將每個排斥力加在一起以產生累積力,該力決定了居民在細胞 C 中移動的方向。

您不需要為每個不同的範圍編寫算法。力的大小可以通過簡單的公式確定。如果您將該公式更改為其他內容(例如斐波納契數),您仍應能夠根據距離和範圍來計算所需的幅度。


Here is some rough code written in pseudo-Java showing the basic ideas: 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<=x && x<=y && y 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);
}

轉載註明原文: 尋找如何重構我的算法的想法

猜你喜歡