生命游戏-此算法是什么

Game of Life - What is with this algorithm
2021-05-11
  •  译文(汉语)
  •  原文(英语)

我创建了一个简化的生活游戏.

这是发生实际情况的单元格:

class Cell
{
    public Cell(MainWindow correspondingMainWindow){
        this.mainWindow = correspondingMainWindow;
    }

    public bool excluded;

    public Boolean Occupied { get; set; }

    public Control correspondingPanel;

    private int[] coordinates;

    private MainWindow mainWindow;

    public int[] Coordinates
    {
        get { return this.coordinates; }
        set { 
            if(value.Length != 2) 
            {
                throw new ArgumentException();
            }
            else if(value[0] < 0 || value [1] < 0
                     || value[0] > Settings.FIELDWIDTH 
                     || value[1] > Settings.FIELDHEIGHT)
            {
                throw new ArgumentException();
            }
            else{
                correspondingPanel = mainWindow.FieldArea.Controls
                         .Find(String.Format("panel{0}_{1}", value[0], value[1]), true)
                         .FirstOrDefault();
                this.coordinates = value;
            }
        }

    }

    //Surrounding Cells in the 3x3 around the current cell
    //this is to speed up the updating as soon as the algorithm runs on many cells
    public Cell Top { get; set; }
    public Cell TopRight { get; set; }
    public Cell Right { get; set; }
    public Cell BotRight { get; set; }
    public Cell Bot { get; set; }
    public Cell BotLeft { get; set; }
    public Cell Left { get; set; }
    public Cell TopLeft { get; set; }

    public void die()
    {
        this.Occupied = false;
        this.correspondingPanel.BackColor = Color.Beige;
    }

    public void populate()
    {
        this.Occupied = true;
        this.correspondingPanel.BackColor = Color.DarkRed;
    }
}

这是有问题的算法:

//should return true if there were any changes to any "living" state
bool Algorithm.runOver(Cell target)
{
    if (target.Occupied && !target.excluded)
    {
        target.Right.populate();
        target.Left.populate();
        target.Top.populate();
        target.Bot.populate();

        target.Right.excluded = true;
        target.Left.excluded = true;
        target.Top.excluded = true;
        target.Bot.excluded = true;
        return true;
    }
    else
    {
        return false;
    }
}

每次算法一次完成所有单元的运行时,被排除并已经运行的被重置为false.这是为了防止在此walk中更新的Cell上调用walkOver().

现在,当我将单元格放在字段的左上边缘(类似于简单的蛇形字段)时,将其标记并运行算法,在第一次运行后它将停止更改.

它实际上以设计的方式更新了Cell,但是随后停止了.

我将单元格保存到Program中的静态列表中(我知道我不应该这样做,但这是直到它正常工作的最简单方法).单元格中有一些面板要匹配.这些面板位于一个名为FieldArea的GroupBox中.它们是根据一些静态常量设置(在坐标的设置验证中看到的)动态生成的.

我确信单元格与面板正确匹配.从左上角(0,0)到右下角穿过FieldArea的对角线中似乎会出现此问题.任何其他起点都可以正常工作.不知何故,当大量的单元格来自"顶部"时,这些单元格会在该字段的顶部和左侧边缘形成边界.

现在的问题是:我在做什么错?为什么我的字段无法正常工作?

解决过程1

您必须保留"世界"的两个副本,因为在应用规则时一个副本必须保持不变.如果将规则应用于唯一的世界,这将导致混合配置,其中某些单元将具有旧状态,而其他单元将已经具有新状态.

因此,请执行以下操作:

private Cell[,] activeWorld = new Cell[w,h];
private Cell[,] hiddenWorld = new Cell[w,h];

Populate(activeWorld);
while (true) {
    Display(activeWorld);
    ApplyRules(activeWorld, hiddenWorld);

    // Swap worlds
    var temp = activeWorld;
    activeWorld = hiddenWorld;
    hiddenWorld = temp;
}

该方法ApplyRules必须从"activeWorld"中读取单元格并将结果写入hiddenWorld.


更新:您的实际设计对我来说似乎是过度设计的.一个简单的二维布尔数组可以判断一个单元是否被占用.不要从优化开始.这很可能会导致复杂,难以读取和错误的代码.而是将注意力集中在算法和良好的代码结构上.如果以后遇到性能问题,请分析问题并进行适当的优化.在超过95%的情况下,问题与编码细节和算法无关,而与I / O有关.在此游戏中,显示单元格可能比应用规则花费更多的时间.无论如何,这可能太快了,您将不得不在游戏循环中添加一个暂停.

