Najpierw opublikowałem to pytanie na temat przepełnienia stosu, ale chyba nikt nie jest zainteresowany grami wideo ...

Jakie algorytmy wyszukiwania ścieżek są używane w grach wszystkich typów? (W każdym razie, gdzie poruszają się postacie) Czy Dijkstra dużo używa? Nie pomyślałbym, że nie, ponieważ tak naprawdę nie określa kroków, które należy podjąć, aby się gdzieś dostać, prawda? Jeśli dobrze to rozumiem, określa tylko, który obiekt jest najbliższy. Tak naprawdę nie chcę niczego kodować; po prostu przeprowadzam badania, ale jeśli wkleisz pseudokod lub coś, to byłoby w porządku (rozumiem Javę i C ++). Zasadniczo szukam szybkiego przeglądu znalezienia ścieżki w ogóle.

Wiem, że A * jest jak algorytm, którego można używać w grach 2D. To świetnie i wszystko, ale co z grami 2D, które nie są oparte na siatce? Rzeczy takie jak Age of Empires lub Link's Awakening. Nie ma wyraźnych kwadratowych spacji do nawigacji, więc co oni robią?

Co robią gry 3D? Przeczytałem tę ciekawą stronę http://www.ai-blog.net/archives/000152.html , która według mnie jest świetnym autorytetem w tej dziedzinie, ale tak naprawdę nie wyjaśnia JAK, po ustawieniu siatek, wyszukiwanie ścieżki jest zakończone. JEŻELI A * jest tym, czego używają, to jak to się robi w środowisku 3D? A jak dokładnie działają splajny zaokrąglające rogi?

Zbyt wiele pytań na raz, więc trudno jest podać konkretną odpowiedź, ale omówić kilka z tych tematów. Podzielę odpowiedź na dwie części i postaram się odpowiedzieć na nią jak najlepiej. Nie twierdzę, że żadna z tych list jest kompletna , ale są to niektóre z różnych metod, które mogłem zapamiętać.

Część 1 - Algorytmy odnajdywania ścieżek

Po pierwsze, istnieje wiele sposobów implementacji odnajdywania ścieżek, ale nie wszystkie z nich zwracają najkrótszą ścieżkę, są wydajne lub nawet niezawodne. Na przykład:

• Prymitywne metody, które nie „patrzą w przyszłość” i wykonują jeden krok na raz:

  • Losowe cofanie - Zrób krok po kroku w kierunku bramki. Jeśli napotkasz przeszkodę, spróbuj obejść ją, cofając się nieco w losowym kierunku, a następnie spróbuj ponownie. W ogóle nie jest wiarygodny i utknie w wielu sytuacjach.

  • Śledzenie przeszkód - inne podejście, podobne do losowego cofania, ale zamiast losowego cofania się, zacznij śledzenie obiektu po znalezieniu kolizji, tak jakbyś miał prawą rękę przyczepioną do ściany i musiałem ją dotknąć. Gdy nie dojdzie do kolizji, kontynuuj jazdę w kierunku bramki. Po raz kolejny może utknąć w wielu sytuacjach.

• Metody, które pozwalają na znalezienie całej ścieżki naraz:

  • Szerokość Pierwsze wyszukiwanie - Proste przejście przez graf, odwiedzając każdą warstwę dzieci naraz, zatrzymaj się, gdy zostanie znaleziona ścieżka. Jeśli wykres jest nieważony (tzn. Odległość między każdym sąsiednim węzłem jest zawsze taka sama), znajdzie najkrótszą ścieżkę, choć niezbyt skutecznie. W przypadku wykresów ważonych może nie zwrócić najkrótszej ścieżki, ale zawsze ją znajdzie, jeśli istnieje.

  • Głębokie pierwsze wyszukiwanie - inny sposób na przejście przez wykres, ale zamiast przenosić go warstwa po warstwie, algorytm próbuje najpierw przeszukać głęboko wykres. Ta metoda może powodować problemy, jeśli głębokość wyszukiwania nie jest ograniczona, szczególnie przy użyciu rekurencyjnej implementacji, co może prowadzić do przepełnienia stosu, dlatego zwykle bezpieczniej jest iteracyjnie zaimplementować stos.

  • Najlepsze pierwsze wyszukiwanie - podobne do pierwszego wyszukiwania szerokości, ale korzysta z heurystyki, która wybiera najpierw najbardziej obiecującego sąsiada. Zwrócona ścieżka może nie być najkrótsza, ale jej uruchomienie jest szybsze niż pierwsze wyszukiwanie. * Jest rodzajem najlepszego pierwszego wyszukiwania.

  • Metoda Dijkstry - Śledzi całkowity koszt od początku do każdego odwiedzanego węzła i używa go do ustalenia najlepszej kolejności przejścia przez wykres. Działa z ważonymi wykresami i zwraca najkrótszą ścieżkę, ale może wymagać wielu poszukiwań.

  • A * - Podobnie jak w przypadku Dijkstry, ale również używa heurystyki, aby oszacować prawdopodobieństwo, że każdy węzeł jest bliski celu, aby podjąć najlepszą decyzję. Z powodu tej heurystyki A * znajduje najkrótszą ścieżkę na wykresie ważonym w znacznie bardziej terminowy sposób.

