Discussion :

[Leododo]

Bonjour à tous,

J'ai ici besoin d'aide pour déterminer le modèle de mon programme, sa structure de données. En gros, de quelle façon le réaliser.

Ce que je veux faire :
- Construire un chemin aléatoire pixel par pixel sur une image png.

Ce que j'utilise :
- Une image de type BufferedImage (img=new BufferedImage(800,600,BufferedImage.TYPE_INT_ARGB)

Les contraintes que je me fixe :
- Un pixel du chemin ne peut être adjacent qu'à deux autres pixels de ce chemin.
- Pour un pixel donné il existe 8 pixels adjacents et non 4 : je prends en compte les coins du pixels.

Ce que j'ai déjà réalisé :
- Une classe MapBuilder qui construit un chemin (ma classe Way) et écrit l'image à l'aide de ma classe ShowImagePNG.
- MapBuilder fait appel à ma méthode buildBoundaries() qui construit une nouvelle instance de Way.
Mais ceci n'est peut être pas la bonne chose à faire

Ce que ça donne vs ce que je veux :
- Le modèle idéal :

- Mon meilleur résultat :


Merci d'avance pour vos réponses.

[Flodelarab]

Bonjour

Les contraintes que je me fixe :
- Un pixel du chemin ne peut être adjacent qu'à deux autres pixels de ce chemin.

Le premier dessin respecte cette contrainte.
Le second non.

C'est cette contrainte que tu ne vérifies pas assez. Tu ne dis rien sur ton algorithme, ta méthode.
Il faudrait vérifier que le nouveau point du chemin n'a que 1 seul point noir autour de lui. Sinon, le chemin aura plus que 2 pixels adjacents à la fin.
Le sous-entendu de l'énoncé est que les 2 pixels adjacents sont le pixel précédent et le pixel suivant.

Pas de possibilité ? C'est que tu as fini de voyager.

[wiwaxia]

Bonjour,

Le tracé aléaoire envisagé amène plusieurs questions:

1°) La condition d'adjacence (ou si l'on veut de proximité); elle peut s'exprimer simplement à l'aide du carré de la distance euclidienne séparant les deux pixels: D_ij² = (x_i - x_j)² + (y_i - y_j)² .
On observe en effet les valeurs suivantes à parir d'un pixel donné:
_ 0 _ 1 _ 4

_ 1 _ 2 _ 5

_ 4 _ 5 _ 8
ce qui conduit à la condition de proximité: D_ij² <3 .

2°) La genèse du parcours, pour la quelle on peut envisager plusieurs procédés:

a) Une suite de tirages aléatoires inconditionnels, avec une plus grande probabilité d'augmentation des coordonnées - ce que paraît avoir fait Leododo; il faut alors faire disparaître les zones d'accumulation par suppression de points intermédiaires par des instructions telles que celles-ci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
FOR h:= Hmax DOWNTO 2
  FOR k:= 1 TO (Kmax - h) DO
    IF (Dist2(P[k], P[k + h]<3) THEN <Supprimer les points de rang k+1, k+2 ... k+h-1>

La borne Hmax (= 5 ou 10 ?) représente la limite au-delà de laquelle il n'y a plus de positions adjacentes - dans le pire des cas, Hmax = Kmax - 1 .

b) Une suite de tirages conditionnels impliquant la non-proximité du nouveau point avec tous les précédents, comme le propose Flodelarab, mais sans contrôle sur la position finale et le nombre (Kmax) de points: la progression du tracé risque en effet de se bloquer dans l'une de ses sinusoïtés avant de parvenir à son terme.
Il faudrait prévoir une marche arrière assez laborieuse à programmer ...

c) En partant de deux points arbitrairement choisis, une insertion systématique de nouveaux points intermédiaires entre ceux déjà présents et non adjacents (D_ij² > 2), par un tirage aléatoire à l'intérieur d'un cercle contré au milieu du segment (P[i]P[j]) et de rayon proportionnel à sa longueur, en codant par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Xc:= 0.5 * (P[i].x + P[j].x); Yc:= 0.5 * (P[i].y + P[j].y); 
D2:= Sqr(P[i].x - P[j].x);    Inc(D2, Sqr(P[i].y - P[j].y));
R2max= (q/4) * D2;            Rmax:= Sqrt(R2max);
REPEAT
  w:= Rmax * Rand; u:= (2*w) - 1; U2:= Sqr(u);
  w:= Rmax * Rand; v:= (2*w) - 1; V2:= Sqr(v); s:= U2 + V2
UNTIL (s<R2max);
Pixel.x:= Round(Xc + u); Pixel.y:= Round(Yc + v);

D'autres conditions doivent être prévues, entre autres pour l'arrêt.

Le paramètre (q) caractérise l'aspect général du trajet, de nature fractale; lorsqu'il est nul, on obtient un segment rectiligne joignant les pixels extrêmes, initialement choisis.
Il existe probablement une limite (Qmin) en-dessous de laquelle les auto-intersections ne sont plus possibles, mais je ne l'ai pas calculée.

[Flodelarab]

