1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2015
    Messages
    57
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2015
    Messages : 57
    Points : 53
    Points
    53

    Par défaut [Structure de données] Chemin aléatoire

    Bonjour à tous,

    J'ai ici besoin d'aide pour déterminer le modèle de mon programme, sa structure de données. En gros, de quelle façon le réaliser.

    Ce que je veux faire :
    - Construire un chemin aléatoire pixel par pixel sur une image png.

    Ce que j'utilise :
    - Une image de type BufferedImage (img=new BufferedImage(800,600,BufferedImage.TYPE_INT_ARGB)

    Les contraintes que je me fixe :
    - Un pixel du chemin ne peut être adjacent qu'à deux autres pixels de ce chemin.
    - Pour un pixel donné il existe 8 pixels adjacents et non 4 : je prends en compte les coins du pixels.

    Ce que j'ai déjà réalisé :
    - Une classe MapBuilder qui construit un chemin (ma classe Way) et écrit l'image à l'aide de ma classe ShowImagePNG.
    - MapBuilder fait appel à ma méthode buildBoundaries() qui construit une nouvelle instance de Way.
    Mais ceci n'est peut être pas la bonne chose à faire

    Ce que ça donne vs ce que je veux :
    - Le modèle idéal :
    Nom : Model.png
Affichages : 144
Taille : 1,4 Ko
    - Mon meilleur résultat :
    Nom : Output_01.png
Affichages : 142
Taille : 2,7 Ko

    Merci d'avance pour vos réponses.

  2. #2
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    110
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 110
    Points : 116
    Points
    116

    Par défaut

    Il y a déjà un soucis dans la génération de l'aléatoire puisqu'on voit une incrémentation quasi linéaire en x et y
    A moins que ce soit dans les corrections apportées lors des adjacences

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 815
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 815
    Points : 3 796
    Points
    3 796

    Par défaut

    A partir du dessin marron :
    - Etape 1 : identifier le début(A) et la fin(B) du tracé : ici, en gros le point le plus bas et le plus haut du tracé. Ces points ne seront jamais effacés. Et ce qu'on va chercher à faire, c'est effacer les points en trop, jamais en ajouter.
    - Etape 2 : Pour chaque point, s'il a un seul voisin, effacer ce point, mais sans jamais effacer les points A et B définis ci-dessus. Et boucler sur cette étape 2 tant qu'il y a des changements.
    - Etape 3 : pour chaque rectangle 3x3, si le point central est actif, et si on est dans une des configurations anormales, effacer le point central.
    Et boucler sur cette étape 3, tant qu'il y a des changements.

    Exemple de rectangles 3x3 :
    110 000 010 111
    011 011 011 011
    000 010 010 000
    Dans ces 3 configurations, et dans toutes les configurations similaires obtenues par rotation ou symétrie, on peut effacer le point central, il est en trop. Il y a peut-être d'autres configurations où il faut effacer le point central, tu devrais les trouver assez vite.

    Je n'ai plus les codes, donc je peux me tromper, mais j'avais fait un truc sur ce principe au siècle dernier, et ça marchait parfaitement.
    Le besoin était un peu différent. Le besoin était de faire des contours les plus fins possible. Si tu as une forme comme une ile au milieu de ton trait (comme c'est le cas vers le bas de ton dessin), cet algorithme laissera les 2 branches autour de cette ile.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Bonjour

    Citation Envoyé par Leododo Voir le message
    Les contraintes que je me fixe :
    - Un pixel du chemin ne peut être adjacent qu'à deux autres pixels de ce chemin.
    Le premier dessin respecte cette contrainte.
    Le second non.

    C'est cette contrainte que tu ne vérifies pas assez. Tu ne dis rien sur ton algorithme, ta méthode.
    Il faudrait vérifier que le nouveau point du chemin n'a que 1 seul point noir autour de lui. Sinon, le chemin aura plus que 2 pixels adjacents à la fin.
    Le sous-entendu de l'énoncé est que les 2 pixels adjacents sont le pixel précédent et le pixel suivant.

    Pas de possibilité ? C'est que tu as fini de voyager.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  5. #5
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Chemin aléatoire

    Bonjour,

    Le tracé aléaoire envisagé amène plusieurs questions:

    1°) La condition d'adjacence (ou si l'on veut de proximité); elle peut s'exprimer simplement à l'aide du carré de la distance euclidienne séparant les deux pixels: Dij2 = (xi - xj)2 + (yi - yj)2 .
    On observe en effet les valeurs suivantes à parir d'un pixel donné:
    _ 0 _ 1 _ 4

    _ 1 _ 2 _ 5

    _ 4 _ 5 _ 8
    ce qui conduit à la condition de proximité: Dij2 <3 .

    2°) La genèse du parcours, pour la quelle on peut envisager plusieurs procédés:

    a) Une suite de tirages aléatoires inconditionnels, avec une plus grande probabilité d'augmentation des coordonnées - ce que paraît avoir fait Leododo; il faut alors faire disparaître les zones d'accumulation par suppression de points intermédiaires par des instructions telles que celles-ci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    FOR h:= Hmax DOWNTO 2
      FOR k:= 1 TO (Kmax - h) DO
        IF (Dist2(P[k], P[k + h]<3) THEN <Supprimer les points de rang k+1, k+2 ... k+h-1>
    La borne Hmax (= 5 ou 10 ?) représente la limite au-delà de laquelle il n'y a plus de positions adjacentes - dans le pire des cas, Hmax = Kmax - 1 .

    b) Une suite de tirages conditionnels impliquant la non-proximité du nouveau point avec tous les précédents, comme le propose Flodelarab, mais sans contrôle sur la position finale et le nombre (Kmax) de points: la progression du tracé risque en effet de se bloquer dans l'une de ses sinusoïtés avant de parvenir à son terme.
    Il faudrait prévoir une marche arrière assez laborieuse à programmer ...

    c) En partant de deux points arbitrairement choisis, une insertion systématique de nouveaux points intermédiaires entre ceux déjà présents et non adjacents (Dij2 > 2), par un tirage aléatoire à l'intérieur d'un cercle contré au milieu du segment (P[i]P[j]) et de rayon proportionnel à sa longueur, en codant par exemple:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Xc:= 0.5 * (P[i].x + P[j].x); Yc:= 0.5 * (P[i].y + P[j].y); 
    D2:= Sqr(P[i].x - P[j].x);    Inc(D2, Sqr(P[i].y - P[j].y));
    R2max= (q/4) * D2;            Rmax:= Sqrt(R2max);
    REPEAT
      w:= Rmax * Rand; u:= (2*w) - 1; U2:= Sqr(u);
      w:= Rmax * Rand; v:= (2*w) - 1; V2:= Sqr(v); s:= U2 + V2
    UNTIL (s<R2max);
    Pixel.x:= Round(Xc + u); Pixel.y:= Round(Yc + v);
    D'autres conditions doivent être prévues, entre autres pour l'arrêt.

    Le paramètre (q) caractérise l'aspect général du trajet, de nature fractale; lorsqu'il est nul, on obtient un segment rectiligne joignant les pixels extrêmes, initialement choisis.
    Il existe probablement une limite (Qmin) en-dessous de laquelle les auto-intersections ne sont plus possibles, mais je ne l'ai pas calculée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #6
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    b) Une suite de tirages conditionnels impliquant la non-proximité du nouveau point avec tous les précédents, comme le propose Flodelarab, mais sans contrôle sur la position finale et le nombre (Kmax) de points: la progression du tracé risque en effet de se bloquer dans l'une de ses sinusoïtés avant de parvenir à son terme.
    Il faudrait prévoir une marche arrière assez laborieuse à programmer ...
    Pas du tout de retour en arrière. Quand un point noir a son suivant et son précédent, on colorie ses voisins blancs en rouge (cases interdites).
    Et on s'assure d'avoir toujours au moins 1 chemin blanc vers la cible.
    À la fin, on colorie tous les points rouges en blanc.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  7. #7
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Chemin aléatoire

    Citation Envoyé par Flodelarab Voir le message
    ... Quand un point noir a son suivant et son précédent, on colorie ses voisins blancs en rouge (cases interdites) ...
    Est-il bien sûr que cela supprime toute possibilité d'impasse, quelle que soit la largeur de la plage de sécurité ? Celle-ci ne fait que prévenir l'auto-intersection ...

    Qu'arrivera-t-il une fois que l'on sera parvenu au point (M) ?
    Nom : Courbe aléatoire.png
