(** Génération procédurale avec des BSP
    ====================================

    Nous allons développer un simple algorithme de génération procédurale basé
    sur la partition binaire de l'espace
    (https://fr.wikipedia.org/wiki/Partition_binaire_de_l%27espace), *binary
    space partitioning* (BSP) en anglais.  Cela peut par exemple être utile pour
    générer des niveaux dans des jeux vidéos.  La génération qu'on va faire est
    typiquement utile pour générer des niveaux de donjons dans un Roguelike, par
    exemple (https://en.wikipedia.org/wiki/Roguelike). *)

(** Notre génération procédurale est basée sur la partition de l'espace binaire,
    il nous faut donc une représentation pour les arbres binaires : *)

type 'a tree =
  | Leaf of 'a
  | Node of 'a tree * 'a tree

(** Il sera nécessaire d'accéder aux feuilles de ces arbres, on définit donc une
    fonction qui nous donne accès à toutes les feuilles. *)

let rec leaves (tree : 'a tree) : 'a list =
  match tree with
  | Leaf x -> [x]
  | Node (l, r) -> (leaves l) @ (leaves r)


(** On introduit un nouveau type : un *conteneur*, qui représente une
    sous-division rectangulaire de l'espace : la sous-division commence à un
    coordonnée précis, et a une certaine taille. *)

type container = {
  x: int;
  y: int;
  w: int;
  h: int;
}

let container_to_string {x; y; w; h} =
  Printf.sprintf "{ x = %d; y = %d; w = %d; h = %d }" x y w h

(** On va partir du conteneur représentant notre écran, en se basant sur un
    terminal de 80x24 caractères.  Cela sera notre base, c'est le plus grand
    conteneur qu'on va ensuite sous-diviser. *)

let screen : container = {
  x = 0; y = 0;
  w = 80; h = 24;
}

(** On va ensuite sous-diviser ce conteneur en deux conteneurs, soit
    horizontalement, soit verticalement. Ceci jusqu'à ce qu'on arrive à une taille
    raisonnable pour une pièce.

    On définit ce qu'est une "taille raisonnable", de façon arbitraire.
    Chaque pièce a une taille minimale et maximale, aussi bien en largeur qu'en hauteur. *)

let max_room_width : int = 20
let max_room_height : int = 10

let min_room_width : int = 6
let min_room_height : int = 4

(** On arrêtera de diviser notre espace une fois qu'on a une pièce qui a une
    taille raisonnable, c'est-à-dire qui est assez petite. *)

let is_small_enough (container : container) : bool =
  container.w < max_room_width &&
  container.h < max_room_height

(** On peut séparer un conteneur en deux aléatoirement, soit verticalement soit
    horizontalement. *)

let rand_between (low : int) (high : int) : int =
  low + (Random.int (high+1-low))

let vsplit (container : container) : container * container =
  let { x ; w; _ } = container in
  let new_width = rand_between min_room_width (w-min_room_width) in
  let left = { container with w = new_width } in
  let right = { container with x = x + new_width; w = w - new_width } in
  (left, right)

(** Exemple : screen |> vsplit |> fst |> vsplit |> fst *)

let hsplit (container : container) : container * container =
  let { y; h; _ } = container in
  let new_height = rand_between min_room_height (h-min_room_height) in
  let up = { container with h = new_height } in
  let down = { container with y = y + new_height; h = h - new_height } in
  (up, down)

(* On souhaite combiner les deux : *)

let split_ (container : container) : container * container =
  let vertical = Random.bool () in
  (if vertical then vsplit else hsplit) container

(** Le problème est qu'on risque de splitter trop dans la même direction et se
    retrouver avec des choses non désirables.  On risque même de se retrouver avec
    des tailles négatives ! En effet, considérons un conteneur de hauteur 2 par
    exemple. Si on le splitte verticalement, on va calculer sa nouvelle hauteur
    basée sur un nombre entre 10 et 2-10, donc entre 10 et -8 !  On va définir une
    variante de `split` guidée par le ratio de la hauteur sur la longueur.  Si le
    conteneur est très large et peu haut, il vaut mieux le splitter horizontalement;
    et inversement. *)

let split (container : container) : container * container =
  if container.w < min_room_width * 2 then
    hsplit container
  else if container.h < min_room_height * 2 then
    vsplit container
  else
    (if Random.bool () then vsplit else hsplit) container

(** On peut appliquer notre méthode de génération à un arbre.  On souhaite
    appliquer les splits uniquement sur les feuilles.  Si une feuille à déjà une
    taille acceptable de pièce, on ne fait rien ceci dit, ce conteneur
    représentera une pièce.  *)

let rec gen_tree (c : container) : container tree =
  if is_small_enough c
  then Leaf c
  else
    let (left, right) = split c in
    Node (gen_tree left, gen_tree right)

(** On peut finalement générer un arbre de conteneurs. *)

let generate () : container tree =
  gen_tree screen

(** On peut donc maintenant sous-diviser notre région en conteneurs.

    On va afficher cela dans le terminal.  On va utiliser un tableau pour
    représenter notre terminal. On peut ensuite parcourir les conteneurs et dessiner
    leurs frontières dans notre tableau. On pourrait le faire de manière purement
    fonctionnel, mais on va un peu tricher ici et utiliser des array. C'est en effet
    quelque chose qui s'approche plus naturellement avec des constructions mutables. *)

type terminal = char array array

(** Le terminal vide est un tableau contenant uniquement des espaces, et qui a
    la taille de l'écran. Étant donné qu'on manipule une matrice (mutable), on
    doit prendre () en argument pour retourner une matrice différente à chaque
    appel. *)

let empty_terminal () : terminal =
  Array.make_matrix screen.h screen.w ' '

(** Pour l'afficher, on affichera notre tableau caractère par caractère. En
    pratique, plutôt que de passer par un tableau, on pourrait manipuler directement
    le TTY pour afficher les caractères au bon endroit. *)

let print_terminal (terminal : terminal) : unit =
  Array.iter (fun line -> Array.iter print_char line; print_newline ()) terminal

(** On peut alors visualiser les conteneurs en dessinant leur frontières dans un
   terminal. *)

let show_containers (term : terminal) (tree : container tree) : unit =
  let put_at c (x, y) =
    Array.set (Array.get term y) x c in
  let show_container {x; y; w; h} =
    let boundaries = List.concat [
        List.init w (fun d -> (x+d, y));
        List.init w (fun d -> (x+d, y+h-1));
        List.init h (fun d -> (x, y+d));
        List.init h (fun d -> (x+w-1, y+d));
      ] in
    List.iter (put_at '*') boundaries in
  List.iter show_container (leaves tree)

let _ =
  let term = empty_terminal () in
  show_containers term (generate ());
  print_terminal term

(** Cela nous donne ceci, par exemple :

    $ ocamlc generation.ml -o generation
    $ ./generation

    De là on peut continuer la génération, par exemple pour générer un donjon pour un roguelike (https://en.wikipedia.org/wiki/Roguelike) :
    - On peut générer une pièce dans chaque conteneur. Les dimensions de la pièces seront légèrement plus petites que le conteneur.
    - On relie ensuite chaque pièce entre elles via un couloir. Si on souhaite un chemin orthogonal, on peut par exemple générer le chemin le plus court entre deux points aléatoires de deux pièces.
 *)