[C] Gestione semplificata collisioni 2D

[MXtreme]

Salve a tutti.
Immaginatevi tante palline verdi che vagano all'interno di una finestra rimbalzandone sui lati.

Vorrei far in modo che quando si scontrino tra loro una delle due compaia e quella che rimane cambi colore.

le palline sono memorizzate in una lista doppiamente concatenata. Ecco il codice delle strutture che uso e le funzioni di inserimento e cancellazione:

typedef struct nodo{
    struct nodo *next,*prec;
    GLfloat color,x,y,v,dir; //dir è la direzione 1 top left; 2bottom left; 3 top right; 4 bottom right;
	GLint id;
}nodo;

typedef struct lista{
	struct nodo *first,*last,*index;
	int nelem;
}lista;

lista ll;

void inserisciNodo(lista *l){
	nodo *tmp;
	/*
	* questa parte gestisce il primo elemento della coda
    */
	if(l->first==NULL){
		tmp = (nodo*) malloc(sizeof (nodo));
        tmp->color=2.0;
		tmp->x=10.0;
		tmp->y=590.0;
		tmp->v=v;
		tmp->dir=4;
		tmp->id=idb;
		idb++;
        tmp->next = NULL;
        tmp->prec=NULL;
		l->first=l->last=tmp;
		l->nelem++;
        nball+=1;
    } else {
        /*
         * questa parte gestisce gli inserimenti sucessivi al primo
         */
        tmp = (nodo*) malloc(sizeof (nodo));
        tmp->color=2.0;
		tmp->x=10.0;
		tmp->y=590.0;
		tmp->v=v;
		tmp->dir=4;
		tmp->id=idb;
		idb++;
        tmp->next = NULL;
        tmp->prec=l->last;
        l->last->next = tmp;
        l->last = tmp;
		l->nelem++;
        nball+=1;
    }
}

void cancellaNodo(nodo *n){
	nodo *tmp;
	if(n->prec!=NULL){
		tmp=n->prec;
		tmp->next=n->next;
		n->prec=tmp;
		free(n);
		ll.nelem--;
	}
	else if(n->prec==NULL){
		ll.first=n->next;
		ll.nelem--;
		free(n);
	}
}

dovrei confrontare tutti i nodi tra loro e quando i 2 nodi sono "sovrapposti" ne cancello uno.
ho provato a scrivere decine di funzioni ma mi imbatto in errori di logica che non riesco a risolvere

grazie

[Ippo343]

Dov'è che trovi problemi? Nel determinare se c'è una collisione?

[Ippo343]

Verificare la collisione è facile: due circonferenze si intersecano se la distanza tra i centri è minore della somma dei raggi.

int collisione(palla_t palla1, palla_t palla2)
{
    if ( distanza(palla1.centro, palla2.centro) < (palla1.raggio + palla2.raggio) )
        return 1;
    else
        return 0;
}

La funzione che vuoi tu è semplice (pseudocodice):

FOREACH (palla1 in lista_palle)
{
    FOREACH (palla2 in lista_palle)
    {
        if (palla1 == palla2) continue;

        if (collisione(palla1, palla2))
        {
             cambia_colore(palla1);
             elimina_palla(palla2);
        }
    }
}

[MXtreme]

Ciao, ti ringrazio. Questa tua dritta mi ha aiutato a risolvere il problema che avevo.
Purtroppo ho dovuto fare qualche brutta variante perché la mia lista non funziona bene. La riguarderò meglio. Il caso per me è chiuso grazie ancora!!!

[Ippo343]

Cerca nel forum, di liste se ne è parlato fino alla nausea.

Ah, nota che l'algoritmo che ti ho dato io ha due grossi difetti:
1) E' inefficiente ( O(n^2) )

2) Immagina che la palla A intersechi la palla B la quale interseca la palla C.
Al primo ciclo viene gestita la collisione A-B: come risultato, B viene rimossa.
Al secondo ciclo, la palla B non esiste: non viene rilevata nessuna collisione per la palla C, che continua ad esistere indisturbata (quando in effetti la collisione c'era).

[MXtreme]

sì infatti non tutte si collidono sempre
dopotutto cercavo qualcosa di semplice proprio come mi hai proposto tu!