Jakie są algorytmy wyszukiwania ścieżki? [Zamknięte]


Odpowiedzi:


34

Jeśli chcesz poszukać informacji i dowiedzieć się ogólnie o wyszukiwaniu ścieżek, zdecydowanie sugeruję nauczenie się więcej niż jednego algorytmu. Będziesz chciał zrozumieć ogólne pojęcia, ale być w stanie zastosować je do tego, nad czym pracujesz. Większość twórców gier, którzy muszą poważnie szukać ścieżki, kończy pisanie własnych niestandardowych algorytmów, choć w oparciu o znane rozwiązania każda gra jest inna i będzie miała inne wymagania.

Zacznę od zapoznania się z niektórymi bardziej znanymi metodami, takimi jak A *, algorytm Dijkstry, wyszukiwania głębokości i szerokości pierwszego wyszukiwania. W każdym z nich jest wiele dobrych informacji w Internecie. ( http://en.wikipedia.org/wiki/Pathfinding )

Czytając je, zwróć uwagę na zalety i wady każdego podejścia, a także rodzaj danych, na których może działać algorytm. Czy można go zastosować do ścieżek trójwymiarowych? Czy można go zmodyfikować, aby uwzględnić naszą ludzką sztuczną inteligencję, która chce unikać min na mapie?

Jeśli chodzi o wyszukiwanie ścieżek, A * jest właściwie złotym biletem, z którego wszyscy korzystają. Zdecydowanie powinieneś wiedzieć, jak to działa. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Oto dobry przykład A *, ponieważ dotyczy gry RTS, która musi brać pod uwagę podmioty o różnej wielkości: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

Powodzenia!


2
+1 za bit o tym, że programiści muszą nauczyć się dostosowywać znane rozwiązania. Jest to coś, czego wielu niedoszłych twórców gier nie rozumie.
Inżynier

22

Algorytmy wyszukiwania ścieżek są w zasadzie algorytmami rozwiązywania problemów z wyszukiwaniem grafów.

http://en.wikipedia.org/wiki/Pathfinding#Al Algorytmy

Najbardziej znany jest algorytm Djikstry: http://en.wikipedia.org/wiki/Dijkstra's_alameterm

i jego wariant algorytmu wyszukiwania A *: http://en.wikipedia.org/wiki/A*


2
Ostatni link jest zepsuty, ponieważ * nie jest postrzegany jako część: en.wikipedia.org/wiki/A%2A
Hendrik Brummermann

fixx0r3d oba linki
tenpn

Proste algorytmy wyszukiwania grafów to tylko podstawy do wyszukiwania ścieżek.
martinkunev

13

Jest to świetny początkowy zasób, który analizuje wszystkie aspekty znalezienia ścieżki w bardzo łatwym do strawienia podejściu.

Uwagi Amita dotyczące poszukiwania ścieżki

... Wyszukiwanie ścieżek rozwiązuje problem znalezienia dobrej ścieżki od punktu początkowego do celu ― unikanie przeszkód, unikanie wrogów i minimalizowanie kosztów (paliwo, czas, dystans, wyposażenie, pieniądze itp.). Ruch rozwiązuje problem podążania ścieżką i poruszania się wzdłuż niej. Można poświęcić wysiłek tylko na jeden z nich. Z jednej strony wyrafinowany pathfinder w połączeniu z trywialnym algorytmem ruchu ...


1
+1 dla Amit. Nauczyłem się A * z jego strony internetowej ponad 10 lat temu.
tenpn

Świetne ilustracje też. Wysoka jakość.
małpa

5

Wyszukiwanie ścieżek jest dość rozwiązanym problemem ... jak wspomniano w prawie każdej odpowiedzi tutaj, pewna odmiana A * będzie tym, czego używasz.

Największym wyzwaniem dla mnie jest to, jak chcesz reprezentować swoją ścieżkę . Korzystanie z siatki, ścieżek, siatek nawigacyjnych, hierarchicznych siatek lub innych złożonych struktur itp.

Nie mam na myśli żadnych konkretnych odniesień, ale eksploracja AIGameDev dostarczy Ci różnego rodzaju pomysłów na to, co tam jest.

Pamiętaj tylko, że każda reprezentacja ma swoje zalety i wady; nie chodzi o znalezienie „najlepszego”, chodzi o znalezienie tego, który najlepiej pasuje do twojej gry .



4

Istnieje kilka algorytmów wyszukiwania ścieżek.

Jednym z najbardziej popularnych jest prawdopodobnie A * ( A-Star ). Jest to bardzo przydatny algorytm, jeśli masz funkcję heurystyczną, która może dać ci szacunkowe koszty do osiągnięcia celu (na przykład byłaby to odległość widzenia od celu). Znak * jest bardzo przydatny, aby znaleźć najkrótszą ścieżkę od początku do punktu końcowego.

Poza tym istnieje również algorytm Dijkstry, który jest bardzo przydatny, aby znaleźć najbliższy przedmiot z kilku przedmiotów. Na przykład. jeśli chcesz dowiedzieć się, który power-up (lub podobny) jest najbliższy twojej postaci do grania.

Istnieje kilka innych algorytmów, ale myślę, że A * jest zdecydowanie najbardziej popularny. Mat Buckland ma doskonały rozdział o wyszukiwaniu ścieżek w swojej książkowej grze AI na przykładzie . Gorąco zachęcam do zdobycia jego kopii. W przeciwnym razie znajdziesz mnóstwo informacji online, wyszukując „Wyszukiwanie gwiazd”.


O mój. Podczas pisania tego samego słowa udzielono tej samej odpowiedzi na temat czasów gazillionów. Przepraszam :)
bummzack

