Moja najnowsza gra odbędzie się na małej planetoidie. Szukam dobrej struktury danych do reprezentowania komórek na powierzchni kuli. Trójkąty, kwadraty, pięciokąty, sześciokąty? Który z nich najbardziej ogranicza rozciąganie i tworzy najlepsze kafelki?
Mapowanie sferyczne jest najłatwiejsze, ale rozciąganie na biegunach jest niedopuszczalne. Tworzenie kostek jest również dość łatwe, ale w pobliżu rogów sześcianu nadal byłby znaczny rozciągnięcie. Podział dwudziestościanu wydaje się najlepszy pod względem rozciągania, ale istnieje problem z indeksowaniem wielu trójkątnych układów i znalezienie sąsiadujących komórek na granicach byłoby trudne.
Wydaje mi się, że przydałby mi się pojedynczy liniowy układ punktów reprezentujących N-gony, każdy z tablicą wskaźników N sąsiadów, ale to wydaje się ogromną stratą miejsca.
Gra ma elementy RTS, więc będę przechowywać takie rzeczy, jak mapy wpływów oraz przeprowadzanie wyszukiwania i konwertowania ścieżki A *, więc reprezentacja musi być wydajna.
Odpowiedzi:
Okej, dla każdego zainteresowanego tym tematem opiszę teraz wybrane rozwiązanie. Dziękujemy wszystkim, którzy odpowiedzieli i dali mi pomysły.
Po pierwsze, dla „najlepszego” teselacji jako punkt wyjścia wybiorę ścięty dwudziestościan . Podzielenie go prowadzi do bardzo ładnego mozaikowania sześciokątów z 12 pięciokątami zapewniającymi krzywiznę. Ponadto kontynuacja podziału na podwójny da mi bardzo dobrą trójkątną siatkę do renderowania z ładnymi właściwościami. Odnośnie 12 pięciokątnych komórek: mogę je zignorować, uczynić je wyjątkowymi (tak jak jedyne miejsca, w których można zbudować bazy) lub ukryć je pod scenerią.
Sześciokątne i pięciokątne komórki będą przechowywane w strukturze danych o połowie krawędzi dla łatwego dostępu do sąsiadów i szybkiego przejścia. Jedyną trudną częścią jest ustalenie, w której komórce znajduje się dany punkt świata, ale można tego dokonać, zaczynając od losowej komórki i idąc w kierunku punktu przez sąsiadów.
Mam nadzieję, że ktoś uzna te informacje za przydatne. Wiele się nauczyłem i nie mogę się doczekać, aby uzyskać pewne wyniki.
Edytować:
Oto obraz pokazujący wynik mojego podziału dwudziestościanu i podwójnego przełączania siatki przy użyciu struktury danych o połowie krawędzi.
Mogę zrobić kilka iteracji relaksacyjnych, aby obszary komórek były jeszcze bardziej jednolite.
źródło
Istnieje sposób, aby to zrobić raczej elegancko, opierając się na dzieleniu dwudziestościanu, jak sugerowałeś w swoim pytaniu. Dwudziestościan składa się z 20 równobocznych trójkątów, które można pogrupować w 5 zestawów, przy czym 4 trójkąty w zestawie tworzą kształt równoległoboku:
(Grupy czterech trójkątów z przeciągniętym przez nie zawijakiem to równoległoboki, o których mówię. Strzałki mówią, które krawędzie byłyby sklejone ze sobą, aby złożyć to w dwudziestościan).
Jeśli te trójkąty są podzielone na mniejsze trójkąty, cały równoległobok może być indeksowany jak tablica prostokątna n przez 4n (n = 4 w przykładzie):
Liczby w każdej komórce są numerami kolumn prostokątnego układu. Zasady znajdowania sąsiadów w tablicy są dość proste: poziomymi sąsiadami są tylko plus lub minus 1 kolumna, podczas gdy pionowy sąsiad jest albo minus jeden rząd i plus jedna kolumna, albo plus jeden rząd i minus jedna kolumna, w zależności od tego, czy numer kolumny jest odpowiednio parzysty lub nieparzysty.
Jednak nadal musisz napisać kod specjalnego przypadku, aby znaleźć sąsiadów, którzy przekraczają granicę od jednego równoległoboku do drugiego. Jest to nieco skomplikowane, ponieważ w niektórych miejscach góra lub dół jednego równoległoboku będzie połączony z bokiem drugiego, lub góra i dół zostaną połączone z poziomym przesunięciem między nimi itp. Prawdopodobnie struktura pół krawędzi lub podobne przydatne byłyby tu równoległoboki. Jednak przynajmniej relacje są symetryczne między wszystkimi 5 równoległobokami: wszystkie mają ten sam wzór, w którym strona jest połączona z którą drugą stroną swoich sąsiadów.
źródło
Hmmm - komentarze na temat rozciągania wskazują, że poruszasz się między mapowaniem sferycznym i planarnym, co prowadzi do zniekształceń na biegunach
Jeśli chcesz, aby płytki były płaskie i jednolite, masz rację, że dwudziestościan, a konkretnie dwudziestościan ścięty, jest dość powszechny
Możesz znaleźć wszystkie różne mapowania tutaj - Kuliste Wielościany na wikipedii
Jeśli chodzi o utrzymywanie relacji między twarzami, jest to problem topologiczny - może być pomocna albo skrzydlata krawędź, albo czworokątna krawędź (i masz wspaniałą okazję poznać zupełnie nową formę algebry) Winged Edge
źródło
Chyba spóźniam się trochę na przyjęcie, ale oto możliwe rozwiązanie, które można wykorzystać do utrzymania kulistego świata o dowolnym rozmiarze i jednolitym wyglądzie.
Kluczową rzeczą do zrozumienia tutaj jest to, że świat nie jest płaski, a zatem 100% jednolite kafelkowanie byłoby niemożliwe (wynika to z tak zwanego twierdzenia Hairy Ball ). Należy dopuścić pewne nieprawidłowości, a najlepsze, na co możemy liczyć, to równomierne rozłożenie tych nierówności na powierzchni, tak aby każda była jak najmniejsza.
W rzeczywistości jest to dość łatwe w sposób niedeterministyczny. Najpierw wybierz równomiernie N losowych punktów wokół powierzchni. Upewnij się, że te punkty są w rzeczywistości jednakowe (patrz Zbieranie punktów kuli , wzory 9-11). W drugim etapie sprawiamy, że punkty te są mniej losowe i bardziej jednolite: zakładamy, że wszystkie te punkty mają ujemny ładunek elektryczny, aby się wzajemnie odpychały. Symuluj ruch punktów przez kilka kroków, aż zbiegną się one w stan równowagi. Ta końcowa konfiguracja punktów da ci siatkę, która jest prawie równomiernie rozmieszczona na powierzchni kuli.
źródło