JeuWeb - Crée ton jeu par navigateur
Génération contrôlée d'un diagramme de Voronoi - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Génération contrôlée d'un diagramme de Voronoi (/showthread.php?tid=7932)

Pages : 1 2

RE: Génération contrôlée d'un diagramme de Voronoi - Thêta Tau Tau - 31-08-2018

Du coup j'ai regardé le code source du générateur passé en lien par seishin.

En résumé :
  • des points sont tirés aléatoirement avec un algorithme nommé "poisson disc sampling" qui sont utilisés pour générer un diagramme de Voronoi. Le résultat est très similaire à l'algo dont j'ai parlé au dessus. C'est probablement plus performant : cet algo est en o(n) alors que les meilleurs algo de diagrame de Voronoi sont en o(n log n). Cela dit l'algo que j'ai présenté à l'avantage de ne presque pas demander de code supplémentaire étant donné qu'il réutilise l'algo de génération de diagramme de Voronoi dont on a de toute façon besoin. A noter aussi qu'avec le poisson disc sampling on fixe une distance minimale entre les points, alors qu'avec mon truc à base de Voronoi on n'a pas de garantie, même si en pratique c'est trop un problème.
  • Ensuite l'altitude des points est générée. Perso quand je veux faire ça je traces les grandes lignes de mon relief puis j’ajoute du bruit de Perlin, c'est une méthode simple et efficace. J'ai pas regardé en détail ce qu'ils font ici (pas tout pigé de leur code), mais il semble qu'ils prennent des points au hasard pour y placer des éléments géographiques (montagnes, collines etc.) et qu'ils appliquent ensuite différent modificateurs (lissage etc.).
  • Pour les rivières ils utilisent l'altitude et font en sorte que les rivières coulent selon la pente. C'est un algo classique mais relativement complexe (pour avoir déjà essayé de l'implémenter). J'ai tendance à préférer des algos maison qui donnent des résultats similaires mais qui ne respectent pas la pente (inspirés des algos de colonisation de l'espace), ce qui n'est pas un problème pour les cartes 2D où on ne verra de toute façon pas si une rivière remonte une pente (en 3D c'est différent).
  • Ensuite ils placent des points au hasard, puis ils génèrent les "cultures" (=régions) en partant de ces points. Leur algo à l'air très complet (routes, villes, hameaux, ports…) avec prise en compte du terrain etc. J'ai encore jamais fait ce genre de truc (c'est en projet). En gros ça consiste à fusionner les cellules de voronoi en régions constituées de plusieurs dizaines de cellules, donc avec une forme irrégulière. Il y a moyen de faire beaucoup plus simple que ce qu'ils ont fait.
  • Ensuite ils font pas mal de trucs pour que ça soit plus joli (tracé des côtes, ajout des dessins de montagnes etc.).


RE: Génération contrôlée d'un diagramme de Voronoi - Xenos - 31-08-2018

J'ai implémenté mon algo de mon côté, pour le fun https://xenos.reinom.com/mdn/voronoi-constrained/voronoi-constrained.html

Résultat:

[Image: voronoi.png]

Avec paramétrage possible. Libre à toi de reprendre le code sans condition (même si être au moins cité, ça fait plaisir Wink ).

PS: les cellules sont bien plus irrégulières qu'avec la méthode des barycentres, trop "hexagonale-convergente" à mon gout :/

Pour reprendre l'algo:

Initialisation:
- Répartition de N points au pif dans la carte (mes "points d'origine", aka les centre des cellules de Voronoi) => Ce sont les points rouges de la variable "cells"

Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister) => Finalement, pas compliqué: on prend chaque pixel, et on cherche le centre de cellule le plus proche. Pas efficace du tout, mais rapide quand même en JS
- Calcul de la surface de chaque cellule => il suffit de compter les pixels de la cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites" => ce sont les tooBig/SmallCellsCount
- calcul du max de ces deux nombres => c'est le invalidCellsCount, qui permet d'avoir une correspondance simple 1-1 entre les cellules trop grandes à "scinder" et les trop petites à fusionner
- Création de deux listes de longueur égale à ce max: la liste des cellules (les coordonnées de leur centre) les plus grandes (qui contiendra donc la liste des cellules "trop grandes") et la liste des cellules les plus petits. Si les listes se chevauchent, repartir de zéro (les points tirés au pif ont vraiment chié) => tooBig/SmallCells
- Déplacer tous les points de la liste des "petites cellules" pour les mettre à proximité d'une grande cellule (pour chaque point de la liste des petites cellules, prendre une grande cellule au pif, et déplacer ce point à une distance R du centre de la grande cellule; on peut approximer R par racine_carrée[surface de la grande cellule]/Pi) => le forEach dessous
- Réitérer jusqu'à avoir des listes vides => le if invalidCellsCount === 0 break

C'est extensible à d'autres conditions que la taille mini/maxi des cellules. => A vous de trouver lesquelles vous voulez
Je ne sais pas quelle est la vitesse de convergence du truc (peut-être qu'on peut se contenter d'ailleurs de de placer des points au pif dans la carte, calculer que le diagramme soit "valide" pour les conditions qu'on fixe, et si non, retirer tous les points au pif... c'est plus simple, mais moins convergent je dirai) => Finalement, en 3-4 itérations, c'est réglé... mais cela doit dépendre des conditions fixées (nota: je n'ai pas implémenté de mécanisme bloquant les requêtes sans solution, par exemple un canvas de 100x100 avec 100 cellules d'au moins 101 pixel, ce sera impossible et l'algo ne s'arrêtera jamais)

Pour connaitre les cellules voisines, c'est dans la construction du Voronoï, donc, inutile de se préoccuper de cela pendant l'algorithme de répartition des centres des cellules. => Je ne l'ai pas implémenté, mais c'est simple à faire: on prend chaque pixel, on regarde sa cellule de Voronoi associée, on prend chacun de ses voisins, et on a donc 4 couples de cellules de voronoi qui sont voisines. On conserve une liste unique de ces couples, en ignorant les couples A-A (la même cellule 2 fois dans le couple) et c'est réglé.

RE: Génération contrôlée d'un diagramme de Voronoi - seishin - 31-01-2019

Salut à tous,

Veuillez m'excuser, je pensais vous avoir remercié pour vos réponses mais apparemment je l'ai rêvé.
(Ca m'arrive de rêver d'avoir fait certains cours, j'engueule mes élèves de ne pas les avoir suivis Wink)

J'ai trouvé une solution (vérifiée visuellement pour le moment) grâce à d3js, je vous mets un exemple en lien.

Pour ceux que cela intéresserait bien sûr