b) Une suite de tirages conditionnels impliquant la non-proximité du nouveau point avec tous les précédents, comme le propose Flodelarab, mais sans contrôle sur la position finale et le nombre (Kmax) de points: la progression du tracé risque en effet de se bloquer dans l'une de ses sinusoïtés avant de parvenir à son terme.
Il faudrait prévoir une marche arrière assez laborieuse à programmer ...

Pas du tout de retour en arrière. Quand un point noir a son suivant et son précédent, on colorie ses voisins blancs en rouge (cases interdites).
Et on s'assure d'avoir toujours au moins 1 chemin blanc vers la cible.
À la fin, on colorie tous les points rouges en blanc.

[wiwaxia]

... Quand un point noir a son suivant et son précédent, on colorie ses voisins blancs en rouge (cases interdites) ...

Est-il bien sûr que cela supprime toute possibilité d'impasse, quelle que soit la largeur de la plage de sécurité ? Celle-ci ne fait que prévenir l'auto-intersection ...

Qu'arrivera-t-il une fois que l'on sera parvenu au point (M) ?
(le tracé est très mauvais, j'en conviens).

Pour être juste, la probabilité d'auto-piégeage devient très faible si le déplacement aléatoire présente un caractère directionnel suffisamment affirmé, par exemple en codant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
CONST Kx = 9;
... / ...
k:= Rand(Kx);
CASE k OF  0: Dec(x); 1: Inc(y); 
           2: Dec(y) ELSE Inc(x)  END;

ce qui donne deux chance sur trois à une augmentation de la coordonnée (x).

... Il faudrait vérifier que le nouveau point du chemin n'a que 1 seul point noir autour de lui. Sinon, le chemin aura plus que 2 pixels adjacents à la fin ...

C'est un critère pertinent mais local, qui ne définit pas l'orientation générale du parcours.

... Et on s'assure d'avoir toujours au moins 1 chemin blanc vers la cible ...

Toute la question est là: comment se ménager un tel chemin ?
Et l'existence d'une cible suppose une visée: cela devrait se retrouver dans les instructions du tirage aléatoire ...

[Flodelarab]

Est-il bien sûr que cela supprime toute possibilité d'impasse, quelle que soit la largeur de la plage de sécurité ?

Oui

(le tracé est très mauvais, j'en conviens).

Le tracé est mauvais, non pas à cause du dessin, mais car il manque tous les points rouges.

Qu'arrivera-t-il une fois que l'on sera parvenu au point (M) ?

Un dessin pourri en vaut un autre: (merci Libreoffice)


Le dernier point accepté pour le chemin est le point gris. En fait, il est noir mais c'est pour qu'on se repère.
Ce point étant déterminé, le point du dessous est complet: un précédent et un suivant.
Donc on colorie autour de ce dernier. Cela fait un joli col roulé au point gris.
Le choix aléatoire, a priori, se fait entre le point fushia, bleu ou jaune. Je n'ai pas mis vert pour ne pas faire croire qu'il y aurait une bonne réponse a priori.
Si le hasard choisissait le bleu, fushia et jaune deviendraient rouge et il n'y aurait plus de chemin blanc vers la cible. Donc bleu n'est pas un choix.
Par contre, fushia et jaune évitent le cul de sac.

Peut-on imaginer une situation où tous les choix sont bloquants ?
Je ne pense pas.
C'est le principe de la liberté. Tout est permis tant que ce n'est pas interdit.
Tu peux avoir des situations de fausse liberté où tu crois choisir alors que le seul chemin possible est le chemin blanc.
Mais à partir du moment où tu as au moins un chemin blanc, tu n'auras pas de blocage.

[valentin03]

Il y a déjà un soucis dans la génération de l'aléatoire puisqu'on voit une incrémentation quasi linéaire en x et y
A moins que ce soit dans les corrections apportées lors des adjacences

[tbc92]

A partir du dessin marron :
- Etape 1 : identifier le début(A) et la fin(B) du tracé : ici, en gros le point le plus bas et le plus haut du tracé. Ces points ne seront jamais effacés. Et ce qu'on va chercher à faire, c'est effacer les points en trop, jamais en ajouter.
- Etape 2 : Pour chaque point, s'il a un seul voisin, effacer ce point, mais sans jamais effacer les points A et B définis ci-dessus. Et boucler sur cette étape 2 tant qu'il y a des changements.
- Etape 3 : pour chaque rectangle 3x3, si le point central est actif, et si on est dans une des configurations anormales, effacer le point central.
Et boucler sur cette étape 3, tant qu'il y a des changements.

Exemple de rectangles 3x3 :
110 000 010 111
011 011 011 011
000 010 010 000
Dans ces 3 configurations, et dans toutes les configurations similaires obtenues par rotation ou symétrie, on peut effacer le point central, il est en trop. Il y a peut-être d'autres configurations où il faut effacer le point central, tu devrais les trouver assez vite.

Je n'ai plus les codes, donc je peux me tromper, mais j'avais fait un truc sur ce principe au siècle dernier, et ça marchait parfaitement.
Le besoin était un peu différent. Le besoin était de faire des contours les plus fins possible. Si tu as une forme comme une ile au milieu de ton trait (comme c'est le cas vers le bas de ton dessin), cet algorithme laissera les 2 branches autour de cette ile.