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.

[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.

[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]

à partir du moment où tu as au moins un chemin blanc, tu n'auras pas de blocage.

Un chemin blanc ne suffit pas puisqu'on ne pourra pas faire demi-tour en évitant les adjacences
Le cas de wiwaxia est imparable sauf à tester à quatre cases pour se garantir le demi-tour

[wiwaxia]

Mais non, il est très bien ce graphe ! Je retiens la référence.

... Le choix aléatoire, a priori, se fait entre le point fushia, bleu ou jaune ...

Jusque là, entièrement d'accord.

... 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 ...

Bien sûr, mais c'est toi qui le vois, comme moi et tout un chacun devant son écran; l'algorithme, tel qu'il est proposé, est myope parce que l'inventaire des positions possibles ne va pas au-delà des cases adjacentes: le saut sur la case bleue n'est donc pas interdit et amènera inéluctablement le blocage de la randonnée pseudo-aléatoire.

Il faudrait mettre au point une procédure de détection des impasses, ce qui me paraît assez difficile ... Pourquoi pas, bien sûr, mais à quel prix ?

[Flodelarab]

Bien sûr, mais c'est toi qui le vois, comme moi et tout un chacun devant son écran;

Pas du tout. Tu fais un genre de coloriage pot de peinture. Et si ta cible est touchée, alors il y a un chemin.

[wiwaxia]

Soit donc un nouveau bloc d'instructions, non mentionné jusqu'à présent, destiné à vérifier la connexité du domaine encore inexploré contenant la position actuelle et la cible.
Il faudra en principe le relancer à chaque étape; cela ne risque pas d'être un peu long ?

Cela revient à travailler sur une matrice (le corps de l'image), au lieu d'un tableau unidimensionnel de points.

[Flodelarab]

Du coup, j'ai fait le programme.


Sans ou avec les traits de construction:


De (0,0) à (99,99) dans une image 100 x 100

Pas de problèmes de coincitude.

J'ai rien contre ta méthode, Wiwaxia. Mais je doute du côté vraiment aléatoire.



Et ces 2 là ont pour point de départ (20,20) et pour arrivée (80,80) dans une image (100,100)




Le message initial parle de 800 par 600. J'avoue que ça rallonge en temps. Il faudrait optimiser.

Tu peux faire ce genre d'algorithme pour programmer une intelligence artificielle dans un jeu comme TRON, pour rester dans la partie la plus grande de l'espace.

[wiwaxia]

Pas mal, les images !

Je n'ai bien pas compris le sens de ta remarque

... Je n'ai rien contre ta méthode, Wiwaxia. Mais je doute du côté vraiment aléatoire ...

Ne confondrais-tu pas parcours aléatoire et parcours isotrope, c'est-à-dire dépourvu de toute direction privilégiée ?
Les deux ne vont pas forcément de pair.

Prenons par exemple les instructions:

Code :

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

1
2
3
4
5
6
CONST K = 4;
z:= Random(K);
CASE z OF  0: x:= x - 1;
           1: y:= y + 1;
           2: y:= y - 1
           ELSE x:= x + 1  END.

Ce code traduit un mouvement de diffusion thermique, de position moyenne nulle.
Mais dès que l'on envisage pour l'entier (K) une valeur plus élevée - par exemple (5) ou (6) - on observe une progression lente du nuage de points dans la direction des (x) croissants: au mouvement de diffusion toujours présent se superpose une migration de direction bien déterminée, caractérisée par une position moyenne au bout de (N) tirs:
x_m = N*(1 - 4/K) , y_m = 0 .

De ce point de vue, il est très facile de retrouver le parcours en biais présenté par Leododo.

Il y a en fait plusieurs façons de comprendre son projet de création d'un parcours pseudo-aléatoire:
- parcours sans contrainte de position ou d'orientation;
- parcours de direction générale donnée;
- parcours joignant deux points déterminés (liste non limitative).

Un tel processus n'exclut pas l'intervention de contraintes extérieures (ne serait-ce que la présence des bords de l'image).

[Flodelarab]

De ce que je devine, c'est pour faire un bord de mer, une côte sur une carte.
Si c'est le cas, il faudra se calmer sur le côté aléatoire.
J'en ai produit une vingtaine, et la planète qui présenterait ce genre de côtes aurait bien souffert. Trop de méandres.
Après, ça dépend aussi du niveau de zoom que tu choisis.

Mais dès que l'on envisage pour l'entier (K) une valeur plus élevée - par exemple (5) ou (6) - on observe une progression lente du nuage de points dans la direction des (x) croissants

Tu as raison. C'est une bonne idée pour son projet.
Tout est possible mais surtout d'arriver en bas. (en partant d'en haut).

[wiwaxia]

Je crois que l'algorithme initial peut être repris en imposant au nouveau point tiré aléatoirement une condition d'éloignement minimal vis-à-vis de l'ensemble du tracé déjà obtenu; la plus petite des distances séparant la nouvelle position de toutes celles déjà occupées doit dépasser un certain seuil, soit en pratique: D2min > 3 (il est plus simple de s'en tenir aux carrés) - voir le message #5 .
Ce procédé est l'équivalent des marques rouges proposées par Flodelarab; je n'ai pas eu le temps de programmer, pour comparer les temps d'exécution sur de grandes images - l'avantage, sous ce rapport, revient probablement à la solution graphique.

Il serait bon aussi de prévoir une sortie du processus de croissance du parcours, dans le cas d'un blocage accidentel, afin d'éviter un plantage do programme; arrêt qui serait déclenché après 10 ou 20 tirs refusés, par exemple.
Cela permettrait en outre de remplir au maximum l'espace disponible, si l'on veut voir ce que cela donne.

[Leododo]

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

=> Oui, javais modifié la génération aléatoire des nombre pour éviter de revenir sur mes pas =) En gros plus de chance de +1 en x et y.

