(** 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.
*)