Czy istnieją jakieś algorytmy wyszukiwania ścieżek, które obsługiwałyby różne typy ruchów?

12

Pracuję nad botem do symulatora gier planszowych BattleTech http://en.wikipedia.org/wiki/BattleTech , jest on turowy.

Plansza jest podzielona na sześciokąty, każdy ma inny typ terenu i wysokość. Prowadzisz robota, który się nad nimi porusza, aby zniszczyć inne roboty.

Znam tylko algorytmy Dijkstry i A *, ale problem polega na tym, że istnieją 3 rodzaje ruchów: chodzić, biegać i skakać po kilka sześciokątów (każdy z nich ma swoje własne reguły). Chodzenie i bieganie są prawie takie same.

Najlepszą ścieżką może być kombinacja lub każdy typ ruchu. Oto przykład mapy http://megamek.info/sites/default/files/isometric_view.png

Czy znasz dobry algorytm dla tego złożonego wyszukiwania ścieżek lub sposób łączenia wyników A * dla każdego rodzaju ruchu?

ai movement path-finding alexvisio
źródło
Myślę, że często jest to obsługiwane przez pewne sprytne manipulowanie ważoną ścieżką za pomocą A * (waga jest kosztem tej ścieżki / kwadratu). Na przykład, jeśli preferowane jest skakanie, ma on mniejszą wagę (np. 5) niż chodzenie (np. 10).
ashes999
Czym dokładnie różnią się trzy rodzaje ruchów? Czy można je łączyć (przejdź do kafelka A, a następnie biegnij do B, a następnie w tej samej turze skocz do C)? Kiedy tak, jakie zasady uniemożliwiają graczowi korzystanie z najtańszej metody przejścia z kafelka A na kafelek B?
Philipp
@Philipp Tak, mogą być, używając A *. Możesz dodać każdy kafelek, do którego możesz przejść z każdym rodzajem ruchu, do otwartej listy, a następnie w oparciu o cenę każdego + dobrą heurystykę, którą możesz określić, aby przejść dalej.
akaltar
@Philipp Nie, możesz użyć tylko jednego rodzaju ruchu w każdej turze.
alexvisio
Spacer: poruszaj się po sześciokątach z niewielką różnicą wysokości. Uruchom: to samo, ale możesz przejść daleko, chociaż generujesz ciepło i tracisz celność strzelania (więc nie zawsze jest to najlepsze). Skok: możesz skakać przez przeszkody (ścianę lub rzekę) zamiast chodzić wokół nich.
alexvisio

Odpowiedzi:

10

Zarówno Dijkstra, jak i A * mogą dodawać różne koszty do krawędzi (= połączeń) z jednej płytki na drugą. Pozwalają również połączyć dwa węzły (= kafelki) z więcej niż jedną krawędzią, każdy z innym kosztem.

Alternatywny tryb skoku oznaczałby, że istnieje alternatywna bezpośrednia krawędź z każdej płytki do każdej płytki w odległości skoku. Ponieważ jednak mech może chodzić lub skakać w turze, kosztem użycia tej krawędzi byłyby punkty ruchu całej tury plus pozostałe punkty bieżącej tury, gdy już był ruch w tej turze.

Zgodnie z Twoim opisem decyzja dotycząca chodzenia a biegania nie ma większego znaczenia w wyborze ścieżki, ale wydaje się, że jest to decyzja strategiczna. Aktor zdecydowanie może chodzić, gdy w bieżącej turze można dotrzeć do celu bez uciekania się do biegania. Ale poza tym istnieje wiele czynników, na przykład:

  • aktualny poziom ciepła i prawdopodobieństwo wzięcia udziału w walce przed schłodzeniem
  • trudność ze strzałami, które należy oddać w tej rundzie
  • jak strategicznie ważne jest szybkie dotarcie do celu

Nie ma twardej zasady podejmowania tej decyzji. Najlepsze, co możesz zrobić, to zastosować podejście heurystyczne. Przypisz wartości dodatnie lub ujemne do wszystkich okoliczności, dodaj je i sprawdź, czy wynik jest dodatni czy ujemny.

Istnieje również inny czynnik w wyszukiwaniu ścieżek, który należy wziąć pod uwagę: w niektórych warunkach sensowne może być uniknięcie przez mecha zakończenia swojej tury w niektórych miejscach. Gdy znajdujesz się w strefie zagrożenia, skorzystanie z trzech zwojów, aby dostać się z A do B, ale zakończenie każdego z nich w osłonie może być lepsze niż użycie tylko dwóch, ale odsłonięcie na końcu każdego. Albo może nie. To zależy od okoliczności i dokładnej mechaniki gry. To znowu jest strategiczna decyzja, którą musisz podjąć w oparciu o heurystykę. Możesz to przedstawić, dodając dodatkowy koszt do krawędzi, które kończą turę na niebezpiecznej płytce, aby zniechęcić AI do wykonania tego ruchu.

Philipp
źródło