Autor Wątek: Jak szybko wykryć, że nie da się gdzieś dojść  (Przeczytany 4919 razy)

Offline Angru

  • Użytkownik

# Październik 20, 2009, 22:41:12
Załóżmy, że mamy prostą mapę z kratką taktyczną. Kratki mogą być dynamicznie blokowane i zwalniane (np. w sytuacji kiedy coś gdzieś wejdzie, lub zniszczymy jakąś barykadę). Potrzebuję wykonać wiele, częstych testów szukania drogi w stylu "jeżeli nie da się dojść do żadnego obiektu jednej klasy, to poszukajmy obiektów innej, mniej interesującej klasy itd.). Znajdowanie drogi robię na A*, która staje się bardzo nieoptymalna w sytuacji kiedy aktualnie nie istnieje żadna możliwa ścieżka. Co więcej muszę założyć, że takie sytuacje będą bardzo częste. Problem wydaje się być klasyczny dla różnego typu gier RTS (jak nie mogę iść wtłuc jednostkom wroga, to zabiorę się chociaż za mur). Sam jednak nie bardzo wiem jak to rozwiązać. Będę wdzięczny za błyskotliwe pomysły, a jeszcze bardziej za wskazanie jakiegoś standardowego rozwiązania.

Offline Mr. Spam

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

Offline ShadowDancer

  • Redaktor

# Październik 20, 2009, 22:46:07
Zrób tak, że podczas sprawdzania drogi nie bierz pod uwagę obiektów przeciwnika, tylko każ jednostkom iść do celu(i rzezać wszystko po drodze).

Offline Angru

  • Użytkownik

# Październik 20, 2009, 22:50:55
Myślałem o tym. Koncept jednak polega na tym, że zadaniem gracza będzie przeszkodzić wrogowi w szybkim i sprawnym dotarciu do pewnego celu. Przy tym rozwiązaniu będzie wystarczało, że gracz nastawia wrogowi różne crapowate kłody pod nogi, a ten będzie się z wielkim zaangażowaniem o nie wszystkie przewracał. Niestety musi być trochę bardziej przebiegły  ;)

Offline Troll

  • Użytkownik
    • Oficjalna strona gry Gizarma

# Październik 20, 2009, 23:37:17
Najprostrzym rozwiązaniem jest ucinanie obliczen algorytmu na którymś kroku.

Offline revo

  • Użytkownik

# Październik 20, 2009, 23:45:24
Jeżeli plansza jest jakimś grafem (a jest), to może warto wyliczyć co jakiś czas spójne składowe (co kilka klatek?). Wtedy mamy, że nie da się dojść, jeżeli punkty należą różnych spójnych składowych.

Offline Liosan

  • Moderator

# Październik 20, 2009, 23:46:44
A* przeprowadzasz z jednego końca, czy z obu naraz? Dwa przeszukiwania zawszę trochę uwydajniają przypadki braku ścieżki - jeśli jeden obiekt (np. docelowy) jest ogrodzony małym murkiem, to zostanie to znalezione szybko. Ale to nie są oczywiście wszystkie przypadki...

Często najprostszym rozwiązaniem takiego problemu może być zwiększenie wielkość oczek siatki - czyli np. grupować kratki w klastry "z każdego da się dojść do każdego" i szukać ścieżek pomiędzy klastrami. Oczywiście, trzeba by to dynamicznie uaktualniać.

Ot, takie dwa luźne pomysły ;)

Liosan


Offline Xion

  • Redaktor
    • xion.log

# Październik 20, 2009, 23:49:14
Najprostrzym rozwiązaniem jest ucinanie obliczen algorytmu na którymś kroku.
Albo na kroku, który jest daleko od punktu docelowego (w sensie metryki, czyli pewnie odległości euklidesowej) niż jakiś zadany próg, albo daleko od punktu startowego, albo od obu naraz. Albo możesz sprawdzać, czy wśród N ostatnich pól choć jedno przybliżyło cię do celu. Albo...

Jak widać możliwości jest mnóstwo, w tym pewnie sporo lepszych od tych co podałem. W każdym razie chodzi o to, żeby miał jakąś heurystykę ucinania obliczeń algorytmu.

Offline Angru

  • Użytkownik

# Październik 20, 2009, 23:57:08
@Troll
Pięknie, powinno wystarczyć. Bardzo lubię takie rozwiązania :) W niektorych przypadkach mogę dorzucić dochodzenie do punktu o najfajniejszej heurystyce, by agent mógł zobaczyć co tam dalej znajdzie, a nóż coś się zmieni. Dzięki, niech żyją Trolle!

