2 pièce(s) jointe(s)
[Structure de données] Chemin aléatoire
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 :weird:
Ce que ça donne vs ce que je veux :
- Le modèle idéal :
Pièce jointe 354491
- Mon meilleur résultat :aie: :
Pièce jointe 354496
Merci d'avance pour vos réponses.
4 pièce(s) jointe(s)
Où il y a beaucoup d'appelés, mais peu d'élus.
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.
Pièce jointe 358730
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:
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 (d2 > 3):
Code:
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:
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.
Pièce jointe 358719
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.
Pièce jointe 358722
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:
Pièce jointe 358734
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.
