ili
ili est un petit algorithme génératif qui dessine un motif approchant le plan de ville schématique.
Je me suis largement inspiré du superbe travail de J.Tarbell. Je n’ai pas tout implémenté ; j’ai laissé les trainées de côté pour garder un côté brut et léger qui me plait bien. Ceci-dit j’aimerai m’amuser encore beaucoup et mieux exploiter les nombreuses possibilités qu’offre cet algorithme.
L’algorithme est très simple en soi, mais il existe plusieurs méthodes pour l’implémenter ; chacune ayant ses avantages et ses inconvénients.
Ici, chaque ligne est prolongée à chaque iteration, en évitant au mieux les intersections avec d’autres lignes. Afin de determiner si une intersection aura lieu à la prochaine itération pour une ligne donnée, l’algorithme se contente de lire le pixel de destination (la ou se trouvera l’extrémité de la ligne après prolongement) : si le pixel est déjà noir, cela signifie qu’il y aura intersection et qu’il faut arrêter la ligne, sinon on peut la prolonger.
Cela est très simple mais pose un certains nombre de problèmes : dès qu’on veut tracer des lignes courbes ou bien prolonger les lignes de plusieurs pixels à la fois (c’est ce qui se passe avec les paramètres par défaut, ou la vitesse est supérieure à 1 pixel par iteration) la valeur du pixel de destination ne suffit plus. Mais finalement le résultat me plait, j’ai donc laissé l’algorithme tel quel 🙂
Pour implémenter cet algorithme, j’aurai pu :
- utiliser une structure de donnée de partition de l’espace (Arbre KD, Quadtree, etc.) pour organiser mes lignes et mieux anticiper les intersections,
- générer les lignes en WebGL (j’ai essayé, mais finalement il n’y a pas de gain réel par rapport au canvas HTML parce qu’il y a peu de lignes à tracer à chaque itération),
- utiliser un shader (ça serait nettement plus fun 😉).