Algoritme saya yang mengekstrak kotak terbesar yang bisa dibuat dari kotak kecil, terlalu lambat

Bayangkan dunia berbasis kubus (seperti Minecraft, Trove, atau Cube World) di mana semuanya terdiri dari kubus berukuran identik dan semua kubusnya memiliki jenis yang sama .

Tujuannya adalah untuk mewakili dunia dengan jumlah kotak persegi paling sedikit (dengan menggabungkan kubus tetapi mempertahankan bentuk cembung (alias, bentuk kotak persegi panjang)). Algoritme saya berhasil dalam hal ini, tetapi kinerjanya terlalu lambat untuk tujuan yang dimaksudkan. Apakah ada algoritma yang lebih cepat?

Kode-pseudo-C # untuk algoritme saya pada dasarnya:

struct Coordinate { int x,y,z; }; //<-- integer based grid
HashSet<Coordinate> world; // <-- contains all the cubes

//width, height, and length represent how many cubes it spans
struct RectangularBox { Coordinate coord; int width,height,length; }

void Begin()
{
    List<RectangularBox> fewestBoxes = new List<RectangularBox>();
    while(world.Count > 0)
    {
         RectangularBox currentLargest = ExtractLargest();
         fewestBoxes.Add(currentLargest);
         world.RemoveRange(currentLargest.ContainedCubes());
    }
    //done; `fewestBoxes` contains the fewest rectangular boxes needed.
}

private RectangularBox ExtractLargest()
{
    RectangularBox largestBox = new RectangularBox();
    foreach (Coordinate origin in world)
    {
        RectangularBox box = FindMaximumSpan(origin);
        if (box.CalculateVolume() >= largestBox.CalculateVolume())
            largestBox = box;
    }
    return largestBox;
}

private RectangularBox FindMaximumSpan(Coordinate origin)
{
    int maxX, maxY,maxZ;
    while (world.Contains(origin.Offset(maxX, 0, 0))) maxX++;
    while (world.Contains(origin.Offset(0, maxY, 0))) maxY++;
    while (world.Contains(origin.Offset(0, 0, maxZ))) maxZ++;

    RectangularBox largestBox;
    for (int extentX = 0; extentX <= maxX; extentX++)
        for (int extentY = 0; extentY <= maxY; extentY++)
            for (int extentZ = 0; extentZ <= maxZ; extentZ++)
            {
                int lengthX = extentX + 1;
                int lengthY = extentY + 1;
                int lengthZ = extentZ + 1;
                if (BoxIsFilledWithCubes(origin, lengthX, lengthY, lengthZ))
                {
                    int totalVolume = lengthX * lengthY * lengthZ;
                    if (totalVolume >= largestBox.ComputeVolume())
                        largestBox = new RectangularBox(origin, lengthX, lengthY, lengthZ);
                }
                else
                    break;
            }
    return largestBox;
}

private bool BoxIsFilledWithCubes(Coordinate coord, 
    int lengthX, int lengthY, int lengthZ)
{
    for (int gX = 0; gX < lengthX; gX++)
        for (int gY = 0; gY < lengthY; gY++)
            for (int gZ = 0; gZ < lengthZ; gZ++)
                if (!world.Contains(coord.Offset(gX, gY, gZ)))
                    return false;
    return true;
}

Pada dasarnya, untuk setiap blok di dunia, pertama-tama ia menemukan berapa banyak blok religius yang ada di masing-masing dari tiga dimensi positif (+ X, + Y, + Z). Dan kemudian itu agak mengisi volume itu dan memeriksa mana yang merupakan isian terbesar yang tidak hilang blok.

Anda bisa memanfaatkan fakta itu kapan

 BoxIsFilledWithCubes(c,x,y,z)

mengembalikan true, maka tidak perlu memeriksa BoxIsFilledWithCubes(c,x+1,y,z)semua kubus dalam rentang koordinat "(c, x, y, z)" lagi. Anda hanya perlu memeriksa kubus tersebut dengan koordinat x baru c.x + (x+1). (Hal yang sama berlaku untuk y+1, atau z+1). Secara lebih umum, dengan membagi sebuah kotak menjadi dua kotak yang lebih kecil (yang Anda mungkin sudah tahu jika keduanya diisi dengan kubus, atau tidak keduanya diisi), Anda dapat menerapkan teknik membagi-dan-taklukkan di sini, yang menjadi lebih cepat daripada Anda pendekatan orisinal ketika Anda men-cache hasil antara.

