Nous sommes actuellement le 23 Juin 2018, 17:53

Le fuseau horaire est UTC+1 heure [Heure d’été]




Publier un nouveau sujet Répondre au sujet  [ 3 messages ] 
Auteur Message
 Sujet du message: Outils pour les régions rectangulaires
MessagePublié: 14 Juil 2013, 22:52 
Hors-ligne

Inscrit(e) le : 24 Juin 2012, 18:53
Message(s) : 457
J'ai créé quelques outils qui peuvent générer automatiquement les régions rectangulaires pour les fichiers def.

On peut les obtenir à github:
elm2mask - crée une image noire et blanche des régions choisies.
mask2rects - calcule un couverture de rectangles des pixels blancs.
rects2def - convertit une liste des rectangles en format de def.

Pour les développer et exécuter, il faut au moins Perl, POV-Ray, ImageMagick, et un compilateur de C++ (par exemple g++). Ils sont testés sous linux.

Je les ai documentés en anglais dans le code source, donc je vais essayer de faire ici un petit tutoriel sur leur fonctionnement. On va créer un def qui fait des dégâts dans les régions enneigées du mont à Nargraw Sud.


1. Création du masque

Le script elm2mask lit un ficher elm et sort une image PNG où un pixel est blanc si la case correspondante croise des objets choisis. On spécifie les objets par leur nom de fichier dans 3dobjects. C'est aussi possible d'utiliser un regex pour en sélectionner plusieurs à la fois (autrement on les liste).

Rien n'empêche de créer l'image du masque dans un logiciel de manipulation des images (par exemple gimp). Il suffit que l'image à la même taille que la carte; un pixel dans l'image est interprété comme une case marchable de jeu.

Pour les régions enneigées on chosit mound_snow comme pattern:
Code :
$ cd /home/user/le/donnees/maps
$ elm2mask.pl 2_nargraw_sud_mont mound_snow
Reading maps/2_nargraw_sud_mont.elm from /home/user/le/donnees
Writing 2_nargraw_sud_mont-mask.pov
Rendering 2_nargraw_sud_mont-mask.png
All done.

Si tout s'est bien passé on devrait avoir le PNG:
Image


2. Calculation de la couverture rectangulaire

Parce que le serveur nécessite des rectangles, on utilise maintenant mask2rects pour les calculer automatiquement de l'image précédente.

