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) coordinatePonadto, 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ąć:
źródło
Odpowiedzi:
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,
źródło