[Java]Grafica 2d in generale: help collision detecion

[DesmoColo]

Ciao a tutti. Avrei bisogno di implementare le collision detection in una applicazione 2d che sto progettando usando le java awt. Cerco di spiegare meglio che posso la mia situazione:
- Ho una classe Window.java che si occupa di creare la finestra. All’interno vi è un metodo render così implementato:

 public boolean render (Graphics g){
        g.setColor (backgroundColor) ;
        g.fillRect (0,0,getWidth(),getHeight()) ;
        if(checkVectors == true){
            for(int h = 0; h < iterator+1;h++){
                g.drawImage(arrayImage[h],attori[h].getX(),attori[h].getY(),this);
            }
        }
 return true ;
    }

che si occupa di fare il rendering, cioè disegnare gli attori all’interno della finestra.
- Ho una classe Attore, che al suo interno ha come variabili un oggetto finestra(affinché l’attore possa avere qualche riferimento al mondo in cui si trova), le coordinate X e Y dell’attore all’interno di quella finestra. Sempre all’interno della classe Attore vi sono metodi per accedere e aggiornare le coordinate.
- Ho anche una classe ListenerAttore per la gestione degli eventi: quando viene premuto un tasto freccia vengono così aggiornate le coordinate dell’attore e questo si muove all’interno della finestra.

Vorrei sapere che architettura devo dare alla mia applicazione per la collision detection. Precisamente vorrei che un attore arriva a un margine della finestra si fermasse cioè non andasse oltre.(evitando ovviamente lo sfarfallio che puo generare del rendering). Inoltre vorrei che se vi sono più attori all’interno di una finestra, questi siano in grado di “vedersi” e fare in modo che non si possano sovrapporre.
Spero di essermi spiegato. Prima di interpellare il forum ho cercato qualche aiuto in rete, ma ho trovato vari articoli sul collision detection in 2d e vari esempi, ma non ne ho trovato alcuno che mi possa dare una mano.Se ritenete che sia più comodo per voi che mi aiutate, posso pubblicare il codice di attore e finestra.
Ciao e grazie per ora a tutti!

[PGI-Bis]

La collisione è un atto divinatorio.

Può funzionare così (non sono al corrente di altre tecniche ma è ben possibile che esistano).

1. rilevi la ncessità di spostare un certo Attore dalla posizione P0 a P1
2. sposti Attore da P0 a P1
3. Attore, in posizione P1, collide con qualcos'altro?
3.1 SI, fai reagire Attore alla collisione
4. disegni Attore

Nel caso in cui la reazione, per il tipo di elemento con cui Attore collida, sia una restrizione al movimento, annulli lo spostamento, riportando Attore da P1 a P0. Il risultato è che Attore, nel caso si trovi vicino ad un "muro" non si muoverà.

Secondo il tipo di movimento potrai dover dividere la previsione di spostamento lungo i due assi:

1. Attore deve andare da P0 a P1
2. sposti attore da P0 a (P1.x, P0.y)
3. Attore collide con qualcosa?
3.1 SI, sposti attore in (P0.x, P0.y)
4. sposti Attore in (posizioneAttore.x, P1.y)
5. Attore collide con qualcosa?
5.1 SI, sposti attore in (posizioneAttore.x, P0.y);
6. disegna Attore.

Il risultato è una forma di movimento in collisione (per angoli di collisione retti).

[DesmoColo]

scusa, ma non ho ben capito cosa dovrei fare! Come faccio a porre la domanda "stai collidendo con qulacosa" a una entita?

[PGI-Bis]

Ogni elemento che possa collidere può occupare (fisicamente o virtualmente) una certa regione di spazio.

Dato P il "punto" in cui si trova Attore, e "img" la sua immagine, la regione potrebbe essere il rettangolo:

Rectangle bounds = new Rectangle(
    p.x, p.y, img.getWidth(), img.getHeight());

