Algo de propagation dans une grille avec obstacle

Je cherche un algorithme de "propagation" dans une grille ou certaines cases bloque la propagation (et à termes ne laissent passer qu'un pourcentage).

En fait j'ai une grille et dans chaque cellule je veux avoir la liste de chaque voisins par niveau mais comme certaines cases bloquent ce n'est pas la distance directe. Pour faire une analogie ce serait comme la propagation d'une vague au milieu de rocher ^^

Merci de vos suggestions (un lien vers un article me suffirait ou ne serait ce que des idées) ;)

Je pense que tu expliques mal ton problème. Tel que tu le décris, il te suffit d'un tableau (2D ou 3D), voir un graphe selon ce que tu modélise, avec pour chaque cellule un coefficient de "permeablité". Tu lances une simu qui tient compte de la vitesse de propagation d'une cellule à l'autre, et tu accumules à chaque pas les objets propagés en chaque cellule.

Maintenant, soit plus précis parce que selon la dimension de ton probleme, c'est peut être un peu lourd... Il faut penser modélisation globale du problème je pense avant de tenter un algo de propagation "générique"

Hum, je ne vois pas trop comment l'expliquer mais je vais donner des détails:

J'ai une classe "environnement" qui stock les cellules (typiquement 100x100 mais à long terme une grille 1000x1000 sera bien). Ces cellules vont avoir des niveaux de voisinage (une grille de 20x20) avec une distance de voisinage (combien de cases à traverser avant d'arriver à celle là). Lors de la propagation d'une variable je vais utiliser le coefficient pour décrémenter la valeur de la variable.

Mon soucis est pour le calcul de se coefficient de manière performante. Au tout départ je pensais faire:

case1 propage à ses 8 voisins avec le coef qui va bien ( 1 ou 2^1/2), les 8 suivantes propagent à leur 8 voisines etc... mais ce n'est pas du tout performant, surtout que j'envisageais de le faire de manière dynamique (pendant l'exécution et non pas à la création).

Ayant fait quelques recherches il me faudrait peut être quelque chose comme un graphe de voronoi (http://fr.wikipedia.org/wiki/Voronoi_diagram) avec des arcs valués entre chaque point ainsi qu'un marqueur de passage mais je n'ai pas tout tout compris ^^ et surtout je ne vois pas trop comment le construire et enfin je ne sais meme pas si ce sera plus performant

Citation:

---

Ces cellules vont avoir des niveaux de voisinage (une grille de 20x20) avec une distance de voisinage (combien de cases à traverser avant d'arriver à celle là). Lors de la propagation d'une variable je vais utiliser le coefficient pour décrémenter la valeur de la variable.

---

Euuuuuhhhh... Comprends bien que le terme niveau de voisinage n'es pas comprehensible tel quel... Cette grille 20x20, c'est une sous-division de ta cellule ou une LUT des cellules voisines ("pointeurs" vers les plus proche voisins)

Citation:

---

mais ce n'est pas du tout performant, surtout que j'envisageais de le faire de manière dynamique (pendant l'exécution et non pas à la création).

---

Mais c'est fait de manière dynamique puisqu'a chaque pas tu mets a jour chaque cellule (tu peux memes mettre des obstacles en cours de route à la souris si ca t'amuses...)8O

Pour la performance tu peux toujours voir une liste des cellules ayant une activité mais ça ne changera pas ta complexité au pire cas.

Voronoi sert essentiellement (pas que mais presque) à creer des maillages... ce qui n'est pas utile dans ton cas, tu as une grille (meme distance d'une cellule à l'autre?)

Ton coefficient et son utilité me semble obscure... un exemple concret sur la propagation d'une cellule avec le calcule stp

J'ai une grille de 100x100 cellules, certaines étant des obstacles, ceux ci devraient (à terme) pouvoir être rajouté dynamiquement.

En pratique j'aurais un individu qui émet un stimulus, par exemple un son. Le volume sonore entendu dans chaque case aux alentours dépendra de la distance que doit parcourir ce son, c'est à ça que sert le coefficient.


Pour niveau de voisinage, c'est que juste les 8 cases adjacentes d'une cellules sont de niveau 1, les cases autour sont de niveau etc .... je penses m'en servir pour créer une map<niveau de voisinage / coefficient de dégradation, tableau de pointeur des cellules> (je prog en c++ ^^)

Le pseudo algorithme que je donnais dans mon msg précédent est il a peu pres clair? Car normalement avec on voit ce que je veux faire ^^


En tout cas merci de ton intérêt ;)

La modelisation de la propagation d'une onde me semble problematique avec une telle méthode... Il faut au moins ajuter une direction de propagation et un facteur d'expansion (typiquement, c'est un tel facteur qui te permettra de creer un cone non exposé derriere un obsacle)

tu selectionnes un point de depart, tu commences par parcourir tes obstacles et donc a identifier les zones cachees par les obstacles, tu les marques d'un coefficient te permettant de joué sur la permeabilité

Tu fais evolué ton onde a l'aide d'une map precalculé de la taille max de ton onde, que tu centres sur le point de depart.

Reste à multiplier par exemple la map de ton onde et le facteur de propagation lié à chaque cellule chaque cellule.

En C++ tu dois facilement pouvoir ainsi creer plusieur ondes simultanément et rajouter des obstacles a ta guise a condition de remettre a jour pour chaque onde les zones protégées.

On est loin d'être rigoureux, c'est même un peu bidouille, mais pour faire mieux il faut savoir exactement ce que tu veux modeliser, et dans quel but

Désolé je n'ai pas été très clair. L'onde n'est qu'une image.

Pour rentrer dans le détail, ma grille constitue un environnement dans lequel sont déposés des stimuli sur une case prise, charge à la case de les propager dans toutes les directions. Je souhaiterais a priori ne pas avoir de limite de propagation quitte à faire une une récursion plus couteuse, par exemple les dernières cellules de la zone sont atteintes et relaye a nouveau l'info dans toutes les directions (sans mise a jour pour les cellules ayant déjà reçu le stimulus car elles l'ont stockés).

Ta méthode me semble bonne mais le calcul du cône doit être fait pour toutes les cellules ayant l'obstacle dans leur zone de propagation (ce qui fait beaucoup de calcul non?) et il faut encore stocké une map par cellules (ouch si je suis en 1000x1000). C'est pourquoi l'idée d'un graphe de voronoi me semblait pas mal, une seule map (géante) pour tout le monde avec des distances entre chaque point (bien sur je n'ai pas toujours pas d'idée de sa création).