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

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

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

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.

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.