Propagation lumière par rayon tableau 2D

**carton99** · 25/08/2013, 22h06

Bonjour,
je suis coincé sur un problème,
J’essai de propager de la lumière sur un damier 2D, le damier est constitué d’une source lumineuse et de mur.
Les rayons lumineux se propagent de la source lumineuse en ligne droite et ne peuvent pas traverser les murs.

Je n’ai pas d’idée pour déterminer les positions du tableau qui sont dans la ligne de mire de la source lumineuse.

Une image comme exemple avec une propagation maximal de 4. Les points jaune représente les positions ou la lumière est visible.

Merci

**FR119492** · 26/08/2013, 12h05

Salut!
Au vu de ton image, il est évident que ton problème est mal formulé: par exemple, si tu fais 1 pas à gauche et 3 en bas, tu trouves un point jaune, alors que si tu fais 1 pas à droite,et 3 en haut, tu n'en trouves pas. Pourquoi?
Jean-Marc Blanc

**carton99** · 26/08/2013, 13h27

bonjour FR119492,
justement il n'y en a pas car le rayon et bloqué par le mur situé 1 pas en haut par rapport à la position de la lumière.
Je rajoute l'image avec le tracé des rayons:

Evidement je cherche un algo qui ne soit pas un tracé de rayon mais un parcourt de tableau afin d'optimiser mon code.

**bertry** · 27/08/2013, 21h30

Salut,
Tu pourrais peut-être utiliser l'Algorithme de Bresenham pour avoir la liste des cases entre ta source et la case d'arrivée: si au moins l'une d'elle est un mur alors la lumière n'y parvient pas...

**carton99** · 29/08/2013, 00h07

Merci pour ta proposition
J'avais vu cette algorithme en parcourent le web.
Malheureusement cet une optimisation d'un lancer de rayon sur un tableau.
Le problème c'est que plus le diamètre de la lumière est grand plus je doit tracer de rayon pour balayer toute une zone ce qui implique de revenir inutilement un très grand nombre de fois sur des cases déjà testé par les rayons précédent(ceux situé au plus près de la source lumineuse).

**ToTo13** · 29/08/2013, 08h29

Envoyé par carton99

Le problème c'est que plus le diamètre de la lumière est grand

Est ce que cela veut dire que la source fait plus d'une case ?
Bresenham est EXTREMEMENT rapide.

**carton99** · 29/08/2013, 12h01

Bonjour,
il n'y a pas de doute sur la rapidité de l'algorithme de Bresenham.
Le problème viens du fait que pour parcourir l'ensemble des cases alentour à la source lumineuse je suis obligé de réaliser un nombre de lancer de rayon dépendent du diamètre de la source lumineuse.
Exemple si la source lumineuse a un rayon de 1 = 9 rayons (un pas de 45degrés.)
Mais si le rayon et de 1000 ± 9000 rayons (un pas de ±0.1degrés) dans ce cas je repasse un très grand nombre de fois sur des cases déjà testé.

**pseudocode** · 29/08/2013, 12h13

Envoyé par carton99

Bonjour,
il n'y a pas de doute sur la rapidité de l'algorithme de Bresenham.
Le problème viens du fait que pour parcourir l'ensemble des cases alentour à la source lumineuse je suis obligé de réaliser un nombre de lancer de rayon dépendent du diamètre de la source lumineuse.
Exemple si la source lumineuse a un rayon de 1 = 9 rayons (un pas de 45degrés.)
Mais si le rayon et de 1000 ± 9000 rayons (un pas de ±0.1degrés) dans ce cas je repasse un très grand nombre de fois sur des cases déjà testé.

?

Il faut faire cela dans l'autre sens:
- tu prends la 1ere case du tableau (haut/gauche) et tu tires un rayon source->case. Ca te permet de déterminer la visibilité de TOUTES les cases traversées par le rayon.
- tu prends la 2nde case du tableau. Si son état est déjà connu, tu passes à la 3ème. Si son état est inconnu, tu tires un rayon source->case et tu complètes la visibilité des cases du tableau.
- etc.

On peut grandement améliorer la performance en tirant seulement des rayons source-> coins des murs. Cela définit des secteurs angulaires contenant deux zones: devant / derrière le mur.

Keywords: Ray casting, 2D, visibility

**carton99** · 29/08/2013, 12h38

Salut,
très bonne idée je vais essayer cela de suite.

**ToTo13** · 30/08/2013, 10h09

Envoyé par pseudocode

?

Il faut faire cela dans l'autre sens:
- tu prends la 1ere case du tableau (haut/gauche) et tu tires un rayon source->case. Ca te permet de déterminer la visibilité de TOUTES les cases traversées par le rayon.
- tu prends la 2nde case du tableau. Si son état est déjà connu, tu passes à la 3ème. Si son état est inconnu, tu tires un rayon source->case et tu complètes la visibilité des cases du tableau.
- etc.

On peut grandement améliorer la performance en tirant seulement des rayons source-> coins des murs. Cela définit des secteurs angulaires contenant deux zones: devant / derrière le mur.

Keywords: Ray casting, 2D, visibility

en fait mon idée était juste de faire cela en parcourant les bords du tableau.