Algoritmo "area di influenza" basato su Silverlight

Question

Algoritmo "area di influenza" basato su Silverlight

#1 da (0 voti)

2

Sto sviluppando uno strumento per un gioco chiamato MechWarrior: Online che definisce una mappa di un'area dello spazio chiamata Inner Sphere. Essenzialmente, questa mappa è un insieme di punti (pianeti) su un piano cartesiano. Ogni pianeta può essere di proprietà di una fazione diversa, tipicamente rappresentata sulla mappa da un colore. Posso colorare i vari punti del pianeta come colori diversi, ma idealmente quello che mi piacerebbe fare è mostrare un'area di influenza (cerchio) per ogni fazione usando qualcosa come GeometryGroup per aiutare con la semplificazione dell'oggetto geometrico che usando cerchi di 2.240 punti, produrrai prima di renderlo su una tela Silverlight.

Tuttavia, non sono nemmeno sicuro che questa sia una buona idea o il modo giusto per affrontare questo problema da un punto di vista algoritmico, in particolare perché dove ci sono sovrapposizioni di influenza sui "confini" della fazione, come affrontare le sovrapposizioni mostrano in modo efficace un'area di influenza ridotta per entrambe le fazioni nella geometria risultante?

Modifica per chiarezza:

Grazie per le risposte finora - l'interpolazione dei colori non era ciò che intendevo, anche se è simile in linea di principio.

L'immagine sopra mostra due pianeti di fazione (un punto rosso, un punto blu) e le loro aree di influenza (un cerchio rosso, un cerchio blu). Nell'immagine in alto, mostra le aree di influenza (territorio) e la loro sovrapposizione. L'immagine in basso mostra come vorrei risolvere la sovrapposizione.

Questo è l'esempio più semplice a cui riesco a pensare e potrebbe essere che espandere questo aspetto su più pianeti funzionerebbe per ottenere il risultato che sto cercando, ma potrebbe diventare molto dispendioso dal punto di vista computazionale come se avessi n pianeti in una fazione e n pianeti in un altro, si potrebbe finire con un valore di notazione O grande di n al quadrato per due fazioni a causa del numero richiesto di confronti per il controllo dell'intersezione e ci sono in realtà 10 fazioni ciascuna con un minimo di due vicini, quindi è più di n al quadrato comunque.

Non sono sicuro di quale effetto effettui un'iterazione da 1 a n fazione mentre eseguo una ricerca per i pianeti nel range del diametro di influenza (cioè l'intervallo di intersezione) avrebbe comunque su quel valore n al quadrato, dato che è impossibile prevedere deterministicamente quanti pianeti sarà nel raggio d'azione tra loro. Presumo che è improbabile che siano molti.

c# algorithms xaml graphics silverlight

posta toadflakz 22.12.2014 - 17:44

fonte

1 risposta

Leggi altre domande sui tag c# algorithms xaml graphics silverlight

Separazione del server Web e dell'API REST stateless Parsing di input in più sottoclassi

score 0 · Accepted Answer

Approccio a cerchi traslucidi:

Un approccio potrebbe essere l'uso di sovrapposizioni traslucide per mostrare l'area di influenza. Dovresti essere in grado di mappare la forza d'influenza della fazione con l'intensità del colore che rappresenta la fazione.

Da lì, lascia semplicemente che i colori si sovrappongano e il colore risultante dimostra che c'è un livello di influenza ridotto nell'area condivisa dalle due fazioni.

Se le forme geometriche che stai utilizzando non ti permetteranno di fondere i colori delle forme sovrapposte, dovrai rilevare i casi in cui vi è sovrapposizione ed eseguire un calcolo per determinare quale dovrebbe essere il colore miscelato.

Approccio bordi colorati:

Un altro approccio sarebbe quello di determinare dove i cerchi di influenza si intersecano con altri cerchi e quindi creare un poligono basato sui punti di intersezione e sui resti dei cerchi. Questo approccio si allinea con quello che hai disegnato nella tua domanda: avresti cerchi con i bordi colorati, ma i centri trasparenti.

Dato che ogni particolare cerchio potrebbe essere tagliato più volte, probabilmente si vorrà iniziare con un cerchio per rappresentare l'influenza, ma trattarlo come un poligono quando si calcolano cicli successivi di sovrapposizione. Il punto qui è portare avanti la forma esistente e non fare ipotesi sulla forma iniziale. In questo modo eviti di ricalcolare il conflitto di influenza da un round completato in precedenza.

In altre parole, il pianeta ABC potrebbe dover far rifilare la cerchia dell'influenza tre volte a causa delle Fazioni in competizione. L'influenza del pianeta ABC inizia come un cerchio mappato su un poligono, diventa un vero poligono dopo il primo ritaglio e rimane un poligono per i prossimi due rifili.

Ottimizzazioni di reattività

Nascosti nella tua domanda ci sono preoccupazioni riguardo alle prestazioni generali o alla capacità di risposta di generare questa mappatura. Ci sono alcune cose che potresti prendere in considerazione per ridurre il numero di calcoli necessari.

La prima considerazione sarebbe quella di ridurre il numero di pianeti da considerare. Quindi rimuoverai qualsiasi pianeta che sia abbastanza lontano da qualsiasi altro pianeta in modo che il cerchio di influenza non possa essere influenzato.

Un'altra considerazione sarebbe quella di creare un grafico aciclico diretto (DAG) per i pianeti. Usa il DAG per determinare i vicini di un dato pianeta. Simile alla prima ottimizzazione, non ha senso verificare la sovrapposizione quando i pianeti sono troppo distanti.

Detto in un altro modo, non controlli i pianeti della Fazione A contro tutti i pianeti della Fazione B. Controlli solo i pianeti di A contro quelli di B quando sono vicini.

Un ultimo modo per ottimizzare la reattività dell'algoritmo è determinare i marcatori che influenzano la cerchia di influenza e aggiornare solo quei pianeti in cui i marcatori sono cambiati. Ciò richiede più spese generali da parte tua, perché devi monitorare lo stato del gioco. Ma non ha senso calcolare qualcosa che non è cambiato rispetto al precedente ciclo di calcoli.