Génération contrôlée d'un diagramme de Voronoi

[seishin]

Bonjour à tous,

Je cherche à générer un diagramme de Voronoi ayant des cellules de surface comprise entre 150 et 310 pixels.

En répartissant  les points générant le diagramme, j'obtiens ceci :



Cela fait un peu trop carré à mon goût.

Auriez-vous une autre idée  en sachant que :

• la surface des cellules doit être comprise entre un minima et un maxima
  
• on doit pouvoir connaitre les cellules voisines 
  

Je dois y aller, je repasse un peu plus tard si il y a des questions ou autres....

[Xenos]

Salut,
ça "fait carré" parce que tu as dû positionner tes points centraux selon une grille... carrée
Pour générer un truc comme ça, perso, je procèderai ainsi:

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

Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister)
- Calcul de la surface de chaque cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites", calcul du max de ces deux nombres
- 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é)
- 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)
- Réitérer jusqu'à avoir des listes vides

C'est extensible à d'autres conditions que la taille mini/maxi des cellules.
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)

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.

[Thêta Tau Tau]

Un algo classique est de tirer des points au hasard, de construire le voronoi, puis de prendre le barycentre des cellules, et de construire un nouveau voronoi à partir de ces cellules. Plus on fait d'itérations, plus on a des cellules régulières.

Cet algo ne permet pas une taille min et max mais on peut fixer la moyenne (nombre de points / aire) et comme les cellules tendent à avoir une taille similaire, on a en général pas trop de problèmes.

[Xenos]

Du coup, avec cette méthode, tu garderas l'effet "carré" (probablement plus proche de l'hexagone en fait, puisque c'est le périmètre minimal pour une surface donnée)... Si j'ai bien compris, là, le but est d'avoir un truc un peu plus irrégulier?!

[Thêta Tau Tau]

Oui si tu fais beaucoup d'itérations tu te retrouve avec des hexagones, si t'en fais pas beaucoup (1 ou 2) ça reste relativement irrégulier.

Pour des formes vraiment irrégulières c'est pas (que) du voronoi qu'il faut faire.

Un script fait en 10 minutes sous R :

Code :

install.packages("deldir")
library(deldir)

#On tire 100 points dans le carré 0-1,0-1
pts = data.frame(
 x = runif(100, 0, 1),
 y = runif(100, 0, 1)
)

par(mfrow = c(2,3), mar = c(0,2,0,0))#paramètres graphiques (osef)

for(it in 0:5){
 dd = deldir(pts$x, pts$y, rw = c(0, 1, 0, 1))
 
 plot(dd, wlines = "tess", main = paste("Itération", it))
 
 pts = tile.centroids(tile.list(dd))
}

[seishin]

Merci pour vos réponses

J'étais parti sur la solution suivante :

Code :

* Générer aléatoirement un grand nombre de points
* Faire le diagramme de Voronoi correspondant
* Parcourir les cellules et fusionner les trop petites avec leurs voisines sans créer une trop grosse

Voilà ce que cela donne :
Un essai

Par contre, il me reste des petites cellules.

Une autre idée que j'avais eue : 

Code :

* Générer aléatoirement un nombre (moins grand) de points
* Faire le diagramme de Voronoi correspondant
* Parcourir les cellules et 
  ** fusionner les trop petites avec leurs voisines sans créer une trop grosse
  ** éclater les trop gros en plus petites cellules

Pour des formes vraiment irrégulières c'est pas (que) du voronoi qu'il faut faire.

@Théta, tu peux développer ?

[Xenos]

Question subsidiaire: tu fais ça pour "l'initialisation" du jeu (c'est à dire que c'est pour construire la carte du jeu, et par la suite, cette carte ne change pas) ou le jeu génère vraiment de nouvelles cartes en temps réel à la volée?
Dans mon cas, sur ECLERD (reboot), j'avais ce genre de problématique: créer une carte du jeu comme un Voronoï avec des conditions. Mais une fois la carte créée, elle ne changera pas (les propriétés des cases changeront au cours du jeu, et peut-être que certaines cases seront scindées et d'autres fusionnées, mais c'est maginal dans la vie du jeu). Si t'es dans ce cas là, ce qui peut être plus simple que de ramer à trouver l'algo parfait, c'est de retoucher ta carte à la mano, en rajoutant des points par exemple (donc, tu génère une carte random, tu sauves la liste de tes points, puis tu déplace certains d'entre eux à la mano pour que cela colle à ton idée).

C'est parfois (souvent? toujours?!) 100x plus efficace que de trimer des semaines à vouloir trouver un algo qui fait le taff d'un human-concepteur de jeu.
(mais ce n'est évidemment pas applicable si tu veux générer des cartes à la volée, en "temps réel")

[Thêta Tau Tau]

@Théta, tu peux développer ?

Un diagramme de Voroinoi te fera forcément des frontières droites entre 2 régions, donc pour avoir des frontières plus intéressantes soit tu fusionne plusieurs régions (comme tu semble parti pour), soit tu "bruite" les frontières (par ex avec du mid point displacment), soit tu génère tes régions autrement qu'avec un diagramme de Voronoi (par ex avec un automate cellulaire).



Ce topic me donne envie de refaire un générateur de carte, mais je m'était promis de ne pas retoucher à ça avant d'avoir un jeu qui a besoin d'une telle carte :p

[seishin]

@Xenos, je cherche à créer un ensemble d'outils pour MJ : création de mondes, de civilisations, système économique, ... 

@Théta, si tu veux, tu peux regarder ce générateur

[Thêta Tau Tau]

Merci pour le lien, je regarde le code source demain.