Właśnie zauważyłem, że wspomniana książka znajduje się również w Google-Books (choć nie jest kompletna). Przeczytaj tutaj: books.google.com/books?id=gDLpyWtFacYC
bummzack



2

Nie jest to zbytnio elementarzem, ale omawialiśmy algorytmy graficzne w naszej klasie algorytmów zeszłej jesieni 2009. Korzystaliśmy z tej książki,

Wprowadzenie do algorytmów, wydanie trzecie - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein

http://mitpress.mit.edu/algorithms/

i ma również towarzyszące wykłady na youtube z klasy MIT.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-alameterms-sma-5503-fall-2005/video-lectures/

Rozdziały 17, 18 i 19 dotyczyły najkrótszych ścieżek.


2

Zobacz [Algorytmy wyszukiwania wykresów i drzew] na Wikipedii 1 . Są to po prostu odmiany wyszukiwania w przestrzeni kosmicznej, wystarczy przejrzeć je wszystkie i znaleźć, gdzie się różnią.

Istnieje również dyfuzja współpracy , która jest jednym z wcześniej wspomnianych algorytmów wykonanych w ciekawy sposób.


+1 Ten dokument na temat dyfuzji współpracy jest dość interesujący.
Inżynier

1
Myślę, że link jest zepsuty. Może to jest poprawny: scalablegamedesign.cs.colorado.edu/gamewiki/index.php/…
pek

-2

Ten wygląda interesująco:

http://www.codeproject.com/Articles/455 Zastanawiam się, czy to jest lepsze niż A *?


Witamy na stronie. To, co dałeś, jest znane jako odpowiedź tylko do linku, co jest odradzane. Lepiej byłoby podsumować zalety metody w swojej odpowiedzi. Następnie możesz spierać się, czy jest to lepsze niż zwykłe A *, zamiast bezczynnie zastanawiać się nad tym w tekście.
Seth Battin

Widzę, że twoja odpowiedź jest mniej więcej równa temu pytaniu (co jest niefortunne). Nie chcę cię wyróżniać, po prostu przekazałem twój wpis w kolejce do sprawdzania pierwszych postów . Niezależnie od tego poprawa odpowiedzi jest zawsze mile widziana.
Seth Battin

Powtórzę tylko to, co powiedział Seth. Podsumować.
Szary
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.