Sto cercando di creare un gioco di difesa della torre in Javascript.Ricerca percorso astar di massa
Sta andando tutto bene a parte il pathfinding ..
sto usando il codice Astar da questo sito: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript che utilizza un heap binario (che credo sia abbastanza ottimale)
il problema che ho Avendo è voglio permettere alle persone di bloccare il percorso degli "attaccanti". Ciò significa che ogni "attaccante" deve essere in grado di trovare la propria strada verso l'uscita da solo (dato che qualcuno potrebbe semplicemente tagliare un singolo "attaccante" e avrebbe dovuto trovare la propria strada verso l'uscita). Ora 5/6 attaccanti possono trovare il path in qualsiasi momento senza problemi. Ma diciamo che il percorso è bloccato per più di 10 attaccanti, tutti e 10 dovranno lanciare il suo script di path-path allo stesso tempo, il che riduce l'FPS a circa 1/2 al secondo.
Questo deve essere un problema comune per chiunque abbia un sacco di percorsi di identità in qualsiasi momento, quindi immagino ci sia un modo migliore del mio approccio.
Quindi la mia domanda è: qual è il modo migliore per implementare l'algoritmo di individuazione dei percorsi di massa su più "robot" nel modo più efficiente.
Grazie,
James
sembra che il 'findGraphNode' in quel codice prende tempo lineare, mentre dovrebbe essere tenuto costante di tempo (con una tabella hash), in modo tale che l'implementazione sia tutt'altro che ottimale. –
Vedrò di vedere se posso accelerarlo un po '. Ma penso che anche con una ricerca di percorso più efficiente finirò comunque con il framerate lento se provo a trovare i robot .. Sto iniziando a pensare che la mia migliore scommessa sia in realtà il pathfinding di tutta la mappa una volta per fotogramma, quindi impostare una direzione su ogni blocco passabile per i bot da seguire .. – james
@james se questo è qualcosa come la maggior parte delle torri di difesa, con approssimativamente un valore dello schermo di mappa e nessun conflitto complesso (cioè i bot non si scontrano tra loro o altri oggetti in movimento, o lo gestisci separatamente) allora sì, penserei che il calcolo dei percorsi per l'intera mappa sarebbe il migliore.In effetti, probabilmente non dovresti nemmeno ricalcolare l'intera mappa ogni fotogramma. Se si presta attenzione nella creazione di un algoritmo, si dovrebbe essere in grado di determinare quali nodi sono interessati da una modifica utente e ricalcolare solo 'upstream' da quei nodi. Sembra interessante! – Tim