Affichages : 110
Taille : 2,6 Ko (le tracé est très mauvais, j'en conviens).

    Pour être juste, la probabilité d'auto-piégeage devient très faible si le déplacement aléatoire présente un caractère directionnel suffisamment affirmé, par exemple en codant:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    CONST Kx = 9;
    ... / ...
    k:= Rand(Kx);
    CASE k OF  0: Dec(x); 1: Inc(y); 
               2: Dec(y) ELSE Inc(x)  END;
    ce qui donne deux chance sur trois à une augmentation de la coordonnée (x).

    Citation Envoyé par Flodelarab Voir le message
    ... Il faudrait vérifier que le nouveau point du chemin n'a que 1 seul point noir autour de lui. Sinon, le chemin aura plus que 2 pixels adjacents à la fin ...
    C'est un critère pertinent mais local, qui ne définit pas l'orientation générale du parcours.

    Citation Envoyé par Flodelarab Voir le message
    ... Et on s'assure d'avoir toujours au moins 1 chemin blanc vers la cible ...
    Toute la question est là: comment se ménager un tel chemin ?
    Et l'existence d'une cible suppose une visée: cela devrait se retrouver dans les instructions du tirage aléatoire ...


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #8
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Est-il bien sûr que cela supprime toute possibilité d'impasse, quelle que soit la largeur de la plage de sécurité ?
    Oui


    (le tracé est très mauvais, j'en conviens).
    Le tracé est mauvais, non pas à cause du dessin, mais car il manque tous les points rouges.


    Qu'arrivera-t-il une fois que l'on sera parvenu au point (M) ?
    Un dessin pourri en vaut un autre: (merci Libreoffice)

    Nom : chemin_aleatoire.png
Affichages : 110
Taille : 1,3 Ko
    Le dernier point accepté pour le chemin est le point gris. En fait, il est noir mais c'est pour qu'on se repère.
    Ce point étant déterminé, le point du dessous est complet: un précédent et un suivant.
    Donc on colorie autour de ce dernier. Cela fait un joli col roulé au point gris.
    Le choix aléatoire, a priori, se fait entre le point fushia, bleu ou jaune. Je n'ai pas mis vert pour ne pas faire croire qu'il y aurait une bonne réponse a priori.
    Si le hasard choisissait le bleu, fushia et jaune deviendraient rouge et il n'y aurait plus de chemin blanc vers la cible. Donc bleu n'est pas un choix.
    Par contre, fushia et jaune évitent le cul de sac.

    Peut-on imaginer une situation où tous les choix sont bloquants ?
    Je ne pense pas.
    C'est le principe de la liberté. Tout est permis tant que ce n'est pas interdit.
    Tu peux avoir des situations de fausse liberté où tu crois choisir alors que le seul chemin possible est le chemin blanc.
    Mais à partir du moment où tu as au moins un chemin blanc, tu n'auras pas de blocage.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  9. #9
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    110
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 110
    Points : 116
    Points
    116

    Par défaut

    Citation Envoyé par Flodelarab Voir le message
    à partir du moment où tu as au moins un chemin blanc, tu n'auras pas de blocage.
    Un chemin blanc ne suffit pas puisqu'on ne pourra pas faire demi-tour en évitant les adjacences
    Le cas de wiwaxia est imparable sauf à tester à quatre cases pour se garantir le demi-tour

  10. #10
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Chemin aléatoire

    Nom : Graphe_02.png
Affichages : 105
Taille : 3,4 Ko
    Mais non, il est très bien ce graphe ! Je retiens la référence.

    Citation Envoyé par Flodelarab Voir le message
    ... Le choix aléatoire, a priori, se fait entre le point fushia, bleu ou jaune ...
    Jusque là, entièrement d'accord.

    Citation Envoyé par Flodelarab Voir le message
    ... Si le hasard choisissait le bleu, fushia et jaune deviendraient rouge et il n'y aurait plus de chemin blanc vers la cible. Donc bleu n'est pas un choix.
    Par contre, fushia et jaune évitent le cul de sac ...
    Bien sûr, mais c'est toi qui le vois, comme moi et tout un chacun devant son écran; l'algorithme, tel qu'il est proposé, est myope parce que l'inventaire des positions possibles ne va pas au-delà des cases adjacentes: le saut sur la case bleue n'est donc pas interdit et amènera inéluctablement le blocage de la randonnée pseudo-aléatoire.

    Il faudrait mettre au point une procédure de détection des impasses, ce qui me paraît assez difficile ... Pourquoi pas, bien sûr, mais à quel prix ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Bien sûr, mais c'est toi qui le vois, comme moi et tout un chacun devant son écran;
    Pas du tout. Tu fais un genre de coloriage pot de peinture. Et si ta cible est touchée, alors il y a un chemin.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  12. #12
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Chemin aléatoire

    Soit donc un nouveau bloc d'instructions, non mentionné jusqu'à présent, destiné à vérifier la connexité du domaine encore inexploré contenant la position actuelle et la cible.
    Il faudra en principe le relancer à chaque étape; cela ne risque pas d'être un peu long ?

    Cela revient à travailler sur une matrice (le corps de l'image), au lieu d'un tableau unidimensionnel de points.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Du coup, j'ai fait le programme.


    Sans ou avec les traits de construction:
    Nom : prems_chemin_propre.png
Affichages : 100
Taille : 1,2 Ko Nom : prems_chemin_sale.png
Affichages : 99
Taille : 1,5 Ko

    De (0,0) à (99,99) dans une image 100 x 100

    Pas de problèmes de coincitude.

    J'ai rien contre ta méthode, Wiwaxia. Mais je doute du côté vraiment aléatoire.

    Nom : chemin_002.png
Affichages : 98
Taille : 1,4 Ko

    Et ces 2 là ont pour point de départ (20,20) et pour arrivée (80,80) dans une image (100,100)
    Nom : chemin2080_003.png
Affichages : 100
Taille : 902 octets

    Nom : chemin2080_004.png
Affichages : 100
Taille : 1,4 Ko Nom : chemin2080_004_sale.png
Affichages : 100
Taille : 1,9 Ko

    Le message initial parle de 800 par 600. J'avoue que ça rallonge en temps. Il faudrait optimiser.

    Tu peux faire ce genre d'algorithme pour programmer une intelligence artificielle dans un jeu comme TRON, pour rester dans la partie la plus grande de l'espace.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  14. #14
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut

    Pas mal, les images !

    Je n'ai bien pas compris le sens de ta remarque
    Citation Envoyé par Flodelarab Voir le message
    ... Je n'ai rien contre ta méthode, Wiwaxia. Mais je doute du côté vraiment aléatoire ...
    Ne confondrais-tu pas parcours aléatoire et parcours isotrope, c'est-à-dire dépourvu de toute direction privilégiée ?
    Les deux ne vont pas forcément de pair.

    Prenons par exemple les instructions:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    CONST K = 4;
    z:= Random(K);
    CASE z OF  0: x:= x - 1;
               1: y:= y + 1;
               2: y:= y - 1
               ELSE x:= x + 1  END.
    Ce code traduit un mouvement de diffusion thermique, de position moyenne nulle.
    Mais dès que l'on envisage pour l'entier (K) une valeur plus élevée - par exemple (5) ou (6) - on observe une progression lente du nuage de points dans la direction des (x) croissants: au mouvement de diffusion toujours présent se superpose une migration de direction bien déterminée, caractérisée par une position moyenne au bout de (N) tirs:
    xm = N*(1 - 4/K) , ym = 0 .

    De ce point de vue, il est très facile de retrouver le parcours en biais présenté par Leododo.

    Il y a en fait plusieurs façons de comprendre son projet de création d'un parcours pseudo-aléatoire:
    - parcours sans contrainte de position ou d'orientation;
    - parcours de direction générale donnée;
    - parcours joignant deux points déterminés (liste non limitative).

    Un tel processus n'exclut pas l'intervention de contraintes extérieures (ne serait-ce que la présence des bords de l'image).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #15
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    De ce que je devine, c'est pour faire un bord de mer, une côte sur une carte.
    Si c'est le cas, il faudra se calmer sur le côté aléatoire.
    J'en ai produit une vingtaine, et la planète qui présenterait ce genre de côtes aurait bien souffert. Trop de méandres.
    Après, ça dépend aussi du niveau de zoom que tu choisis.

    Mais dès que l'on envisage pour l'entier (K) une valeur plus élevée - par exemple (5) ou (6) - on observe une progression lente du nuage de points dans la direction des (x) croissants
    Tu as raison. C'est une bonne idée pour son projet.
    Tout est possible mais surtout d'arriver en bas. (en partant d'en haut).
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  16. #16
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Chemin aléatoire

    Je crois que l'algorithme initial peut être repris en imposant au nouveau point tiré aléatoirement une condition d'éloignement minimal vis-à-vis de l'ensemble du tracé déjà obtenu; la plus petite des distances séparant la nouvelle position de toutes celles déjà occupées doit dépasser un certain seuil, soit en pratique: D2min > 3 (il est plus simple de s'en tenir aux carrés) - voir le message #5 .
    Ce procédé est l'équivalent des marques rouges proposées par Flodelarab; je n'ai pas eu le temps de programmer, pour comparer les temps d'exécution sur de grandes images - l'avantage, sous ce rapport, revient probablement à la solution graphique.

    Il serait bon aussi de prévoir une sortie du processus de croissance du parcours, dans le cas d'un blocage accidentel, afin d'éviter un plantage do programme; arrêt qui serait déclenché après 10 ou 20 tirs refusés, par exemple.
    Cela permettrait en outre de remplir au maximum l'espace disponible, si l'on veut voir ce que cela donne.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  17. #17
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2015
    Messages
    57
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2015
    Messages : 57
    Points : 53
    Points
    53

    Par défaut

    Citation Envoyé par valentin03 Voir le message
    Il y a déjà un soucis dans la génération de l'aléatoire puisqu'on voit une incrémentation quasi linéaire en x et y
    A moins que ce soit dans les corrections apportées lors des adjacences
    => Oui, javais modifié la génération aléatoire des nombre pour éviter de revenir sur mes pas =) En gros plus de chance de +1 en x et y.

    Citation Envoyé par tbc92 Voir le message
    A partir du dessin marron [...] Dans ces 3 configurations, et dans toutes les configurations similaires obtenues par rotation ou symétrie, on peut effacer le point central, il est en trop. Il y a peut-être d'autres configurations où il faut effacer le point central, tu devrais les trouver assez vite.
    J'avais fait un truc sur ce principe au siècle dernier, et ça marchait parfaitement. Le besoin était de faire des contours les plus fins possible.
    => Je n'avais pas pensé à partir de mon essai mal contraint et d'effacer ce qu'il y a en trop. C'est une piste que je vais explorer dans un second temps =)
    Mon besoin est en effet de faire des contours les plus fins possible.

    Citation Envoyé par Flodelarab Voir le message
    Il faudrait vérifier que le nouveau point du chemin n'a que 1 seul point noir autour de lui. Sinon, le chemin aura plus que 2 pixels adjacents à la fin. Le sous-entendu de l'énoncé est que les 2 pixels adjacents sont le pixel précédent et le pixel suivant.
    => Oui, c'est cela, et c'est l'élément qui me manquais : Dans ma méthode j'ai commencé à vérifier que le pixel précédent n'était adjacent qu'à 2 pixels noir, alors qu'en effet il me suffit de vérifier que le pixel suivant n'est adjacent qu'à un autre pixel noir. En gros je revenais au pixel d'avant pour rien.

    Citation Envoyé par wiwaxia Voir le message
    La condition d'adjacence (ou si l'on veut de proximité); elle peut s'exprimer simplement à l'aide du carré de la distance euclidienne séparant les deux pixels: Dij2 = (xi - xj)2 + (yi - yj)2 .
    On observe en effet les valeurs suivantes à parir d'un pixel donné:
    _ 0 _ 1 _ 4

    _ 1 _ 2 _ 5

    _ 4 _ 5 _ 8
    ce qui conduit à la condition de proximité: Dij2 <3 .

    En partant de deux points arbitrairement choisis, une insertion systématique de nouveaux points intermédiaires entre ceux déjà présents et non adjacents (Dij2 > 2), par un tirage aléatoire à l'intérieur d'un cercle contré au milieu du segment (P[i]P[j]) et de rayon proportionnel à sa longueur, en codant par exemple:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Xc:= 0.5 * (P[i].x + P[j].x); Yc:= 0.5 * (P[i].y + P[j].y); 
    D2:= Sqr(P[i].x - P[j].x);    Inc(D2, Sqr(P[i].y - P[j].y));
    R2max= (q/4) * D2;            Rmax:= Sqrt(R2max);
    REPEAT
      w:= Rmax * Rand; u:= (2*w) - 1; U2:= Sqr(u);
      w:= Rmax * Rand; v:= (2*w) - 1; V2:= Sqr(v); s:= U2 + V2
    UNTIL (s<R2max);
    Pixel.x:= Round(Xc + u); Pixel.y:= Round(Yc + v);
    => Les conditions sont tout à fait vrai, cependant en travaillant avec Java je peux vérifier l'adjacence grâce à une méthode getRGB() me renvoyant si oui ou non le pixel adjacent est utilisé =)

    Citation Envoyé par wiwaxia Voir le message
    Est-il bien sûr que cela supprime toute possibilité d'impasse, quelle que soit la largeur de la plage de sécurité ? Celle-ci ne fait que prévenir l'auto-intersection ... C'est un critère pertinent mais local, qui ne définit pas l'orientation générale du parcours.
    => C'est juste, j'avais prévu de stopper le programme dès qu'une situation comme celle ci apparaissait. Mais ça risque de me stopper tôt.

  18. #18
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2015
    Messages
    57
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2015
    Messages : 57
    Points : 53
    Points
    53

    Par défaut

    Après avoir lu et surtout compris la discussion entre Flodelarab et wiwaxia, ce que j'avais initialement prévu est ce résultat présenté :
    Citation Envoyé par Flodelarab Voir le message
    Du coup, j'ai fait le programme. Sans ou avec les traits de construction:
    Nom : prems_chemin_propre.png
