Próbuję stworzyć grę obrony wieży w JavaScript.Mass astar pathfinding
To wszystko idzie dobrze oprócz pathfinding ..
Używam kod Astar z tej strony: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript który używa binarny sterty (co moim zdaniem jest dość optymalna)
Problem "Mam, to chcę pozwolić ludziom zablokować ścieżkę" napastników ". Oznacza to, że każdy "atakujący" musi samodzielnie znaleźć drogę do wyjścia (ponieważ ktoś mógłby po prostu odciąć jednego "napastnika" i musiałby znaleźć własną drogę do wyjścia). Teraz 5/6 atakujących może zindeksować w dowolnym momencie bez problemu. Ale powiedzmy, że ścieżka jest zablokowana dla 10+ atakujących, wszystkie 10 z nich będzie musiało wystrzelić skrypt śledzenia w tym samym czasie, który po prostu obniża FPS do około 1/2 na sekundę.
To musi być powszechny problem dla każdego, kto ma wiele ścieżek śledzenia w dowolnym momencie, więc wyobrażam sobie, że musi istnieć lepszy sposób niż moje podejście.
Moje pytanie brzmi: jaki jest najlepszy sposób na wdrożenie algorytmu masowego odnajdywania ścieżek do wielu "botów" w najbardziej efektywny sposób.
Dzięki,
James
wygląda jak 'findGraphNode' w tym kodzie wykonuje liniowy wymiarze godzin, podczas gdy powinno być przy stałej czasu (z tabeli mieszania), więc wdrożenie jest dalekie od optymalnego. –
Zobaczę, czy mogę trochę przyspieszyć. Ale myślę, że nawet przy bardziej efektywnym odnajdywaniu ścieżek, nadal będę kończył z wolnymi framerates jeśli spróbuję i pathfind boty ... Zaczynam myśleć, że mój najlepszy zakład jest w rzeczywistości ścieżka, która wskazuje całą mapę raz na ramkę, a następnie ustawienie kierunku na każdym przejezdnym bloku dla botów, które będą podążać .. – james
@james, jeśli jest to coś w rodzaju większości obrony wieży, z grubsza ekranem mapy i bez skomplikowanych obiektów (np. boty nie kolidują ze sobą ani z innymi ruchomymi obiektami, lub zajmujesz się tym oddzielnie), tak, tak, myślę, że najlepsze byłoby obliczanie ścieżek dla całej mapy.W rzeczywistości prawdopodobnie nie musisz nawet przeliczać całej mapy w każdej klatce. Jeśli będziesz ostrożny w budowaniu algorytmu, powinieneś być w stanie określić, na które węzły ma wpływ zmiana użytkownika, i ponownie obliczyć "w górę" od tych węzłów. Brzmi interesująco! – Tim