从元胞自动机模拟中获取特定的单元格组

Question

我正在 Unity 中制作一款游戏，玩家可以从我的模拟中删除一些单元格。
假设所有单元格仅通过其邻居连接到顶行。
玩家进来并删除单元格，创建一组分开的单元格。我想得到它们。
作为下图中玩家删除绿色单元格后的示例，我想获取红色周边的单元格。

Answer 1

好吧，它非常广泛，并且在很大程度上取决于您的数据结构。我能想到的快速而肮脏但直接的是

对于每个单元存储它的邻居——这显然是你在创建板时必须设置的东西——比如

public class Cell
{
    public bool Enabled;

    public Vector2Int position;

    public Cell top;
    public Cell bottom;
    public Cell left;
    public Cell right;
}

然后你可以通过

收集所有启用的单元格组

遍历整个电路板并找到第一个启用的单元格
创建一个新组
将此单元格添加到组中
每四个方向检查是否有另一个启用的单元格
如果是，加入组并重复最后一步
如果您第二次遇到单元格（=当它们已经在组中时），请忽略它们
如果在所有方向上都没有更多已启用的单元格不在组中，您就完成了
返回第一步但跳过任何组中已有的单元格
当你到达棋盘的尽头时你就完成了

在代码中这可能有点像

// Assuming you have a board grid like
private Cell[,] grid = new Cell[width, height];

public List<HashSet<Cell>> FindGroups()
{
    var output = new List<HashSet<Cell>>();
    var alreadyTracked = new HashSet<Cell>();      

    // Iterate the grid
    for(var x = 0; x < width; x++)
    {
        for(var y = 0; y < height; y++)
        {
            var current = grid[x,y];

            // skip if not enabled
            if(!current.Enabled) continue;

            // skip if cell was already tracked in any group before
            if(alreadyTracked.Contains(current)) continue;

            // Create new group and fill it recursively
            var group = new HashSet<Cell>();

            current.FindConnectedEnabledCells(current, alreadyTracked, group);

            // Add that new group to the final output
            output.Add(group);
        }
    }

    return output;
}

// Finds all cells connected to the given cell that are enabled recursively
// and adds them to the given collections
private void GetConnectedEnabledCells(Cell current, HashSet<Cell> alreadyTracked, HashSet<Cell> group)
{
    // This cell is not enabled -> ignore
    if(!current.Enabled) return;

    // This cell is already in the group -> ignore
    if(group.Contains(current)) return;

    // Add the current cell to the collections itself
    group.Add(current);
    alreadyTracked.Add(current);

    // Recursively fetch all connected cells that are not null (e.g. Edge cells) and are enabled

    if(current.top?.Enabled) current.top.GetConnectedEnabledCells(cells);
    if(current.bottom?.Enabled) current.bottom.GetConnectedEnabledCells(cells);
    if(current.left?.Enabled) current.left.GetConnectedEnabledCells(cells);
    if(current.right?.Enabled) current.right.GetConnectedEnabledCells(cells);
}

然后因为您似乎已经知道顶行总是在那里，您可以忽略第一组，因为那是与您的“天花板”相连的组。

我不知道这是不是最有效的方法 ;)

您可能希望将 HashSet 替换为 List，具体取决于您的网格大小。对于大型集合，HashSet 在 Contains 中更好，但在 Add 中更差。

如果您认为对角线是“连接的”，则添加、填充并检查 Cell class.

中相应的额外四个单元格条目

注意：如果您的单元格 class 是 MonoBehaviour，则不用

if(current.top?.Enabled)

宁可使用

if(current.top && current.top.Enabled)

从元胞自动机模拟中获取特定的单元格组

Get specific groups of cells from a cellular automata simulation

c#

algorithm

cellular-automata

unity3d