Supponendo che ogni Attore abbia il suo rettangolo, la collisione diventa pane per i loro denti:

1. dato l'attore A
2. per ogni Attore B diverso da A:
2.1 se l'area di A interseca l'area di B A è in collisione con B

Il coinvolgimento dei rettangoli dovrebbe restare al livello di dettaglio. Ad esempio dichiari:

public class Attore {
    private Rectangle bounds = ...
    public boolean collidesWith(Attore that) {
        return this.bounds.intersects(that.bounds);
    }
}

Nota che la faccenda dei rettangoli è un'approssimazione. E' possibile usare i pixel che compongono le immagini degli attori per stabilire se ci sia una collisione. Puoi dire, ad esempio, che A collida con B nel caso in cui l'area di A intersechi l'area di B E almeno un pixel non trasparente dell'immagine di A coincida con un pixel non trasparente dell'immagine di B. Oppure estrai dall'immagine il contorno...insomma volendo si possono ottenere sistemi più raffinati.

Nel caso in il numero di sprite sullo schermo sia esorbitante, il "ciclone" per la verifica delle collisioni potrebbe richiede al sistema un bel po' di lavoro. Puoi ridurlo ripartendo lo spazio in cui esistono gli sprite.

Dividi lo schermo in tanti quadrati. Determini il quadrante in cui si trova l'attore. Poi stabilisci quali altri sprite si trovino nello stesso quadrante, operando una scrematura sull'insieme di sprite presenti. Poi verifichi le collisione tra l'attore e quegli sprite.

[DesmoColo]

Ho capito l'idea. Ma non mi è chiara una cosa:
Questo tipo di approccio credo funzioni se so a priori che vi sono due attori. Ma nel mio caso, il render disegna un vettore di attori. Quindi credo che a un singolo attore non basti conoscere la posizione di un altro attore, ma deve conoscere le posizioni di tutti gli altri attori presenti nell'array (e deve scartare però se stesso, visto che anch'egli è nel medesimo array) Ogni volta quindi dovrei comunicare a un singolo attore le posizioni di tutti gli altri, ma questo secondo me comprometterebbe le prestazioni dell'applicazione. Sbaglio qualcoa nel ragionamento? Scusa se la domanda e la questione possono essere banali, ma in grafica 2d non sono molto ferrato...

[PGI-Bis]

E' tutto esatto, salvo il limite dei due attori. Senza la ripartizione dello spazio in cui si muovono gli attori, l'algoritmo è un O(n)². Scriveremmo infatti:

//ArrayList<Attore> attori = lista di tutti gli attori esistenti
for(int i = 0; i < attori.size(); i++) {
    Attore a = attori.get(i);
    for(int k = 0; k < attori.size(); k++) {
        if(k == i) continue;
        Attore b = attori.get(k);
        if(a.collidesWith(b)) {
            //...gestione della collisione
        }
    }
}

Non c'è un limite al numero di attori in sè ma, come rilevi, esiste un problema di praticabilità: troppi attori potrebbero causare un degrado delle prestazioni (dipende dalle capacità della macchina).

Si può cercare una soluzione mediamente migliore. Mediamente, ma il caso peggiore è sempre un O(n²).

Se dividi lo spazio in settori quadrati e per ogni attore verifichi se questo collida con i soli attori presenti nello stesso quadrante, puoi scartare alcune collisioni con un'operazione più semplice della intersezione tra rettangoli.

Se associ ad ogni attore il quadrante in cui si trova, puoi scartare la verifica di collisione tra elementi che non si trovino nello stesso quadrante e che non siano passati da un quadrante all'altro nel ciclo corrente del motore di gioco.

Si tratta comunque di miglioramenti al "caso medio" e di semplificazioni apportate alle istruzioni che verificano la collisione (scartare alcune ipotesi con operazioni meno dispendiose della verifica per pixel, nel caso di sprite 2d).

Non so se ci siano algoritmi che abbiano un caso peggiore diverso di O(n²).