Algoritmo per simulatore

[Lim]

Sto sviluppando un software per la simulazione di un ambiente acquoso in cui si muovono degli "oggetti".
Mi trovo a dover fare i conti con il problema della "mappatura" dell'ambiente tridimensionale in cui avviene lo spostamento. Intuitivamente mi era venuto in mente di utilizzare una matrice a 4 dimensioni (3 spaziali ed 1 temporale), in modo tale che in ogni cella della matrice venga memorizzato il riferimento all'oggetto che occupa quella posizione.
Dovendo tener conto anche delle dimensioni dei singoli oggetti, pensavo di memorizzare in un gruppo di celle adiacenti + riferimenti allo stesso oggetto (ad esempio una sfera di celle della matrice, in cui ogni cella rappresenta sempre lo stesso oggetto).

Considerata la grande differenza di dimensioni tra i singoli soggetti coinvolti e le diverse velocità di spostamento, devo per forza utilizzare una unità di misura molto piccola, il che mi porta ad avere uno spazio di propagazione enorme (non è possibile utilizzare una matrice a 4 dimensioni con oltre 100.000 celle in ogni direzione).

Quindi, ricapitolando, devo modellare un ambiente tridimensionale in cui avviene la propagazione di + soggetti di dimensioni e velocità molto diverse. devo inoltre gestire eventuali collisioni ecc...

Qualcuno ha qualche suggerimento da darmi?

[lupoxxx87]

sfruttare il paradigma degli oggetti ?

ogni elemento avrà delle caratteristiche geometriche, una terna x,y,z che andrai a modificare nel tempo, e le altre informazioni che ti servono.

se stai lavorando in un linguaggio imperativo/procedurale puoi usare delle struct

[Lim]

Beh, ho già creato una classe "Position" che tra i propri attributi ha le coordinate del centro dell'oggetto che rappresenta ed il raggio (ipotizzando oggetti sferici ovviamente). Pensavo, poi, di memorizzare nella matrice tridimensionale N riferimenti a questo oggetto Position, 1 per ogni cella che l'oggetto occupa con il suo ingombro...
Ovviamente temo di dover abbandonare questo approccio, ma l'oggetto Position lo tengo sicuramente.

Purtroppo al momento mi viene in mente soltanto di scandire, ad ogni step temporale, gli attributi di ogni oggetto Position per un confronto incrociato con tutti gli altri (migliaia...)


Tu suggerivi una cosa simile a questa?

Con l'altro approccio la gestione delle collisioni sarebbe stata molto + semplice ed immediata...

[Lim]

P.S. Sto usando Java e faccio un discreto uso dei Design Pattern...

[lupoxxx87]

una coppia di matrici tridimensionali ?

int now[][][] = ...
int next[][][] = ...

calcoli i valori temporali di new e li salvi in next, poi copi tutta next in new e riparti...

[banryu79]

Una considerazione:
se modelli lo spazio significativo per la collision detection degli oggetti come una bounding sphere (mi pare di aver capito che questo è il tuo approccio) si fa prestissimo a verificare se un singolo oggetto collide un un altro, date le loro rispettive posizioni e i rispettivi raggi delle bounding sphere: il problema, come dici, è che è costoso stare lì, per ogni oggetto, a effettuare il controllo con tutti gli altri.

