All geek questions in one place

The algorithm of "propagation" of decreasing values ​​on a three-dimensional array

I need to find an efficient algorithm that does this:

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

For this:

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

What's happening

In the initial array there are two cells that are set to the initial value, the other cells are set to 0. The algorithm should “propagate” this value to neighboring cells (without diagonals, just up / down / left / right). Each time the value extends to new cell, the value decreases by 1 and propagates again, recursively. When the value reaches 0, it stops.

If the value extends to a cell with a value> 0, the largest of the two values ​​should be saved instead of simply overwriting.

The example shows a 2D array, but I'm really working with a 3D array.

My attempt

#. , . 3D- 4 >= 10. ( , , , Minecraft . Minecraft ).

. # 3D-:

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 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;
}
+4
3

. 1D- , 2D-. .

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.

+3

(2D) - ​​ . 3D :

class Program
{
    class ArrayPoint { public int x; public int y;}

    private static byte[,] startArray =
    {
        {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}
    };

    private static int rows = startArray.GetLength(0);
    private static int cols = startArray.GetLength(1);

    static void Main(string[] args)
    {
        Spread(startArray);
    }

    static void Spread(byte[,] array)
    {
        var points = GetStartPoints(array);

        foreach (var point in points.ToList())
            SpreadPoint(array, point.x, point.y);

        Display(array);
    }

    static void SpreadPoint(byte[,] array, int x, int y)
    {
        for (var i = x-1; i < x+2; i++)
            for (var j = y-1; j < y+2; j++)
                if (  (i==x || j==y) && !(i==x && j==y) && (i >= 0 && i < rows && j >= 0 && j < cols)
                    && array[i, j] + 1 < array[x, y])
                {
                    array[i, j] = (byte)(array[x, y] - 1);
                    SpreadPoint(array, i, j);
                }
    }

    static void Display(byte[,] array)
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
                Console.Write("{0} ",array[i,j]);
            Console.WriteLine();
        }
        Console.WriteLine();
    }


    static IEnumerable<ArrayPoint> GetStartPoints(byte[,] array)
    {
        for (var i = 0; i < rows; i++)
            for (var j = 0; j < cols; j++)
                if (array[i, j] != 0)
                    yield return new ArrayPoint {x = i, y = j};
    }
}

:

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
+2

My two cents: consider the possibility of expanding points simultaneously along wavefronts. Thus, individual wave fronts can be terminated if done earlier than others.

Simplified JavaScript Example:

var s = new Array(81)
for (var i=0; i<81; i++){
    s[i] = i == 40 ? 5 : 0
}

var max = 5, m = 9, n = 9

function expand(wavefront){ 
    while (wavefront.val > 0) {

        //Southwest
        var tmpLoc = wavefront.loc--
        for (var i=0; i<max - 1 - wavefront.val; i++){
            s[tmpLoc] = wavefront.val
            tmpLoc += n + 1
        }
        //Southeast...
        //...
        wavefront.val--
    }
}

expand({loc: 49, val: 4})

s now looks like this:

        [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,1,2,3,0,0,0,0,0
        ,0,0,1,2,0,0,0,0,0
        ,0,0,0,1,0,0,0,0,0
        ,0,0,0,0,0,0,0,0,0]
0
source

Source: https://habr.com/ru/post/1529115/

More articles:


All Articles