Affichages : 100
Taille : 1,2 Ko Nom : prems_chemin_sale.png
Affichages : 99
Taille : 1,5 Ko
    Je vais donc programmer ça (en Java) grâce à vos éclaircissements et je reviens vers vous dès que j'ai le même résultat =)
    Par la suite je pourrai passer à une condition d'éloignement minimal vis-à-vis de l'ensemble du tracé déjà obtenu dont vous parlez =)

  19. #19
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    637
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 637
    Points : 1 288
    Points
    1 288
    Billets dans le blog
    5

    Par défaut Où il y a beaucoup d'appelés, mais peu d'élus.

    J'ai écrit à la hâte un programme élémentaire susceptible de produire une parcours aléatoire en biais, ressemblant à celui de Leododo, sans les imperfections dont celui-ci peine à se débarrasser.

    Nom : H0_Leododo_02.png
Affichages : 74
Taille : 1,7 Ko
    Faute de temps pour explorer mes archives, je m'en suis simplement tenu à une plage rectangulaire d'écran-texte (80x60), la position initiale (10, 10) se situant près du coin supérieur gauche et la zone d'arrêt correspondant au carré (10x10) placé au coin inférieur droit.

    Le tir pseudo-aléatoire du déplacement élémentaire a été improvisé comme il suit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     PROCEDURE TirageDir(VAR V_: VectW2);
       CONST I0 = 50; L1 = 10;  L2 = 2 * L1;       L3 = 3 * L1;
             I3 = 1 + (3 * I0); I4 = 1 + (4 * I0);
             I6 = 1 + (6 * I0); I7 = 1 + (7 * I0); I8 = 1 + (8* I0);
             L4 = L3 + I3;      L5 = L4 + I4;      L6 = L5 + I6;
             L7 = L6 + I7;      L8 = L7 + I8;
       VAR m: Word; Va: VectW2;
       BEGIN
         Va:= V_; m:= Random(L8 + 1);
         CASE m OF   0..L1-1: Dec(Va.y);
                    L1..L2-1: BEGIN Dec(Va.x); Dec(Va.y) END;
                    L2..L3-1: Dec(Va.x);
                    L3..L4-1: BEGIN Dec(Va.x); Inc(Va.y) END;
                    L4..L5-1: BEGIN Inc(Va.x); Dec(Va.y) END;
                    L5..L6-1: Inc(Va.y);
                    L6..L7-1: BEGIN Inc(Va.x); Inc(Va.y) END
                    ELSE      Inc(Va.x)  END;
         V_:= Va
       END;
    Une simple consultation des intervalles en cause fait apparaître la préférence donnée aux augmentations des coordonnées (x) et (y), préférence d'autant plus marquée que le terme (I0) est plus grand - de cette constante dépendent en fait toutes les autres qui n'ont pas de valeur unique.
    Il conviendrait évidemment de reprendre ces calculs sur des considérations géométriques; mais il s'agit ici d'une question secondaire.

    1°) J'ai tenté en vain de supprimer les boucles & auto-intersections d'un parcours généré sans contrainte autre que l'interdiction de sortie du domaine - (0 < x < 81) et (0 < y < 61); il m'a fallu renoncer à défaire ce sac de noeuds (au sens propre du terme), et d'autres plus avisés que moi viendront à bout de ce problème.

    2°) Je m'en suis donc tenu au codage d'une progression respectant l'éloignement minimal par rapport aux points déjà présents, au risque du blocage évoqué auparavant. Cette contrainte est assurée par la fonction booléenne suivante, qui reprend la condition (d2 > 3):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     FUNCTION TestProx(Np: Word; Po: VectW2; VAR L_: LstVw2): Bool;
       VAR k: Word; VAR Min, s, u, U2, v, V2, w: Z_32; Test: Bool;
       BEGIN
         IF (Np=0) THEN Test:= True
                   ELSE BEGIN
                          s:= 0; Min:= 10000;
                          FOR k:= 0 TO (Np - 1) DO
                            BEGIN
                              w:= L_[k].x; u:= w - Po.x; U2:= Sqr(u);
                              w:= L_[k].y; v:= w - Po.y; V2:= Sqr(v);
                              s:= U2 + V2; IF ((Min>s)) THEN Min:= s
                            END;
                          IF (Min>3) THEN Test:= True
                                     ELSE Test:= False
                        END;
         TestProx:= Test
       END;
    Voici l'essentiel du programme source, que chacun transposera dans son propre langage:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
     CONST Nmax= 5000;
    
     TYPE VectW2 = RECORD  x, y: Word  END;
          LstVw2 = ARRAY[0..Nmax] OF VectW2;
    
     VAR Ndep, Nparc: Word; Liste: LstVw2;
    
     PROCEDURE ZeroE(VAR k: Word);
       BEGIN
         k:= 0
       END;
    
     PROCEDURE TraceP(We: VectW2);
       BEGIN
         GotoXY((We.x MOD 256), (We.y MOD 256)); Write('Û')
       END;
    ... / ...
     PROCEDURE Trace1(VAR Nd: Word; VAR Li: LstVw2);
       CONST NmaxTir = 100;
       VAR h, k, m: Word; Va, Ve: VectW2; Tx, Ty, Tz: Bool;
       BEGIN
         Randomize; k:= 0; Ve:= Li[0];
         REPEAT
           h:= 0;
           REPEAT
             Inc(h);                        Va:= Ve;
             TirageDir(Va);                 Tx:= ((0<Va.x) AND (Va.x<81));
             Ty:= ((0<Va.y) AND (Va.y<61)); Tz:= TestProx(k, Va, Liste)
           UNTIL (((Tx AND Ty) AND Tz) OR (h>NmaxTir));
           IF (h<=NmaxTir) THEN BEGIN
                                  Inc(k);     Ve:= Va;
                                  Li[k]:= Ve; TraceP(Ve)
                                END;
         UNTIL (k=(Nmax - 1)) OR ((Ve.x>70) AND (Ve.y>50)) OR (h>NmaxTir);
         IF (h>NmaxTir) THEN E(0012) ELSE E(0009);
         TraceP(Liste[k]); Nd:= k
       END;
    
     PROCEDURE InitV(Vx, Vy: Word; VAR V1: VectW2);
       VAR V2: VectW2;
       BEGIN
         WITH V2 DO BEGIN
                      x:= Vx; y:= Vy
                    END;
         V1:= V2
       END;
    
     PROCEDURE InitL(VAR Li: LstVw2);
       CONST Vzero: VectW2 = (x:0; y:0);
       VAR k: Word;
       BEGIN
         FOR k:= 1 TO Nmax DO Li[k]:= Vzero
       END;
    
     PROCEDURE Trace0;
       BEGIN
         InitL(Liste);         InitV(10, 10, Liste[0]);
         E(1010);              TraceP(Liste[0]);
         F(71, 51, 80, 60, 5); E(0014)
       END;
    Les parcours complets, d'aspect très variable, présentent des circonvolutions d'autant plus marquées que la constant (I0) est plus faible - les valeurs injectées allant de (1) à (50); la limite nulle correspondant au mouvement brownien isotrope dans un espace à deux dimensions.

    Nom : H1_Tracé_076_309.png