不要试图优化获取周围单元格索引的逻辑.痛苦是不值得的.

解决边缘单元问题的一种好方法是环游世界.使右侧看不见的东西重新出现在左侧,依此类推.为此,使用模运算(%).x % N总是产生范围内的值0 ... N-1.给定x和ay坐标,您可以像这样获得3 x 3单元的坐标:

for (int dx = -1; dx <= +1; dx++) {
    int i = (x + dx + Width) % Width;
    for (int dy = -1; dy <= +1; dy++) {
        int j = (y + dy + Height) % Height;
        bool occupied = world[i, j];
        ...
    }
}

+ Width+ Height确保我们始终为正值.

解决过程2

好吧,正如我所承诺的,这是我本周的个人胜利:

上面提到的算法是"错误的"

不幸的是,我正在排除未更改的单元格.当我从"左上方"浏览列表时,错误就出现了.

我将排除项移至die()和populate()函数.

public void die(){
    this.Occupied = false;
    this.correspondingPanel.BackColor = Color.Beige;
    this.excluded = true;
}

然后我还必须确保循环正确断开:

public Algorithm.walkOver(Cell target)
{
   if (target.Occupied && !target.excluded)
   {
       bool b = true;

   //if there could no changes be made, we also have to return there were no changes... 
   //else the while loop continues forever and we lose the process :(
       if (target.Right.Occupied && target.Left.Occupied 
           && target.Bot.Occupied && target.Top.Occupied)
       b = false;

       if(!target.Right.Occupied)
           target.Right.populate();

       if (!target.Left.Occupied)
           target.Left.populate();

       if (!target.Top.Occupied)
          target.Top.populate();

       if (!target.Bot.Occupied)
          target.Bot.populate();

       return b;
   }
   else
   {
      return false;
   }
}

我也将重置移动到while循环的开始,因为"选择"一个单元格将其排除在外.

速聊1:
如果您的问题解决了,请忘记我的评论.

I have created a simplified game of life.

This is my cell where the actual stuff happens:

class Cell
{
    public Cell(MainWindow correspondingMainWindow){
        this.mainWindow = correspondingMainWindow;
    }

    public bool excluded;

    public Boolean Occupied { get; set; }

    public Control correspondingPanel;

    private int[] coordinates;

    private MainWindow mainWindow;

    public int[] Coordinates
    {
        get { return this.coordinates; }
        set { 
            if(value.Length != 2) 
            {
                throw new ArgumentException();
            }
            else if(value[0] < 0 || value [1] < 0
                     || value[0] > Settings.FIELDWIDTH 
                     || value[1] > Settings.FIELDHEIGHT)
            {
                throw new ArgumentException();
            }
            else{
                correspondingPanel = mainWindow.FieldArea.Controls
                         .Find(String.Format("panel{0}_{1}", value[0], value[1]), true)
                         .FirstOrDefault();
                this.coordinates = value;
            }
        }

    }

    //Surrounding Cells in the 3x3 around the current cell
    //this is to speed up the updating as soon as the algorithm runs on many cells
    public Cell Top { get; set; }
    public Cell TopRight { get; set; }
    public Cell Right { get; set; }
    public Cell BotRight { get; set; }
    public Cell Bot { get; set; }
    public Cell BotLeft { get; set; }
    public Cell Left { get; set; }
    public Cell TopLeft { get; set; }

    public void die()
    {
        this.Occupied = false;
        this.correspondingPanel.BackColor = Color.Beige;
    }

    public void populate()
    {
        this.Occupied = true;
        this.correspondingPanel.BackColor = Color.DarkRed;
    }
}

Here is the algorithm in question:

//should return true if there were any changes to any "living" state
bool Algorithm.runOver(Cell target)
{
    if (target.Occupied && !target.excluded)
    {
        target.Right.populate();
        target.Left.populate();
        target.Top.populate();
        target.Bot.populate();

        target.Right.excluded = true;
        target.Left.excluded = true;
        target.Top.excluded = true;
        target.Bot.excluded = true;
        return true;
    }
    else
    {
        return false;
    }
}

excluded and already run are resetted to false everytime the algorithm has finished running all cells once. this is to prevent the call of walkOver() on a Cell updated in this walk.

