Discussion :

[toufraita]

Bonjour,

Je suis en train d'essayer de programmer le dessin de fractales par les L-systems, avec le principe de la tortue sur Caml-light. Le principe est simple : la tortue est définie par ses positions x et y et sa direction phi. Une chaîne de caractères est lue au fur et à mesure, et à chaque caractère correspond à une instruction. Cette chaîne est obtenue à partir d'une chaîne de départ, qui est changée à chaque itération à partir de règles que le programmeur précise. Mais là n'est pas mon problème.

J'ai plusieurs types de caractères dans ces chaînes :
* F : la tortue avance d'un pas constant l selon sa direction phi, en traçant une ligne sur son parcours.
* f : la torute se déplace de la même manière, mais sans tracer de ligne.
* + : un angle constant phi est ajouté a la direction de la torute
* - : Cet angle est cette fois soustrait.
* [ : le programme garde en mémoire l'état de la tortue.
* ] : la tortue revient au dernier état correspondant au dernier [ précédent.

Ces deux dernières commandes permettent de créer des branches dans les graphes... et me posent problème. Voici mon code qui dessine le graphe à partir d'une chaîne de caractères:

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
let dessine phrase l theta p = 
clear_graph();
let L = string_length phrase and stock = ref [] in
	for i = 0 to L-1 do
	match phrase.[i] with
		|`F`-> F p l;
		|`f`-> f p l;
		|`+`-> plus p theta;
		|`-`-> moins p theta;
		|`[`-> stock := p::(!stock);
		|`]`-> let pc = (hd !stock) in 
			p.x <- pc.x; p.y <- pc.y ; p.phi <- pc.phi;
			stock := (tl !stock);
		| _ -> ();
	done;;

la fonction prend en entrée la chaîne de carctères à étudier, phrase, le pas selon lequel avancer, l, l'angle selon lequel l'orientation change, theta, et l'état initial de la tortue, p={x:float;y:float;phi:float}.

J'ai créé auparavant les fonctions correspondant à `F`,`f`,`+`,`-`, respectivement F, f, plus et moins. Elles fonctionnent : j'ai pu faire le flocon de Von Koch.
stock est la liste conservant les états de la tortues à chaque passage de `[`, puisqu'il peut y avoir plusieurs branches imbriquées. A chaque passage devant ce caractère, l'état est stocké en début de liste. Lorsque `]` est lu, le tortue doit revenir au dernier état stocké, donc celui en début de liste. La tortue y retourne, et cet état, désormais inutile, est ôté de stock.

Et là je ne sais pas trop quoi penser du résultat... Tout à l'heure j'ai réussi à avoir des branches, mais impossible de rendre compte sur le graphe de branches imbriquées. Et il y a quelques instants, sans que j'ai fait de modifications, je n'ai même plus de branches, seulement une ligne.

Je n'arrive pas à trouver mon erreur de syntaxe et/ou de logique. Quelqu'un saurait-il m'aider?

Bien cordialement,
Toufraita

PS:au cas où ça vous intéresse, les fonctions F, f, plus, moins, et la définition du type tortue.

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
 
 
type turtule = {mutable x : float; mutable y : float; mutable phi : float};;
 
let F p l =
        let x2 = (p.x) +. l *. cos (rad_of_deg p.phi)
	and y2 = (p.y) +. l *. sin (rad_of_deg p.phi) in
              moveto (round p.x) (round p.y); lineto (round x2) (round y2);
	      p.x <- x2; p.y <- y2;;
 
let f p l =
	p.x <-  p.x +. l *. cos (rad_of_deg p.phi);
	p.y <-  p.y +. l *. sin (rad_of_deg p.phi);;	
 
let plus p theta =
	p.phi <- p.phi +. theta;;
 
let moins p theta =
	p.phi <- p.phi -. theta;;

round arrondit le flottant en entier, rad_of_deg convertit l'angle en degré en radians, puisque les fonctions cos et sin prennent en entrée des radians.

[Ptival]

Bonjour,

Après avoir porté ton programme en OCaml, j'ai fait tourner quelques tests qui me confirment que ton code marche bien, en partie.

Ce qui ne fonctionne pas, c'est ta sauvegarde des tortues via '['. Tu sauvegardes un record de références au lieu de sauvegarder leur valeur respective, tu as donc toujours du partage qui s'effectue entre toutes tes tortues en stock et ta tortue courante.

Une solution "cheap" au problème consiste à forcer une copie au moment d'empiler :

Code :

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

stock := { x = p.x; y = p.y; phi = p.phi }::(!stock)

(Il y a peut-être une fonction que j'ignore qui fait cette copie.)

(Sinon je trouve l'utilisation de références assez superflue dans ce code, mais c'est ton problème... )

Le code OCaml pour ceux qui veulent tester. J'ai changé les crochets en < > pour faire plaisir à emacs. J'ai retouché 2/3 trucs à l'arrache pour faire plaisir à OCaml.

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
 
open Graphics
 
type turtle = {
  mutable x : float;
  mutable y : float;
  mutable phi : float;
}
 
let round = int_of_float
 
let pi = 3.1415
 
let rad_of_deg a = a *. pi /. 180.
 
let fprint p l =
  let x2 = (p.x) +. l *. cos (rad_of_deg p.phi)
  and y2 = (p.y) +. l *. sin (rad_of_deg p.phi) in
  moveto (round p.x) (round p.y);
  lineto (round x2) (round y2);
  p.x <- x2;
  p.y <- y2
 
let f p l =
  p.x <- p.x +. l *. cos (rad_of_deg p.phi);
  p.y <- p.y +. l *. sin (rad_of_deg p.phi)
 
let plus p theta =
  p.phi <- p.phi +. theta
 
let moins p theta =
  p.phi <- p.phi -. theta
 
let dessine phrase l theta p =
  clear_graph();
  let len = String.length phrase
  and stock = ref [] in
  for i = 0 to len-1 do
    match phrase.[i] with
      | 'F' -> fprint p l
      | 'f' -> f p l
      | '+' -> plus p theta
      | '-' -> moins p theta
      | '<' -> stock := { x = p.x; y = p.y; phi = p.phi }::(!stock)
      | '>' ->
          let pc = (List.hd !stock) in
          p.x <- pc.x;
          p.y <- pc.y ;
          p.phi <- pc.phi;
          stock := (List.tl !stock)
      | _ -> assert false
  done
 
let test_tortue () =
  let t = { x = 100.; y = 100.; phi = 0. } in
  open_graph "";
  dessine "F+F-F+ff<FffF>-ffFffF" 50. 90. t

Pour tester :

Code :

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

1
2
3
4
5
6
7
 
$ rlwrap ocaml
        Objective Caml version X.Y.Z
 
# #load "graphics.cma";;
# #use "Turtle.ml";;
# test_tortue ();;

[gasche]

Un détail d'esthétique et de design:

Code :

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

1
2
3
4
          let pc = (List.hd !stock) in
          p.x <- pc.x;
          p.y <- pc.y ;
          p.phi <- pc.phi;

C'est pas beau et ça scale pas. Il vaudrait mieux utiliser un type immutable pour les tortues.

Code :

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

1
2
3
4
5
6
7
8
9
type turtule = {
  x : float;
  y : float;
  phi : float;
}
 
[...]
 
let plus p theta = { p with phi = p.phi +. theta }

(Toutes les fonctions qui changent l'état renvoient le nouvel état au lieu de modifier l'état existant en place)

De la même façon tu pourrais avoir ta pile d'état comme une liste immutable passée en paramètre à une fonction récursive, au lieu d'avoir une référence comme ici. Ça ferait déjà des bugs en moins.

Par ailleurs je me méfie des usages des flottants pour représenter les angles. Avec les imprécisions liées au calcul flottant tu vas à tous les coups te retrouver avec une tortue qui fait des tours sur elle-même pour partir dans une direction un peu déviée de la ligne droite. Il vaut mieux manipuler des rationnels dans πℚ.

[toufraita]

Merci de vos réponses!

Ce qui ne fonctionne pas, c'est ta sauvegarde des tortues via '['. Tu sauvegardes un record de références au lieu de sauvegarder leur valeur respective, tu as donc toujours du partage qui s'effectue entre toutes tes tortues en stock et ta tortue courante.

J'ai fait les modifications et ça marche en effet, mais faute d'expérience et de vocabulaire d'info, je n'ai pas bien compris la différence...

Pour l'usage de la référence n'est-il pas nécessaire si ma liste stock est vouée à changer au cours du programme? Je ne vois peut-être pas un solution plus élégante...

ça scale pas.

Qu'entends-tu par là?

En ce qui concerne les angles en flottants, j'ai pu faire le flocon de Von Koch avec précision. Caml reconnait-il Pi directement quand on l'écrit? Dans ce cas, avec quelle précision est-il stocké? Pour ma fonction de conversion rad/deg j'ai utilisé Pi à la précision 3,141593.

En tout cas merci encore pour vos réponses rapides et précises!

[Ptival]

J'ai fait les modifications et ça marche en effet, mais faute d'expérience et de vocabulaire d'info, je n'ai pas bien compris la différence...

Ce que tu stockais dans ta liste, c'est une structure à trois champs, qui sont des références. Lorsque tu écris :

Code :

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

stock := p :: !stock

Alors les références dans p (références à x, à y et à phi), et celles dans (List.hd !stock) sont identiques. C'est-à-dire qu'elles pointent vers la même case mutable. Du coup, quand tu fais par la suite :

Code :

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

p.x <- ...

Ca a l'effet de modifier p.x, mais cela modifie aussi le champ .x de toutes les valeurs de ta liste, puisqu'elles pointent vers la même case (que tu viens de modifier). C'est pour cela que je parlais de partage.

Ce que tu veux, c'est que ta liste contienne une copie de ta tortue au moment où elle est ajoutée dans la liste, et que les modifications faites à ta tortue ne se répercutent pas sur la copie.

Pour l'usage de la référence n'est-il pas nécessaire si ma liste stock est vouée à changer au cours du programme? Je ne vois peut-être pas un solution plus élégante...

Qu'entends-tu par là?

Que nenni !

Comme te l'a indiqué gasche, le principe va être de créer des fonctions qui transforment des tortues en de nouvelles tortues. Au lieu de :

Code :

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

1
2
3
4
 
type blatype = { x: ref int }
 
incr bla = bla.x <- !(bla.x) + 1

Tu peux écrire :

Code :

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

1
2
3
4
 
type blatype = { x: int }
 
incr bla = { bla with x = bla.x + 1 }

par exemple. Cela a pour avantages :
- déjà, cela élimine complètement le problème dans lequel tu es tombé, et toute cette famille de problèmes, puisqu'il n'y a plus de références.
- ensuite, ça favorise un code sans effets, qui sera en général plus simple à comprendre (et à débugger).

En ce qui concerne les angles en flottants, j'ai pu faire le flocon de Von Koch avec précision.

Ce contre quoi gasche te met en garde est le fait que les calculs avec des nombres flottants sont fortement approximatifs. Ce sont des calculs avec des arrondis dûs à la façon dont sont représentés ces nombres en machine, et ces arrondis peuvent s'accumuler pour te faire dériver de façon grossière.

Par exemple, il est possible qu'en sommant n fois la valeur (360.0 / x), tu ne retombes pas sur 360.0, mais sur 359.9 ou 360.1. Cela voudrait dire que ta tortue fait "plus" ou "moins" d'un tour par tour. Au bout d'une centaines de tours, elle est complètement à l'ouest.

Si au contraire, tu gardes ton angles dans une représentation plus précise (au sens calculatoire), tu ne vas pas accumuler ces erreurs au fil de l'exécution, et peut-être obtenir un résultat meilleur. A la limite tu auras une erreur par calcul lorsque tu multiplieras par Pi, mais cette erreur ne se propagera pas au calcul suivant, et ne s'accumulera donc pas.

Caml reconnait-il Pi directement quand on l'écrit? Dans ce cas, avec quelle précision est-il stocké? Pour ma fonction de conversion rad/deg j'ai utilisé Pi à la précision 3,141593.

A priori non. cf. le manuel :

Code :

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

1
2
3
 
#let pi = 4.0 *. atan 1.0;;
val pi : float = 3.14159265358979312

A priori, tu vas finir par arrondir au pixel et par te limiter à une zone de la taille d'un écran, et donc tu n'as pas besoin d'une valeur extrèmement précise de pi (mais cela n'est pas en contradiction avec mon point précédent).

[toufraita]

Tout s'éclaircit .

Merci beaucoup pour ces explications précises!