À noter que les coordonnées de l'image ont l'origine en haut à gauche (c'est à dire le (0,0) des coordonnées (x,y), regardant l'image sur l'écran) mais dans le jeu le case (0,0) serait en bas à gauche. Donc il faut utiliser l'option -f pour que la coordonnée verticale (y) soit inversée dans le résultat.

L'algorithme n'est pas très sophistiqué; il s'agit de générer quelques couvertures aléatoirement et garder la meilleure. On peut aussi manipuler combien de fois le logiciel va essayer (option -i), le nombre maximal des rectangles dans une région (-c), le nombre maximal des cases qui peuvent rester sans couverture (-u), et la taille minimale des rectangles (-a). L'intérêt de ces dernières options est de réduire le nombre total des rectangles dans le résultat, si c'est acceptable que la couverture ne soit pas complete.

On essaie les paramètres par défault, et met aussi -r test.png pour qu'une image de la couverture soit créée:
Code :
$ mask2rects 2_nargraw_sud_mont-mask.png -r test.png
wrote rectangle bounds to 'output-rects.txt'
wrote PNG image to 'test.png'

Voilà la visualisation de la couverture test.png:
Image

Dans l'image chaque région trouvée est indiquée par un contour vert, et les rectangles de la couverture sont affichés en couleurs differentes.

On voit que c'est pas mal, mais il y a encore des pixels blancs qui n'étaient pas couverts. Si on met l'option -v on peut voir pourquoi:
Code :
$ mask2rects 2_nargraw_sud_mont-mask.png -r test.png -v
...
calculating cover for 92x112 region
iteration 0: cover found has 50 rectangles (269 uncovered points)
iteration 1: cover found has 50 rectangles (372 uncovered points)
iteration 2: cover found has 50 rectangles (303 uncovered points)
iteration 3: cover found has 50 rectangles (282 uncovered points)
iteration 4: cover found has 50 rectangles (257 uncovered points)
iteration 5: cover found has 50 rectangles (259 uncovered points)
iteration 6: cover found has 50 rectangles (289 uncovered points)
iteration 7: cover found has 50 rectangles (305 uncovered points)
iteration 8: cover found has 50 rectangles (304 uncovered points)
iteration 9: cover found has 50 rectangles (309 uncovered points)
final cover has 50 rectangles and 257 uncovered points
...


La région est trop grande et irrégulière pour seulement 50 rectangles. Essayons donc 100 rectangles et 50 essais:
Code :
$ mask2rects 2_nargraw_sud_mont-mask.png -r test.png -v -c 100 -i 50
...
iteration 47: cover found has 100 rectangles (56 uncovered points)
iteration 48: cover found has 100 rectangles (54 uncovered points)
iteration 49: cover found has 100 rectangles (59 uncovered points)
final cover has 100 rectangles and 45 uncovered points
...


Mieux, mais peut-être avec 200 rectangles?
Code :
$ mask2rects 2_nargraw_sud_mont-mask.png -r test.png -v -c 200 -i 50
...
iteration 47: cover found has 143 rectangles (0 uncovered points)
iteration 48: cover found has 139 rectangles (0 uncovered points)
iteration 49: cover found has 138 rectangles (0 uncovered points)
final cover has 131 rectangles and 0 uncovered points
...

Ça y est!
Image

La couverture réussit à couvrir les cases mais il y a beaucoup de rectangles:
Code :
$ wc -l output-rects.txt
172 output-rects.txt


Pour ce tutoriel ça serait acceptable. Finalement on met l'option -f pour que le résultat soit en le format attendu par la prochaine étape:
Code :
$ mask2rects 2_nargraw_sud_mont-mask.png -c 200 -i 50 -f
Flipping y coordinates in output to 'output-rects.txt'
wrote rectangle bounds to 'output-rects.txt'



3. Conversion en lignes de fichier def

Les rectangles dans output-rects.txt sont donnés comme:
Code :
12,92,69,123
48,55,69,68
52,69,68,83
90,66,95,75
...


Alors on utilise rects2def pour la conversion simple en format def:
Code :
$ rects2def.pl output-rects.txt walk_damage value=1 > out.def


ce qui fait:
Code :
[walk_damage]
min_x: 12
min_y: 92
max_x: 69
max_y: 123
value: 1
[/walk_damage]
[walk_damage]
min_x: 48
min_y: 55
...


Et enfin on ajoute le texte du fichier out.def dans le def de la carte:
Code :
$ cat out.def >> 2_nargraw_sud_mont.def



Voilà les rectangles de def faits, j'espère, plus vite et avec moins de fautes que si on essayait le faire à la main.

Si vous avez des questions sur le fonctionnement ou requêtes d'amélioration, ou bien si vous trouvez des bugs, n'hésitez pas à me contacter.


Dernière édition par Crayona le 15 Juil 2013, 05:06, édité 2 fois.

Haut
 Profil  
 
 Sujet du message: Re: Outils pour les régions rectangulaires
MessagePublié: 14 Juil 2013, 23:22 
Hors-ligne
Avatar de l’utilisateur

Inscrit(e) le : 04 Mars 2007, 20:31
Message(s) : 7011
Merci Crayona :)

_________________
Mappeur, membre de l'équipe section Map (et aide anim a temps perdu)
La mort est un jour qui mérite d'etre vécu, à vos armes bande de limaces!
http://www.ffjdr.org/
Prêt pour un cours de cryptographie?


Haut
 Profil  
 
 Sujet du message: Re: Outils pour les régions rectangulaires
MessagePublié: 16 Juil 2013, 20:18 
Hors-ligne

Inscrit(e) le : 18 Déc 2005, 19:31
Message(s) : 7350
Joli travail Crayona !

_________________
Celui qui apprend quelque chose de moi enrichit son savoir sans réduire le mien, tout comme celui qui allume sa chandelle à la mienne se donne de la lumière sans me plonger dans l'obscurité.
-- Thomas Jefferson


Haut
 Profil  
 
Afficher les messages publiés depuis :  Trier par  
Publier un nouveau sujet Répondre au sujet  [ 3 messages ] 

Le fuseau horaire est UTC+1 heure [Heure d’été]


Qui est en ligne ?

Utilisateur(s) parcourant ce forum : Aucun utilisateur inscrit et 0 invité(s)


Vous ne pouvez pas publier de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum

Recherche de:
Aller vers :  
cron
Powered by phpBB® Forum Software © phpBB Group
Traduit par Maël Soucaze et Elglobo © phpBB.fr