Mój algorytm, który wyodrębnia największe pudełko, które można zrobić z mniejszych pudełek, jest zbyt wolny

Wyobraź sobie świat oparty na kostkach (taki jak Minecraft, Trove lub Cube World), w którym wszystko składa się z kostek o identycznych rozmiarach, a wszystkie kostki są tego samego rodzaju .

Celem jest przedstawienie świata z najmniejszą liczbą prostokątnych pudełek (poprzez łączenie kostek, ale zachowując wypukły kształt (inaczej prostokątny kształt pudełka)). Algorytmowi się to udaje, ale jego wydajność jest zbyt niska, aby osiągnąć zamierzony cel. Czy są szybsze algorytmy?

Kod pseudo-C # dla mojego algorytmu to w zasadzie:

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;
}

Zasadniczo, dla każdego bloku na świecie najpierw sprawdza, ile jest bloków zakaźnych w każdym z trzech pozytywnych wymiarów (+ X, + Y, + Z). A potem wypełnia tę objętość i sprawdza, które jest największym wypełnieniem, w którym nie brakuje żadnych bloków.

Możesz skorzystać z faktu, że kiedy

 BoxIsFilledWithCubes(c,x,y,z)

zwraca true, wtedy nie trzeba ponownie rejestrować BoxIsFilledWithCubes(c,x+1,y,z)wszystkich tych kostek w zakresie współrzędnych „(c, x, y, z)”. Musisz tylko sprawdzić te kostki za pomocą nowej współrzędnej x c.x + (x+1). (To samo dotyczy y+1, lub z+1). Mówiąc bardziej ogólnie, dzieląc pudełko na dwa mniejsze pudełka (dla których możesz już wiedzieć, czy oba są wypełnione kostkami, czy nie oba są wypełnione), możesz zastosować tutaj technikę dziel i zwyciężaj, która staje się szybsza niż twoja oryginalne podejście podczas buforowania wyników pośrednich.

Aby to osiągnąć, zacznij wdrażać BoxIsFilledWithCubes(c,x,y,z)rekurencyjnie, na przykład:

 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

 }

a następnie użyj funkcji zapamiętywania (tak jak to omówiono tutaj ), aby uniknąć powtarzających się połączeń BoxIsFilledWithCubesz tymi samymi parametrami. Pamiętaj, że musisz wyczyścić pamięć podręczną zapamiętywania po zastosowaniu zmiany w worldkontenerze, na przykład przez world.RemoveRange. Niemniej jednak sądzę, że przyspieszy to twój program.

Zbuduj oktawę o wielkości aabb węzła liścia wielkości twojego pudełka. Podczas przemierzania oktetu można tanio łączyć węzły. Całkowicie wypełnione węzły są łatwe do scalenia (nowe pole = nadrzędny aabb), natomiast w przypadku częściowo wypełnionych węzłów można użyć wariantu bieżącego algorytmu do sprawdzenia możliwości scalenia.

Wydajesz się mieć co najmniej O (n ^ 2) (patrz duża notacja O ), gdy przeglądasz wszystkie pola na świecie w „Begin ()”, a następnie dla każdego pola zapętlasz wszystkie pola na świecie w ExtractLargest ( ). Tak więc świat z 10 niepowiązanymi pudełkami zajmie 4 razy dłużej niż świat z 5 niepowiązanymi pudełkami.

Dlatego musisz ograniczyć liczbę pól, które musi przeglądać ExtractLargest (), aby to zrobić, musisz użyć pewnego rodzaju wyszukiwania przestrzennego , ponieważ pracując w 3D, możesz potrzebować wyszukiwania przestrzennego 3D. Jednak najpierw zacznij od zrozumienia wyszukiwania przestrzennego 2D.

Zastanów się, czy kiedykolwiek będziesz mieć wiele pól nad sobą, a jeśli nie, wówczas 2d przestrzenne wyszukiwanie, które obejmuje tylko x, y może wystarczyć do zmniejszenia pętli.

Octree / quadtree są jedną z opcji, ale istnieje wiele innych opcji partycjonowania przestrzeni ,

Ale możesz być w stanie po prostu użyć dwuwymiarowej tablicy list ( indeks przestrzenny siatki ), w której wszystkie pola pokrywające punkt (a, b) znajdują się w tablicy [a, b] .list. Ale najprawdopodobniej doprowadziłoby to do zbyt dużej tablicy, więc co z tablicą [mod (a, 100), mob (b, 100)]. List? Wszystko zależy od tego, jakie są twoje dane .

(Widziałem, że rozwiązanie gridowe działa bardzo dobrze w prawdziwym życiu).

Lub zrób to, co mówi Wilbert, używając oktetu z węzłem liścia o wielkości aabb wielkości twojego pudełka, ale później prawdopodobnie będziesz musiał znaleźć pudełko, na które wskazuje mysz użytkownika itp., Po raz kolejny przypadek wyszukiwania przestrzennego.

( Musisz zdecydować, czy po prostu próbujesz uruchomić to oprogramowanie, czy próbujesz zrozumieć, jak być lepszym programistą, a zatem bardziej interesuje Cię nauka, niż szybkie rozwiązanie ).