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

Chciałbym przeczytać o algorytmach wyszukiwania ścieżek. Czy jest dostępny podkład lub jakiś materiał lub tutoriale w Internecie, które byłyby dla mnie dobrym początkiem?

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!

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*

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 ...

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 .

Istnieje dobra lista na Wikipedii: Pathfinding

O ile mi wiadomo, A * i D * są dość popularne.

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”.

Oto samouczek na temat używania algorytmu Dijkstry do wyszukiwania ścieżek.

Oto dobry przykład użycia A * w grze z pewnym kodem psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

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.

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.

Ten wygląda interesująco:

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