Algorytm do generowania krawędzi i wierzchołków na zewnątrz od początku z maksymalną wielokrotnością 3

Tworzę grę 2D na stronę internetową, na której wszechświat może stać się bardzo duży (w zasadzie nieskończenie duży). Początkowo wszechświat składa się z 6 gwiazd, które są w równej odległości od początku (0, 0). Moim zadaniem jest generowanie większej liczby gwiazd, które będą miały „ścieżki” (krawędzie), które się ze sobą połączą. Jak zaprojektować algorytm, który spełnia te ograniczenia:

Gwiazdy są losowo generowane na zewnątrz. (np. współrzędne (x, y) nowych gwiazd będą powoli wychodzić na zewnątrz od (0, 0) we wszystkich kierunkach, najlepiej w formacie spiralnym)
Krawędzie NIE przekroczą.
Chociaż powinna istnieć pewna wariancja, nowe gwiazdy nie powinny znajdować się zbyt daleko lub zbyt blisko innych gwiazd. (Np. Musi być minimalny promień)
Żadna gwiazda / punkt nie powinna mieć krotności większej niż 3.
Biorąc pod uwagę, że wszystko to będzie przechowywane w bazie danych, algorytm nie może być zbyt kosztowny. Innymi słowy, chciałbym osiągnąć coś o złożoności O (n) (nie wiem, czy jest to wykonalne).

Zasadniczo chodzi o galaktykę o spirali, w której gwiazdy są punktami na wykresie, a podróż między gwiazdami jest przedstawiona za pomocą krawędzi między tymi gwiazdami.

Konkretne kroki, które muszę rozwiązać, to:

Generuj losowo punkt w sąsiedztwie innych gwiazd, które nie mają jeszcze wielokrotności 3.
Znajdź pierwszą gwiazdę, która nie ma jeszcze wielokrotności 3, która nie spowoduje konfliktu krawędzi.
Jeśli gwiazda znajduje się w odległości co najmniej x jednostek, stwórz krawędź między dwoma punktami.

Próbowałem szukać rozwiązań, ale moje umiejętności matematyczne (i wiedza na temat teorii grafów) wymagają dużo pracy. Również wszelkie zasoby / linki w tej sprawie byłyby bardzo mile widziane.

Oto kilka pseudo-kodów, o których myślałem, ale nie jestem pewien, czy to w ogóle zadziałałoby i jestem pewien, że nie działałoby to zbyt dobrze po kilku 10.000 gwiazdkach itp.

newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
    for (star in the known universe):
        if(distance between newStar and star > x units):
            if(star has < 3 multiplicity):
                if(path from newStar to star does not intersect another path):
                    connect the star to the other star
                    break;

    newStar = new random (x, y) coordinate

Ponadto, jeśli ktoś ma jakieś porady na temat tego, jak powinienem przechowywać to w bazie danych MySQL, byłbym wdzięczny.

Na koniec, jeśli nic nie ma sensu powyżej, zamieściłem poniżej obraz tego, co chciałbym osiągnąć:

— John F.
źródło

Podróżnik tego wszechświata prawdopodobnie poruszałby się w jednym kierunku, co oznacza, że jeśli zabraknie gwiazd, będziesz musiał wygenerować gwiazdy we wszystkich kierunkach od początku. Innymi słowy, jeden znudzony użytkownik może uszkodzić bazę danych. Czy rozważałeś tę możliwość (zakładając, że może to stanowić problem)?

— Neil,

Kolejna myśl, że umieszczenie gwiazd nie musi być zapamiętane. Jeśli użyjesz odtwarzalnej generacji gwiazd, możesz wygenerować gwiazdy, które użytkownik może zobaczyć w taki sposób, że gwiazdy te będą generowane w ten sam sposób w przyszłości. Oznacza to, że Twoja baza danych musi tylko zapisywać informacje o gwiazdach. Jego pozycja to jego tożsamość.

— Neil

Co zrobisz, jeśli każda wygenerowana gwiazda ma dokładnie wielokrotność 3, więc krok 1 nie powiedzie się? Czy jest jakikolwiek błąd na twoim obrazie z wielokrotnością liczby 4?

— Doc Brown

Nie. Jeśli możesz generować gwiazdy w przewidywalny sposób, będzie tak, jakby zawsze tam były, jeśli odejdziesz, a następnie wrócisz. Tylko algorytm i ziarno się nie zmieniają.

— Neil

@JF See No Man's Sky . Facet dosłownie generuje wszechświat. Zapisuje tylko planety, które odwiedzili gracze, a jednak istniejące planety pozostają w tych samych miejscach. Wszystko opiera się na użyciu właściwego ziarna używanego do generowania liczb losowych.

— Neil

Sugestia: Utrzymuj sieć wewnętrznego wszechświata idealnie uporządkowaną, algorytmiczną i stosunkowo prostą. Potrzebujesz, aby wszechświat wyglądał losowo, gdy jest wyświetlany na ekranie użytkownika . Zastosuj tylko losowe przesunięcia do pozycji gwiazd w celu wyświetlenia przez użytkownika.

Problem: Najbardziej oczywiste podejście do obliczania losowego przesunięcia dla każdej gwiazdy nie da się dobrze ukryć pod prawdziwą strukturą. Możesz losowo wybierać gwiazdy tylko w niewielkiej ilości, zanim ryzykują kolizję ze sobą lub skrzyżowanie ścieżek.

Rozwiązanie: Możesz zastosować duże losowe zniekształcenia i uzyskać znacznie bardziej przypadkowy i interesujący wygląd wszechświata, jeśli zastosujesz skoordynowaną nielokalną losowość. Wyobraź sobie umieszczenie gwiazd na gumowym arkuszu i wyobraź sobie losowe rozciąganie i zgniatanie różnych części arkusza. To może przesunąć całe grupy gwiazd na dużą odległość. Nigdy się nie zderzą ani nie przekroczą, ponieważ pobliskie gwiazdy rozciągają się i kurczą względem siebie.

Jak to zrobić: sprawdź generatory fraktalnego terenu. Jest na to mnóstwo darmowego i otwartego kodu. Potrzebujesz tylko podstawowego kodu, który generuje wartość wysokości dla każdego punktu na mapie. Użyjemy tego w inny sposób. Użyj tego kodu, aby wygenerować DWIE niezależne mapy wysokości terenu. Zacznij od prawdziwej pozycji X, Y gwiazdy, spójrz na to miejsce na każdej mapie, użyj jednej wartości mapy, aby przesunąć pozycję wyświetlania gwiazdy X, a drugiej wartości mapy, aby przesunąć pozycję wyświetlania gwiazdy Y. Będziesz musiał grać z niektórymi czynnikami skalowania, ale może to dać ci losowo wypaczony efekt gumowej blachy. Duże różnice w położeniu gwiazdy powinny całkowicie ukryć leżące u podstaw uporządkowane pozycje. Fraktalna natura losowości daje bardzo naturalny efekt,

— Alsee
źródło