A * Algorytm dla taktycznych gier RPG?

Mam problemy z pisaniem naprawdę słabej taktycznej gry RPG w C ++. Do tej pory mam mapę kafelków 2D i właśnie uruchomiłem algorytm A * oparty na pseudokodzie w wikipedii .

Ale prawdziwe taktyczne gry RPG nie tylko znajdują najlepszą ścieżkę na płaskim samolocie i się tam poruszają. Zazwyczaj mają ograniczone zakresy ruchów i muszą wspinać się w górę lub w dół. Jeśli kiedykolwiek grałeś w Final Fantasy Tactics, miałyby na to wpływ statystyki ruchu i skoku. Tu się zgubiłem. Jak zmienić algorytm A *, aby znalazł najlepszą ścieżkę do celu, ale ścieżka ma tylko tyle płytek? Jak wziąć pod uwagę różnice wysokości i statystyki skoków? Jak wdrożyć przeskakiwanie przez lukę?

Jeśli to pomaga, w tej chwili moja mapa jest reprezentowana przez obiekty Vector of Tile. Każdy kafelek ma wskaźniki do północnego, południowego, wschodniego i zachodniego kafelka, które są ustawione na nullptr, jeśli nie istnieje tam żaden kafelek, na przykład wzdłuż krawędzi mapy lub jeśli kafelek jest ustawiony jako niemożliwy do przejścia.

Wspinaczka i luki to po prostu różne funkcje kosztów. Dla jednostki, która może przeskoczyć lukę, ma normalny (?) Koszt, podczas gdy dla jednostki, która nie skacze, ma arbitralnie wysoki koszt. Wspinaczka kosztuje dodatkowo, podobnie jak trudny teren itp. Algorytm A * dobrze radzi sobie z funkcjami kosztowymi, więc jeśli twoja implementacja jeszcze tego nie robi, po prostu google jak zaimplementować A * z funkcją kosztów.

Powiedziawszy to, nie sądzę jednak, aby A * było szczególnie dobrym podejściem do taktycznej gry RPG. Mówiąc dokładniej, nie jest to pełna historia. Nie chcesz, aby twoje jednostki ślepo popełniły błąd w kierunku celu, chcesz, aby ustawiły się w celu wykorzystania osłony, wysokiego terenu, cokolwiek, jednocześnie dążąc do ostatecznego celu i starając się flankować przeciwników i tak dalej. Tak więc wartość taktyczna punktu końcowego każdego ruchu ma ogromne znaczenie, a nie tylko to, jak blisko jest celu. Wymaga to bardziej dogłębnego rozwiązywania problemów niż zwykłego szukania ścieżki.

Jeśli chcesz wszystkich możliwych opcji ruchu jednostki, skorzystaj z Algorytmu Dijkstry .

Różnica między A * i Dijkstra polega na tym, że Dijkstra oferuje wszystkie możliwe najkrótsze trasy osiągalne przy danym koszcie, a jeśli żadna z nich nie dotrze jeszcze do miejsca docelowego, zwiększa koszt o jedną i kontynuuje. Z drugiej strony A * woli najpierw obliczyć trasy, które mają dużą szansę na dotarcie do celu.

Więc jeśli chcesz tylko najkrótszą ścieżkę od punktu A do punktu B, to A * jest dobrym wyborem. Ale jeśli chcesz wszystkich możliwych opcji ruchu i najkrótszej ścieżki do każdej z nich, to Dijkstra jest dokładnie tym, czego chcesz.

Wszystko, co musisz zrobić, to uruchomić Algorytm Dijksta bez określonego węzła docelowego, ale z maksymalnym kosztem, którego nie można przekroczyć (zasięg ruchu jednostki). Podczas podróży do węzła przekroczyłby maksymalny koszt, nie odwiedzaj go. Kiedy algorytm kończy się z powodu braku nieodwiedzonych krawędzi, każdy węzeł w odwiedzanym zestawie jest możliwym miejscem docelowym, a poprzednie znaczniki węzłów w węzłach tworzą połączoną listę reprezentującą ścieżkę z powrotem do początkowego węzła.

