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


11

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.

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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.

wprowadź opis zdjęcia tutaj

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).

Odpowiedzi:


12

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%.

To dobra rada. Wadą jest to, że prawdopodobnie nie robi nic, aby chronić mnie przed nieskończenie małymi odbytnicami. Potrzebuję jakiegoś sposobu, aby ograniczyć, jak małe i jak duże są rektyki. Obecnie pracuję nad inną metodą. Porównuję wyniki i zaktualizuję.
AturSams

@ArthurWulfWhite Następnie twoje pytanie nie zostało określone i powinno zostać zaktualizowane. Minimalna wielkość pokoju zależy od rozdzielczości mapy-komórki; więc jeśli zrobisz to wystarczająco gruboziarniste, aby pomieścić minimalny rozmiar pokoju, możesz następnie dostosować osie na podstawie zmiennoprzecinkowej, przywracając bardziej organiczny wygląd.
Inżynier

Masz rację! Myślałem, że napisałem tę część. Ale ja nie. Przepraszam za ten błąd. Tak, jestem świadomy rozmiaru siatki. Pokój może być tak mały, jak pozwala na to siatka.
AturSams

OK - mam nadzieję, że znajdziesz odpowiednie rozwiązanie. BTW Miałem na myśli „dostosuj linie siatki”, a nie „dostosuj osie”.
Inżynier

1
Właściwie robię coś dokładnie takiego, luźno opartego na koncepcjach, o których myślałeś. Zamieszczę również wyniki tutaj.
AturSams

2

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):

wprowadź opis zdjęcia tutaj

Negocjowanie na osi x (2):

wprowadź opis zdjęcia tutaj

Negocjowanie na osi y (3):

wprowadź opis zdjęcia tutaj

Wynik (4):

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj


To było luźno zainspirowane wglądem @Nick Wiggill
AturSams

2
Można to jeszcze poprawić, najpierw łącząc losowo grupy n * m sąsiednich komórek w pojedynczy prostokąt. Maskuje to siatkę leżącą poniżej widoczną na powyższym wydruku. Negocjacje z tymi większymi prostokątami muszą teraz działać na wszystkich komórkach wzdłuż jednej z jego krawędzi.
DMGregory

DOBRZE. Nadal bardzo wiele granic kolinearnych, pracowałbym nad nimi dalej, ale dobrze, że znalazłeś swoje rozwiązanie! Cieszę się, że mogę pomóc.
Inżynier

@DMGregory Rozważyłem to, ale chciałem, aby stosunek między małymi i dużymi prostokątami był w pewnym stopniu spójny. Gdyby to była tekstura lub poziom, na pewno bym to zrobił (w rzeczywistości mam poprzedni przykład, który to robi).
AturSams

@NickWiggill Mogę całkowicie wyeliminować linie kolinearne. To tylko kwestia dostosowania algorytmu. Musi istnieć sposób na dalszą poprawę (aktualizacja najnowszej wersji)
AturSams
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.