@revo
Też dobre i jeszcze szybsze. Wtedy też mogę znaleść szybko stan grafu o najlepszej heurystyce szukając w ramach jednej składowej.

@Liosan
Z jednego końca. Obiekt ogrodzony małym murkiem może być częstym przypadkiem ale jeszcze nie wiem jak częstym. Twoja druga propozycja - w innym prototypie robiłem graf na zasadzie drzewa czwórkowego i jest to ogólnie fajne rozwiązanie. Nie pasuje jednak do tej konkretnej specyfiki problemu.

@Xion
Chyba tak właśnie będę kombinował i zobaczę co się najlepiej sprawdza.

Dzięki wszystkim za odpowiedzi. Nie ma to jak rozproszona burza mózgów :)

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Październik 21, 2009, 21:55:17
Często najprostszym rozwiązaniem takiego problemu może być zwiększenie wielkość oczek siatki - czyli np. grupować kratki w klastry "z każdego da się dojść do każdego" i szukać ścieżek pomiędzy klastrami. Oczywiście, trzeba by to dynamicznie uaktualniać
Tu przychodzi mi do głowy typowo gamedevowa struktura danych - drzewo czwórkowe, czyli octree. Gdyby pola mapy ułożyć w takie drzewo i dla węzłów wewnętrznych pamiętać jeden ze stanów: -cały przeszkoda -cały pusty -różnie, to może zoptymalizowałoby to przechodzenie mapy przy obliczeniach, np. poszukiwaniu drogi czy innych, także grafowych.

Offline Angru

  • Użytkownik

# Październik 21, 2009, 23:13:59
Tu przychodzi mi do głowy typowo gamedevowa struktura danych - drzewo czwórkowe, czyli octree.
Czepnę się tylko, że termin Ci się machnął  ;) drzewo czwórkowe - quadtree, drzewo ósemkowe - octree, w sumie to samo. Zgadzam się, że takie drzewo czworkowe (o zmiennej rozdzielczości) zwykle w takich sytuacjach jest dobrą optymalizacją. Tutaj jednak częstą sytuacją będzie to, że na całej mapie będziemy mieli rozsiane, zajęte, najmniejsze kratki. Nie sprawdzałem, ale intuicyjnie podejrzewam, że w większości przypadków generacja skończy się drzewem rozległym i głębokim. Z drugiej strony agentów z założenia ma być dość sporo, więc jeśli będzie mulić, będę się łapał każdego pomysłu jak to przyspieszyć.

Offline matmis

  • Użytkownik

# Październik 22, 2009, 12:42:08
istnieją zaawansowane struktury danych na dynamiczną spójność grafu, takie że zarówno wstawianie/usuwanie krawędzi jak i sprawdzanie, czy dwa wierzchołki są obecnie w tej samej spójnej składowej są względnie szybkie

Offline lewymati

  • Użytkownik

# Listopad 02, 2009, 20:44:58
istnieją zaawansowane struktury danych na dynamiczną spójność grafu, takie że zarówno wstawianie/usuwanie krawędzi jak i sprawdzanie, czy dwa wierzchołki są obecnie w tej samej spójnej składowej są względnie szybkie
pewnie chodzi o Find&Union
I nie jest to aż taka zaawansowana struktura ^.^ Jest w miarę prosta w implementacji

Offline Liosan

  • Moderator

# Listopad 02, 2009, 20:53:52
Ale dowód złożoności operacji na tej strukturze jest zaawansowany ;)

Liosan

Offline Angru

  • Użytkownik

# Listopad 02, 2009, 23:35:21
W każdym razie ja zaimplementowałem liczenie spójnych składowych, a także obcinanie przeszukiwania po n-tym kroku. To nie wystarczyło, bo mam tu chmarę agentów, będących dla siebie przy okazji dynamicznymi przeszkodami, więc było wolno i nie ładnie. Ostatecznie zrobiłem mały, szybki, reaktywny system poruszania. Agenci, trochę jak stado krów, biegną w kierunku swojego celu, wybierając na każdym kroku najbardziej pożądany z możliwych, nieblokowanych kierunków. W sytuacji kiedy nie jest możliwy żaden krok, który przybliża agenta do celu, dopiero wtedy łapie się on planowania drogi, czyli A* w jego spójnej składowej. Działa bardzo fajnie.

Offline matmis

  • Użytkownik

# Listopad 03, 2009, 10:54:40
Nie chodzi o Find-Union, bo tam jest tylko dodawanie krawędzi, a nie ma ich usuwania