now when i take my cell in the top left edge of my field (which continues like the simple snake field), mark it and run the algorithm, it stops changes after the first run through.

it actually updates the Cell in the designed way, but then just stops.

i save my cells into a static List in Program (i know i shouldn't but it's the easiest way to go until it works correctly). the cells have some panels to match. these panels are in a GroupBox named FieldArea. they are generated dynamically on the basis of some static constant settings (that you see in the set validation for coordinates).

I am sure the cells match to the panels correctly. this problem seems to occur in the diagonal through the FieldArea from top left (0,0) to bottom right. any other starting point works correctly. somehow when a larger amount of cells is coming from "the top" the cells form a border on the top and left edge of the field.

Question now is: what am i doing wrong? Why is my field not working correctly?

Solutions1

You must keep two copies of your "world", beacuse one must remain unchanged while you are applying the rules. If you apply the rules to one only world, this will result in a mixed configuration where some cells will have an old state, while others will already have the new one.

Therefore do something like this:

private Cell[,] activeWorld = new Cell[w,h];
private Cell[,] hiddenWorld = new Cell[w,h];

Populate(activeWorld);
while (true) {
    Display(activeWorld);
    ApplyRules(activeWorld, hiddenWorld);

    // Swap worlds
    var temp = activeWorld;
    activeWorld = hiddenWorld;
    hiddenWorld = temp;
}

The method ApplyRules must read the cells from 'activeWorld' and write the result to hiddenWorld.


UPDATE: Your actual design seems to be over-designed to me. A simple 2-d Boolean array telling whether a cell is occupied or not should be sufficient. Don't start with optimizations. This will most probably result in a complicated, hardly readable and faulty code. Instead focus your attention to the algorithm and to a good code structure. If later, you experience performance problems, analyze the problems and apply appropriate optimizations. In > 95% of the cases the problem is not related to coding details and algorithms but to I/O. In the case of this game, displaying the cells will probably take much more time than the application of the rules. And probably it will be too fast anyway and you will have to add a pause in the game loop.

Don't try to optimize away the logic of getting the indexes of the surrounding cells. It's not worth the pain.

One good way of solving the margin cells problem is to wrap the world around. Make things going out of sight on the right side reappear on the left side, and so on. Use the modulo operation (%) for this. x % N always yields a value in the range 0 ... N-1. You can get the coordinates of the 3 x 3 cells like this given an x and a y coordinate:

for (int dx = -1; dx <= +1; dx++) {
    int i = (x + dx + Width) % Width;
    for (int dy = -1; dy <= +1; dy++) {
        int j = (y + dy + Height) % Height;
        bool occupied = world[i, j];
        ...
    }
}

The + Width and + Height ensure that we always have positive values.

Solutions2

Alright, as promised here is my personal win-of-the week:

the above mentioned algorithm was "faulty"

unfortunately I was excluding cells, that weren't changed. and as I walked through the List from the "top left" the error showed up there.

i moved the exclusion to the die() and populate() functions.

public void die(){
    this.Occupied = false;
    this.correspondingPanel.BackColor = Color.Beige;
    this.excluded = true;
}

then i also had to make sure the loop gets correctly broken:

public Algorithm.walkOver(Cell target)
{
   if (target.Occupied && !target.excluded)
   {
       bool b = true;

   //if there could no changes be made, we also have to return there were no changes... 
   //else the while loop continues forever and we lose the process :(
       if (target.Right.Occupied && target.Left.Occupied 
           && target.Bot.Occupied && target.Top.Occupied)
       b = false;

       if(!target.Right.Occupied)
           target.Right.populate();

       if (!target.Left.Occupied)
           target.Left.populate();

       if (!target.Top.Occupied)
          target.Top.populate();

       if (!target.Bot.Occupied)
          target.Bot.populate();

       return b;
   }
   else
   {
      return false;
   }
}

I also moved the reset to the start of the while loop, as "chosing" a cell was excluding it.

Talk1:
If your problem is sloved, please, forget my comment.
转载于:https://stackoverflow.com/questions/20199935/game-of-life-what-is-with-this-algorithm

本人是.net程序员,因为英语不行,使用工具翻译,希望对有需要的人有所帮助
如果本文质量不好,还请谅解,毕竟这些操作还是比较费时的,英语较好的可以看原文

留言回复
我们只提供高质量资源,素材,源码,坚持 下了就能用 原则,让客户花了钱觉得值
上班时间 : 周一至周五9:00-17:30 期待您的加入