An english version of the project is available here!
Dans ce projet, l’objectif est de sauver les villes d'une région d'un incendie. Le but est donc de placer astucieusement des points d'intervention de pompiers pour empêcher le feu d'atteindre les villes. Ce projet se déroulera en plusieurs étapes :
Concernant l’organisation :
On part d'une image simplifiée de la région avec peu de couleurs, représentant les zones habitées (à protéger, mais les pompiers ne peuvent pas intervenir dans une ville sans causer de dégâts), les zones d'eau, inaccessibles pour le feu et pour les pompiers, et les zones agricoles ou forestières, accessible aux deux.
Des pixels rouges sont ajoutés, représentant des départ de feu. Pour simplifier le problème, on suppose que le feu ne se propage qu'en ligne droite et donc ne peut pas contourner un obstacle. De plus, on peut supposer que les flammes empêchent les pompiers de s'approcher trop près du départ de feu. Un pompier peut ignifuger une zone d'un rayon fixe autour de sa position.
Le but est de sauver toutes les villes avec le moins de pompier possible. Il faudra renvoyer l'image sur laquelle sont modifiés les pixels correspondants aux positions d'intervention des pompiers.
Les images d'entrée et de sortie sont au format PPM et accompagnées d'un fichier texte.
Le format PPM (pour Portable Pixmap) est un moyen très simple de décrire une image sous forme textuelle. Dans notre cas, il s’agira de fichiers ASCII de ce format (voir Wikipedia) avec un stockage correspondant à un row-major order (voir Wikipedia) :
P3 # fichier PPM ASCII sous format RGB
# Created by GIMP... #on travaillera avec des images créées sous GIMP qui met ce commentaire
3 2 # l'image contient 3 colonnes et 2 lignes
255 # chaque composante R, G et B est représentée par un entier entre 0 et 255
255 255 0
0 0 0
0 0 255 # fin première ligne
255 255 0
0 0 255
255 0 0 # fin deuxième ligneEn plus du fichier au format PPM, un fichier de configuration config.txt permet d’indiquer :
(R,G,B)) présente dans le fichier PPM est associé à un indice de zone (expliqué ci-après). Le nombre d'angles est un entier qui permet de discrétiser les angles, on considère na direction partant de chaque départ de feu.
À vous de choisir une valeur adaptée.
Le rayon de fournaise (distance minimale à laquelle on peut s'approcher du départ de feu) rf et le rayon d'action d'un pompier rp sont deux flottants supérieurs ou égaux à 1, en pixels.
Enfin, on définit des indices pour chaque type de zone dont l'interprétation est fixée ci-dessous, et pour chaque indice, on lui associe une couleur de l'image.
Voici un exemple de fichier de configuration config.txt:
700 # nombre d'angles
4.5 #rayon de fournaise
1.6 #rayon d'action d'un pompier
0 255 0 0 # rouge: Feu
1 0 255 0 # vert: Pompier
2 0 0 0 # noir: Ville
3 0 0 255 # bleu: Inaccessible
4 255 255 0 # jaune: Libre
On notera que les pixels verts (indice 1) ne concernent que l'image solution.
Voici un exemple concret de plan d'une zone en gironde.
Cette image a été largement simplifiée (les étapes de création d'images seront explicitées plus tard) pour obtenir une image plus petite au format PPM, à télécharger ici.
Si on ouvre ce fichier, on s’aperçoit notamment que l’image est de taille 100*100 :
les 100 premiers triplets représentent la première ligne, les triplets 100 à 200 la deuxième ligne et ainsi de suite.
Cette image contient 4 couleurs différentes :
On peut ainsi remarquer que la couleur bleue représente les zones d’eau, la couleur noire les zones de ville et le jaune les zones forestières et agricoles. Il y a deux départs de feu: les pixels rouges.
On peut lui associer le fichier de configuration proposé en exemple précédemment, téléchargeable ici.
Vous pouvez facilement créer d’autres instances de votre choix. Voici une aide pour créer ce genre d'image sous GIMP.
!!! Attention, GIMP introduit une ligne de commentaire en 2eme ligne, et par défaut on suppose la présence de cette ligne. Si vous créez des images ppm autrement, faite attention au possible décalage.
file.png.À partir de cette image, on va en créer une simplifiée sous GIMP, donc pour commencer, ouvrir file.png avec GIMP ;
Il vous faudra ensuite certainement diminuer le nombre de pixels dans l'image. Pour cela
Il vous faudra ensuite diminuer le nombre de couleurs pour arriver aux 3 de base (Ville/Inaccessible/Libre) :
Enfin, pour exporter l’image en PPM :
file.ppm > Exporter ;Il vous faudra ensuite lancer la commande suivante depuis un terminal :
foo@bar:~$ awk '{ ++x; if(x<=4) print $0; else { l1=$0; getline; l2=$0; getline; print l1 " " l2 " " $0; }}' file.ppm > res.ppmCeci permet de récupérer le fichier PPM final dans un fichier res.ppm.
Ici, le x<=4 signifie que la couleur du pixel de coordonnées (0,0) est sur la ligne 5 du fichier file.ppm.
On vous demande un petit rapport (fichier texte ou PDF) expliquant :
Date limite : vendredi 30 septembre
On vous demande un rapport (fichier texte ou PDF) expliquant :
Date limite : vendredi 28 octobre
Il vous est demandé d’envoyer votre rapport final (format PDF) d’ici le 16 janvier . Les soutenances auront lieu le 19 janvier (CREMI, salle 201) et dureront 20 minutes par groupe. Les soutenances et questions/réponses pourront être au choix en Français ou Anglais. Les horraires de passage sont :
Nous vous demandons d’entrer discrètement dans la salle 10 minutes avant votre horaire et de vous installer sur un ordinateur afin d’éviter toute perte de temps. Vous devrez présenter rapidement ce que vous avez fait, puis nous vous poserons des questions à propos de votre projet. Vous pouvez utiliser des slides, mais ce n’est pas obligatoire.