Jak tworzyć naturalnie wyglądające ścieżki z A * na siatce?

Czytałem to: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Ale są pewne rzeczy, których nie rozumiem, na przykład artykuł mówi, aby użyć czegoś takiego do szukania ścieżki z ruchem ukośnym:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

Nie wiem, jak ustawić D, aby uzyskać naturalnie wyglądającą ścieżkę, jak w artykule, ustawiłem D na najniższy koszt między sąsiednimi kwadratami, jak to powiedziano, i nie wiem, co mieli na myśli przez rzeczy o heurystyce powinny być 4 * D, to nic nie zmienia.

To jest moja funkcja heurystyczna i funkcja ruchu:

def heuristic(self, node, goal):
    D = 5
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * max(dx, dy)

def move_cost(self, current, node):
   cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
   return 7 if cross else 5

Wynik:

Płynna ścieżka żeglowania, którą chcemy osiągnąć:

Reszta mojego kodu: http://pastebin.com/TL2cEkeX

Aktualizacja

To najlepsze rozwiązanie, jakie do tej pory znalazłem:

def heuristic(node, start, goal):
    dx1 = node.x - goal.x
    dy1 = node.y - goal.y
    dx2 = start.x - goal.x
    dy2 = start.y - goal.y
    cross = abs(dx1*dy2 - dx2*dy1)

    dx3 = abs(dx1)
    dy3 = abs(dy1)

    return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3)

def move_cost(current, node):
    cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
    return 7 if cross else 5

Z drugiego zdjęcia tworzy pożądaną ścieżkę, ale nie radzi sobie dobrze z przeszkodami (ma tendencję do czołgania się po ścianach) i czasami nie tworzy optymalnych ścieżek na dłuższych dystansach.

Jakie poprawki i optymalizacje mogę zastosować, aby je ulepszyć?

A * daje najkrótszą ścieżkę na wykresie. Podczas korzystania z siatki jako wykresu często istnieje wiele najkrótszych ścieżek. Na pierwszym diagramie jest to jedna z najkrótszych ścieżek. Najpierw wszystkie ruchy osiowe, a następnie wszystkie ruchy po przekątnej. Ale to ta sama długość ścieżki, jak gdyby na pierwszym miejscu były wszystkie przekątne lub mieszane ruchy osiowe i ukośne. Wszystkie są jednakowo krótkie, a wybór A * zależy od sposobu pisania kodu i reprezentacji wykresu.

Myślę, że chcesz:

1. Musisz poruszać się po siatce, ale chcesz mieszać kroki osiowe i ukośne, aby wyglądało to lepiej. Jednym z podejść jest wybranie jednej z innych równie krótkich ścieżek; czytaj dalej tę stronę heurystyczną, aby znaleźć „rozstrzygające remisy”. Innym podejściem jest, gdy oceniasz sąsiadów, wybieraj losowo, który ocenisz jako pierwszy, aby nie zawsze wybierał jednego przed drugim. Ja nie polecam korzystania euklidesową / kartezjański odległość, jeśli chce się przenieść na starcie; to niedopasowanie, które powoduje, że A * działa wolniej.
2. Nie musisz poruszać się po siatce i chcesz poruszać się po linii prostej. Jednym z podejść jest wyprostowanie ścieżek za pomocą „ciągnięcia sznurka”. Szukasz miejsc, w których kręci się ścieżka, i rysujesz linie proste między tymi punktami. Innym podejściem jest zastosowanie tego do samego wykresu bazowego. Zamiast znajdowania ścieżki na siatce, znajdź ścieżkę w kluczowych punktach na mapie, a następnie poruszaj się wzdłuż prostych linii między tymi kluczowymi punktami. Można zobaczyć przykład tutaj . Jeszcze innym podejściem jest algorytm Theta * .

Algorytm A * pozwala przypisywać różne koszty do krawędzi ścieżki. Możesz także przypisać koszty w zależności od okoliczności. Jest to twoje główne narzędzie do kształtowania ścieżek A * tak, aby wyglądały tak, jak chcesz.

