(** Cette fonction nous sera utile *)
let rec replicate (n : int) (x : 'a) : 'a list =
if n = 0 then []
else x :: (replicate (n-1) x)
(** Nous allons implémenter ici le jeu 2048 (https://play2048.co/), avec une
interface utilisateur dans le terminal.
Structures de données
---------------------
Dans le jeu 2048, on déplace des tuiles annotées avec des nombres. On va
simplement représenter chaque tuiles par un nombre. Les tuiles sont soit 0
pour une tuile vide, soit une puissance de deux. *)
module Tile = struct
type t = int
let to_string (tile : t) : string =
string_of_int tile
end
module Direction = struct
(** Déplacement
-----------
On peut déplacer les tuiles dans une des quatre directions orthogonales.
L'idéal pour représenter ces directions et d'introduire un type énuméré. *)
type t =
| Left
| Right
| Up
| Down
end
module Grid = struct
(** Ces tuiles sont placées sur une grille à deux dimensions, qu'on représente
par une liste de liste de tuiles. *)
type t = Tile.t list list
(** La grille initiale est vide. Notre grille sera de 4 tuiles de hauteur et 4
tuiles de largeur. On rajoutera des tuiles aléatoirement dessus au fur et
à mesure de l'avancée du jeu. La fonction `replicate` va nous permettre
d'initialiser une liste d'une certaine taille. *)
(** La grille initiale est donc remplie de 0 : c'est une liste de 4 liste de 4 0. *)
let empty : t =
replicate 4 (replicate 4 0)
(** On va vouloir afficher les grilles. Pour ce faire, on va définir une
fonction qui prends une grille en argument et nous retourne la chaîne de
caractère à afficher à l'écran. Pour afficher une grille, on l'affiche
ligne par ligne. Pour chaque ligne, on affiche une tuile sur 5 caractères
: 4 réservés pour le nombre (de 2 à 2048), et une espace. On utilise
`Printf.sprintf` pour cela, car `Printf.sprintf "%4d" 16` crée la chaîne
de caractère `" 16"`, c'est-à-dire qu'elle place des espaces avant le
nombres à afficher pour toujours créer une chaîne de quatre caractères. La
fonction `String.concat` quand à elle concatène une liste de chaîne en y
ajoutant la chaîne voulue entre chaque paire d'éléments. *)
let to_string (grid : t) : string =
String.concat "\n"
(List.map (fun line -> String.concat " " (List.map Tile.to_string line)) grid)
(** Exercice: une grille est *valide* si elle a exactement une taille de 4x4 et
qu'elle contient des tuiles qui sont des puissances de 2. Définir les deux fonctions
suivantes :
(* Renvoie True si la tuile est bien une puissance de 2 *)
val is_valid_tile : tile -> bool
(* Renvoie True si la grille est une grille valide, c'est-à-dire
aux bonnes dimensions et ne contenant que des tuiles valides *)
val is_valid_grid : grid -> bool
*)
(** Notre but est maintenant de définir une fonction `move` qui déplace les
éléments d'une grille dans une direction donnée. La fonction aura le type
suivant :
val move : direction -> grid -> grid
Pour cela, la fonction `move_line` va nous aider. Elle prends une ligne de
tuiles, et déplace les tuiles vers la gauche. Les tuiles de même valeurs
sont fusionnés ensembles, et leur valeur sont ajoutées. Ainsi, la ligne
`[2, 2, 8, 8]`, déplacée vers la gauche, devient `[4, 16, 0, 0]` : les deux
2 sont fusionnés en un 4, et les deux 8 sont fusionnés en un 16. *)
let rec move_line (line : Tile.t list) : Tile.t list =
match line with
| 0 :: xs -> (move_line xs) @ [0]
| x :: y :: xs when x = y -> ((x+y) :: (move_line xs)) @ [0]
| x :: xs -> x :: move_line xs
| [] -> []
(** On aura aussi besoin de transposer des grilles, qui transforme une grille
en changeant les lignes en colonnes, et inversement (c'est une transposition
de matrices classique). *)
let rec transpose (grid : t) : t = match grid with
| []
| [] :: _ -> []
| rows ->
List.map List.hd rows :: transpose (List.map List.tl rows)
(** Par exemple :
1 4 1 2 3
2 5 > transpose > 4 5 6
3 6
Pour avoir une définition simple de `move`, on va en fait se baser uniquement
sur `move_line` pour tout exprimer sous forme de déplacement vers la gauche.
Pour se déplacer vers la droite par exemple, on va inverser chaque ligne de
notre grille, utiliser `move_line` pour faire un déplacement vers la gauche, et
réinverser le résultat, ce qui a pour résultat final d'avoir fait un déplacement
vers la droite.
Pour faire un déplacement vers le haut, il faut faire une rotation avant tout.
Idem pour un déplacement vers le bas.
Pour faire une rotation vers la droite, on a presque ce que l'on veut avec
`transpose`, mais les lignes sont dans le mauvais sens: on voudrait la matrice
suivante :
1 4 3 2 1
2 5 > rotate_right > 6 5 4
3 6
On peut donc juste inverser chaque ligne : **)
let rotate_right (grid : t) : t =
List.map List.rev (transpose grid)
(** La rotation vers la gauche suit la même idée, mais plutôt que d'inverser les
lignes, on souhaite inverser les colonnes.
1 4 4 5 6
2 5 > rotate_left > 1 2 3
3 6
*)
let rotate_left (grid : t) : t =
List.rev (transpose grid)
(** On peut maintenant définir `move` en se basant sur `move_line`, `List.rev`, et
`rotate_left`/`rotate_right`. *)
let rec move (dir : Direction.t) (grid : t) : t = match dir with
| Left -> List.map move_line grid
| Right -> List.map (fun x -> List.rev (move_line (List.rev x))) grid
| Up -> rotate_right (move Left (rotate_left grid))
| Down -> rotate_left (move Left (rotate_right grid))
(** Ajouter des tuiles
------------------
On a tout ce qu'il faut pour effectuer des déplacements, mais sans ajouter de
tuiles à notre grille, celle-ci n'aura jamais aucune tuile. On définit la
fonction `add_two` qui ajoute une tuile 2 le plus à gauche possible d'une ligne,
à la place d'un 0. *)
let rec add_two (line : Tile.t list) : Tile.t list = match line with
| [] -> []
| 0 :: xs -> 2 :: xs
| x :: xs -> x :: add_two xs
(** Pour appliquer cela à une grille, on va définir une fonction plus générique qui applique une
transformation à une grille.
Une transformation est une liste de fonction, par exemple `[f1, f2, f3, f4]`.
Appliquer une transformation à une grille composée des lignes `[l1, l2, l3, l4]` reviendra à
calculer `[f1 l1, f2 l2, f3 l3, f4 l4]`.
La fonction `List.combine` nous est très utile pour cela : elle prend deux
listes, et combine les éléments sous forme de paires. Par exemple, `List.combine
[1; 2; 3] [4; 5; 6] = [(1, 4); (2, 5); (3, 6)]`. *)
let apply_transform (transform : (Tile.t list -> Tile.t list) list) (grid : t) : t =
List.map (fun (f, x) -> f x) (List.combine transform grid)
(** Finalement, on peut définir une fonction qui ajoute 2 dans une ligne à partir de
l'indice de cette ligne. Cette fonction appelle `apply_transform` avec une
transformation qui garde les lignes identiques, sauf pour la ligne où on
souhaite rajouter un 2. Pour rappel, la fonction `id` est la fonction qui
retourne son argument. *)
let add_two_to_line (line_idx : int) (grid : t) : t =
let id = fun x -> x in
apply_transform ((replicate line_idx id) @ [add_two] @ (replicate (4-line_idx-1) id)) grid
end
(** Interface
---------
Le reste du code sert à afficher notre grille à tout moment, et à lire les
événements claviers afin de déplacer les tuiles de la façon demandée. *)
let rec loop (state : Grid.t) =
Printf.printf "%s\n> %!" (Grid.to_string state);
let direction = match read_line () with
| "\027[A" -> Some Direction.Up
| "\027[B" -> Some Direction.Down
| "\027[D" -> Some Direction.Left
| "\027[C" -> Some Direction.Right
| _ -> None
in
match direction with
| Some dir ->
let state_after_move = Grid.move dir state in
let random_idx = Random.int 3 in
let state_after_adding_two = Grid.add_two_to_line random_idx state_after_move in
loop state_after_adding_two
| None -> loop state
let _ = loop Grid.empty