Una idea che mi viene in mente è questa: se lo spazio fisico da modellare non è illimitato, si potrebbe suddividerlo in "settori".
Ogni oggetto, nella simulazione, contiene dentro di se anche il riferimento al settore in cui si trova in quel dato momento (ad ogni passo della simulazione, oltre alla posizione x,y,z andrebbe quindi aggiornato anche il settore in cui l'oggetto rientra in quel momento, e questo si può farlo rapidamente con una semplice operazione di look-up, se i settori con cui suddividere lo spazio sono precalcolati) e quando devi effettuare la collision detection di un oggetto lo confronti solo con gli oggetti che sono nello stesso settore, così risparmi il tempo del confronto con tutti gli altri.

Naturalmente va gestito il caso in cui un ogetto si trova parzialmente in due settori; inoltre la "grandezza" dei settori andrebbe tarata in modo oppourtuno.

Non so se è un approccio promettente o meno però, sono un profano in materia

[PGI-Bis]

Puoi usare una libreria per la fisica (JBullet ad esempio) oppure se devi gestire la questione da te usare un albero a ottanti.

In questo secondo caso associ ad ogni oggetto un'approssimazione del suo volume (che può benissimo essere un punto).

[Johnn]

Ma per cosa serve (studio/lavoro/svago)? E' una applicazione critica?

Come sono descritte le dinamiche del sistema? Cioè è descritto il movimento degli oggetti?

[Lim]

Grazie a tutti x gli ottimi suggerimenti, li verificherò subito domani mattina.

x l'approccio event-driven, sinceramente al momento non mi viene in mente una soluzione, ci devo ragionare su ancora un pò.

L'applicazione che sto sviluppando è per studio, diciamo che sono piuttosto libero sulla modalità di implementazione, ma poi ovviamente dovrò giustificare le scelte fatte.
Purtroppo sto sviluppando un simulatore piuttosto generico (ho progettato un'architettura di classi astratte che verranno poi implementate per le specifiche simulazioni). Quindi il movimento degli oggetti viene implementato attraverso una classe generica (astratta appunto) che ho chiamato MobilityModel, realizzando di fatto il pattern Strategy...

[Lim]

Originariamente inviato da PGI-Bis

Puoi usare una libreria per la fisica (JBullet ad esempio) oppure se devi gestire la questione da te usare un albero a ottanti.

In questo secondo caso associ ad ogni oggetto un'approssimazione del suo volume (che può benissimo essere un punto).

Albero a ottanti? ho provato a cercare info, ma non trovo nulla...
Sei sicuro che si chiami così?

[Johnn]

.

[PGI-Bis]

Originariamente inviato da Lim

Albero a ottanti? ho provato a cercare info, ma non trovo nulla...
Sei sicuro che si chiami così?

Sì.

Lo trovi con "Octree". E' come un albero a quadranti solo che dividi lo spazio in otto parti (e la parte si chiama ottante, da cui il nome).

[B|4KWH|T3]

Io non ho ben capito se la domanda è sulla simulazione o solo sulla sua rappresentazione grafica

[Lim]

La domanda è sulla simulazione, la parte grafica non è richiesta.
Durante la simulazione raccolgo dati che verranno poi rielaborati in seguito...

[-MiStO-]

gli octree, come suggerisce il buon PGI-Bis, sono la prima cosa che mi è venuta in mente per risparmiare un bel po' di lavoro

http://en.wikipedia.org/wiki/Octree

[Torav]

Se gli oggetti sono sfere completamente impenetrabili (aka sfere dure) allora conviene fare event driven, altrimenti dinamica molecolare. In entrambi i casi devi trovare un modo per evitare di fare controlli O(N^2) ad ogni passo. In questo caso solitamente si utilizzano o le linked list (dividi lo spazio in domini che contengono gli oggetti, ogni volta che un oggetto passa in un altro dominio lo togli da uno e lo metti nell'altro, si implementa facilmente come una single linked list) o le liste di Verlet (ogni particelle interagisce solamente con le particelle distanti al massimo rcut, dove rcut è un cut-off che si sceglie in base al potenziale che si utilizza). Le celle di Verlet vanno aggiornate ogni tanto: questo ritrasforma la complessità in O(N^2) ma con un prefattore molto minore di prima. Se però utilizzi le linked list per costruire le liste di Verlet allora la complessità diventa O(N). Quale metodo ti convenga utilizzare dipende da densità, potenziale di interazione, numero di oggetti, ecc

[Tesinevb]

Originariamente inviato da Lim

La domanda è sulla simulazione, la parte grafica non è richiesta.
Durante la simulazione raccolgo dati che verranno poi rielaborati in seguito...

Se devi fare una simulazione fisica non serve un'algoritmo, devi usare i vettori 3d per ogni oggetto e il tempo:

pallaPosition(x, y, z)
pallaMassa(x)
pallaSuperficie per l'attrito(x)
VelocityPalla(x)
Gravità(0, -0.98, 0) per tutti gli oggetti

AcquaLiscia gasata o ferrarelle(x)
MovimentoForzaAcqua(x, y, z)
Vento(x, y, z)

ecc, ecc...

Ma la cosa + importante per fare la simulazione ti serve la posizione del PosTerreno(x, y, z) o vasca dove si muovono gli oggetti il terreno lo dividi in celle e poi fai l'algoritmo per vedere se 2 o 3 o + oggetti si trovano nella stessa cella se si allora vai a calcolare solo la loro collissione con il bounding e il raggio
tipo:
D3DVECTOR relPos = pObject[it].Pos - pObject[k].Pos;
dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
float minDist = 1.0f + 1.0f; //raggio sfera
return dist <= minDist * minDist; //nessuna collisione
// c'è stata collisione


Non serve un'algoritmo ma un update nel loop del render() dei valori. Se hai per esempio messo una mano nella vasca allora i valori fisici si alterano e si ripercuotono sulla massa sulla velocità ecc ecc dell'oggetto/i e si alterano i loro valori ecc ecc..
e naturalmente il time legato alla velocità per ogni oggetto pos*velocita*time
tipo:
pAI->TimeWay += fElapsedTime;
position = pAI->Vel * pAI->TimeWay);


Terreno e le celle lo dividi per 10 o per cento come ti serve meglio e poi vai a vedere con la posizione attuale dell'oggetto in che cella ti trovi

terreno
4 asse y
3|||||||||
2|||||||||
1|||||||||
0---------
0 1 2 3 4 asse x

Ora per sapere in che cella ti trovi si usa fare un algoritmo in un ciclo for per scandire il terreno diviso in quadrati o celle

Edit: puoi anche usare invece un octree o albero bmp o altri modi

by okay