Untuk mencapai ini, Anda mulai menerapkan BoxIsFilledWithCubes(c,x,y,z)secara rekursif, misalnya:

 bool BoxIsFilledWithCubes(coord,lx,ly,lz)
 {
     if(lx==0|| ly==0 || lz==0)
        return true;
     if(lx==1 && ly==1 && lz==1)
          return world.Contains(coord);
     if(lx>=ly && lx>=lz)  // if lx is the maximum of lx,ly,lz ....
         return BoxIsFilledWithCubes(coord,lx/2,ly,lz) 
             && BoxIsFilledWithCubes(coord.Offset(lx/2,0,0), lx-lx/2, ly, lz);
     else if(ly>=lz && ly>=lx)  
         // ... analogously when ly or lz is the maximum

 }

dan kemudian menggunakan memoisasi (seperti yang dibahas di sini ) untuk menghindari panggilan berulang BoxIsFilledWithCubesdengan parameter yang sama. Perhatikan bahwa Anda harus menghapus cache memoisasi ketika Anda menerapkan perubahan pada worldwadah Anda , seperti oleh world.RemoveRange. Meskipun demikian saya kira ini akan membuat program Anda lebih cepat.

Buat octree dengan ukuran leaf node aabb dari ukuran kotak Anda. Saat melintasi octree Anda bisa dengan murah menggabungkan node. Node yang benar-benar terisi sangat mudah untuk digabung (kotak baru = parent aabb), sedangkan untuk node yang terisi sebagian, Anda dapat menggunakan varian dari algoritma Anda saat ini untuk memeriksa kemampuan gabungan.

Anda tampaknya setidaknya O (n ^ 2) (lihat notasi O besar ) saat Anda mengulangi semua kotak di dunia di "Begin ()", maka untuk setiap kotak, Anda mengulangi semua kotak di dunia di ExtractLargest ( ). Jadi dunia dengan 10 kotak yang tidak terkait akan memakan waktu 4 kali lebih lama dari dunia dengan 5 kotak yang tidak terkait.

Karena itu Anda perlu membatasi jumlah kotak yang harus dilihat ExtractLargest (), untuk itu Anda perlu menggunakan beberapa jenis pencarian spasial , karena Anda bekerja di 3d, Anda mungkin perlu pencarian spasial 3d. Namun pertama-tama mulailah dengan memahami pencarian spasial 2d.

Kemudian pertimbangkan jika Anda akan memiliki banyak kotak di atas satu sama lain, jika tidak maka pencarian spasial 2d yang hanya mencakup x, y mungkin cukup untuk mengurangi perulangan Anda.

Octree / quadtree adalah salah satu opsi, tetapi ada banyak opsi lain untuk partisi ruang ,

Tetapi Anda mungkin bisa hanya menggunakan daftar array 2 dimensi ( Grid spatial index ), di mana semua kotak yang menutupi titik (a, b) berada dalam array [a, b] .list. Tapi yang paling menjilat adalah array yang terlalu besar, jadi bagaimana dengan array [mod (a, 100), mob (b, 100)] .list? Ini semua tergantung pada seperti apa data Anda .

(Saya telah melihat solusi grid bekerja dengan sangat baik di kehidupan nyata.)

Atau lakukan apa yang dikatakan Wilbert dengan sebuah octree dengan node daun ukuran aabb dari ukuran kotak Anda, tetapi nantinya Anda cenderung harus menemukan kotak yang ditunjuk oleh mouse pengguna, dll., Sekali lagi kasus pencarian spasial.

( Anda harus memutuskan apakah Anda hanya berusaha agar perangkat lunak ini berfungsi, atau jika Anda mencoba memahami bagaimana menjadi programmer yang lebih baik dan karenanya lebih tertarik pada pembelajaran daripada solusi cepat. )