(** Fractales et Automates **)




(* Quelques utilitaires *)
type Etat == int;;
type AD = { initial : int;
		arcs : Etat -> char -> Etat;
		vals : Etat -> int; (* Numéro état -> valeur *) 
	    };;

#open "graphics";;

let sgn x = if x=0. then 0 else int_of_float (x/.(abs_float x));;

let trunc x = let E=float_of_int(int_of_float x) in
	if abs_float(x-.E)>.0.5 then (int_of_float E) +(sgn x)
					else int_of_float E
;;

let Pi = 4.*.(atan 1.);;

let ecrit_bin n =
	let rec boulot result = function
		|0 -> result
		|n -> boulot (result^(string_of_int (n mod 2))) (n/2)
in boulot "" n;;

let fct_of_auto auto n =
	let state=ref 0 and transit=auto.arcs and chaine=ecrit_bin n
in	for t=0 to (string_length chaine -1) do
		state:=transit (!state) chaine.[t]
	done;
	auto.vals !state
;;

let mot auto deb fin =
	let marche chaine = let state=ref 0 and transit=auto.arcs in
		for t=0 to (string_length chaine -1) do
			state:=transit (!state) chaine.[t]
		done;
		string_of_int (auto.vals !state)

in	let result=ref "" in
		for t=deb to fin do
			result:=!result^(marche (ecrit_bin t))
		done;
		!result
;;

(* La suite de Thue Morse T(n) *)
let auto_thuemorse={initial=0;
			  arcs= (fun x y -> match (x,y) with
					|0,`0`->0
					|0,`1`->1
					|1,`0`->1
					|1,`1`->0
					|_	->failwith "Transition non prévue");
			  vals= function n->n
			 };;

let calcul n = mot auto_thuemorse 0 n;;

(* Pliage de papier P(n) *)
(* i=0; a=1; b=2; c=3 *)

let auto_pliage= {initial=0;
			arcs=(fun x y -> match (x,y) with
					|0,`0`->1
					|0,`1`->0
					|1,`0`->2
					|1,`1`->3
					|2,`0`->2
					|2,`1`->2
					|3,`0`->3
					|3,`1`->3
					|_	->failwith "Transition non prévue");
			vals=function
					|3 -> 0
					|0|1|2 -> 1
					|_ -> failwith "Erreur"
			};;

let dessine_dragon n pas =
	let fct=fct_of_auto auto_pliage
in	let calcul angl p = match p with
		|0 -> angl-.Pi/.2.
		|1 -> angl+.Pi/.2.
		|_   -> failwith "Erreur"
	and trace x y = lineto ((trunc x)+size_x()/2) ((trunc y)+size_y()/2)
in	let x=ref 0. and y=ref 0. and angl=ref 0. in
		begin
		open_graph "";
		moveto (size_x()/2) (size_y()/2);
		for t=1 to n do
			angl:=calcul !angl (fct t);
			x:=!x +. pas*.cos (!angl); y:=!y +. pas*.sin (!angl);
			trace !x !y;
		done;
		end
;;

dessine_dragon 20000 3.;;

(* La suite de Von Koch K(n) *)
let auto_vonKoch= {initial=0;
			arcs=(fun x y -> match (x,y) with
					|0,`0`->1
					|0,`1`->2
					|1,`0`->0
					|1,`1`->3
					|2,`0`->2
					|2,`1`->2
					|3,`0`->3
					|3,`1`->3
					|_	->failwith "Transition non prévue");
			vals=function
					|0|2 -> 0
					|1|3 -> 1
					|_ -> failwith "Erreur"
			};;

let dessine_flocon n pas =
	let fct=fct_of_auto auto_vonKoch 
in	let calcul angl p = match p with
		|0 -> angl +. Pi /. 3.
		|1 -> angl -. 2. *. Pi /. 3.
		|_   -> failwith "Erreur"
in	let x=ref 5. and y=ref 5. and angl=ref 0. in
	begin
	open_graph "";
	moveto (trunc !x) (trunc !y);
	for t=1 to n do
		x:=!x +. pas*.cos (!angl); y:=!y +. pas*.sin (!angl);
		lineto (trunc !x) (trunc !y);
		angl:=calcul !angl (fct t);
	done;
	end
;;

dessine_flocon 1024 3.;;
dessine_flocon 4096 1.;;