Autor Wątek: pathfinding  (Przeczytany 1811 razy)

Offline gawron89

  • Użytkownik

# Wrzesień 07, 2010, 13:30:41
Witam.

Ostatnio robie sobie małego rpg (nie mmo) i doszedłem do fazy z ai, bedę używał A* jeśli uda mi się zrobić, jeśli nie to mam już zaimplementowany ten drugi, podobny skrypt chyba na literę 'B', nie pamiętam nazwy. Mam tam 2 rodzaje obiektów z kolizjami: unit i solid, niema kolizji miedzy jednostkami. Wszystkie obiekty są luźno poukładane na mapie, mają różną wielkość kolizji, za podstawę mają idealne koła lub kwadraty bez możliwości obrotu, i problem pojawia się gdy np. 2 obiekty solid leżą częściowo na kwadracie od siatki, a jednostka ma bardzo mały promień kolizji i mogła by się miedzy tymi obiektami przecisnąć, tylko nie bardzo wiem jak to zrobić. Co radzicie?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kuba D.

  • Użytkownik

# Wrzesień 08, 2010, 13:05:27
Najlepiej będzie się sprawować A*. Jest bardzo prosty do zaimplementowania no i gwarantuje że zawsze znajdzie ścieżkę jeśli oczywiście ona istnieje. I istnieje wiele jego wariantów oraz optymalizacji ( zarówno w celu wydajności jak i realizmu generowanych ścieżek, unikania potencjalnych zagrożeń, najlepsze ścieżki pod względem taktycznym itp).
Co do "wymijania się obiektów" to gdy już masz wygenerowaną ścieżkę, sprawdzasz ( o ile gracz znajduje się odpowiednio blisko blokującego obiektu) czy nie przecina się ona z jakimś dynamicznym obiektem. Jeśli przecina to przesuwasz lub dodajesz nowy punkt kontrolny w niedalekiej odległości od tego obiektu i sprawdzasz czy dalej się przecina, jeśli tak to znowu przesuwasz, jeśli nie to idziesz zmodyfikowaną ścieżką. Jeśli jest duże skupisko obiektów to nie ma sensu pchanie się między nimi tylko lepiej jest wyznaczyć ścieżkę przechodzącą gdzieś obok całej grupy. Oczywiście sprawdzanie czy nic nam nie stoi na drodze powinno dotyczyć tylko niewielkiego, najbliższego wycinka ścieżki.

Offline Ivian

  • Użytkownik
    • Ivian's Cave

# Wrzesień 08, 2010, 20:57:07
Mozesz zmniejszyc siatke na pathfinding. Przy dwoch stanach tablica nawet 20kx20k nie zajmie duzo miejsca. A jej iteracje mozna zoptymalizowac. Np tablica 10x10 struktur : bool tab[20][20];
bool total_free;
sposobow jest wiele.

Offline mosowski

  • Użytkownik

# Wrzesień 16, 2010, 16:44:44
Godny uwagi jest też algorytm Roya-Floyda. ( http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm )
Jest bardzo ciekawy - szukanie trasy jest bardzo szybkie (czas stały!), wymaga jedynie preprocessingu, który też można przyspieszyć prostymi heurystykami, lub zepchnąć go na GPU.

Papier: idm.me.uk/ai/wfi.pdf

Offline gawron89

  • Użytkownik

# Wrzesień 17, 2010, 00:26:57
Ostanio to  przemyślałem i doszedłem do wniosku że nie warto sobie komplikować życia ;p i rozwiąże to w ten sposób: obiekty z kolizjami nie będą się przemieszczać więc jednak będą 'snap to grid', ale sprity nie będą sztywno przypisane do pozycji, będą miały niewielki offset, co sprawi wrażenie że są ustawiane per-pixel. z a-star nie daje sobie jednak rady (wsyd ;p), narazie zostaje przy algorytmie Dijkstra, będę testował niewielkie fragmenty mapy, jakieś 50x50 wystarczy, więc chyba nie będzie problemów szybkością.

Ten algorytm Roya-Floyda dokładniej obadam jutro, dzisiaj jestem zbyt zmęczony ;p

Wszystkim dzięki za pomoc, pozdro.