NukeBoards

Pomoc - [teoria] Wyszukiwanie ścieżki
Dexter - 29-02-2012, 00:19
: Temat postu: [teoria] Wyszukiwanie ścieżki
Hej,
mam pytanie czysto teoretyczne - nie chodzi mi o zdarzenia, a po prostu o samą zasadę działania. Starałem się to rozpracować, ale jakoś nic mi nie przychodzi do głowy.

Powiedzcie mi na jakiej zasadzie działa AI, które tworzy ścieżkę ruchu w kierunku gracza. Co mam na myśli - mamy pomieszczenie, w którym jest gracz, dwa pomieszczenia dalej znajduje się przeciwnik, jeżeli zbliżymy się do niego wystarczająco (z tym nie ma problemu, przekątna prostokątu o bokach z różnicy współrzędnych) zaczyna podążać w naszym kierunku najbliższą drogą omijając po drodze wszystkie przeszkody i idąc w kierunku gracza.

Na tej samej zasadzie chodzą jednostki w grach RTS - klikamy w jedno miejsce, a one omijają przeszkody i zbliżają się do wskazanego punktu. Chodzi mi dokładnie o zasadę działania takiego cudu.

Mam nadzieję, że napisałem wszystko w miarę czytelnie.
Z góry dzięki za odpowiedzi.

Pozdrawiam
Dexter
Andrzejek98 - 29-02-2012, 00:46
:
Po prostu przeciwnik podąża za nami sprawdzając czy na jego polu widzenia znajduje się jakiś obiekt do którego może dobić, jeśli tak >> omiń.

Prościej się nie da tego wyjaśnić, no chyba że na czynniki pierwsze ale to już nie moja działka ;)
Minty - 29-02-2012, 11:34
:
Pathfinding to nie tylko omijanie. AI robi mapę otoczenia (jako raster lub tylko węzły sieci), nadaje poszczególnym punktom wagi i potem sprawdza wszystkie drogi do celu, szukając takiej o najniższej wadze.
Fadex - 29-02-2012, 14:29
:
Są dwa typy pathfindingu. To wykorzystane w RTSach to typ wektorowy - czyli jak już wspomniane przez RXa linie i węzły, które mają za zadanie ominąć przeszkody. To drugie to typ rastrowy - czyli po prostu wyszukiwanie najkrótszej ścieżki metodą bruteforce. Teoretycznie działa wyłącznie na mapie opartej o siatkę, jednak po kilku modyfikacjach daje się je zastosować do wszystkich typów map, o ile droga nie jest za długa/sprzęt jest wystarczająco wydajny aby sprawdzić wszystkie punkty na mapie. Można też starać się optymalizować algorytm wyszukujący. Po dotarciu algorytmu do danego miejsca droga jest odtwarzana z powrotem - czyli w trakcie trwania algorytmu przechowywane są informacje jak ma poruszać się obiekt (w przypadku ruchu o siatce wystarczą 2 bity na krok - cztery kierunki)

Do obu typów wymagana jest mapa, w przypadku rastrowym wystarczy dwuwymiarowa tablica pozycji X i Y, w przypadku wektorów jest to nieco bardziej skomplikowane.
Dexter - 29-02-2012, 20:51
:
Nie miałem pojęcia, że profesjonalnie nazywa się to 'pathfinding'. Poszperałem troszkę i znalazłem metodę A*, która wydaje się naprawdę logiczna i prosta. Do jej wykorzystania przydałyby się wielowymiarowe tablice powiązane z obiektami, ma ktoś pomysł jak przez to przebrnąć? Construct udostępnia tablicę tylko trójwymiarową, a przydałaby się większa. Najlepiej, gdyby obiekty miały swoje tablice, tak jak mają values.

Jest może jakiś plugin, który daje taką możliwość? Ostatecznie podobny plugin do MMF2?
Neoqueto - 29-02-2012, 22:50
:
Do MMF2 są to:
Pathfinding Object
Advanced Path Finding Object
A* FlashString (Flash)