Jak określić zakres możliwego ruchu w turowej grze strategicznej opartej na odległości?

Tworzę dwuwymiarową, turową grę strategiczną z wykorzystaniem c ++ i SFML-2.0. Ruch jest oparty raczej na odległości niż na siatce, z kilkoma różnymi trójkątnymi elementami, które w danym ruchu mogą się obracać w miejscu lub poruszać się do przodu.

Ruch będzie działał w taki sposób, że gracz wybierze miejsce, do którego element ma się przenieść, co generuje potencjalną ścieżkę do przejścia. Gdy gracz potwierdzi swoją decyzję, pionek przemieści się tą ścieżką do wybranej lokalizacji. Ścieżki są ograniczone przez dwa czynniki: odległość, jak daleko kawałek może się posunąć, biorąc pod uwagę wszelkie zakręty (więc jeśli istnieje krzywa, będzie to długość wzdłuż krzywej, a nie bezpośrednio od punktu do punktu); oraz kąt skrętu, jak daleko element może się obracać w dowolnym (i do każdego) punkcie podczas ruchu (na przykład od -30 do 30 stopni).

Moje pytanie brzmi: jak powinienem zająć się określeniem zakresu potencjalnych lokalizacji, w których gracz może wybrać, aby przesunąć kawałek?

Nie jestem do końca pewien, jakich równań i / lub algorytmu użyć tutaj. Mój pierwotny plan był niezwykle skomplikowany do tego stopnia, że ​​jego realizacja była prawie niemożliwa, nie mówiąc już o wyjaśnieniach, i jestem w tym momencie całkowicie zagubiony, gdy projekt utknął w martwym punkcie.

Jak mogę określić zasięg, który jednostka może przesunąć, biorąc pod uwagę jej promień skrętu?

Na przykład na poniższym obrazku. Czerwone, niebieskie i zielone linie miałyby taką samą długość. Fioletowy okrąg oznacza zakres ruchu, który jednostka może przesunąć. (Kształt jest prawdopodobnie niedokładna i linie prawdopodobnie nie są faktycznie tej samej długości, ale masz pomysł)

Wygeneruj pole przepływu lub odległości, używając Dijsktry.

Zasadniczo wypełnij siatkę za pomocą algorytmu Dijkstra bez miejsca docelowego (prawdopodobnie pod inną nazwą; nie wiem). Wystarczy wziąć każdy otwarty węzeł, obliczyć osiągalnych sąsiadów, pchnąć ich na otwartą listę, ustawić na zamkniętej liście, odpowiednio zaktualizować ścieżkę „następnego” węzła nadrzędnego itp. Określając koszt dotarcia do nowego węzła, należy wziąć pod uwagę ograniczenia skrętu.

Rezultatem będzie teraz, że masz sieć wszystkich swoich węzłów, aby wrócić do początku. Węzły, do których nie można dotrzeć, nie zostaną dotknięte przez pierwszy krok. Węzły, które można osiągnąć, będą miały obliczony element „następny węzeł wzdłuż najlepszej możliwej ścieżki do rodzica”, dzięki czemu można zarówno podświetlić wszystkie węzły, a następnie użyć tych informacji do wyświetlenia lub wykonania ścieżki ruchu, gdy użytkownik unosi się lub klika zaznaczone obszary.

Brutalną siłą byłoby:

1. Utwórz okrąg wierzchołków wokół jednostki, z jednostką pośrodku. Promień koła to maksymalna odległość ruchu. Gęstość wierzchołków może się zmieniać w zależności od tego, jak szczegółowy ma być końcowy wynik.
2. Dla każdej pozycji wierzchołka zasymuluj ruch jednostki kierującej w kierunku tej pozycji. Odbywa się to w ciasnej pętli bez renderowania.
3. Po osiągnięciu maksymalnej odległości w symulacji sterowania, przesuń wierzchołek do punktu symulowanej jednostki. Ten punkt jest najbliżej jednostki, która może dostać się do tego wierzchołka, zanim skończy się obecny obrót. To powoduje zmniejszenie koła do rozmiaru rzeczywistego ruchu.
4. Użyj tych wierzchołków wraz z wierzchołkiem wycentrowanym na jednostce, aby utworzyć renderowany okrąg i narysować możliwe odległości ruchu.

Tak więc, zaczynając od niebieskiego koła, przetwarzacie ścieżki, a kończąc na fioletowym kółku. Następnie możesz użyć tych punktów z punktem środkowym na urządzeniu, aby czerwone trójkąty były wymagane do wyświetlenia kształtu. (Samo zrobienie tego obrazu uświadamia mi, że ten kształt jest nieprawidłowy, ale interesujące będzie zobaczenie, co jest właściwie poprawne)

