Languages
» Algorytmy znajdowania ścieżek w Unity
Tutaj znajdziesz informacje o algorytmach znajdowania ścieżek. Jeśli potrzebujesz wizualizacji, bo chciał(a)byś lepiej zrozumieć zasadę działania, to poniżej zamieszczam link do aplikacji 🙂
Aplikacja
Cała aplikacja wraz z tutorialem video i muzyką zostały zrobione całkowicie przeze mnie.
Wyjaśnienie kolorów
Zamieszczam tu wyjaśnienie kolorów użytych w aplikacji. Jak tylko dokończę panel ustawień, będzie można je do woli zmienić z poziomu programu.
Węzły:
Morski – domyślny
Różowy – start
Zielony – cel
Czarny – zablokowany
Markery:
Żółty – gotowy do sprawdzenia (otwarty)
Zielony – sprawdzony (zamknięty)
Niebieski – ścieżka
Algorithms
Założenia do wyjaśnień:
- Kolory węzłów są takie jak w opisie powyżej.
- Dozwolone kierunki i ich kolejność jest następująca: góra, dół, lewo, prawo.
- Zablokowane węzły jak i te już dodane do kolekcji (otwarte) są pomijane.
W mojej implementacji pierwsze dwa etapy są wszędzie takie same niezależnie od typu algorytmu:
1. Sprawdź, czy węzeł startowy jest węzłem końcowym. Jeśli tak, to rysuj ścieżkę. Jeśli nie – przejdź dalej.
2. Dodaj wszystkie węzły dookoła do sprawdzenia zgodnie z założoną kolejnością kierunków. Jeśli któryś jest już dodany, pomiń go. W algorytmie BFS, a w szczególności DFS, szybkość znalezienia odpowiedniej ścieżki zależy od kolejności dodawania kolejnych węzłów.
Breadth first search
Jak sama nazwa wskazuje jest to szukanie po szerokości (breadth = width = szerokość), to znaczy że zaczynając od węzła startowego algorytm najpierw sprawdza wszystkie dookoła niego (kolejność do ustalenia), potem wszystkie dookoła tych sprawdzonych, itd. W zależności od tego od której strony zaczniemy rezultat może być inny (więcej bądź mniej ruchów będzie potrzeba do znalezienia celu).
3. Sprawdź następny węzeł z kolekcji otwartych węzłów i zamknij go. Węzły są sortowane zgodnie z regułą FIFO (pierwszy w środku pierwszy na zewnątrz), więc następnym węzłem powinien być ten otwarty najwcześniej (jeszcze nie zamknięty). Dlatego że nasza kolejność jest następująca: góra, dół, lewo, prawo, a górny węzeł jest zablokowany, algorytm przechodzi do węzła poniżej.
4. Powtórz punkty 2 i 3 aż znajdziesz węzeł końcowy albo sprawdzisz wszystkie węzły możliwe do sprawdzenia. Węzłami następnymi w kolejce są: lewy, a potem prawy.
5. Jeśli kursor znalazł węzeł końcowy, narysuj ścieżkę od pozycji startowej do końcowej.
Depth first search
Jak sugeruje nazwa, ten algorytm wybiera jeden korytarz, sprawdza węzły przesuwając się w obranym kierunku dotąd, aż korytarz ten się skończy. Tutaj kolejność kierunków ma wielki wpływ na całkowity czas potrzebny do znalezienia ścieżki. Nie jesteśmy także zapewnieni, że będzie to najkrótsza ścieżka z możliwych.
3. Sprawdź kolejny węzeł z kolekcji otwartych i zamknij go. Węzły są posortowane zgodnie z regułą LIFO (ostatni w środku pierwszy na zewnątrz), więc kolejnym węzłem powinien być ten otwarty najpóźniej (jeszcze nie zamknięty). Dlatego że nasza kolejność to: góra, dół, lewo, prawo, algorytm porusza się w prawo (prawy węzeł został dodany najpóźniej).
4. Powtórz punkty 2 i 3 aż znajdziesz węzeł końcowy albo sprawdzisz wszystkie węzły możliwe do sprawdzenia. Skoro ostatnim dodanym węzłem jest ten z prawej strony, algorytm kontynuuje sprawdzanie poruszając się prawą stronę, aż dotrze do końca labiryntu. Następnie cofa się do poprzednio otwartego korytarza.
5. Jeśli kursor znalazł węzeł końcowy, narysuj ścieżkę od pozycji startowej do końcowej.
A*
A* jest nieco bardziej złożonym algorytmem, ale nie aż tak. Jego różnica w porównaniu do poprzednich jest w posiadaniu swego rodzaju konkretnego kryterium sortowania otwartych węzłów, więc kolejność węzłów przygotowanych do sprawdzenia zmienia się dynamicznie w miarę pracy algorytmu.
Każdy węzeł musi mieć określone 3 wartości zwykle nazywane:
- H = koszt do celu
- G = koszt od startu
- F = H + G (wynik)
Koszt do celu (H) może być mierzony jako zwykły dystans od wybranego węzła do końcowego, wyliczony z użyciem Twierdzenia Pitagorasa czy też inną drogą (np. liczba ruchów w kierunku horyzontalnym i wertykalnym, które algorytm musi wykonać aby osiągnąć punkt docelowy).
Koszt od startu (G) może być po prostu ustawiany jako liczbę ruchów, które algorytm musiał wykonać w celu osiągnięcia wybranego węzła. Możesz również dodać specjalne ograniczenia do ruchu ukośnego, jeśli chcesz.
Wynik (F) jest sumą wartości powyższych. Algorytm ustala kolejny węzeł do sprawdzenia właśnie poprzez tę wartość. Odnosząc się do wybranego węzła, im mniejszy wynik posiada, tym wcześniej zostanie wybrany.
3. Sprawdź kolejny węzeł z kolekcji otwartych i zamknij go. Węzły są posortowane zgodnie z wartością wyuniku (F) wyjaśnioną powyżej. Każdy otwarty dotąd węzeł, ma ten sam koszt od startu (G), ale możemy zauważyć gołym okiem, że ten z prawej strony posiada najkrótszy dystans do węzła końcowego (pomijając wszystkie węzły zablokowane – w linii prostej). Toteż wybrany zostaje węzeł z prawej strony.
4. Powtórz punkty 2 i 3 aż znajdziesz węzeł końcowy albo sprawdzisz wszystkie węzły możliwe do sprawdzenia. Na tym etapie dystans każdego następnego węzła jest krótki do takiego stopnia, że ich wyniki są nadal niższe od wyników węzłów zostawionych z tyłu (pomimo ciągle rosnącej wartości kosztu od startu – G).
5. Jeśli kursor znalazł węzeł końcowy, narysuj ścieżkę od pozycji startowej do końcowej.
The most beautiful things in the world cannot be seen or touched, they are felt with the heart.
-- Little Prince --