Ricerca percorso astar di massa

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

fonte

2012-04-12 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

Usa Anti-oggetti, questo è l'unico modo per ottenere pathfinding a buon mercato, per quanto ne so: http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

Anti-oggetto in sostanza significa che invece di bot avere Ai singoli, avrai uno "swarm ai", che è legato alla tua mappa di gioco.

P.S .: Ecco un altro link di pathfinding in generale (forse il migliore di riferimento on-line disponibili): http://theory.stanford.edu/~amitp/GameProgramming/index.html

fonte

2012-04-12 10:01:55 c69

grazie per la risorsa darò un'occhiata un po 'più tardi. Anche se solo da quello che hai detto sembra che abbia più senso trovare l'intera mappa e magari impostare una direzione su ciascun "blocco" che i bot seguono .. hmmm – james

Proprio cache il risultato.

Archiviare il percorso come valore in una tabella hash (oggetto), assegnare a ciascun nodo un UUID, concatenare gli UUID per formare una chiave di tabella hash univoca e inserire il percorso in esso.

Quando si recupera il percorso di nuovo fuori dalla tabella hash, percorrere la via, e vedere se è ancora valido, se non, ricalcolare e inserire quello nuovo indietro nel.

Ci sono molti di ottimizzazione che si può fare :)

come C69 detto sciame aI o mente alveare vengono in mente: P

fonte

2013-10-28 03:54:31 Metalstorm

risposta

Problemi correlati