Mein Algorithmus, der die größte Box extrahiert, die aus kleineren Boxen erstellt werden kann, ist zu langsam

9

Stellen Sie sich einen Würfel basierten Welt (wie Minecraft, Trove oder Cube World) , wo alles gleich großer Würfel aus und alle Würfel sind von der gleichen Art .

Das Ziel ist es, die Welt mit der geringsten Anzahl rechteckiger Kästchen darzustellen (indem Würfel zusammengeführt werden, aber die konvexe Form beibehalten wird (auch bekannt als rechteckige Kastenform)). Mein Algorithmus ist erfolgreich, aber seine Leistung ist zu langsam für den beabsichtigten Zweck. Gibt es schnellere Algorithmen?

Der Pseudo-C # -Code für meinen Algorithmus lautet im Grunde:

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

Im Wesentlichen wird für jeden Block auf der Welt zunächst ermittelt, wie viele zusammenhängende Blöcke sich in jeder der drei positiven Dimensionen befinden (+ X, + Y, + Z). Und dann füllt es das Volumen irgendwie mit Flut und prüft, welche Füllung die größte ist, bei der keine Blöcke fehlen.


Update: Da ich anscheinend angedeutet habe, dass dies für die Rendering-Engine eines Spiels ist, möchte ich nur klarstellen, dass dies nicht für die Rendering-Engine eines Spiels gilt. Es ist für einen Dateikonverter. keine GUI.

Herr smith
quelle
2
Vielleicht besser geeignet für codereview.stackexchange.com
Rotem
4
@Rotem Vielleicht, aber ich suche tatsächlich nach alternativen Algorithmen und nicht nach einer Überprüfung meines Codes. Ich habe meinen Code nur aus Gewohnheit bereitgestellt.
Mr. Smith
Klar, macht Sinn.
Rotem
Algorithmusfragen sind eher für SE-Sites wie Informatik geeignet ...
Bakuriu
Dies hängt auch davon ab, wie oft Sie die Methode aufrufen. Wenn Sie es jeden Frame nennen oder nur, wenn sich ein Block ändert. Diese Spiele haben normalerweise Blöcke (Rechteck mit einer bestimmten Größe, z. B. 64 x 64 x 32 Blöcke), Cache-Werte so weit wie möglich und werden nur pro Block berechnet. Und berechnen Sie diese Werte nur für die sichtbaren Blöcke.
the_lotus

Antworten:

6

Sie können die Tatsache nutzen, dass wenn

 BoxIsFilledWithCubes(c,x,y,z)

Gibt true zurück, dann müssen nicht BoxIsFilledWithCubes(c,x+1,y,z)alle Würfel im Koordinatenbereich "(c, x, y, z)" erneut eingecheckt werden. Sie müssen diese Würfel nur mit der neuen x-Koordinate überprüfen c.x + (x+1). (Gleiches gilt für y+1oder z+1). Im Allgemeinen können Sie durch Aufteilen einer Box in zwei kleinere Boxen (für die Sie möglicherweise bereits wissen, ob beide mit Würfeln gefüllt sind oder nicht beide) eine Divide-and-Conquer-Technik anwenden, die schneller als Ihre wird ursprünglicher Ansatz, wenn Sie die Zwischenergebnisse zwischenspeichern.

Um dies zu erreichen, beginnen Sie mit der BoxIsFilledWithCubes(c,x,y,z)rekursiven Implementierung , zum Beispiel:

 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

 }

und verwenden Sie dann Memoization (wie hier beschrieben ), um wiederholte Aufrufe BoxIsFilledWithCubesmit denselben Parametern zu vermeiden . Beachten Sie, dass Sie den Memoization-Cache leeren müssen, wenn Sie eine Änderung an Ihrem worldContainer vornehmen , z. B. by world.RemoveRange. Trotzdem denke ich, dass dies Ihr Programm schneller machen wird.

Doc Brown
quelle
5

Bauen Sie einen Octree mit einem Blattknoten auf, der ungefähr so ​​groß ist wie Ihre Box. Während Sie den Octree durchlaufen, können Sie Knoten kostengünstig zusammenführen. Vollständig gefüllte Knoten sind trivial zusammenzuführen (neues Feld = übergeordnetes aabb), während Sie für teilweise gefüllte Knoten eine Variante Ihres aktuellen Algorithmus verwenden können, um die Zusammenführungsfähigkeit zu überprüfen.

Wilbert
quelle
Dass zwei Knoten vollständig gefüllt sind, bedeutet nicht, dass sie zusammengeführt werden sollten. Es ist kein Schritt, um die größte Kiste zu finden. Wenn Sie sie zusammenführen, müssen Sie sie wahrscheinlich zu einem späteren Zeitpunkt erneut aufteilen, sobald das größte Feld gefunden wurde. Ich sehe nicht, wie ein Octree in diesem Szenario hilft.
Mr. Smith
Vollständige Knoten können in dem Sinne zusammengeführt werden, dass alle 8 untergeordneten Elemente Teil einer einzelnen größeren Box werden können. Diese größere Box muss später nicht mehr geteilt werden, kann aber zusammengeführt werden. Die Hierarchie ermöglicht es Ihnen, viele Felder schnell zusammenzuführen. Mit vollständig gefüllten Knoten können Sie ohne weitere Tests eine Ebene höher springen.
Wilbert
1

Sie scheinen mindestens O (n ^ 2) zu sein (siehe große O-Notation ), wenn Sie in „Begin ()“ alle Felder der Welt durchlaufen. In ExtractLargest () durchlaufen Sie für jedes Feld alle Felder der Welt. ). Eine Welt mit 10 nicht verwandten Boxen dauert also viermal länger als eine Welt mit 5 nicht verwandten Boxen.

Sie müssen daher die Anzahl der Felder, die ExtractLargest () betrachten muss, begrenzen. Dazu müssen Sie eine Art räumliche Suche verwenden. Da Sie in 3D arbeiten, benötigen Sie möglicherweise eine räumliche 3D-Suche. Beginnen Sie jedoch zunächst mit dem Verständnis der räumlichen 2D-Suche.

Überlegen Sie dann, ob Sie jemals viele Kästchen übereinander haben werden. Wenn nicht, kann eine räumliche 2D-Suche, die nur x, y abdeckt, ausreichen, um Ihre Schleife zu verringern.

Octree / Quadtree sind eine Option, aber es gibt viele andere Optionen für die Speicherpartitionierung .

Möglicherweise können Sie jedoch nur ein zweidimensionales Array von Listen ( räumlicher Rasterindex ) verwenden, wobei sich alle Felder, die den Punkt (a, b) abdecken, in der Array-Liste [a, b] befinden. Aber am lecksten würde das zu einem zu großen Array führen. Was ist also mit Array [mod (a, 100), mob (b, 100)]. List? Dies hängt alles davon ab, wie Ihre Daten aussehen .

(Ich habe gesehen, dass die Netzlösung im wirklichen Leben sehr gut funktioniert.)

Oder machen Sie das, was Wilbert sagt, mit einem Octree mit einem Blattknoten, der ungefähr so ​​groß ist wie Ihre Box, aber später müssen Sie wahrscheinlich die Box finden, auf die die Maus des Benutzers zeigt, usw., wieder ein Fall von räumlicher Suche.

( Sie müssen sich entscheiden, ob Sie nur versuchen, diese Software zum Laufen zu bringen, oder ob Sie verstehen möchten, wie man ein besserer Programmierer ist, und daher mehr am Lernen als an einer schnellen Lösung interessiert sind. )

Ian
quelle