Wyrównany podział przestrzenny osi: podzielić przestrzeń na losowe prostokąty?

Potrzebuję metody dzielenia przestrzeni 3D na losowe kształty pól wyrównanych do osi. Na razie obecnie dzielę przestrzeń 2d na potrzeby testowania. Najbardziej natychmiastowe podejście, jakie wymyśliłem, to zdefiniowanie prostokąta o rozmiarze (1, 1), a następnie rekurencyjne podzielenie wszystkich istniejących prostokątów na dwa nierówne prostokąty na przemian między osią X i Y.

Problem tutaj jest oczywisty. Takie podejście skutkuje długimi liniami rozciągania (zaznaczonymi na czerwono)

To, co chciałbym, to coś bardziej organicznego (podałem przykład)

Zobacz, żadnych długich prostych linii od góry do dołu lub od lewej do prawej.

Jedynym ograniczeniem jest to, że mogę chcieć ograniczyć minimalny rozmiar prostokąta bez wpływu na ziarnistość rozmiarów. tzn. jeśli najmniejszy prostokąt ma 1 centymetr kwadratowy, to w sekundach najmniejsze pomieszczenie nie powinno wynosić 2 jednostek kwadratowych.

Idealnie więc algorytm powinien spełniać wszystkie trzy następujące ograniczenia:

1. Prostokąty nie są nieskończenie małe.
2. Rozmiary prostokątów nie są dyskretnym pomnożeniem najmniejszego rozmiaru prostokąta. tzn. jeśli najmniejszy rekt ma 3 jednostki kwadratowe niż większe rekt nie są ograniczone do 6, 9, 12 itd. jednostek kwadratowych, a zamiast tego mogą wynosić 3,2 lub 4,7 w tym przypadku).
3. Algorytm działa w czasie wielomianowym (wymaga szybkiego obliczenia).

Podejście, które zarysujesz, jest proste i przydatne, ale cierpi z powodu strasznych artefaktów, jak pokazano. Unikaj tego. Potrzebujesz algorytmu równoległego wzrostu; w przypadku modelu jednowątkowego stosuje się podejście oparte na algorytmie round-robin:

1. Losowo umieszczaj różne punkty w obszarze mapy. Normalizuj ich rozkład (unikając brzydkiego skupiania) za pomocą rozkładu Gaussa lub stosując iteracyjny algorytm relaksacji, aby przesunąć losowo rozmieszczone punkty od siebie, zgodnie z relaksacją Lloyda dla diagramów Voronoi . Punkty te reprezentują centroidy twoich przyszłych pokoi.
2. (Runda równoległa / Powtórz dla wszystkich pomieszczeń) Z każdego punktu wyhoduj 4 wierzchołki na zewnątrz (pokój prostokątny), przesuwając się od punktu centralnego na każdą iterację globalną (możesz wyhodować różne pokoje w różnych prędkościach na każdej osi, a nie takie same dla wszystko i zobacz, jak to się potoczy - być może w celu uzyskania bardziej organicznych / zróżnicowanych wyników). W pewnym momencie niektóre z twoich prostokątów zaczną się dociskać do siebie. W tym momencie ogranicz wzrost w tej osi, upewnij się, że sąsiednie krawędzie dwóch pokoi dokładnie się dotykają i idź dalej.
3. Powtórz krok 2, zwiększając stopniowo każdy pokój, aż cały wzrost zostanie ograniczony przez sąsiednie pokoje lub granice mapy.
4. Nadal pozostanie kilka pustych miejsc. Problemem staje się teraz lokalizacja i tworzenie pomieszczeń z niezajętych przestrzeni. W rzeczywistości, jeśli twoja podstawowa przestrzeń to (indeksowana liczbą całkowitą) siatka (i każda iteracja wzrostu przyciąga się do tej siatki), wtedy jest to o wiele łatwiejsze do opanowania, ponieważ możesz utrzymywać listy zajętych i niezajętych komórek siatki: Po „ umieściłem i wyhodowałem wszystkie pokoje, przeszukuj niezajętą ​​listę w poszukiwaniu dyskretnych przestrzeni składających się z grup sąsiednich komórek. Ponieważ wiele nieużywanych przestrzeni będzie miało nieprostokątne kształty, musisz losowo wybrać komórkę z tej nieprostokątnej przestrzeni i urosnąć do jej maksymalnego rozmiaru, tak jak w przypadku pomieszczeń w kroku 2. Powtórz w obrębie tego non -prostokątna przestrzeń, aż do całkowitego wypełnienia.
5. Powtarzaj krok 4, aż twoja mapa będzie zajęta w 100%.

Jak widać udało mi się pozbyć świata tych artefaktów. Pomysł jest bardzo podobny.

1. Podziel przestrzeń 2d na niejednorodną siatkę. Jeśli dwie linie są zbyt blisko, usuń jedną.
2. Wybierz losowo prostokąt, sprawdź, czy został zmodyfikowany na osi y (na wysokości) i czy jego bezpośredni sąsiad został zmodyfikowany na osi y. Oba nie zostały zmodyfikowane, niech renegocjują odcinek między nimi (jeden przekaże trochę miejsca drugiemu).
3. Zrób to samo co w kroku 2 tylko tym razem na drugiej osi.
4. Powtarzaj proces, aż zmodyfikujesz jak najwięcej.

Siatka nierównomierna (1):

Negocjowanie na osi x (2):

Negocjowanie na osi y (3):

Wynik (4):