algorithm
* Algorytm odnajdywania ścieżek

Wprowadzenie

Prosty przykład odnajdywania ścieżki A *: labirynt bez przeszkód

Powiedzmy, że mamy następującą siatkę 4 na 4:

Załóżmy, że to labirynt . Jednak nie ma ścian / przeszkód. Mamy tylko punkt początkowy (zielony kwadrat) i punkt końcowy (czerwony kwadrat). Załóżmy również, że aby przejść z zielonego na czerwony, nie możemy poruszać się po przekątnej. Rozpoczynając od zielonego kwadratu, zobaczmy, do których kwadratów możemy się przenieść, i zaznaczmy je na niebiesko:

Aby wybrać, do którego kwadratu chcesz przejść, musimy wziąć pod uwagę 2 heurystyki:

1. Wartość „g” - To jest odległość tego węzła od zielonego kwadratu.
2. Wartość „h” - to odległość od tego węzła od czerwonego kwadratu.
3. Wartość „f” - jest to suma wartości „g” i wartości „h”. To ostatnia liczba, która mówi nam, do którego węzła się przenieść.

W celu obliczenia tych heurystyk użyjemy następującego wzoru: distance = abs(from.x - to.x) + abs(from.y - to.y)

Jest to znane jako formuła „Manhattan Distance” .

Obliczmy wartość „g” dla niebieskiego kwadratu bezpośrednio na lewo od zielonego kwadratu: abs(3 - 2) + abs(2 - 2) = 1

Świetny! Mamy wartość: 1. Teraz spróbujmy obliczyć wartość „h”: abs(2 - 0) + abs(2 - 0) = 4

Doskonały. Teraz uzyskamy wartość „f”: 1 + 4 = 5

Zatem końcowa wartość dla tego węzła to „5”.

Zróbmy to samo dla wszystkich pozostałych niebieskich kwadratów. Duża liczba na środku każdego kwadratu to wartość „f”, podczas gdy liczba w lewym górnym rogu to wartość „g”, a liczba w prawym górnym rogu to wartość „h”:

Obliczyliśmy wartości g, h i f dla wszystkich niebieskich węzłów. Teraz, co wybieramy?

Którykolwiek ma najniższą wartość f.

Jednak w tym przypadku mamy 2 węzły o tej samej wartości f, 5. Jak wybieramy między nimi?

Po prostu wybierz jeden losowo lub ustaw priorytet. Zwykle wolę mieć taki priorytet: „W prawo> W górę> W dół> W lewo”

Jeden z węzłów o wartości f 5 prowadzi nas w kierunku „w dół”, a drugi w lewo. Ponieważ Down ma wyższy priorytet niż Left, wybieramy kwadrat, który zabiera nas „Down”.

Zaznaczam teraz węzły, dla których obliczyliśmy heurystykę, ale do których nie przestawiłem, jako pomarańczowy, a węzeł, który wybraliśmy jako cyjan:

W porządku, obliczmy teraz tę samą heurystykę dla węzłów wokół węzła cyjan:

Ponownie wybieramy węzeł schodzący z węzła cyjan, ponieważ wszystkie opcje mają tę samą wartość f:

Obliczmy heurystykę dla jedynego sąsiada, który ma węzeł cyjan:

W porządku, ponieważ będziemy postępować zgodnie z tym samym wzorem, co my:

Jeszcze raz obliczmy heurystykę dla sąsiada węzła:

Przejdźmy tam:

Wreszcie widzimy, że mamy obok siebie zwycięski kwadrat , więc się tam poruszamy i gotowe.