Jaka jest dobra metoda losowego generowania krawędzi między węzłami wykresu?

Robię losowy generator map dla kosmicznej gry 4X.

Każdy węzeł w grze jest umieszczony w losowej (x, y) współrzędnej na siatce 2d. Węzeł może mieć jedną lub więcej dwukierunkowych krawędzi do innego węzła (reprezentujących tunele czasoprzestrzenne). Wszystkie węzły muszą mieć co najmniej jeden tunel czasoprzestrzenny, a wszystkie węzły muszą należeć do tego samego wykresu.

Idealnie, tunel czasoprzestrzenny nie powinien przekraczać maksymalnej długości, a jeśli to możliwe, tunele czasoprzestrzenne nie powinny się krzyżować.

Moją naiwną implementacją jest iteracja przez wszystkie węzły i połączenie węzła z najbliższymi 3 węzłami. Skończyłem jednak na licznych pod wykresach. Jaka jest dobra metoda generowania krawędzi dla węzłów?

Oto dobra odpowiedź na podobne pytanie.

Najpierw utwórz połączony wykres, być może używając minimalnego drzewa opinającego jak w powyższym linku. Sugeruje użycie losowych wag krawędzi, aby losowe „minimalne” drzewo było losowe. Następnie możesz losowo dodać więcej krawędzi, aby nie było to tylko minimalne drzewo. To, jak dokładnie dodasz losowe krawędzie, zależy od tego, jakiego rodzaju wykres chcesz.

W rzeczywistości, jeśli problemem jest tylko upewnienie się, że wszystkie węzły należą do tego samego wykresu, możesz wziąć swoją bieżącą metodę generowania losowego (lub dowolną inną) i zastosować na niej algorytm Prim. Jeśli chcesz wprowadzić minimalne zmiany na wykresie, aby upewnić się, że wszystkie podsgrafy są połączone, możesz ustawić koszt krawędzi na 0 dla krawędzi, które już tam są.

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.

1. Losowo utwórz pełną chmurę punktów.
2. Delaunay-trianguluje to.
3. 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.
4. 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ą.