Niska wydajność implementacji A * w grze typu tower defense

9

Tworzę grę Tower Defense we Flashu bez wstępnie zdefiniowanej ścieżki.

Chociaż moja siatka ma wymiary 40 x 40 (mała?), A * ma trudności z ponownym obliczaniem za każdym razem. Więc zrobiłem własną modyfikację, aby ułatwić ponowne obliczenie, a liczba dotkniętych komórek spadła do około 900 (podczas modyfikacji w pobliżu korzenia). Nadal zawiesza się na bardzo krótki, ale wykrywalny czas po umieszczeniu nowej wieży.

Czy to problem z implementacją, czy 40x40 to po prostu za dużo?

Edytować:

Struktura mojego kodu:

  • Wszystkie dane są zapisywane w 2d tablicy komórek.
  • Każda komórka zawiera swojego elementu nadrzędnego w kierunku ścieżki (1-8 zgodnie z ruchem wskazówek zegara) i zakodowaną bitowo tablicę swoich elementów podrzędnych na ścieżce (każdy bit reprezentuje dziecko).
  • Wyszukiwanie jest wykonywane przez A * z oszacowaniem odległości euklidesowej.
flash algorithm path-finding tower-defense Dani
źródło
Będziesz musiał być bardziej konkretny tutaj. Nie mamy pojęcia, jak wygląda twój kod, jak jest zorganizowany itp., Dlatego nie możemy wyciągać żadnych wniosków na temat tego, co powoduje jego spowolnienie.
Sean James
1
Kiedy po raz ostatni wdrożyłem A *, pamiętam, że biegnie on przez siatkę 64x64 co najwyżej 1ms. Tak, wydaje się, że jest to problem z twoją implementacją. Sugeruję opublikowanie kodu lub jego istoty, abyśmy mogli Ci pomóc.
Marc Müller,
Zobacz zmianę, którą dodałem
Dani
1
Jeśli 40x40 jest zbyt wolny, istnieje duże prawdopodobieństwo, że robisz coś bardzo złego. Opublikuj swój kod lub profiluj go. Możesz też przeskalować i zobaczyć, co się stanie - jeśli siatka 80x80 zajmuje więcej niż cztery razy więcej czasu, masz tam coś bardzo zepsutego.
ZorbaTHut,
Czy tytuł może być nieco bardziej informacyjny?
tenpn

Odpowiedzi:

4

Nie mogę komentować, ale pierwszy profil w Flex, wszystko inne jest przypuszczeniem.

Jonathan Fischoff
źródło
Jak mogę profilować projekt Flash w trybie Flex?
Dani
Tak i nie. Nie sądzę, że ładujesz projekt flash bezpośrednio. Myślę, że możesz profilować plik SWF bez źródła i nadal otrzymywać informacje o poziomie funkcji. Zrobiłbym wyszukiwanie w Google dla „profilowania projektu flash elastycznie” lub podobnego. Zrobiłem to i dostałem to: flexblog.edchipman.ca/…, co wygląda obiecująco.
Jonathan Fischoff
Dzięki, naprawdę pomogło mi znaleźć problematyczną część (nie było w algorytmie, patrz komentarz do pytania)
Dani
13

Zakładam, że niszczyciel czołgów to „Tower Defense”

Myślę, że A * idzie trochę za burtę.

Na początku gry zalej obszar gry od punktów wyjścia, aby utworzyć mapę ruchu:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

a ruch jest zawsze w kierunku kwadratu o niższej wartości.

Kiedy gracz umieszcza wieżę, zaktualizuj każdy z ośmiu sąsiednich pól: dla każdego kwadratu ustaw jego wartość ruchu o jeden więcej niż najniższą sąsiednią wartość. Jeśli wartość się zmienia, powtórz proces wyśrodkowany na zaktualizowanym kwadracie. Następnie, aby sprawdzić, czy droga do wyjścia nie jest zablokowana, upewnij się, że wszystkie kwadraty sąsiadują z kwadratem o niższej wartości.

Kiedy gracz usunie wieżę, ustaw wartość ruchu o jeden więcej niż najniższy sąsiadujący kwadrat i powtórz powyższą procedurę.

