Generowanie losowych map - strategie rozpraszania / grupowania losowych węzłów

Robię prostą grę strategiczną 4X w kosmosie, w której każdy węzeł jest interesujący (planeta, asteroida itp.).

Aby losowo wygenerować mapę, wykonałbym poniższe kroki

1. Zdecyduj, ile rodzajów każdego węzła będzie miała mapa (być może, powiedzmy, 5 planet podobnych do Ziemi, 10 jałowych planet itp.)

2. Umieść każdy typ węzła na mapie.

W kroku 2 chciałbym mieć równomierny rozkład każdego typu węzła. Na przykład zacznę od umieszczenia wszystkich planet podobnych do ziemi. Jeśli po prostu zrobię rand (map.width, map.height) w celu ustalenia pozycji, mogę skończyć zgrupowaniem wszystkich planet podobnych do ziemi, co da przewagę graczowi, który zaczyna w tym obszarze.

Czy istnieją jakieś metody, takie jak użycie różnych funkcji wykresu lub funkcji szumu, które mogłyby wygenerować ciąg współrzędnych (x, y), które są od siebie oddalone. Podobnie, czy istnieją sposoby generowania współrzędnych, które są blisko siebie?

Problem, przed którym stoisz, polega na tym, że losowa selekcja nie dyskryminuje, a to może oznaczać, że nie pasuje idealnie do tego, co musisz zrobić. Ale istnieje co najmniej jeden łatwy sposób obejścia tego:

1. Podziel swoją przestrzeń na sektory (np. Jeśli masz powierzchnię 100 na 100 i musisz wygenerować 100 takich układów słonecznych, a następnie podziel swój obszar na siatkę sektorów 10 na 10)

2. Pętlę przez każdy sektor i powtórz krok 3 (który z kolei powtórzy krok 4 wiele razy)

3. Losowo określ liczbę planet dla bieżącego układu słonecznego (np. Dla zakresu od 3 do 7 planet, po prostu uzyskaj liczbę losową od 0 do 4 i dodaj 3) w bieżącym sektorze (jeśli masz więcej niż jedno słońce system w sektorze, tutaj należy ustawić kolejną pętlę)

4. Losowo przypisz swoje planety do bieżącego Układu Słonecznego określonego przez twoją pętlę (możesz również użyć liczb losowych, aby zwiększyć minimalne odległości między planetami); to tutaj decydujesz o typach planet, które można również losowo określić za pomocą różnych wag lub dowolną metodą, którą wolisz zastosować

Możesz także zdefiniować obszar „poza granicami” wokół krawędzi każdego sektora, aby zapobiec bezpośredniemu kontaktowi planet z sąsiednich sektorów (na wypadek, gdyby były one skutecznie losowo rozmieszczone obok siebie), lub. ..

Innym rozwiązaniem może być podjęcie decyzji o położeniu każdego układu słonecznego i / lub każdej planety, aby po prostu przeprowadzić szybkie sprawdzenie bliskości sąsiednich sektorów i odpowiednio dostosować (np. Oddalić się od krawędzi o minimalną odległość plus losową odległość ).

Najlepszym sposobem na zapewnienie równomiernego rozkładu jest traktowanie każdego węzła jako rodzaju cząsteczki fizycznej. Najpierw wykonaj losowy rozkład na ciągłej (zmiennoprzecinkowej) płaszczyźnie xy. Stosując siły odpychania między każdą odrębną parą pojedynczych cząstek na płaszczyźnie, przekonasz się, że powoli się rozsuwają. W pewnym sensie przypomina to rozwiązywanie kolizji, tyle że nie ma rzeczywistego kontaktu, o którym można by mówić. Łatwo jest zatem przekonwertować tę płaszczyznę („zrasteryzować” ją) z powrotem na siatkę indeksowaną liczbą całkowitą. Możesz po prostu zrobić to z siatki indeksowanej liczbami całkowitymi na początek, ale może być trochę trudniej uzyskać rzeczy „ładne” - zależy to od tego, jak wysoka rozdzielczość twojej siatki jest ... im wyższa, tym lepsza , w tym przypadku.

Oczywiście możesz również zastosować jakieś siły z krawędzi kwadratowej płaszczyzny, albo możesz znaleźć wiele cząstek „zmywających brzeg”. Alternatywnie możesz utworzyć pole znacznie większe niż potrzebujesz, a następnie zrobić migawkę jego niewielkiego obszaru - pozwala to uniknąć wyżej wspomnianego problemu.

Gdy chcesz, aby zapewnić przeciwnego, tzn klastrów nie występują, a następnie spójrz na „standardową” lub „Gaussa” dystrybucji. Dlatego losowo generowane pola gwiezdne często wyglądają na fałszywe; używają czystego losowego rozkładu zamiast bardziej naturalistycznego modelu dystrybucji.

Możesz użyć prostego algorytmu dystrybucji dysku Poissona, aby uzyskać rozkład „niebieskiego szumu”. Powoduje to, że punkty w płaszczyźnie są z grubsza rozmieszczone w równych odstępach od siebie. Działa to nie tylko w twoim przykładzie 2D, ale również w 3D, a także w przestrzeniach innych niż euklidesowe, ale obliczenia mogą szybko stać się nieporęczne.

Podstawową ideą tych algorytmów jest to, że zaczynasz od pierwszego punktu „początkowego”, a następnie ćwiczysz na zewnątrz, dodając losowe lub pseudolosowe punkty w pierścieniu między maksymalnymi i minimalnymi odległościami, które chcesz mieć od tego momentu, i eliminuj te, które leżą zbyt blisko siebie. Algorytm działa wtedy na zewnątrz w taki sposób, aż zostanie dodana ilość potrzebnych punktów (co daje mniej więcej okrągłą chmurę punktów) lub dostępna przestrzeń zostanie wypełniona.

Szybki i elegancki alternatywny algorytm do generowania takiego szumu 2D, a także krótkie omówienie jego właściwości, można znaleźć w „ Strukturze danych przestrzennych do szybkiego generowania próbek dysku Poissona ” Daniela Dunbara i Grega Humphreysa z Uniwersytetu z Wirginii.