A partir du dessin marron [...] 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.
J'avais fait un truc sur ce principe au siècle dernier, et ça marchait parfaitement. Le besoin était de faire des contours les plus fins possible.

=> Je n'avais pas pensé à partir de mon essai mal contraint et d'effacer ce qu'il y a en trop. C'est une piste que je vais explorer dans un second temps =)
Mon besoin est en effet de faire des contours les plus fins possible.

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.

=> Oui, c'est cela, et c'est l'élément qui me manquais : Dans ma méthode j'ai commencé à vérifier que le pixel précédent n'était adjacent qu'à 2 pixels noir, alors qu'en effet il me suffit de vérifier que le pixel suivant n'est adjacent qu'à un autre pixel noir. En gros je revenais au pixel d'avant pour rien.

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 .

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);

=> Les conditions sont tout à fait vrai, cependant en travaillant avec Java je peux vérifier l'adjacence grâce à une méthode getRGB() me renvoyant si oui ou non le pixel adjacent est utilisé =)

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 ... C'est un critère pertinent mais local, qui ne définit pas l'orientation générale du parcours.

=> C'est juste, j'avais prévu de stopper le programme dès qu'une situation comme celle ci apparaissait. Mais ça risque de me stopper tôt.

[Leododo]

Après avoir lu et surtout compris la discussion entre Flodelarab et wiwaxia, ce que j'avais initialement prévu est ce résultat présenté :

Du coup, j'ai fait le programme. Sans ou avec les traits de construction:

Je vais donc programmer ça (en Java) grâce à vos éclaircissements et je reviens vers vous dès que j'ai le même résultat =)
Par la suite je pourrai passer à une condition d'éloignement minimal vis-à-vis de l'ensemble du tracé déjà obtenu dont vous parlez =)

[wiwaxia]

J'ai écrit à la hâte un programme élémentaire susceptible de produire une parcours aléatoire en biais, ressemblant à celui de Leododo, sans les imperfections dont celui-ci peine à se débarrasser.


Faute de temps pour explorer mes archives, je m'en suis simplement tenu à une plage rectangulaire d'écran-texte (80x60), la position initiale (10, 10) se situant près du coin supérieur gauche et la zone d'arrêt correspondant au carré (10x10) placé au coin inférieur droit.

Le tir pseudo-aléatoire du déplacement élémentaire a été improvisé comme il suit:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 PROCEDURE TirageDir(VAR V_: VectW2);
   CONST I0 = 50; L1 = 10;  L2 = 2 * L1;       L3 = 3 * L1;
         I3 = 1 + (3 * I0); I4 = 1 + (4 * I0);
         I6 = 1 + (6 * I0); I7 = 1 + (7 * I0); I8 = 1 + (8* I0);
         L4 = L3 + I3;      L5 = L4 + I4;      L6 = L5 + I6;
         L7 = L6 + I7;      L8 = L7 + I8;
   VAR m: Word; Va: VectW2;
   BEGIN
     Va:= V_; m:= Random(L8 + 1);
     CASE m OF   0..L1-1: Dec(Va.y);
                L1..L2-1: BEGIN Dec(Va.x); Dec(Va.y) END;
                L2..L3-1: Dec(Va.x);
                L3..L4-1: BEGIN Dec(Va.x); Inc(Va.y) END;
                L4..L5-1: BEGIN Inc(Va.x); Dec(Va.y) END;
                L5..L6-1: Inc(Va.y);
                L6..L7-1: BEGIN Inc(Va.x); Inc(Va.y) END
                ELSE      Inc(Va.x)  END;
     V_:= Va
   END;

Une simple consultation des intervalles en cause fait apparaître la préférence donnée aux augmentations des coordonnées (x) et (y), préférence d'autant plus marquée que le terme (I0) est plus grand - de cette constante dépendent en fait toutes les autres qui n'ont pas de valeur unique.
Il conviendrait évidemment de reprendre ces calculs sur des considérations géométriques; mais il s'agit ici d'une question secondaire.

1°) J'ai tenté en vain de supprimer les boucles & auto-intersections d'un parcours généré sans contrainte autre que l'interdiction de sortie du domaine - (0 < x < 81) et (0 < y < 61); il m'a fallu renoncer à défaire ce sac de noeuds (au sens propre du terme), et d'autres plus avisés que moi viendront à bout de ce problème.

