c# - 算法到 "spread"在 3D 数组上递减值

Question

我需要找到一个高效的算法来执行此操作:

byte[,] initialArray

0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   5   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   5   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0

对此:

byte[,] resultArray

0   0   0   1   2   1   0   0   0   0
0   0   1   2   3   2   1   0   0   0
0   1   2   3   4   3   2   1   0   0
1   2   3   4   5   4   3   2   1   0
0   1   2   3   4   3   2   1   0   0
0   1   2   2   3   2   1   0   0   0
1   2   3   2   2   1   0   0   0   0
2   3   4   3   2   1   0   0   0   0
3   4   5   4   3   2   1   0   0   0
2   3   4   3   2   1   0   0   0   0

发生了什么

初始数组有两个设置为初始值的单元格，其他单元格设置为 0。算法需要将该值“传播”到相邻单元格(没有对角线，只有上/下/左/右) .每次值传播到新的单元格时，该值都会减少 1，然后递归地再次传播。当该值达到 0 时它停止。

如果值传播到值 > 0 的单元格，则应保留两个值中的最大值，而不是简单地覆盖。

该示例显示的是 2D 数组，但我实际上使用的是 3D 数组。

我的尝试

我已经设法用 C# 编写了一个简单的递归算法。它可以工作，但效率肯定非常低。这是在具有 4 个初始单元且值 >= 10 的大型 3D 阵列上减速的方法。必须有更好的方法来执行此操作(对于那些熟悉的人，这是 Minecraft 游戏用来确定每个单元的光强度的方法游戏中的单元格。Minecraft 关卡阵列很大，可以包含许多光源)

我正在寻找执行此操作的最有效方法。这是我的 3D 数组的 C# 实现:

main ... {

    List<int[]> toCheck = new List<int[]>(); 

    // This list will keep a record of the initial cells that have a value > 0
    // For loop over each cell to find those with initial value > 0

    for (int x=0; x<worldX; x++){
        for (int y=0; y<worldY; y++){
            for (int z=0; z<worldZ; z++){

                if (data[x,y,z].light > 0)
                    toCheck.Add (new int[] {x,y,z});

            }
        }
    }

    // For each cell w/ initial value > 0, spread the light
    foreach (int[] i in toCheck) 
        SpreadLight(i[0],i[1],i[2],(byte)(data[i[0],i[1],i[2]].light - 1));


}


void SpreadLight(int x, int y, int z, byte light) {

    try {
        // Make sure this cells current value is smaller than the value we want to assign to it
        if (data[x,y,z].light < light) {
            data[x,y,z].light = (byte)light;
        }

        // If the value at this cell is > 0, get adjacent cells and spread the light to each of them
        if (light > 0) {
            int[][] adjBlocks = GetAdjacentBlocks(x,y,z);
            for (int i = 0; i < 6; i++) {
                SpreadLight(adjBlocks[i][0], adjBlocks[i][1], adjBlocks[i][2],(byte)(light-1));
            }
        }
    }
    catch { return; }  // I'm not proud if this, it's the easiest way I found to avoid out of array bounds error

}


// This method simply returns an array with the 3D coordinates of each adjacent cell
int[][] GetAdjacentBlocks(int x, int y, int z) {
    int[][] result = new int[6][];

    // Top
    result[0] = new int[] {x, y+1, z};
    // North
    result[1] = new int[] {x, y, z+1};
    // East
    result[2] = new int[] {x+1, y, z};
    // South
    result[3] = new int[] {x, y, z-1};
    // West
    result[4] = new int[] {x-1, y, z};
    // Bottom
    result[5] = new int[] {x, y-1, z};

    return result;
}

Answer 1

试试这个。以我的经验，一维阵列比二维阵列工作得快得多。还实现了计算的几个快捷方式。

二维版

class Program
{
    static void Main(string[] args)
    {
        Area A=new Area(10, 10);
        A[3, 4]=5;
        A[8, 2]=5;

        Console.WriteLine(A);
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   5   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        //0   0   5   0   0   0   0   0   0   0  
        //0   0   0   0   0   0   0   0   0   0  
        bool spread1=A.CheckSpread();

        Console.WriteLine();
        Console.WriteLine("Spreading...");
        A.Spread();
        bool spread2=A.CheckSpread();

        Console.WriteLine(A);
        //0   0   0   1   2   1   0   0   0   0  
        //0   0   1   2   3   2   1   0   0   0  
        //0   1   2   3   4   3   2   1   0   0  
        //1   2   3   4   5   4   3   2   1   0  
        //0   1   2   3   4   3   2   1   0   0  
        //0   1   2   2   3   2   1   0   0   0  
        //1   2   3   2   2   1   0   0   0   0  
        //2   3   4   3   2   1   0   0   0   0  
        //3   4   5   4   3   2   1   0   0   0  
        //2   3   4   3   2   1   0   0   0   0  
    }
}

public struct Area
{
    byte[] map;
    int rows, columns;