Prostszym podejściem byłoby ponowne wypełnienie zalewu.

Skizz
źródło
6
Ponowne wykonanie wypełnienia zalewowego jest droższe niż wykonanie A * w przypadku niewielkiej liczby jednostek - mniej więcej długości płyty - przynajmniej w kategoriach algorytmicznych (a ponieważ jest to Flash, stałe nie algorytmiczne, takie jak układ pamięci, prawdopodobnie mogą ” stosować bardzo skutecznie). Jest to jednak bardzo dobry model dla wielu komunikujących się jednostek i nazywa się dyfuzją kooperacyjną - scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diffusion .
@Joe Wreschnig: wow nice link. Użyłem tej techniki wcześniej, ale nigdy nie wiedziałem, jak się nazywa. Dzięki.
tenpn
@Joe, dopóki na mapie jest co najmniej kilka barier, nie sądzę, że byłoby to bardziej nieefektywne niż wywołanie A *. To znaczy, sądzę, że tylko dla szeroko otwartej, prawie bez barier mapy z kilkoma jednostkami może być gorzej.
edA-qa mort-ora-y
@edA: Z definicji zalanie musi ostatecznie dotknąć każdego dostępnego punktu na mapie; Znak * zapewnia sprawdzone górne granice liczby punktów, które musi dotknąć, czyli co najwyżej każdy dostępny punkt na mapie i zwykle znacznie mniej. Wypełnienie zalewowe jest prostszym algorytmem służącym do optymalizacji takich elementów, jak układ pamięci, ale, jak powiedziałem, we Flashu to prawdopodobnie nie ma znaczenia.
@Joe, właśnie to twierdzę, że nawet z garstką wież A * prawdopodobnie dotknie prawie wszystkich przestrzeni. Ale w przypadku N potworów wystarczy tylko total_squares / N, aby być mniej wydajnym niż wypełnienie powodziowe.
edA-qa mort-ora-y
2

Dziwne, myślałem, że odpowiedziałem na to, ale odpowiedź wydaje się zniknąć. Ustaw algorytm wyszukiwania w taki sposób, aby można go było aktualizować w kilku krokach, dzięki czemu po ustawieniu wieży i odtworzeniu animacji będziesz mógł wykonać trochę każdej klatki, a będziesz miał około pół sekundy na sekundę na aktualizację A * bez zauważalnej przerwy. To opóźnienie - jeśli nie możesz go przyspieszyć, znajdź sposób, aby to ukryć. Odtwarzanie animacji podczas umieszczania wieży byłoby naturalne dla gry i stanowi dobre miejsce do jej schowania.

Kaj
źródło
Jest to ogólnie dobry pomysł, ale zły na to konkretne pytanie. A * na tak małej siatce powinno być prawie natychmiastowe, nie zajmując znacznej ilości czasu.
davr
Słusznie. To jedyna odpowiedź, jaką mogę udzielić, która rozwiązałaby problem bez znajomości szczegółów implementacji, które spowodowałyby spowolnienie.
Kaj
0

Na początek możesz zmienić tablicę na wektor - powinno to dać ci poprawę prędkości. Opublikuj kod, a być może będziemy mogli zaproponować więcej optymalizacji.

Iain
źródło
0

Sądzę, że twoje spowolnienie jest spowodowane tym, że obliczasz ścieżkę dla wszystkich postaci jednocześnie. Obliczanie ścieżki dla jednej postaci jest szybkie, ale jeśli na scenie znajdują się dwa tuziny znaków, może to zapaść.

Zamiast tego należy rozłożyć obciążenie na kilka ramek. Rozłóż aktualizacje AI, aby różne postacie aktualizowały swoją ścieżkę w różnych ramkach. Byłoby to naprawdę zauważalne, gdyby postać nie zareagowała przed sekundą, ale tylko jedna klatka nie spowoduje złych reakcji.

jhocking
źródło
Odpowiedzi udzielono na to prawie rok temu, a doszło do zderzenia jedynie z powodu pracy edytorskiej Grace. (Nie miało to nic wspólnego ze zbyt dużą liczbą postaci.)
Dzięki, że dałeś mi znać. Nie zauważyłem dat.
jhocking