Zamierzam rozwinąć rozwiązanie Seana w osobnej odpowiedzi, ponieważ reprezentuje ono inne podejście niż początkowo proponowałem.

To rozwiązanie jest prawdopodobnie najbardziej dostępną metodą. Wymaga podzielenia środowiska na węzły. Tak, jest to ponowne wprowadzenie podejścia opartego na siatce, ale można to zrobić stosunkowo dobrze lub zastosować do szerokiego wyszukiwania ścieżek z dokładniejszym pozycjonowaniem obsługiwanym w węźle. Im bardziej zgrubna jest struktura węzła, tym szybsze jest wyszukiwanie ścieżki.

Dużym problemem jest to, że tak naprawdę masz do czynienia ze stawianiem czoła statkom, więc wielu tradycyjnych rozwiązań wyszukiwania ścieżek nie można używać bez modyfikacji. Zazwyczaj są one zależne od ścieżki, ponieważ nie dbają o to, jak dotarłeś do węzła, w którym się znajdujesz. Działa to dobrze, gdy przyspieszanie, zwalnianie i skręcanie są natychmiastowe i bezpłatne. Niestety dla ciebie zawracanie nie jest darmowe. Ponieważ jednak w tym uproszczeniu istnieje jedna dodatkowa informacja, możemy zakodować ją jako inną zmienną. W fizyce byłoby to znane jako przestrzeń fazowa.

Zakładając na razie 2-wymiary, możesz ekstrapolować dla 3:

Zwykle potrzebujesz jednego węzła dla każdego dopuszczalnego, dyskretnego położenia współrzędnych. Na przykład:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Itd. Zbudowałbyś nodegraph sąsiednich punktów i połączyłeś je przy pomocy przestrzennego sąsiedztwa. Następnie użyłbyś algorytmu Dijkstry, zabijając węzły, które przekraczają dopuszczalną wartość ruchu dla tury, dopóki nie będzie żadnych nieodkrytych, żywych węzłów pozostających połączonych z badanymi węzłami. Każdy węzeł śledzi najmniejszą odległość wymaganą do jego osiągnięcia.

Aby rozszerzyć tę metodę na użyteczną z Obracaniem, wyobraź sobie ten sam nodegraph w 3 wymiarach. Kierunek Z odpowiada obrotowi / skierowaniu i jest cykliczny, co oznacza, że ​​jeśli będziesz podróżował w kierunku + Z, wrócisz do miejsca, w którym zacząłeś. Teraz węzły odpowiadające sąsiednim pozycjom są połączone tylko w poprzek powierzchni, która odpowiada temu kierunkowi. Powtarzasz jak zwykle węzły połączone z już zbadanymi węzłami. W tym schemacie zalecałbym ograniczenie do N, NE, E, SE, S, SW, W, NW.

To rozwiązanie powie ci wszystkie dostępne regiony przestrzeni, a także najlepszą drogę, aby się tam dostać, ile rotacji masz, kiedy tam dotrzesz, i wszystkie orientacje, które możesz mieć, kiedy tam dotrzesz.

Następnie, kiedy faktycznie wykonujesz ścieżkę, możesz dowolnie interpolować / sześcienny splajn, aby wyglądał bardziej autentycznie.

Wygląda na to, że musisz najpierw zdecydować, jak dokładnie chcesz włączyć pracę w podróży. Opcje takie jak:

• Jeśli poruszają się w obrębie stożka, najpierw obróć, a następnie zacznij się poruszać. Jest to łatwiejsze rozwiązanie do wdrożenia i ścieżki. Jest również mniej interesujący, więc nie chciałbym go używać.

• Ciągłe obracanie podczas ruchu, do 45 stopni. Ten jest o wiele trudniejszy i mam nadzieję, że ten, którego szukasz. Integracja numeryczna na ścieżce przy użyciu ustalonego czasu jest prawdopodobnie najłatwiejszym sposobem na zbliżenie się do tego. Twój stożek będzie ograniczony maksymalnym (+ X stopni co krok) i minimalnym (-X stopni co krok) obrotem.

To, jak najlepiej przejść przez przestrzeń kosmiczną przy drugim z tych wymagań, zależy w dużej mierze od środowiska, w którym będą się poruszać. Jeśli istnieje wiele przeszkód, które trzeba pokonywać, sprawy mogą stać się naprawdę trudne i bardzo drogie. Jeśli jednak nie ma, możesz obrócić ładunek od przodu (a nawet zwężać) obrót, aby skończyć w żądanym miejscu.

Mam wrażenie, że mogłem tylko częściowo omówić tematy, o które zadałeś pytanie, więc dodaj komentarze w komentarzach i mogę rozszerzyć dyskusję.