Impossible de trouver un titre pertinent pour ce post !
 
L'application est un jeu.
 
Le besoin est de connaître les entités qui se "voient" (cad, la distance entre deux entités du jeu est inférieure à une valeur arbitraire).
 
Je recherche un algorithme efficace pour obtenir : pour chaque entité, la liste des entités visibles.
 
Soit E l'ensemble des entités du jeu : { e1, e2, e3.... en }.
 
Soit P le prédicat tq P(e1,e2) retourne vrai si les entités e1 et e2 se "voient".
 
Soit V l'ensemble associatif des entités du jeu associées à l'ensemble des entités qui sont en vu { (e1,{ei,ej,ek...}), (e2,{ei,ej,ek...}), .... (en,{ei,ej,ek...}) }.
 
Voila l'algorithme de base [O(n²)]:
 
for ei = e1...en
   for ej = e1...en
      if ei != ej
         if P(ei,ej)
            V[ei].push(ej)
 
 
Vous l'aurez deviné.... j'y connais rien en algo. Cela dit, il y a certainement une ou plusieurs manières d'améliorer mon algo 'pourri'. Pouvez vous m'orienter vers une solution meilleure !?
 
Merci d'avance.  

Si P est symetrique, c'est a dire si P(ei,ej) <=> P(ej,ei) (ce qui est le cas d'apres tes explications), alors tu peux te contenter de faire ta deuxieme boucle de ei+1 a en. Ce qui fait encore une complexite en O(n^2), mais quand meme moitie moins de calculs.

Si la visibilité de l'ensemble des entités est recalculée à chaque fois, il faut bien sûr passer à un algorithme de type "incrémental", dans lequel la visibilité ne sera recalculée que pour les entités concernées par le dernier changement.
Il faut aussi optimiser ce qui ce trouve au coeur des boucles. Cela peut souvent se faire avec des tables précalculées.

matafan > Pas con. Si j'ai bien compris ...
 
for ei = e1...en
   for ej = ei+1...en
      if ei != ej
         if P(ei,ej)            
            V[ei].push(ej)  
            V[ej].push(ei)  
 
Olivthill > Exact (toutes les 100ms!). Je n'ai présenté que la partie algorithmie. J'ai prévu une certain nombre de "caches" à différentes étapes du traitement...

C'est ca, mais tu peux enlever le test if ei != ej puisque tu n'aura jamais ei == ej. Ca fait n*(n-1)/2 invocations de P.

Pour le test, c'est bien sur !
 
Je ne calcul pas vraiment la distance exacte (juste une approx. grossière dans un plan, jeu 2D ;-) ) :
 
| ei.x - ej.x | < d  ET | ei.y - ej.y | < d
 
Ca suffit largement !  
 
Merci à vous deux.