Jeśli chcesz zniechęcić długie przekątne, możesz je ukarać. Dodaj odrobinę kosztów za każdym razem, gdy ścieżka zmierza w tym samym kierunku. Gdy to zrobisz, algorytm automatycznie spróbuje rozmieścić kroki po przekątnej tak równomiernie, jak to możliwe na całej ścieżce. Upewnij się tylko, że ten dodatkowy koszt nigdy nie jest większy niż koszt uzyskania dodatkowej przewagi, w przeciwnym razie algorytm zacznie robić całkowicie niepotrzebne objazdy tylko po to, aby uniknąć linii prostych.

Dobrą formułą może być:

cost = normal_cost * (1.1 - 0.1 / num_of_steps_in_the_same_direction)

Zauważ, że wymaga to, aby koszt ścieżki był śledzony jako wartości zmiennoprzecinkowe, a nie jako liczby całkowite.

Dostosowanie A *

Jak powiedział Philipp, powinieneś doliczyć koszty, gdy kierunek nie zmienia się przez długi czas. Ale funkcja Filipa może szybko doprowadzić do zsumowania dodatkowych kosztów, które są wyższe niż koszt przejścia dodatkowej płytki. Ale jego kluczowa idea jest poprawna!

Łatwo jest dostosować A *, aby obliczyć „wszystkie” optymalne ścieżki (o najkrótszej długości), a następnie wybrać jedną z nich za pomocą innej heurystyki. Ale jest problem. Jeśli masz długą ścieżkę, może istnieć wiele rozwiązań o optymalnej długości. To powoduje, że algorytm A * również zajmuje dużo więcej czasu na obliczenie wszystkich innych rozwiązań. To dlatego, że siatka. Nie można chodzić o 80 stopni zamiast 90 stopni, co prowadzi do wielu nieoptymalnych rozwiązań zamiast jednego optymalnego rozwiązania. Dla wyobraźni wyobraź sobie mapę bez przeszkód. Odległość x wynosi 2, a odległość y wynosi 3. Oznacza to, że wszystkie najkrótsze ścieżki mają 2 ruchy po przekątnej i 1 ruch prosty. Istnieją 3 prawidłowe kombinacje: SDD, DSD, DDS (gdzie D = przekątna, S = prosta) dla tej prostej ścieżki. Prawdziwa „zabawa” zaczyna się już wtedy, gdy masz ścieżki np 3 ruchy proste i 2 ruchy po przekątnej: SSSDD, SSDSD, SSDDS, SDSSD, SDSDS, SDDSS, DSSSD, DSSDS, DSDSS, DDSSS (10 wariantów najkrótszej ścieżki, jeśli żadnej nie przegapiłem). Myślę, że powinieneś mieć pomysł ...

Dlatego powinniśmy to naprawić, dostosowując funkcję kosztów w taki sposób, aby mniej rozwiązań (lub nawet tylko jedno rozwiązanie) było „optymalne”.

Dostosowanie funkcji kosztów

Wykonanie adaptacji, jak sugeruje Philipp w swojej przykładowej formule, da ci znacznie lepsze wyniki, ale nadal ma pewne problemy. Nie rozłoży równomiernie krótszych / dłuższych „części” wzdłuż ścieżki, co oznacza: zmiany kierunku będą występować częściej na początku ścieżki lub odwrotnie.

Dodatkowo ścieżka z nieskończonym zmuszaniem aktora do „skrętu” wydaje się być nieoptymalna, gdy obserwuje go człowiek. Ponieważ wymaga czasu (aby wyświetlić animację zakrętu) i dlatego musi być wolniejsza.

Jednak zamiast stosować zmiennoprzecinkowe koszty, można wdrożyć „koszt wtórny” lub kryteria sortowania wtórnego. Jeśli koszty pierwotne są takie same, koszt wtórny służy do oszacowania, które rozwiązanie należy preferować. Nie spowoduje to przypadkowo wzrostu kosztów pierwotnych (długości trasy w ramach miary sieci).