Główne ograniczenia twojego problemu są dwojakie: tworzenie wykresu połączonego 1; i tworzenie go za pomocą połączeń bliższych. Odpowiedź Filipa, choć w pewnym stopniu cenna, nie uwzględnia wszystkich ograniczeń twojego problemu
Idealnie, tunel czasoprzestrzenny nie powinien przekraczać maksymalnej długości, a jeśli to możliwe, tunele czasoprzestrzenne nie powinny się krzyżować.
Kiedy naiwnie łączysz punkty w chmurze, ryzykujesz (a nawet wysokie), że te warunki nie zostaną spełnione.
Widzisz, problem nie polega na łączności, ale na bliskości tych połączeń. Łączy każdy węzeł na wykresie z każdym innym węzłem, ale łączenie tylko z tymi, które są najbliżej, przy jednoczesnym zachowaniu 1-połączenia całego wykresu jest nieco trudniejsze.
To właśnie tworzy triangulacja Delaunaya w wymiarach n . Pierwszym powodem zastosowania triangulacji Delaunaya jest to, że spełnia oba z nich w sposób dorozumiany. Drugi powód jest taki, że o wiele łatwiej jest pracować wstecz od takiego wykresu (odejmując niepotrzebne krawędzie i wierzchołki), niż próbować go utworzyć w inny sposób.
- Losowo utwórz pełną chmurę punktów.
- Delaunay-trianguluje to.
- Zbuduj wykres (połączenie punktów). W tym celu możesz najpierw wygenerować cały wykres (każdą gwiazdę), a następnie uzyskać wykres jako nieletni reprezentujący regiony połączone z tunelem czasoprzestrzennym, wykonując krok 4. Alternatywnie możesz pracować na odwrót, generując tylko regiony związane z tunelem czasoprzestrzennym najpierw jako węzły supergrafinowe, a następnie w drugiej fazie, generują pojedyncze gwiazdy w obrębie ograniczających objętości tych regionów (dla nich wyprowadziłbym podwójny wykres triangulacyjny Delaunaya - diagram Voronoi w 3 wymiarach) jako subgrrafy. Teraz masz bliżej połączone gromady gwiazd, a wszystkie gromady są połączone rzadszymi tunelami czasoprzestrzennymi: twoja topologia i topografia mają sens dla gracza.
- Zastosuj inteligentne metody kształtowania super- i subgrafów, w zależności od tego, jak wybrałeś leczenie w kroku 3.
Ważne jest, aby zobaczyć, że jest to proces hierarchiczny. Pierwszy poziom dotyczy połączeń tuneli czasoprzestrzennych; drugi dotyczy odległości, które przypuszczalnie można pokonać przy użyciu standardowego napędu statku. Możesz zastosować Delaunay na jednym lub obu poziomach, aby spełnić swoje ograniczenia.
Wykonanie tego czysto topologicznie pozostawi tunele czasoprzestrzenne, które nie mają sensu, ponieważ mogą łączyć jedną stronę galaktyki z drugą, pomimo dużej gęstości gwiazd pomiędzy nimi (a być może nawet spadając na bezpośrednią trasę tunelu czasoprzestrzennego). Topologia nie jest topografią; ta druga kwestia jest rozważana ponad pierwszą. Martwisz się bliskością, a tym samym topografią.