Introduction
Existe-t-il des personnes qui n'apprécient pas les labyrinthes ? J'ai récemment interrogé quelques-uns de mes collègues à ce sujet et, à ma surprise, j'ai découvert que bon nombre d'entre eux ne partagent pas cet enthousiasme. Certains sont moins extrêmes et accepteraient de se prêter au jeu à condition d'avoir une tronçonneuse. Mais je vais partir du principe que si vous avez ouvert cet article, c'est que ça vous amuse au moins un peu. Par ailleurs l'idée est plutôt de les disséquer au scalpel, si cela peut donner l'envie à certains lecteurs à se lancer 😄
Cet article présente un projet qui génère des labyrinthes simples. Par simple j'entends avec des cellules carrées, un système orthonormé, pas de tunnels, pas de chemins multiples, pas de tronçonneuse (navré, Boss, peut-être dans un prochain article).
La plupart des concepts fondamentaux présentés ici s'inspirent de l'ouvrage 'Mazes for Programmers', écrit par Jamis Buck. En utilisant le langage Kotlin, je m'efforce de vous initier à certaines pratiques de programmation attrayantes. Au cours de notre discussion, nous évoquerons certains design patterns sans pour autant les nommer explicitement. Essayez de les identifier au fur et à mesure. C'est parti !
C'est quoi un labyrinthe ?
Un labyrinthe est essentiellement une grille avec des passages qui relient certaines cellules adjacentes. Cette grille est finie et contient donc des limites. En général, on démarre d'une grille où toutes les positions sont isolées et on creuse des passages entre des paires de positions. Voici donc une interface qui représente une telle grille.
package net.pijcke.mazes
interface Grid<P: Position<P>> {
fun getPositions(): Collection<P>
fun isWithinBounds(position: P): Boolean
fun link(position1: P, position2: P)
fun linked(position1: P, position2: P): Boolean
}Une grille est paramétrée par un type de position, lui-même paramétré par ... un type de position ?
Un système de coordonnées
Dans cet article nous nous limiterons aux positions cartésiennes simples, c'est-à-dire des couples (x, y) où x et y sont entiers. Pour autant, vu qu'un jour nous utiliserons des cellules plus amusantes telles que des triangles plus ou moins équilatéraux, des hexagones, des tridécagones et bien d'autres, nous laissons déjà ouverte cette possibilité. Du coup, bien que notre interface Position ressemblait à ceci pour commencer ...
package net.pijcke.mazes
interface Position {
fun neighbours(): List<Position>
}... malheureusement ça ne suffit pas, car quand nous récupérerons la liste des voisins d'une position cartésienne, nous voulons en retour des positions cartésiennes, pas des positions au sens général du terme. L'astuce habituelle en Java ou Kotlin est de paramétrer la position par le type plus précis à retourner, comme ceci.
package net.pijcke.mazes
interface Position<P>: Comparable<P> {
fun neighbours(): List<P>
}Vous avez peut-être remarqué que j'en ai profité pour ajouter l'interface Comparable. Ça nous permettra plus tard (section SideWinder) d'accéder rapidement aux structures utilisant des positions.
Voici donc enfin l'implémentation des coordonnées cartésiennes, où nous fournissons les accesseurs north(), west(), south() et east(). Nous avons choisi arbitrairement de placer l'origine au sud ouest et d'orienter les vecteurs unitaires vers le nord pour l'ordonnée y et vers l'est pour l'abscisse x.
package net.pijcke.mazes.rectangular
import net.pijcke.mazes.Position
data class CartesianPosition(val x: Int, val y: Int) : Position<CartesianPosition> {
override fun neighbours() = listOf(south(), north(), west(), east())
fun south() = CartesianPosition(x, y - 1)
fun north() = CartesianPosition(x, y + 1)
fun west() = CartesianPosition(x - 1, y)
fun east() = CartesianPosition(x + 1, y)
override fun compareTo(other: CartesianPosition): Int {
return Comparator.comparing(CartesianPosition::x)
.thenComparing(CartesianPosition::y)
.compare(this, other)
}
}Des grilles rectangulaires, pour le moment
Comme annoncé, nous gardons les choses simples pour le moment, mais sans nous fermer de portes pour les labyrinthes plus compliqués. Du coup, un labyrinthe sur une grille composée de carrés doit juste connaître sa largeur et sa hauteur. Nous pouvons déjà fournir l'implémentation de la fonction isWithinBounds(P).
Cette interface nous suffira pour générer et résoudre des labyrinthes, alors même que la façon dont les positions et les connexions entre ces positions n'est pas définie. Nous verrons plus tard deux possibilités d'implémentation, l'une à base de cellules qui savent à qui elles sont connectées, l'autre à base d'un ensemble de cellules et d'un ensemble de liens, faisant plutôt penser à un graphe composée de sommets et d'arcs.
package net.pijcke.mazes.rectangular
import net.pijcke.mazes.Grid
interface RectangularGrid: Grid<CartesianPosition> {
val width: Int
val height: Int
override fun isWithinBounds(position: CartesianPosition) =
position.x in 0 ..< width && position.y in 0 ..< height
}Parcourir une grille, avec un poil trop de classe
Nos algorithmes et nos programmes requièrent souvent de parcourir une grille (pas forcément une grille rectangulaire). Pour ça, nous proposons une interface GridWalker qui permettra de parcourir une grille à partir d'une origine donnée et en suivant des vecteurs unitaires données. La méthode est simple : On parcourt la grille selon le premier vecteur unitaire, et pour chaque position, on parcourt la grille selon les vecteurs unitaires suivants.
package net.pijcke.mazes.binarytree
import net.pijcke.mazes.Grid
import net.pijcke.mazes.Position
interface GridWalker<P: Position<P>> {
fun origin(grid: Grid<P>): P
fun unitVectors(): List<(P) -> P>
fun makeSequence(grid: Grid<P>): Sequence<P> = makeSequence(grid, origin(grid), unitVectors())
private fun makeSequence(grid: Grid<P>, startingPoint: P, remainingUnitVectors: List<(P) -> P>): Sequence<P> {
if (remainingUnitVectors.isEmpty()) {
return sequenceOf(startingPoint)
}
val curF = remainingUnitVectors.first()
val nextVectors = remainingUnitVectors.drop(1)
return generateSequence(startingPoint) { curF(it) }
.takeWhile { grid.isWithinBounds(it) }
.flatMap { makeSequence(grid, it, nextVectors) }
}
}Par exemple, pour parcourir une grille rectangulaire depuis l'origine (0, 0) horizontalement, puis verticalement, on peut implémenter le GridWalker suivant.
package net.pijcke.mazes.rectangular
import net.pijcke.mazes.Grid
import net.pijcke.mazes.binarytree.GridWalker
class RectangularGridWalker : GridWalker<CartesianPosition> {
override fun origin(grid: Grid<CartesianPosition>) = CartesianPosition(0, 0)
override fun unitVectors(): List<(CartesianPosition) -> CartesianPosition> =
listOf({ it.north() }, { it.east() })
}Très franchement, pour l'utilisation qu'on en fait, on est assez loin dans le domaine de l'overkill. Ce GridWalker permet en effet de parcourir des grilles à plus (ou moins) de deux dimensions, de changer de sens de parcours, de parcourir la grille selon des schémas en spirale, etc.
Pour ceux qui se demandent à quoi ressemble une grille à une dimensions, voici probablement la plus connue qui soit composée de cellules identiques à 13 côtés. Le petit nom de cette figure est "One-armed spiral of a reflexed tridecagon" ou spirale à un bras de tridécagones reflétés. L'image est prise de l'article "Voderberg Deconstructed & Triangle Substitution Tiling" de Cye H. Waldman (2014).
BinaryTree
Tout est en place pour implémenter deux algorithmes simples de génération de labyrinthes. C'est surprenant dans le sens où nous n'avons pas défini comment nous stockons physiquement nos cellules et nos liens. J'ai volontairement gardé ce détail pour plus tard, puisque je veux qu'il soit clair que notre implémentation ne dépend que de l'interface définie plus haut. Maintenant si ça vous perturbe, n'hésitez pas à lire d'abord la section suivante et à revenir à celle-ci juste après 😄.
BinaryTree se contente de visiter toutes les cellules et de creuser aléatoirement un chemin vers le nord ou vers l'est, si c'est possible (et c'est toujours possible sauf pour la cellule du nord-est).
package net.pijcke.mazes.binarytree
import net.pijcke.mazes.rectangular.CellRectangularGrid
import net.pijcke.mazes.rectangular.CartesianPosition
import net.pijcke.mazes.rectangular.RectangularGridWalker
object BinaryTree {
fun on(grid: CellRectangularGrid, walker: RectangularGridWalker) {
for (p in walker.makeSequence(grid)) {
possibleLinkedPositions(grid, p, walker).randomOrNull()?.let {
grid.link(p, it)
}
}
}
private fun possibleLinkedPositions(grid: CellRectangularGrid, position: CartesianPosition, walker: RectangularGridWalker): List<CartesianPosition> {
return walker.unitVectors().map { it(position) }.filter { grid.isWithinBounds(it) }
}
}Les plus observateurs auront remarqué que plutôt que dire explicitement nord et est, nous utilisons les vecteurs définis dans RectangularGridWalker, ça nous assure que nous aurons un labyrinthe cohérent même si on change le walker. Notez également l'utilisation d'un object plutôt que d'une classe puisque l'algorithm BinaryTree ne prend aucun paramètre en entrée.
Les labyrinthes ainsi générés auront toujours la colonne à l'est et la ligne au nord exemptes de connexions, ce qui en fait des labyrinthes excessivement simples à résoudre si on se dirige vers le nord ou vers l'est.
SideWinder
L'algorithme SideWinder est légèrement moins facile à décrire. Encore une fois on va parcourir le labyrinthe ligne par ligne, vers l'est puis vers le nord. À chaque cellule visitée, on va décider de joindre la cellule à celle qu'on vient de visiter (connectEast), ou de connecter le cluster de cellules à gauche avec une cellule au nord de ces dernières, au hasard (connectCluster).
La rangée du haut doit être gérée différemment puisqu'il est impossible de connecter le cluster vers le nord. Dans ce cas, on connecte directement à l'est.
package net.pijcke.mazes.sidewinder
import net.pijcke.mazes.rectangular.RectangularGrid
import net.pijcke.mazes.rectangular.CartesianPosition
import net.pijcke.mazes.rectangular.RectangularGridWalker
import java.util.Random
object SideWinder {
fun on(grid: RectangularGrid) {
val walker = RectangularGridWalker()
val expandablePositions = mutableListOf<CartesianPosition>()
walker.makeSequence(grid).forEach { currentPosition ->
// Connect top row
if (!grid.isWithinBounds(currentPosition.north())) {
if (grid.isWithinBounds(currentPosition.east())) {
connectEast(grid, currentPosition)
}
return@forEach
}
expandablePositions.add(currentPosition)
if (grid.isWithinBounds(currentPosition.east()) && Random().nextBoolean()) {
connectEast(grid, currentPosition)
}
else {
connectCluster(grid, expandablePositions)
}
}
}
private fun connectEast(grid: RectangularGrid, position: CartesianPosition) {
println("Connecting $position east.")
grid.link(position, position.east())
}
private fun connectCluster(grid: RectangularGrid, expandablePositions: MutableList<CartesianPosition>) {
val positionToExpand = expandablePositions.random()
println("Connecting cluster north : $expandablePositions. Picked $positionToExpand")
grid.link(positionToExpand, positionToExpand.north())
expandablePositions.clear()
}
}Encore une fois, on utilise un object puisque l'algorithme SideWinder ne prend aucun paramètre. Remarquez également l'utilisation du return@forEach qui permet de sortir d'un bloc forEach et nous évite un niveau d'indentation dans un else { ... }.
CellGrid
Il est finalement temps de décider comment nous allons stocker nos labyrinthes en mémoire. La première implémentation utilise une classe Cell<P: Position<P>> qui donne les positions connectées à une position donnée. La seconde implémentation utilise une liste de positions et une liste de connections entre ces positions. Chacune a ses avantages et nous donnons les deux implémentations pour montrer la facilité avec laquelle on peut passer de l'une à l'autre.
Chaque implémentation travaille sur une grille pas forcément rectangulaire. Dans chaque cas la méthode isWithinBounds(Position<P>) est manquante et, dans le cas des grilles rectangulaires, fournie par l'interface RectangularGrid.
Une cellule est caractérisée par une position et l'ensemble des cellules auxquelles elle est connectée.
package net.pijcke.mazes.grid.cell
import net.pijcke.mazes.Position
class Cell<P: Position<P>>(val position: P) {
private val links = mutableListOf<Cell<P>>()
fun link(cell: Cell<P>) = links.add(cell)
fun isLinkedTo(position: P): Boolean = links.any { it.position == position }
}Une grille de cellules associe à chaque position une cellule. Les opérations utilisent simplement les capacités des cellules.
package net.pijcke.mazes.grid.cell
import net.pijcke.mazes.Grid
import net.pijcke.mazes.Position
import java.lang.IllegalArgumentException
abstract class CellGrid<P: Position<P>>(cells: Collection<Cell<P>>): Grid<P> {
private val cells: Map<P, Cell<P>> = cells.associateBy { it.position }
override fun getPositions() = cells.keys
override fun link(position1: P, position2: P) {
val cell1 = cells[position1] ?: throw IllegalArgumentException("No cell at position $position1.")
val cell2 = cells[position2] ?: throw IllegalArgumentException("No cell at position $position2.")
cell1.link(cell2)
cell2.link(cell1)
}
override fun linked(position1: P, position2: P): Boolean {
return cells[position1]?.isLinkedTo(position2) ?: false
}
}Notez la manière dont on passe d'une liste à une table en utilisant la fonction associateBy.
Pour finir, une grille rectangulaire de cellules allie les fonctionnalités de la classe CellGrid et de l'interface RectangularGrid.
package net.pijcke.mazes.rectangular
import net.pijcke.mazes.grid.cell.Cell
import net.pijcke.mazes.grid.cell.CellGrid
class CellRectangularGrid(
override val width: Int, override val height: Int
): RectangularGrid, CellGrid<CartesianPosition>(List(width * height) { Cell(CartesianPosition(it % width, it / width)) })GraphGrid
Pour la représentation sous forme de graphe, on commence par définir un lien entre deux positions. Ces liens utilisent l'interface Comparable pour permettre de les retrouver rapidement s'ils sont stockés dans une structure à accès rapide comme un TreeSet.
package net.pijcke.mazes.grid.graph
import net.pijcke.mazes.Position
data class Edge<P: Position<P>>(val position1: P, val position2: P): Comparable<Edge<P>> {
override fun compareTo(other: Edge<P>): Int {
return position1.compareTo(other.position1)
.takeIf { it != 0 }
?: position2.compareTo(other.position2)
}
}Une grille sur un graphe est essentiellement une collection de positions et une collection de liens.
package net.pijcke.mazes.grid.graph
import net.pijcke.mazes.Grid
import net.pijcke.mazes.Position
import java.util.*
abstract class GraphGrid<P: Position<P>>(private val nodes: Collection<P>, edges: MutableCollection<Edge<P>>): Grid<P> {
private val edges = TreeSet(edges)
override fun getPositions() = nodes
override fun link(position1: P, position2: P) {
edges.add(Edge(position2, position1))
edges.add(Edge(position1, position2))
}
override fun linked(position1: P, position2: P): Boolean {
return edges.contains(Edge(position1, position2))
}
}Et comme pour les grilles rectangulaires à base de cellules, les grilles rectangulaires sur graphe allient simplement les fonctionnalités de la classe abstraite et de l'interface correspondantes.
package net.pijcke.mazes.rectangular
import net.pijcke.mazes.grid.graph.GraphGrid
class GraphRectangularGrid(
override val width: Int, override val height: Int
): RectangularGrid, GraphGrid<CartesianPosition>(List(width * height) { CartesianPosition(it % width, it / width) }, mutableListOf())Afficher un labyrinthe
Toute la logique est en place, il nous reste à afficher nos labyrinthes et à lier le tout dans une fonction main.
package net.pijcke.mazes.rectangular
class RectangularGridPrinter(private val grid: RectangularGrid) {
fun print() {
println("+---".repeat(grid.width) + "+")
for (y in grid.height - 1 downTo 0) {
(0 ..< grid.width)
.map { CartesianPosition (it, y) }
.map { " " + if (grid.linked(it, it.east())) " " else "|" }
.joinToString("", "|", "")
.let { println(it) }
(0 ..< grid.width)
.map { CartesianPosition (it, y) }
.map { if (grid.linked(it, it.south())) " " else "---" }
.joinToString("+", "+", "+")
.let { println(it) }
}
}
}package net.pijcke.mazes
import net.pijcke.mazes.binarytree.BinaryTree
import net.pijcke.mazes.sidewinder.SideWinder
import net.pijcke.mazes.rectangular.CellRectangularGrid
import net.pijcke.mazes.rectangular.GraphRectangularGrid
import net.pijcke.mazes.rectangular.RectangularGridPrinter
import net.pijcke.mazes.rectangular.RectangularGridRenderer
import net.pijcke.mazes.rectangular.RectangularGridWalker
import java.io.File
import java.time.LocalDateTime
import javax.imageio.ImageIO
fun main() {
val grid = CellRectangularGrid(15, 15)
// val grid = GraphRectangularGrid(15, 15)
val walker = RectangularGridWalker()
BinaryTree.on(grid, walker)
// SideWinder.on(grid, walker)
val renderer = RectangularGridRenderer(20, NoDistances(), 2)
val image = renderer.toPng(grid)
ImageIO.write(image, "png", File("BinaryTreeDemo_${LocalDateTime.now()}.png"))
val printer = RectangularGridPrinter(grid)
printer.print()
}+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| |
+ +---+ + + + + +---+ + +---+---+ + + +
| | | | | | | | | | | |
+ + + + + +---+---+---+ + +---+ +---+ + +
| | | | | | | | | | |
+ +---+---+ + +---+ +---+ + + + +---+ + +
| | | | | | | | | | |
+ + + +---+---+ + + + +---+ +---+---+ + +
| | | | | | | | | | |
+ + +---+ +---+---+ + + + +---+ + + + +
| | | | | | | | | | | |
+---+---+---+ +---+ + +---+---+---+---+---+---+ + +
| | | | | |
+ + +---+ + +---+ + + + + +---+ + + +
| | | | | | | | | | | | |
+---+ +---+---+ +---+---+---+ +---+ + +---+---+ +
| | | | | | |
+---+ +---+ + + + +---+---+ +---+ +---+ + +
| | | | | | | | | |
+ +---+---+ +---+ +---+ +---+---+ + +---+---+ +
| | | | | | | |
+---+---+ +---+---+ +---+ +---+---+---+ + +---+ +
| | | | | | |
+---+---+ +---+---+ +---+ + +---+ + +---+---+ +
| | | | | | | |
+ + +---+ +---+---+---+---+---+---+---+ + +---+ +
| | | | | | |
+ + + + +---+---+ + + +---+ +---+---+ + +
| | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+Conclusion
Vous pouvez choisir l'implémentation de grille souhaitée (graphe ou cellules), et l'algorithme de génération souhaité (BinaryTree ou SideWinder). Dans le premier cas il s'agit du design pattern Builder qui permet de séparer la construction d'un objet de sa représentation. Dans le second cas nous nous sommes inspirés sans vraiment l'implémenter du design pattern Strategy, qui permet d'utiliser des algorithmes de manière interchangeable.
J'espère que cette brève exploration de la génération de labyrinthes vous a fait découvrir quelques pratiques intéressantes. De mon côté je compte bien vous en montrer plus avec un autre article qui arrive très bientôt et qui traite de la résolution de ces derniers, avec l'algorithme Dijkstra. Nous en profiterons aussi pour passer à la vitesse supérieure et les afficher en PNG plutôt qu'en mode console !
Vous pouvez télécharger le code via l'archive suivante. Notez que les packages ont été légèrement réorganisés. Le code est par contre le même. Vous devriez pouvoir ouvrir le projet directement avec, par exemple, IntelliJ IDEA.