• Następnie istnieją odmiany A * (lub ogólnie optymalizacje ścieżki), które sprawiają, że jest ono szybsze lub bardziej dostosowane do pewnych okoliczności, takich jak (patrz odpowiednia odpowiedź i obszerna lista na cstheory.SE ):

  • LPA * - podobny do A *, ale może szybciej obliczyć najlepszą ścieżkę po wprowadzeniu niewielkiej zmiany na wykresie
  • D * Lite - w oparciu o LPA * robi to samo, ale zakłada, że ​​„punkt początkowy” to jednostka zbliżająca się do mety podczas wprowadzania zmian na wykresie
  • HPA * (hierarchiczna) - używa kilku warstw na różnych poziomach abstrakcji, aby przyspieszyć wyszukiwanie. Na przykład warstwa wyższego poziomu może po prostu łączyć pokoje, podczas gdy warstwa niższego poziomu zajmuje się omijaniem przeszkód.
  • IDA * (iteracyjne pogłębianie) - Zmniejsza zużycie pamięci w porównaniu ze zwykłym A *, stosując iteracyjne pogłębianie.
  • SMA * (Simplified Memory-Bounded) - Wykorzystuje dostępną pamięć tylko do wyszukiwania.
  • Jump Point Search - Podziękowania dla Erica w komentarzach za wzmiankę o nim! Przyspiesza wyszukiwanie ścieżek na mapach siatki o jednolitych kosztach ( link ).

Część 2 - Reprezentacja przestrzeni wyszukiwania

I wreszcie, aby odpowiedzieć na to pytanie:

Wiem, że A * jest jak algorytm, którego można używać w grach 2D. To świetnie i wszystko, ale co z grami 2D, które nie są oparte na siatce?

Dwie wielkie nieporozumienia tutaj! W rzeczywistości:

1. * Nie ma znaczenia, czy gra jest 2D czy 3D, i jest równie odpowiednia w obu przypadkach.
2. * Działa pod dowolną reprezentacją wykresu, więc nie ma znaczenia, czy świat jest siatką, czy nie.

Więc jeśli świat nie musi być siatką, w jaki inny sposób możesz go przedstawić? Oto krótki przegląd sposobów podziału światowej przestrzeni na szukanie ścieżek, a większość z nich działa zarówno w 2D, jak i 3D:

• Siatka prostokątna - Podziel świat na regularną siatkę kwadratów, przy czym każda komórka w siatce jest jednym węzłem na wykresie, a połączenie między dwoma niezakłóconymi węzłami jest krawędzią.

  

• Quadtree - Kolejny sposób na podzielenie przestrzeni, ale zamiast podziału na siatkę komórek o regularnych rozmiarach, podziel na cztery części, a następnie ponownie rekurencyjnie podziel każdą z nich na cztery. Dodanie trzeciego wymiaru czyni ósemkę .

  

• Wypukłe wielokąty - podział obszaru, na którym można chodzić, na siatkę połączonych wypukłych wielokątów. Każdy wielokąt staje się węzłem, a wspólne krawędzie są krawędziami wykresu. Mogą to być na przykład trójkąty, a czasem nawet siatka stworzona przez artystę podczas tworzenia zasobów poziomu. Często nazywane siatką nawigacyjną . Zobacz ten link . Oto bardzo popularny zestaw narzędzi do budowy siatki nawigacji: Przekształcenie .

  

• Punkty widoczności - najczęstszym sposobem jest umieszczenie węzła tuż za każdym z wypukłych wierzchołków przeszkody, a następnie połączenie każdej pary węzłów, które mogą się widzieć . Sprawdź ten link . Węzły nie muszą być jednak wierzchołkami i mogą zostać umieszczone ręcznie przez projektanta na mapie. W takim przypadku system jest często określany jako wykres punktu trasy .