Sto lavorando alla ricerca del percorso per un gioco RTS, in cui sto costruendo una mesh di navigazione dalla griglia del gioco.Algoritmo di triangolazione più veloce con fori?
Ho scritto un algoritmo simile a Marching Square che crea e semplifica i confini tra le regioni percorribili e non scorrevoli della mappa. Ora ho una "mesh" composta da soli bordi. Ho bisogno di triangolare questa mesh in modo che la triangolazione finale contenga i bordi iniziali, e quindi posso rimuovere le regioni non espandibili per creare buchi nella mesh di navigazione. Per esempio, ho bisogno di fare questo ...
I triangoli rappresentano le regioni calpestabili della mappa. I fori rappresentano regioni insormontabili come montagne o edifici. La mesh può essere considerata 2D, poiché l'altezza è irrilevante. Questo è ovviamente un caso molto semplificato. La mesh di navigazione nel gioco consisterà in migliaia di vertici e molti buchi, ma potrei suddividerlo in blocchi più piccoli per l'aggiornamento dinamico.
Ho esaminato gli algoritmi di triangolazione Delaunay vincolati, che prima creano una triangolazione di Delaunay dei punti, quindi rimuovono tutti i triangoli che intersecano i bordi vincolati, quindi ri-triangolano i triangoli rimossi.
Questo sembra un po 'ridondante per i miei scopi. La mia mesh non ha bisogno di essere Delaunay, e consiste completamente di bordi vincolati, quindi mi piacerebbe saltare le triangolazioni extra se possibile. C'è un algoritmo migliore per questo? Ho guardato e guardato, e sono stato solo in grado di trovare algoritmi Delaunay vincolati. O forse ho sbagliato, e un algoritmo Delaunay vincolato sarebbe il migliore?
Ho già eseguito la ricerca del percorso della mesh di navigazione da zero, ma non ho mai dovuto generare la mesh di navigazione da solo. Gli algoritmi di triangolazione sono nuovi per me. Qualche intuizione?
Poiché non hai richieste speciali sui triangoli, un approccio più semplice come [polygon triangulation] (http://en.wikipedia.org/wiki/Polygon_triangulation) è meglio usare rispetto a Delaunay. – Ante
Ho osservato il metodo Ear-Clipping, che sembra essere leggermente più lento di una triangolazione di Delaunay, ma mi richiederebbe di ordinare i miei vertici in ordini di looping, giusto? –
Ora mi rendo conto che hai solo bordi. In ogni caso dovrai collegare e orientare i bordi, trovare una parte è all'interno di un'altra parte (per sapere se è un buco o meno) e quindi triangolare il poligono con i fori. I fori possono essere rimossi aggiungendo 2 stessi bordi da un foro a un bordo di poligono o un altro foro. Il clipping dell'orecchio è un metodo semplice e con partizionamento dello spazio (albero BSP, quad tree, ...) è più veloce di O (n^2). – Ante