    public Area(int rows, int columns)
    {
        this.map=new byte[rows*columns];
        this.columns=columns;
        this.rows=rows;
    }
    public Area(Area other)
        : this(other.rows, other.columns)
    {
        Array.Copy(other.map, this.map, other.map.Length);
    }
    public Area(byte[,] array)
    {
        this.rows=array.GetLength(0);
        this.columns=array.GetLength(1);
        this.map=new byte[rows*columns];
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<columns; j++)
            {
                this.map[i*columns+j]=array[i, j];
            }
        }
    }

    public int Rows { get { return rows; } }
    public int Columns { get { return columns; } }
    public byte[] Map { get { return map; } }

    public byte this[int index]
    {
        get { return map[index]; }
        set { map[index]=value; }
    }
    public byte this[int row, int column]
    {
        get { return map[row*columns+column]; }
        set { map[row*columns+column]=value; }
    }

    public byte[,] ToArray2()
    {
        byte[,] array=new byte[rows, columns];
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<columns; j++)
            {
                array[i, j]=map[i*columns+j];
            }
        }
        return array;
    }

    public void Spread()
    {
        bool changed;
        do // CAUTION: This is not guaranteed to exit. Or is it?
        {
            changed=false;

            for (int k=0; k<map.Length; k++)
            {
                byte x=map[k];
                if (x<=1) continue; // cannot affect neighbors

                int i=k/columns;
                int j=k%columns;

                int k_N=i>0?(i-1)*columns+j:-1;
                int k_S=i<rows-1?(i+1)*columns+j:-1;
                int k_E=j<columns-1?i*columns+j+1:-1;
                int k_W=j>0?i*columns+j-1:-1;

                if (k_N>=0&&map[k_N]+1<x) { map[k_N]=(byte)(x-1); changed=true; }
                if (k_S>=0&&map[k_S]+1<x) { map[k_S]=(byte)(x-1); changed=true; }
                if (k_E>=0&&map[k_E]+1<x) { map[k_E]=(byte)(x-1); changed=true; }
                if (k_W>=0&&map[k_W]+1<x) { map[k_W]=(byte)(x-1); changed=true; }
            }

        } while (changed); 
    }

    public bool CheckSpread()
    {
        for (int k=0; k<map.Length; k++)
        {
            byte x=map[k];
            if (x<=1) continue; // cannot affect neighbors

            int i=k/columns;
            int j=k%columns;

            int k_N=i>0?(i-1)*columns+j:-1;
            int k_S=i<rows-1?(i+1)*columns+j:-1;
            int k_E=j<columns-1?i*columns+j+1:-1;
            int k_W=j>0?i*columns+j-1:-1;

            if (k_N>=0&&map[k_N]+1<x) return false;
            if (k_S>=0&&map[k_S]+1<x) return false;
            if (k_E>=0&&map[k_E]+1<x) return false;
            if (k_W>=0&&map[k_W]+1<x) return false;
        }
        return true;
    }

    public override string ToString()
    {
        string[] table=new string[rows];
        for (int i=0; i<rows; i++)
        {
            string[] row=new string[columns];
            for (int j=0; j<columns; j++)
            {
                row[j]= string.Format("{0,-3}", map[i*columns+j]);
            }
            table[i]= string.Join(" ", row);
        }
        return string.Join(Environment.NewLine, table);
    }
}

3D版

public struct Area3
{
    byte[] map;
    int rows, columns, pages;
    public Area3(int rows, int columns, int pages)
    {
        this.map=new byte[rows*columns*pages];
        this.columns=columns;
        this.rows=rows;
        this.pages=pages;
    }
    public Area3(Area3 other)
        : this(other.rows, other.columns, other.pages)
    {
        Array.Copy(other.map, this.map, other.map.Length);
    }
    public Area3(byte[, ,] array)
    {
        this.rows=array.GetLength(0);
        this.columns=array.GetLength(1);
        this.pages=array.GetLength(2);
        this.map=new byte[rows*columns*pages];
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<columns; j++)
            {
                for (int l=0; l<pages; l++)
                {
                    this.map[(l*rows+i)*columns+j]=array[i, j, l];
                }
            }
        }
    }
    public int Rows { get { return rows; } }
    public int Columns { get { return columns; } }
    public int Pages { get { return pages; } }
    public byte[] Map { get { return map; } }

    public byte this[int index]
    {
        get { return map[index]; }
        set { map[index]=value; }
    }
    public byte this[int row, int column, int page]
    {
        get { return map[(page*rows+row)*columns+column]; }
        set { map[(page*rows+row)*columns+column]=value; }
    }
    public byte[, ,] ToArray3()
    {
        byte[, ,] array=new byte[rows, columns, pages];
        for (int i=0; i<rows; i++)
        {
            for (int j=0; j<columns; j++)
            {
                for (int l=0; l<pages; l++)
                {
                    array[i, j, l]=map[(l*rows+i)*columns+j];
                }
            }
        }
        return array;
    }
    public void Spread()
    {
        bool changed;
        do
        {
            changed=false;

            for (int k=0; k<map.Length; k++)
            {
                byte x=map[k];
                if (x<=1) continue; // cannot affect neighbors

                int l=k/(rows*columns);
                int i=(k%(rows*columns))/columns;
                int j=(k%(rows*columns))%columns;

                int k_N=i>0?(l*rows+i-1)*columns+j:-1;
                int k_S=i<rows-1?(l*rows+i+1)*columns+j:-1;
                int k_E=j<columns-1?(l*rows+i)*columns+j+1:-1;
                int k_W=j>0?(l*rows+i)*columns+j-1:-1;
                int k_U=l<pages-1?((l+1)*rows+i)*columns+j:-1;
                int k_D=l>0?((l-1)*rows+i)*columns+j:-1;

                if (k_N>=0&&map[k_N]+1<x) { map[k_N]=(byte)(x-1); changed=true; }
                if (k_S>=0&&map[k_S]+1<x) { map[k_S]=(byte)(x-1); changed=true; }
                if (k_E>=0&&map[k_E]+1<x) { map[k_E]=(byte)(x-1); changed=true; }
                if (k_W>=0&&map[k_W]+1<x) { map[k_W]=(byte)(x-1); changed=true; }
                if (k_U>=0&&map[k_U]+1<x) { map[k_U]=(byte)(x-1); changed=true; }
                if (k_D>=0&&map[k_D]+1<x) { map[k_D]=(byte)(x-1); changed=true; }
            }

        } while (changed);
    }

}

没有为 3D 编码的可视化。