Pathfinding in un mondo 3d con ostacoli?

-1

Quali sono alcuni metodi per trovare il percorso in un mondo 3d?

L'oggetto X deve spostarsi dal punto A al punto B, ma potrebbe dover evitare cose come asteroidi, pianeti o sacche di gas che rallentano l'oggetto.

Il programma utilizza un octtree e non è basato su "tile" o "grid".

Es .:
Che tipo di sistema di identificazione dei percorsi fa giochi come Homeworld 2, Peccati di un impero solare e uso simile?

Ci sarebbero molti oggetti che volano in giro in questo spazio 3d, ognuno con il punto di partenza A e il punto di destinazione B, ma ciascuno dovrebbe aggiornare periodicamente il suo percorso per evitare gli altri oggetti.

Ho implementato l'algoritmo A * prima da solo. Il meglio che posso pensare è usare un campo di flusso ma ho percepito che è molto inefficace su larga scala.

Poiché i campi di flusso devono essere calcolati su una vasta area, farlo per centinaia o addirittura migliaia di oggetti può diventare un processo lento. Supreme Commander 2 utilizza i campi di flusso per il rilevamento dei percorsi ed è possibile avere centinaia di unità. Sotto il cofano, il path-finding è molto semplice, però. Funziona solo per trovare percorsi semplici perché trovare un modo per uscire da un labirinto molto semplice è un problema e fare sì che le unità sfondino le pareti / gli edifici.

Utilizzare un campo di flusso per lo scopo suona, almeno per me, come una buona decisione. Purtroppo, non sono sicuro se sia una scelta saggia quando i campi di flusso devono essere aggiornati spesso in modo che altri oggetti possano essere evitati. O c'è forse una tecnica per calcolare tutto dall'inizio alla fine prima di spostare gli oggetti? Se c'è, non so come si chiama o come trovare informazioni al riguardo.

    
posta Solrik 16.04.2015 - 21:07
fonte

1 risposta

1

What are some methods for pathfinding in a 3d world?

Lo stesso di un mondo 2D.

La maggior parte degli algoritmi di path-path funzionano su grafici e funzioneranno felicemente con un numero arbitrario di percorsi da un nodo. Potresti avere alcune difficoltà nel costruire quel grafico dalle tue strutture dati esistenti; e potrebbe essere necessario modificare la distanza / euristica per quanto è "buono" un percorso, ma i metodi per il path-finding non cambiano.

    
risposta data 16.04.2015 - 21:13
fonte

Leggi altre domande sui tag