Jeśli chodzi o skoki: mogą być reprezentowane jako kolejna przewaga w A * i Dijkstra. Mogą mieć taki sam koszt, jak przemierzanie zwykłej krawędzi lub innej. Możesz także przekazać do algorytmu parametr „jump_height”, który nakazuje algorytmowi ignorowanie skoków przekraczających daną wysokość.

Inne odpowiedzi zawierają dobre informacje, więc przeczytaj je.

Jednak, aby odpowiedzieć na twoje pytanie: na podstawie pseudokodu, z którym się połączyłeś, masz jakąś funkcję, w heuristic_cost_estimatektórej obliczasz koszt od płytki A do płytki B (zakładając, że są sąsiednie). Zamiast używać płaskiego (1) dla tego kosztu, musiałbyś go dostosować, aby zawierał statystyki kafelków i statystyki jednostek oraz ewentualnie statystyki krawędzi.

Na przykład:

if (edge == JUMP && !unit.canJump()) 
    return INF;
if (tile.Type == Forest && unit.moveType == HORSE) 
    return 2;
//Other cases here
//-----
else 
    return 1;

To da ci swoją ścieżkę. Następnie po prostu przesuwałbyś jednostkę wzdłuż ich ścieżki, zużywając punkty ruchu i zatrzymując je, gdy pozostały Punkty <EdgeCost. Pamiętaj, że może to nie być całkowicie optymalne, jeśli skończysz z pozostałymi punktami = 1, ale powinno to wystarczyć na ćwiczenie RPG. W rzeczywistości chcesz więcej taktyczności, jak zauważył Jack Aidley!

Wyzwanie:
Jeśli chcesz być bardziej zaawansowany, prawdopodobnie chcesz użyć Djikstras, tak jak sugerowano, aby znaleźć wszystkie pola w odległości X, a następnie chcesz ocenić każde pole na tej liście pod kątem „najlepszego” miejsca, w oparciu o bliskość do celu, obronę moc, niezależnie od tego, czy możesz zostać zaatakowany z tej pozycji itp. Na podstawie tych informacji, wybierasz kafelek, a następnie przesuwasz się tam, podążając ścieżką, którą właśnie obliczyłeś za pomocą Djikstras.

Wspinaczka i luki są dość trywialne, ponieważ modyfikują tylko koszty. Pathfinding (i większość taktycznej sztucznej inteligencji) polega na zsumowaniu kosztów na wszystkich odwiedzanych węzłach i zminimalizowaniu tego. Nieprzejezdny klif będzie miał nieskończony (bardzo, bardzo wysoki) koszt, stoki będą miały wyższy koszt niż normalnie itp.

Znajduje to jednak optymalną globalnie ścieżkę, która nie jest najlepszym rozwiązaniem, ponieważ prawdziwi przeciwnicy zwykle tego nie robią znajdują optymalnej ścieżki. Jest wysoce nierealistyczny, czasem do punktu, który jest oczywisty dla gracza i denerwujący (szczególnie, gdy AI jako taka jest w zasadzie niezwyciężona, ponieważ ona również wybiera optymalne).

Celowe dobre symulacje nie znajdują najlepszej ścieżki. Znacznie lepszym algorytmem może być hierarchiczne wyszukiwanie ścieżek - jeśli nic innego, poprzez narysowanie linii prostej na mapie i pobranie 4-5 punktów, a następnie znalezienie ścieżki od jednego punktu do drugiego, biorąc pod uwagę tylko dotychczasowe wagi węzłów znany i ustawiając wszystkie pozostałe wagi węzłów na „obojętne”. Alternatywnie możesz najpierw uruchomić A * na grubszej siatce, a następnie znaleźć ścieżkę od jednego dużego węzła do drugiego (ale domyślam się, że rysowanie linii na mapie też jest w porządku).

Jest to o wiele bardziej realistyczne (a także zużywa ułamek mocy obliczeniowej, ponieważ wykres jest znacznie mniejszy). Tak, może to oznaczać, że jednostka zbliża się do klifu, aby dowiedzieć się, że nie może się przedostać. W porządku, zdarza się to także prawdziwym przeciwnikom. Następnym razem to się nie powtórzy (ponieważ teraz wiadomo nieskończony koszt).