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


11

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ł)

wprowadź opis zdjęcia tutaj


Nadal będzie mógł poruszać się tylko o tę samą (całkowitą) odległość. Pytanie naprawdę polega na tym, aby dowiedzieć się, „jak daleko się skręca?” / „Ile trzeba skręcić?” / „ Gdzie trzeba skręcić?”. Prawdopodobnie musisz zacząć od ustalenia zwykłej ścieżki, a następnie cofnąć początek skrętu z powrotem dla kątów powyżej pewnej kwoty; zwróć uwagę, że końcowa odległość będzie dłuższa na linii prostej (ostatni zakręt) niż na krzywych.
Clockwork-Muse,

Tak, przejechana odległość jest głównym czynnikiem ograniczającym. Moją największą przeszkodą jest to, że muszę wziąć pod uwagę, że element może się obracać i kontynuować obracanie w dowolnym punkcie, do którego może dotrzeć, o ile nadal ma do dyspozycji dostępną odległość.
sfphilli

Co masz na myśli, zasięg, który jednostka może przesunąć? Masz na myśli punkty, do których może się przenieść? Czy znasz algebrę liniową (wektory)?
BlueRaja - Danny Pflughoeft

1
Jaki scenariusz z życia próbujesz wymodelować? Twój problem jest zbyt niejasny co do wymagań, co skutkuje zaproponowaniem zbyt wielu rozwiązań. Istnieją dobrze znane podejścia (praktycznie) do każdego konkretnego problemu w tej dziedzinie, ale wszyscy zgadują, który z wielu problemów faktycznie rozwiązujesz.
Pieter Geerkens

1
@PieterGeerkens Przypuszczam, że ponieważ OP nie żąda kodu, żądają algorytmu. I dostarczył wystarczająco dużo szczegółów na temat scenariusza, aby można było rozsądnie opracować algorytm. Jest to powszechne i dopuszczalne.
MichaelHouse

Odpowiedzi:


4

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.


Nie do końca, jak wyjaśnię tę koncepcję lub jak ją zrealizuję, ale z pewnością właściwe podejście.
Pieter Geerkens,

Rozumiem ten algorytm w obecnej postaci, że przejście przez węzeł musi być niezależne od ścieżki. Aby to osiągnąć, musisz dodać kolejny stopień swobody (kolejna oś, na której chcesz utworzyć węzły) poświęcony licowaniu. Innymi słowy, będziesz miał węzeł dla każdej kombinacji różnych X, Y, potencjalnie Z i Oblicowania. W przeciwnym razie znalezienie najkrótszej ścieżki do wejścia do węzła nie rozróżnia różnych okładzin po jego opuszczeniu. Czy to jest poprawne? Jeśli tak, to czy ta metoda jest prawdopodobnie zbyt intensywna?
TASagent

@TASagent: dobra uwaga, nie do końca to przemyślałem. Algorytm może być więc trochę nie w porządku, ale podejście powinno działać.
Sean Middleditch,

@PieterGeerkens: Zgadzam się, że to złe wytłumaczenie. Powinieneś udzielić własnej odpowiedzi, która wyjaśnia wszystko lepiej.
Sean Middleditch,

Wygląda na to, że jest bardzo blisko tego, czego potrzebuję, ale muszę przyznać, że nigdy nie słyszałem o tym algorytmie, więc nie wiem, jak uogólnić go na to, czego potrzebuję. Czy zdarza ci się mieć link do dobrych informacji lub samouczków na ten temat?
sfphilli

4

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.

wprowadź opis zdjęcia tutaj

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)


3

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.


1
To jest wspaniałe. Muszę zrobić trochę badań nad algorytmem i poeksperymentować z nim w mojej grze, ale to naprawdę wydaje mi się idealne dopasowanie, zwłaszcza, że ​​mogę uogólnić go na inne ważne części gry.
sfphilli

1

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ę.


Zdecydowanie chcę skorzystać z drugiej opcji, skręcając do (na przykład) 45 stopni w dowolnym i potencjalnie każdym punkcie wzdłuż ścieżki. Pojawią się także przeszkody, większe od pionów (pomyśl gigantyczne skały). Pierwotnie myślałem o tym, aby wygenerować stożek możliwych punktów końcowych, a następnie dla każdego z tych punktów końcowych wygenerować nowy stożek i tak dalej dla każdej możliwej lokalizacji, dopóki nie osiągnie maksymalnej odległości. To powiedziawszy, nie jestem do końca pewien, jak to zrobić bez szalonej nadmiernej komplikacji.
sfphilli,

Hmmm, wygląda na to, że byłem trochę niejasny co do niektórych szczegółów. Patrząc wstecz na pytanie, widzę, że określiłeś „turowe” i że jednostki mogą „obracać się lub poruszać” podczas swojej tury. Czy to oznacza zatem, że gracz planuje swoje działania wiele tur wcześniej, a ty chcesz robić poszukiwania ścieżki podczas ruchu? Pomocne byłoby dalsze wyjaśnienie, w jaki sposób powinien działać ruch.
TASagent

Nie, miałem na myśli to, że w danej turze gracz może albo obrócić swój kawałek na swoim miejscu, bez względu na to, jak daleko chce, lub może ruszyć w kierunku, w którym już patrzy. Jeśli się poruszają, mogą przejść określoną odległość wzdłuż ścieżki i mogą obracać się lub kierować do określonego kąta (na przykład od -45 do 45 stopni) podczas ruchu. Wyobraź sobie więc, że wybrana ścieżka wymagałaby krzywej, aby przejść w lewo lub w prawo. Ścieżka zostanie określona przez gracza, który wybierze punkt, do którego chce się przenieść, w zakresie możliwych punktów, z którymi mam problemy.
sfphilli

Ok, więc właściwie to brzmi, jak niestety, twoje pożądane cechy są prawdopodobnie zbyt restrykcyjne dla algorytmu Dijkstry, o którym mówimy powyżej: - \. Możliwie. Naszkicuję to na później, kiedy wrócę do domu.
TASagent

Być może zechcesz edytować niektóre z zebranych informacji, aby wyjaśnić problem w pierwotnym pytaniu, aby osoby, które przyjdą później, mogą zacząć od większej ilości informacji.
TASagent
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.