Znajdowanie możliwych ruchów bytu w grze 2d taflowej


10

Mam problemy ze znalezieniem konkretnego terminu do wyszukania tego, ale jak można znaleźć możliwe ruchy w strategicznej grze turowej 2D (tj. FF: Tactics, Fire Emblem, Advance Wars).

wprowadź opis zdjęcia tutaj

W tym momencie nie myślę zbytnio o terenie (ani nawet kolizji). Zastanawiam się tylko, jakiego algorytmu mogę użyć, aby dowiedzieć się, że istota X może przesunąć 5 płytek i zaatakować 2 dalsze płytki.

Wiem, że mogę użyć czegoś takiego jak Dijkstra, aby znaleźć odległość między dwoma punktami. Jedną z możliwych implementacji jest rozpoczęcie od lokalizacji gracza, a następnie rozgałęzienie stamtąd, aż odległość zwrócona przez Dijkstrę będzie większa niż liczba ruchów.

Zastanawiam się tylko, czy ktoś mógłby skierować mnie we właściwym kierunku (tj. Nazwy algorytmów, techniki, artykułów itp.).


Myślę, że to się nazywa szukanie ścieżki dla wyszukiwanego terminu? Jeśli korzystasz ze znajdowania ścieżki, możesz mieć liczniki do obsługi tego, czego potrzebujesz
Exikle

Jest to zasadniczo część wyszukiwania ścieżki (obliczanie metadanych dotyczących kosztów ruchu). Określasz tylko lokalizacje, które znajdują się w zasięgu, ale niekoniecznie określasz również trasę, którą wybierzesz.
Mario

1
To nie jest czas rzeczywisty (RTS), jeśli jest oparty na systemie FFTactics. : p
Alayric 9.09.13

W 2d można użyć kalkulacji Taxicab / Manhattan en.wikipedia.org/wiki/Taxicab_geometry
Gerben Jacobs

Odpowiedzi:


5

Myślę, że ograniczona Dijkstra jest dokładnie tym, czego chcesz użyć. Sposób, w jaki Dijkstra znajduje odległość między dwoma punktami, polega na odwzorowaniu odległości do każdego węzła od węzła początkowego, a następnie „wybraniu” najkrótszej ścieżki z tej mapy odległości. Chcesz zrobić praktycznie to samo, z wyjątkiem tego, że wykres węzła odległości tworzy on jako wynik, a nie ścieżkę do określonego punktu.

Jedną modyfikacją, którą chcesz wprowadzić, jest pominięcie obliczania odległości od węzłów, które już przekroczyły maksymalny zasięg ruchu. Następnie otrzymasz wykres węzłów wszystkich węzłów, do których jednostka może podróżować, oraz granicę, więc po prostu wytnij węzły, które mają odległość większą niż limit ruchu.

Altówka.

Innymi słowy, właściwie to, co opisałeś w swoim pytaniu, jest tym, co musisz zrobić. Ma również tę zaletę, że może wykorzystać dane wyjściowe do znalezienia ścieżki, bez konieczności wykonywania dalszych obliczeń.


Myślę, że Dijkstra jest w tym przypadku przesadą. OP nie potrzebuje ścieżki do wszystkich możliwych miejsc ruchu, wystarczy odpowiedź tak / nie, czy agent może się tam dostać. Może obliczyć ścieżkę później, gdy użytkownik ją wybrał.
Michael Kristofik

Koszt użycia algorytmu Dijkstry do obliczenia ścieżki po ustaleniu miejsca docelowego jest prawie dokładnie taki sam, jak korzystanie z niego z góry (chyba że zastosujesz heurystyczne podejście, takie jak A * do ścieżki). Nie robienie tego z góry po prostu tworzy zbędną pracę, ponieważ Dijkstra odpowiedziałby zarówno na pytania „gdzie mogę iść”, jak i „jak się tam dostać?”. Pozwala także na dodanie komplikacji do środowiska, które zmieniają koszt ruchu, choć może to być niepotrzebne dla aplikacji. Ponadto podejście jest dobrze udokumentowane, co jest pomocne dla osoby wdrażającej.
TASagent

1
Patrząc na odpowiedź Mario, tak naprawdę opisuje algorytm Dijkstry, tyle że odwraca odległość i nie wspomina, że ​​to Dijkstra.
TASagent

1
Nie powiedziałbym, że to Dijkstra, ponieważ tak naprawdę nie szukasz najkrótszej trasy ani nie próbujesz dotrzeć do jakiegoś konkretnego punktu. Jest to zasadniczo pierwsza część algorytmu Dijkstry, ale to prawda. Problem z twoim sformułowaniem, używając Dijkstry, może być mylący i myślę, że to także myliło Michaela. Prawdopodobnie myślał, że zasugerowałeś użycie Dijkstry raz dla każdego pola / komórki.
Mario

1
Ostatecznie zastosowałem to podejście, ponieważ działało dobrze i jest bardzo łatwe do rozszerzenia, aby poradzić sobie z przeszkodami.
NRaf,

12

Najprostsze (i prawdopodobnie najbardziej naiwne) podejście, jakie mogę teraz wymyślić:

  • Zacznij od swojej postaci i zaznacz wszystkie otaczające pola jako steps - 1.
  • Iteruj po wszystkich nowo zaznaczonych polach i ponownie zaznacz otaczające je pola, tak jak steps - 1gdzie stepsbyłby numer kroku bieżącego pola, chyba że nowe pole ma już wyższą liczbę.
  • Powtarzaj ostatni krok, aż zabraknie Ci kroków.

1
Ten algorytm ma nazwę: Flood Fill .
Michael Kristofik

6
@MichaelKristofik: Nazwałbym to obszarem pierwszego wyszukiwania . Wypełnienie powodziowe nie śledzi odległości.
BlueRaja - Danny Pflughoeft

2

Myślę, że to, czego szukasz, może być Manhattan Distance . Zakładając, że nie ma przeszkód, można powiedzieć, że do kwadratu można dotrzeć po prostu, jeśli:

| toX-fromX | + | toY-fromY | <maxMoveDistance

Ten algorytm może nie być dobrym kierunkiem, jeśli później napotkasz przeszkody; jednym z możliwych sposobów dostosowania może być rzucanie „cieni” przez przeszkody i ponowna ocena od najbliższego punktu.

EDYCJA (Ponieważ mam teraz trochę więcej wolnego czasu):

Przez „cienie” rozumiem coś takiego: jeśli 0 to osiągalny kwadrat, C to postać, a X to przeszkoda:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Ponieważ (5, 2) jest przeszkodą, zaczynasz od założenia, że ​​nie możesz dojść do niczego za pomocą x> = 5 AND y <= 2. Następnie możesz ponownie obliczyć z innego kwadratu; jeśli chcesz przejść do (5, 1), możesz obliczyć odległość manhattanu z (4, 1) i sprawdzić, czy ta + odległość od postaci do (4, 1) jest mniejsza niż odległość ruchu gracza.

Jest to dość trywialny przykład, ale jeśli masz wiele przeszkód i / lub nieco większy zasięg ruchu, powinien być w stanie poradzić sobie ze złożonością.

Bez względu na to, czy byłoby to lepsze niż wypełnianie powodziowe, zarówno pod względem złożoności programowania, jak i wydajności wykonania, nie mam pojęcia. Wydawało się, że jest to bardziej interesujący sposób rozwiązania problemu.


Co masz na myśli mówiąc o rzucaniu cieni?
NRaf,

1
Edytowane w celu wyjaśnienia.
Tin Man
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.