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.
Aktualizacja: Ponieważ zdawałem się sugerować, że chodzi o silnik renderowania gry, chcę tylko wyjaśnić, że nie dotyczy to silnika renderowania gry; jest to konwerter plików; brak GUI.