2°) Je m'en suis donc tenu au codage d'une progression respectant l'éloignement minimal par rapport aux points déjà présents, au risque du blocage évoqué auparavant. Cette contrainte est assurée par la fonction booléenne suivante, qui reprend la condition (d² > 3):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 FUNCTION TestProx(Np: Word; Po: VectW2; VAR L_: LstVw2): Bool;
   VAR k: Word; VAR Min, s, u, U2, v, V2, w: Z_32; Test: Bool;
   BEGIN
     IF (Np=0) THEN Test:= True
               ELSE BEGIN
                      s:= 0; Min:= 10000;
                      FOR k:= 0 TO (Np - 1) DO
                        BEGIN
                          w:= L_[k].x; u:= w - Po.x; U2:= Sqr(u);
                          w:= L_[k].y; v:= w - Po.y; V2:= Sqr(v);
                          s:= U2 + V2; IF ((Min>s)) THEN Min:= s
                        END;
                      IF (Min>3) THEN Test:= True
                                 ELSE Test:= False
                    END;
     TestProx:= Test
   END;

Voici l'essentiel du programme source, que chacun transposera dans son propre langage:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 CONST Nmax= 5000;
 
 TYPE VectW2 = RECORD  x, y: Word  END;
      LstVw2 = ARRAY[0..Nmax] OF VectW2;
 
 VAR Ndep, Nparc: Word; Liste: LstVw2;
 
 PROCEDURE ZeroE(VAR k: Word);
   BEGIN
     k:= 0
   END;
 
 PROCEDURE TraceP(We: VectW2);
   BEGIN
     GotoXY((We.x MOD 256), (We.y MOD 256)); Write('Û')
   END;
... / ...
 PROCEDURE Trace1(VAR Nd: Word; VAR Li: LstVw2);
   CONST NmaxTir = 100;
   VAR h, k, m: Word; Va, Ve: VectW2; Tx, Ty, Tz: Bool;
   BEGIN
     Randomize; k:= 0; Ve:= Li[0];
     REPEAT
       h:= 0;
       REPEAT
         Inc(h);                        Va:= Ve;
         TirageDir(Va);                 Tx:= ((0<Va.x) AND (Va.x<81));
         Ty:= ((0<Va.y) AND (Va.y<61)); Tz:= TestProx(k, Va, Liste)
       UNTIL (((Tx AND Ty) AND Tz) OR (h>NmaxTir));
       IF (h<=NmaxTir) THEN BEGIN
                              Inc(k);     Ve:= Va;
                              Li[k]:= Ve; TraceP(Ve)
                            END;
     UNTIL (k=(Nmax - 1)) OR ((Ve.x>70) AND (Ve.y>50)) OR (h>NmaxTir);
     IF (h>NmaxTir) THEN E(0012) ELSE E(0009);
     TraceP(Liste[k]); Nd:= k
   END;
 
 PROCEDURE InitV(Vx, Vy: Word; VAR V1: VectW2);
   VAR V2: VectW2;
   BEGIN
     WITH V2 DO BEGIN
                  x:= Vx; y:= Vy
                END;
     V1:= V2
   END;
 
 PROCEDURE InitL(VAR Li: LstVw2);
   CONST Vzero: VectW2 = (x:0; y:0);
   VAR k: Word;
   BEGIN
     FOR k:= 1 TO Nmax DO Li[k]:= Vzero
   END;
 
 PROCEDURE Trace0;
   BEGIN
     InitL(Liste);         InitV(10, 10, Liste[0]);
     E(1010);              TraceP(Liste[0]);
     F(71, 51, 80, 60, 5); E(0014)
   END;

Les parcours complets, d'aspect très variable, présentent des circonvolutions d'autant plus marquées que la constant (I0) est plus faible - les valeurs injectées allant de (1) à (50); la limite nulle correspondant au mouvement brownien isotrope dans un espace à deux dimensions.



Les parcours produits sont majoritairement interrompus par blocage interne, ou sur les frontières; l'option de fin prématurée se révèle donc indispensable, même si sa probabilité s'affaiblit sur de plus grands domaines.



Une variante du même programme permet de dénombrer les parcours bloqués en interne (NbI) ou contre les parois (NbP,) ainsi que les parcours complets (Npc) obtenus sur des séries de 10000 trajectoires aléatoires correspondant à la même valeur de (I0); les valeurs (50, 10, 5, 1) ont conduit aux résultats ci-dessous:



La proportion des parcours complets décroît de 55 à 0.06 % - ils sont donc loin d'être majoritaires, sur le domaine des valeurs utilisées.
Remarquer aussi l'évolution rapide de la nature du blocage.

[Flodelarab]

Super rapport


Je n'ai pas lâché l'affaire non plus. J'essaie d'obtenir un temps raisonnable pour un 800x600. J'avais un souvenir plus rapide du "pot-de-peinture".
Mais même en utilisant un réseau sémaphore qui permet à un pixel de savoir instantanément s'il atteint la cible ou non, c'est trop lent.
Et le demi-million de pixels empêche la récursivité. Obligé d'utiliser l'itération.

J'ai dû coder cela avec les pieds. Je retenterai ma chance.