Affichages : 75
Taille : 22,1 Ko

    Les parcours produits sont majoritairement interrompus par blocage interne, ou sur les frontières; l'option de fin prématurée se révèle donc indispensable, même si sa probabilité s'affaiblit sur de plus grands domaines.

    Nom : H2_BlocI_P.png
Affichages : 74
Taille : 20,3 Ko

    Une variante du même programme permet de dénombrer les parcours bloqués en interne (NbI) ou contre les parois (NbP,) ainsi que les parcours complets (Npc) obtenus sur des séries de 10000 trajectoires aléatoires correspondant à la même valeur de (I0); les valeurs (50, 10, 5, 1) ont conduit aux résultats ci-dessous:

    Nom : H_Stat_I0=50_10_05_01.png
Affichages : 76
Taille : 12,8 Ko

    La proportion des parcours complets décroît de 55 à 0.06 % - ils sont donc loin d'être majoritaires, sur le domaine des valeurs utilisées.
    Remarquer aussi l'évolution rapide de la nature du blocage.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  20. #20
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 967
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 967
    Points : 6 959
    Points
    6 959

    Par défaut

    Super rapport


    Je n'ai pas lâché l'affaire non plus. J'essaie d'obtenir un temps raisonnable pour un 800x600. J'avais un souvenir plus rapide du "pot-de-peinture".
    Mais même en utilisant un réseau sémaphore qui permet à un pixel de savoir instantanément s'il atteint la cible ou non, c'est trop lent.
    Et le demi-million de pixels empêche la récursivité. Obligé d'utiliser l'itération.

    J'ai dû coder cela avec les pieds. Je retenterai ma chance.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Comment créer une structure de donnée dynamiquement ?
    Par Beaunico dans le forum Langage
    Réponses: 9
    Dernier message: 24/01/2006, 09h34
  2. Aide pour diagramme de structure des données
    Par DeezerD dans le forum Décisions SGBD
    Réponses: 4
    Dernier message: 04/12/2004, 19h10
  3. Méta-Programmation - [ structures de données ]
    Par Dam)rpgheaven dans le forum C++
    Réponses: 3
    Dernier message: 03/12/2004, 19h38
  4. Structure des données en retour d'un DBExtract ?
    Par mikouts dans le forum XMLRAD
    Réponses: 4
    Dernier message: 24/01/2003, 15h15
  5. Structure de données de type "RECORD"
    Par chaours dans le forum VB 6 et antérieur
    Réponses: 2
    Dernier message: 30/09/2002, 17h10

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo