Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

Création d'un logiciel sur le principe de TETRIS



  1. #1
    mysterytour

    Création d'un logiciel sur le principe de TETRIS


    ------

    Bonjour,

    Voilà le challenge à résoudre:

    D'un côté une surface,celle d'un mur: hauteur/longueur
    ex: 3,50m x 2,70m

    De l'autre: 114 formats différents de toiles sur châssis (considérons les comme des figures géométriques carrées ou rectangulaires)

    Comment en entrant les données de surface d'une part et les 114 formats d'autre part obtenir toutes les combinaisons possibles pour couvrir le mur?
    Merci aux programmeurs qui voudront bien se pencher sur ce problème que je dois résoudre pour lancer un nouveau concept déco.

    -----

  2. Publicité
  3. #2
    bzh_nicolas

    Re : Création d'un logiciel sur le principe de TETRIS

    Une fonctions récursive me semble le plus adapté.

  4. #3
    mysterytour

    Re : Création d'un logiciel sur le principe de TETRIS

    Merci tout d'abord de vous interesser à mon problème.Reste qu'il me faut à présent comprendre ce qu'est une fonction récursive...Et ce que j'en fais.

  5. #4
    DomiM

    Re : Création d'un logiciel sur le principe de TETRIS

    Pour ajouter un tableau sur le mur on peut faire comme si on écrivait un texte
    En gros ça serait ça avec quelques test suplémentaire
    Code:
    ym=2,7
    do 
      ym=ym-EcritLigne(3,50)
    while ym>0
    
    Function EcritLigne(d)
      ym=0
      for i=1 to 114
        if f[i,0]<d then
          d=d-f[i,0]
          if ym<f[i,1] then
            ym=f[i,1]
          endif
          ajouteTableau(i)
        endif
      next i
      EcritLigne=ym
    End function
    Dernière modification par Philou67 ; 09/12/2010 à 09h26. Motif: Merci d'utiliser la balise CODE et l'indentation
    Mesurer la masse de la situation permettrait de connaitre sa gravité :)

  6. A voir en vidéo sur Futura
  7. #5
    Philou67

    Re : Création d'un logiciel sur le principe de TETRIS

    J'aurais tendance à penser que ce problème relève de la recherche opérationnelle, et qu'un algorithme glouton me semblerait adapté.

    Au retour de la pose café, j'essayerai de proposer une algorithme (mais à priori, c'est un problème classique de placement et d'optimisation : il existe sans doute un algorithme bien nommé pour cela).
    :'( Plus j'apprends, et plus je mesure mon ignorance

  8. #6
    mysterytour

    Re : Création d'un logiciel sur le principe de TETRIS

    Merci tout d'abord aux membres dont la réactivité à ma question m'impressionne. A la lecture de vos réponses je me dis qu'un point qui n'est pas de détail vous aura peut être échappé.Chacun son job et la programmation n'est pas le mien.Je fonctionne à l'intuition et en inventant ce concept (à mi chemin entre l'art contemporain,la muséographie et l'architecture intérieure) je n'avais qu'un seul mot à ma disposition: algorithme.Lequel,comment,aucu ne idée...Mais une fois créé l'outil de calcul les applications (avec leur aspect très ludique et créatif) pourraient se révéler passionnantes,notamment du point de vue des rapports colorés (la perception rétinienne de chaque couleur étant influencée par celles qui l'entourent (théorie de Chevreul dont les pointillistes et tout l'art abstrait du XXème se sont inspirés).Bon je ne m'étends pas sur l'histoire de l'art,encore une fois chacun son job. Ce qui est certain c'est qu'il s'agit en effet d"un problème classique de placement et d'optimisation". Ce qui est non moins certain c'est que la rencontre entre l'art et la science est un enjeu passionnant à mon sens.

  9. Publicité
  10. #7
    DomiM

    Re : Création d'un logiciel sur le principe de TETRIS

    On sait que le plan peut être pavé par les format An (A4,A3,A2,A1,A0)
    donc en centrant chacune de vos toiles sur le format An le plus proche le problème se simplifie
    Mesurer la masse de la situation permettrait de connaitre sa gravité :)

  11. #8
    Philou67

    Re : Création d'un logiciel sur le principe de TETRIS

    J'en viens donc à mon idée d'algorithme glouton (heuristique) : l'idée principale est de tenter de placer les plus grosses pièces en premier. Chaque pièce posée découpe l'espace disponible en deux, créant ainsi deux espaces rectangulaires disponibles à remplir.
    Si l'on considère que les œuvres d'arts n'ont pas de sens de visualisation, on peut considérer que l'espace peut être découpé selon deux sens (donc récursivement, si l'une des voies ne donne pas de résultat, il faudra explorer l'autre).
    De même, il existe 4 possibles de placement, à chaque coin de l'espace. On pourra soit explorer les 4 voies, soit ne considérer que le placement en haut à gauche.

    Code:
    pieces[114] = (...) // renseigner les 114 pièces
    espaces[] = (...)   // renseigner l'espace disponible
    placements[] = ()
    Trier le tableau pieces[] par ordre de taille décroissant (critère : soit la surface, soit une critère à deux clés : largeur puis hauteur)
    Appeler Placer(pieces, espaces, placements)
    
    function Placer(pieces[], espaces[], placements)
    
    Si pieces est vide
      Afficher "Solution", placements
    Sinon
      Pour espace parmi tous les espaces[]
        Si la pièces[0] tient dans espace
          placements[] <- pièces[0]
          supprimer pièces[0]
          remplacer dans espaces[], espace par 2 espaces résultant du découpage horizontal suite au placement
          Appeler Placer(pièces, espaces, placements)
          remplacer dans espaces[], les 2 espaces précédent par 2 espaces résultant du découpage vertical
          Appeler Placer(pièces, espaces, placements)
        Finsi
    
      Pour espace parmi tous les espaces[]
        Si la pièces[0] tournée à 90° tient dans espace
          placements[] <- pièces[0] tournée à 90°
          supprimer pièces[0]
          remplacer dans espaces[], espace par 2 espaces résultant du découpage horizontal suite au placement
          Appeler Placer(pièces, espaces, placements)
          remplacer dans espaces[], les 2 espaces précédent par 2 espaces résultant du découpage vertical
          Appeler Placer(pièces, espaces, placements)
        Finsi
      FinPour
    Finsi
    Je ne suis absolument pas sûr que cet algorithme soit correct, et surtout qu'il donne une solution.
    :'( Plus j'apprends, et plus je mesure mon ignorance

  12. #9
    mysterytour

    Re : Création d'un logiciel sur le principe de TETRIS

    3 cas de figure peuvent se présenter. Dans le 1er et le 2nd cas,le sens de visualisation est à prendre en compte (vertical ou horizontal),dans le 3ème cas,aucune importance.
    1er cas: Accrochage de n oeuvres à optimiser sur un panneau (exploitation muséographique ou galerie)
    2ème cas: insertion d'une ou plusieurs oeuvres dans le "tetris" (le reste du mur étant couvert de n toiles monochromes). A noter que les oeuvres signées comme les monochromes qui les entourent sont toujours réalisés sur des chassis standard (parmi les 114 formats existants).
    3ème cas: Le mur est uniquement composé de chassis monochromes (de différentes couleurs). Dans ce cas pas de sens d'accrochage requis.
    J'ai scanné 2 petits croquis qui vous permettraient de visualiser la chose mais pour l'instant je n'ai pas trouvé l'option me permettant de les joindre.
    Sur le mur qui m'a servi de test il y a dix formats différents.En l'ocurrence:
    6 chassis 50x50
    3 chassis 50x100
    2 chassis 70x 100
    1 chassis 100x100
    2 chassis 40x120
    1 chassis 40x50
    1 chassis 30x40
    4 chassis 50x65
    1 chassis 10x15
    2 chassis 15x15

    Parmi les n options possibles: remplacer par exemple le 50x50 par 25 10x10. ou partiellement 16 10x10 par 4 20x20,etc,etc...Combien de combinaisons possibles pour une surface donnée? Il faudrait que je puisse vous communiquer les dimensions des 114 formats pour tester. En tout cas encore merci pour votre intérêt.

Discussions similaires

  1. quel es le principe d'un logiciel de synchronisation ?
    Par mapappaloosa dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 07/02/2009, 12h47
  2. creation d'un logiciel
    Par hamza21 dans le forum Logiciel - Software - Open Source
    Réponses: 1
    Dernier message: 20/11/2008, 18h15
  3. création d'un logiciel commercial
    Par tithai000 dans le forum Logiciel - Software - Open Source
    Réponses: 8
    Dernier message: 12/07/2008, 19h21
  4. rapport sur creation de logiciel
    Par ABN84 dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 24/09/2007, 21h36
  5. Logiciel création gallerie photo sur CD
    Par Marcopoloz dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 18/09/2005, 17h36