IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Développement 2D, 3D et Jeux Discussion :

Génération Aléatoire d'Univers


Sujet :

Développement 2D, 3D et Jeux

  1. #1
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut Génération Aléatoire d'Univers
    Génération Aléatoire d'Univers


    1. Introduction

    J'ai tout récemment eu l'envie de m'atteler à la génération aléatoire d'univers, et cet article a pour but de vous faire partager mon expérience et mes résultats. Loin d'être un expert dans le domaine, toute contribution complémentaire sera appréciée. Le langage utilisé dans cet exposé sera TypeScript, dont vous pourrez trouver une présentation ici.

    La génération procédurale pour créer des univers est une pratique très courante dans le domaine des jeux vidéos se déroulant dans le vide intersidéral. Le mythique Elite fut l'un des précurseurs et pour ne citer que quelques titres, on peut relever la série des Master of Orion, Galactic Civilization, Faster than Light, Star Wars: Empire at War, etc, etc, etc.


    Master of Orion 3


    Faster than Light

    Je vais ici présenter les différentes approches que j'ai essayé pour générer des univers aléatoires ayant une topologie à peu près acceptable. Dans un plan en deux dimensions, il s'agira donc de générer un ensemble de positions (des étoiles ou des planètes dans le cas d'un contexte spatial, ou de villes s'il s'agit d'un contexte plus réaliste).

    Ces positions devront être reliées par des liens (des chemins si on considère des villes, ou bien des routes spatiales si on est dans le vide intersidéral) de façon à respecter une certaine règle de proximité. On privilégiera de relier deux positions proches plutôt que deux positions éloignées.


    2. Génération des positions

    2.1. Approche naïve

    Une position sera définie comme un point à deux dimensions ayant d'autres attributs que nous ajouterons par la suite. En TypeScript cela pourrait donner ceci :
    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
    class Position extends Point {
      // autres attributs...
     
      constructor(x: number, y: number) {
        super(x, y);
      }
    }
     
    class Point {
      x: number;
      y: number;
     
      constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
      }
    }
    Pour le moment, la distinction entre Point et Position peut sembler assez artificielle. Elle n'est pas indispensable mais permet de bien séparer ce qui relève de l'outillage (la classe Point) et ce qui relève de la sémantique (la classe Position). Les fonctions utilitaires à usage généraliste seront associées à la classe Point, tandis que ce qui relèvera des spécificités de l'application sera associé à la classe Position.

    Pour peupler notre univers, une façon naïve pourrait consister tout d'abord à générer un ensemble aléatoire de couples (x, y), où la valeur de l'abscisse (resp. de l'ordonnée) représente un pourcentage de la longueur (resp. de la largeur) de l'univers, puisque cette valeur est comprise entre 0 et 1. En retardant le plus possible l'utilisation des dimensions concrètes de l'Univers, cela permet de rendre l'implémentation plus générique.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    var nbPositions = 400; // Nombre de positions
    univers: Position[] = [];
     
    for (var i = 0; i < nbPositions; i++) {
      univers.push(new Position(Math.random(), Math.random()));
    }
    Ceci donne les résultats qu'on peut voir ci-dessous.


    On se rend compte que cette approche naïve pose deux problèmes assez évidents. Le premier est que certaines positions sont trop proches du bord du domaine. Le second est que certaines positions sont trop proches les unes des autres ou se confondent.

    La résolution de ces deux problèmes est assez simple. Pour le premier problème, nous réduirons l'intervalle des nombres aléatoires qui est pour le moment compris entre 0 et 1 avec la méthode de base Math.random(). Pour le second problème, nous empêcherons la génération d'une nouvelle position, si elle est trop proche de positions déjà générées.

    2.2. Correction du phénomène de bord

    Donnons-nous une "marge" autour du bord dans laquelle aucune position ne pourra être créé, et fixons sa valeur à 5% en longueur et à la même chose en largeur. Avec une simple règle de mise à l'échelle, cela donnerait la formule suivante applicable à la fois aux abscisses et aux ordonnées générées aléatoirement :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    0.05 + 0.90 * Math.random()
    2.3. Correction des points trop rapprochés

    Pour éviter d'avoir des positions trop proches les unes des autres, il suffit de définir une distance minimale en deçà de laquelle générer une nouvelle position n'est pas permis. En utilisant l'approche simple, celle qui consiste à balayer linéairement l'ensemble des points existants, on pourrait avoir le code suivant :

    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
    var nbPositions = 400; // Nombre de positions
    var univers: Position[] = [];
     
    var i = 0;
    var point = new Point(0, 0);
    while (i < nbPositions) {
      point.x = 0.05 + 0.90 * Math.random()
      point.y = 0.05 + 0.90 * Math.random();
     
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point.x, point.y));
        i++;
      }
    }
     
    function isValidLocation(point: Point, univers: Position[]): boolean {
      for (var i = 0; i < univers.length; i++) {
        var pos = univers[i];
     
        if (distance(point.x, point.y, pos.point.x, pos.point.y) < 0.02) {
          return false;
        }
      }
     
      return true;
    }
     
    function distance(x1: number, y1: number, x2: number, y2: number): number {
      return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }
    Il va sans dire au final, en terme d'efficacité algorithmique, que cette méthode n'est pas très efficiente puisque l'ordre de grandeur est une complexité en O(n²) ce qui peut vite se révéler rédhibitoire pour un grand ensemble de positions. Pour améliorer les performances de ce processus, il serait sans doute utile d'implémenter une variante de l'algorithme des plus proches voisins (All Nearest Neighbors)

    Cependant, pour le moment, nous nous contenterons de l'approche "naïve" compte-tenu d'un nombre de positions à priori limité. Le résultat de ces modifications, l'ajout d'une "marge" et l'application d'une distance minimale entre les positions, donne ce qui suit.


    Nous pouvons estimer en première approche cette distribution des positions comme satisfaisante ce qui nous amène à la seconde partie de cet exposé, à savoir la liaison entre les positions.

    >> suite
    Tutoriels et FAQ TypeScript

  2. #2
    Membre chevronné Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    Mai 2007
    Messages
    1 042
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mai 2007
    Messages : 1 042
    Points : 2 232
    Points
    2 232
    Par défaut
    Bonjour,

    C'est un beau travail

    Juste une petite optimisation ici:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    if (distance(point.x, point.y, pos.point.x, pos.point.y) < 0.02)
    Tu peux économiser les racines carrées qui ont un cout énorme pour les processeurs en comparant la distance au carré comme ceci donc:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    if (distanceSquare(point.x, point.y, pos.point.x, pos.point.y) < 0.0004)
    Normalement, dans le calcul des distances tu auras très rarement besoin de la racine carré sauf si tu veux la distance réel à afficher quelque part.
    Homer J. Simpson


  3. #3
    Membre chevronné Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    Mai 2007
    Messages
    1 042
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mai 2007
    Messages : 1 042
    Points : 2 232
    Points
    2 232
    Par défaut
    Autre chose

    Je ne connais pas TypeScript mais est-ce que ceci:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    var i = 0;
    while (i < nbPositions) {
      var point = new Point(0.05 + 0.90 * Math.random(), 0.05 + 0.90 * Math.random());
     
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point));
        i++;
      }
    }
    Ne serait pas plus lent que ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    var i = 0;
    var point : new Point;
    while (i < nbPositions) {
       var rand  = 0.05 + 0.90 * Math.random();
      point.x = rand ;
      point.y = rand ;
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point));
        i++;
      }
    }
    Si tu y gagne après avoir mesurer la différence, alors tu devrais également sortir le new Position de la boucle
    Homer J. Simpson


  4. #4
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par Astraya Voir le message
    Juste une petite optimisation ici:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    if (distance(point.x, point.y, pos.point.x, pos.point.y) < 0.02)
    Tu peux économiser les racines carrées qui ont un coup énorme pour les processeurs en comparant la distance au carré comme ceci donc:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    if (distanceSquare(point.x, point.y, pos.point.x, pos.point.y) < 0.0004)
    Normalement, dans le calcul des distances tu aura très rarement besoin de la racine carré sauf si tu veux la distance réel à afficher quelque part.
    C'est en effet une optimisation tout à fait pertinente. Merci de l'avoir signalée

    Citation Envoyé par Astraya Voir le message
    Autre chose

    Je ne connais pas TypeScript mais est-ce que ceci:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    var i = 0;
    while (i < nbPositions) {
      var point = new Point(0.05 + 0.90 * Math.random(), 0.05 + 0.90 * Math.random());
     
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point));
        i++;
      }
    }
    Ne serait pas plus lent que ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    var i = 0;
    var point : new Point;
    while (i < nbPositions) {
       var rand  = 0.05 + 0.90 * Math.random();
      point.x = rand ;
      point.y = rand ;
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point));
        i++;
      }
    }
    Si tu y gagne après avoir mesurer la différence, alors tu devrais également sortir le new Position de la boucle
    J'aime bien les idées présentes dans ta proposition. Mais elles ne sont pas applicables en TypeScript.

    Tout d'abord, un objet Position tel qu'il a été défini dans l'article contient une référence sur un objet Point, et non les valeurs x et y en elles-même. Ce qui fait que je ne peux pas créer une instance de Point en dehors de la boucle sous peine d'avoir toutes mes instances de Position avoir les mêmes coordonnées x, y. Ce raisonnement s'applique également à la création d'un objet Position dans le tableau univers. Si je ne crée pas à chaque pas de boucle un nouvel objet, alors je me retrouverai avec un univers ayant une multitude de copies d'une seule et même position.

    Pour ce qui est de l'optimisation sur la génération aléatoire, ta proposition a l'inconvénient d'affecter à point.x et à point.y la même valeur aléatoire ce qui au final engendrera un univers avec des positions uniquement présente sur une diagonale.
    Tutoriels et FAQ TypeScript

  5. #5
    Membre chevronné Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    Mai 2007
    Messages
    1 042
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mai 2007
    Messages : 1 042
    Points : 2 232
    Points
    2 232
    Par défaut
    J'aime bien les idées présentes dans ta proposition. Mais elles ne sont pas applicables en TypeScript.

    Tout d'abord, un objet Position tel qu'il a été défini dans l'article contient une référence sur un objet Point, et non les valeurs x et y en elles-même. Ce qui fait que je ne peux pas créer une instance de Point en dehors de la boucle sous peine d'avoir toutes mes instances de Position avoir les mêmes coordonnées x, y. Ce raisonnement s'applique également à la création d'un objet Position dans le tableau univers. Si je ne crée pas à chaque pas de boucle un nouvel objet, alors je me retrouverai avec un univers ayant une multitude de copies d'une seule et même position.
    Ok je vois, je ne connais pas du tout ce langage, je me demandais si cela ne faisait pas de copie. J'ai proposé ça afin d'éviter un maximum le nombre d'allocation faite, car peut importe le langage, instancier 1 fois X objets est moins couteux que instancier X objet fois 1. (HS: On peut tromper 1 personnes 1000 fois mais pas 1 fois 1000... euh non... On peut tromper 1000 .... )

    Pour ce qui est de l'optimisation sur la génération aléatoire, ta proposition a l'inconvénient d'affecter à point.x et à point.y la même valeur aléatoire ce qui au final engendrera un univers avec des positions uniquement présente sur une diagonale.
    Je suis allez un peu vite sur ce coup la :p

    J'attends la suite
    Homer J. Simpson


  6. #6
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    J'ai modifié la classe Position qui désormais dérive de la classe Point, au lieu d'inclure un attribut point.
    Ceci permet de rendre le code un peu plus compact et permet une petite optimisation.

    Je n'ai pas touché par contre aux calculs des distances pour des raisons de clarté explicative même si pour une implémentation, rester au niveau des carrés de distances sans extraire la racine serait plus optimal.
    Tutoriels et FAQ TypeScript

  7. #7
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    3. Génération des connexions

    3.1. Seuil simple

    Cet aspect peut sembler au premier abord trivial. En effet, rien de plus simple que de relier deux points. Simplement, dans un souci de réalisme et de cohérence, il est peu probable qu'on veuille relier systématiquement toutes les positions entre elles. Dans la réalité, par exemple, les villes ne sont pas toutes reliées directement les unes avec les autres par des routes. Tout au plus, une ville est reliées avec quelques une de ses voisines, et de proche en proche cela constitue ce qu'on nomme communément le réseau routier.

    La première approche simpliste pour relier les positions consiste à se donner un seuil au-delà duquel deux positions ne peuvent pas être reliées. Ce seuil correspondra à la contrainte de proximité entre les positions qu'on devine intuitivement.

    Pour cela, nous devons ajouter un attribut à la classe Position qui servira à stocker les liaisons pour faciliter le parcours du réseau, et devient ainsi autre chose qu'un simple Point.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Position extends Point {
      links: Position[];
      // autres attributs...
     
      constructor(x: number, y: number) {
        super(x, y);
        this.links = [];
      }
    }
    Dans cette première approche simpliste, la connexion entre les différentes positions se réalise via une double boucle sur l'ensemble des positions de l'univers engendré, en se fixant un éloignement maximal qui dans l'exemple est fixé à 6,5% mais peut être ajusté.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for (var i = 0; i < univers.length; i++) {
      var posA = univers[i];
     
      for (var j = 0; j < univers.length; j++) {
        var posB = univers[j];
        if (distance(posA.point.x, posA.point.y, posB.point.x, posB.point.y) < 0.065) {
          posA.links.push(posB);
        }
      }
    }
    Avec ce seuil à 6,5%, on obtient les résultats suivant :

    Le rendu est globalement intéressant et pourrait suffire pour pas mal d'utilisations. Cependant, on peut relever divers menus défauts.
    1. Certains morceaux de taille significative sont isolés du reste du réseau (cf. exemple 2 en bas à gauche, et exemple 3 à droite)
    2. Il est fréquent que des connexions se croisent ce qui n'est pas esthétique et on pourrait préférer que seules les positions soient le lieu de confluence des connexions.
    3. Il n'est pas rare qu'une position soit directement reliée à deux autres positions qui sont pratiquement dans le même alignement ce qui fait pratiquement se confondre une connexion avec une autre.


    Pour résoudre le problème de non-connexité de certaines parties de l'univers, un réflexe serait d'augmenter le seuil au-delà duquel les connexions entre positions ne sont plus permises. Par exemple, en se donnant un seuil à 7%, on pourrait engendrer les univers suivants :

    On se rend compte avec ces nouveaux résultats qu'augmenter le seuil résout le problème de non-connexité, mais aggrave les deux autres problèmes, celui des connexions qui se croisent et celui des connexions qui se confondent, ou presque.

    3.2. Contraintes sur les angles

    Il est possible à priori d'imaginer des raffinements à la précédente approche en imposant de nouvelles contraintes sur la formation des connexions. Nous pourrions envisager par exemple d'imposer un angle minimal entre deux connexions afin d'éviter le problème des connexions qui se confondent.

    L'implémentation de cette contrainte n'est pas triviale. L'idée générale est de partir d'un graphe complet sur lequel on supprimera progressivement les connexions formant un angle trop petit avec d'autres.

    Tout d'abord, pour les besoins de cette approche améliorée, nous allons enrichir la classe Point d'une nouvelle méthode nous permettant de déterminer l'angle formée par trois points.
    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
    class Point {
      x: number;
      y: number;
     
      constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
      }
     
      angle(p1: Point, p2: Point): number {
        var p1c = this.distance(p1);
        var p2c = this.distance(p2);
        var p1p2 = p1.distance(p2);
     
        return Math.acos((p1c * p1c + p2c * p2c - p1p2 * p1p2) / (2 * p2c * p1c));
      }
    }
    Ensuite, nous aurons recours à la matrice d'incidence du graphe formé par l'ensemble des positions qui est une matrice booléenne carrée de dimension N² où N est le nombre de positions. Cette matrice sera initialisée à vrai (true) partout, sauf sur la diagonale puisqu'une position n'admet à priori pas de connexion sur elle-même.
    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
    var incidence: boolean[][] = [];
     
    for (var i = 0; i < univers.length; i++) {
      var line: boolean[] = [];
     
      for (var j = 0; j < univers.length; j++) {
        if (i != j) {
          line.push(true);
        }
        else {
          line.push(false);
        }
      } // for j
      incidence.push(line);
    } // for i
    Une fois la matrice d'incidence initialisée, nous pouvons nous attaquer à la suppression des "mauvaises" connexions.
    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
    for (var i = 0; i < univers.length; i++) {
      var posA = univers[i];
     
      for (var j = 0; j < univers.length; j++) {
        var posB = univers[j];
     
        if (!incidence[i][j]) { // posA et posB ne sont pas reliées
          continue;
        }
     
        if (distance(posA.x, posA.y, posB.x, posB.y) > 0.07) {
          incidence[i][j] = false;
          incidence[j][i] = false;
          continue;
        }
     
        for (var k = 0; k < univers.length; k++) {
          if (k != i && k != j && incidence[i][k]) {
            var posC = univers[k];
     
            if (posA.angle(posB, posC) < Math.PI / 8) {
              incidence[i][k] = false;
              incidence[k][i] = false;
            }
          }
        } // for k
      } // for j
    } // for i
    Dans le code ci-dessus, le seuil de distance a été fixé à 7% et l'angle minimal a été fixé à PI / 8, soit 22,5°.

    Une fois réalisé le nettoyage des connexions jugées invalides, il ne nous reste plus qu'à balayer à nouveau la matrice d'incidence pour stocker les destinations possibles pour chaque position.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (var i = 0; i < univers.length; i++) {
      var posA = univers[i];
      for (var j = 0; j < univers.length; j++) {
        var posB = univers[j];
        if (incidence[i][j]) {
          posA.links.push(posB);
        }
      } // for j
    } // for i
    Les performances de cette nouvelle approche reste tout à fait acceptable, bien qu'il y ait sans doute des choses à optimiser, et le rendu visuel est intéressant.

    Cependant, reste toujours le défaut non négligeable qui est celui des connexions qui se croisent. Donc nous pouvons mieux faire !

    A suivre...
    Tutoriels et FAQ TypeScript

  8. #8
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    4. Triangulation de Delaunay

    Le problème des connexions qui se croisent peut être résolu en utilisant une méthode issue de l'algorithmique géométrique qui se nomme la Triangulation de Delaunay. C'est une technique courante qui permet de relier un nuage de points de façon connexe à l'aide de triangles. En utilisant cette méthode, nous éviterons ainsi d'avoir des connexions qui se croisent. Cet algorithme tend également à éviter de produire des triangles plats ce qui devrait limiter le problème des connexions qui semblent se confondre.

    Plutôt que de réécrire cet algorithme, nous réutiliserons une implémentation en Javascript déjà existante : https://github.com/ironwallaby/delaunay.

    Son utilisation est très simple. La fonction principale se nomme triangulate et prend en paramètre une liste de couples x, y. Cette fonction renvoie les triangles de Delaunay sous une forme aplatie. Par exemple les trois premiers éléments de la liste contiennent respectivement l'indice des trois points formant le premier triangle, les trois éléments suivants contiennent l'indice des points formant le deuxième triangle et ainsi de suite.

    Mais avant de l'utiliser dans un programme en TypeScript, il convient de créer un petit fichier de déclarations ayant l'extension .d.ts tel qu'on peut le voir ci-dessous :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    interface DelaunayStatic {
     
      triangulate(vertices: number[][], key?: number): number[];
    } // DelaunayStatic
     
    declare var Delaunay: DelaunayStatic;
    Si ce fichier est nommé delaunay.d.ts, nous devrons y faire référence en début du source TypeScript de la façon suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    /// <reference path="delaunay.d.ts"/>
    Si vous avez une certaine arborescence, bien évidemment il faudra modifier le chemin en conséquence.

    L'appel à la fonction triangulate peut se faire ainsi :
    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
    var vertices: number[][] = [];
    var i = 0;
    var point = new Point(0, 0);
    while (i < nbPositions) {
      point.x = 0.05 + 0.90 * Math.random();
      point.y = 0.05 + 0.90 * Math.random();
     
      if (this.isValidLocation(point)) {
        univers.push(new Position(point.x, point.y));
        vertices.push([point.x, point.y]);
        i++;
      }
    } // while
     
    var triangles = Delaunay.triangulate(vertices);
     
    for (i = 0; i < triangles.length; i += 3) {
      var p0 = univers[triangles[i + 0]];
      var p1 = univers[triangles[i + 1]];
      var p2 = univers[triangles[i + 2]];
      p0.links.push(p1);
      p0.links.push(p2);
      p1.links.push(p0);
      p1.links.push(p2);
      p2.links.push(p0);
      p2.links.push(p1);
    } // for i
    A noter que la variable vertices est la liste des couples x, y des positions. Cette variable est initialisée à la génération des positions, puis elle est passée en paramètre dans la fonction triangulate.

    Une fois l'appel à la fonction triangulate réalisé, il convient de parcourir le résultat sous forme de liste par bloc de 3 éléments afin de stocker les connexions dans chacune des positions.

    En terme de rendu visuel, on obtient ceci :


    On constate que les trois problèmes qui avaient été identifiés sur l'approche simple ont disparu et notamment celui des connexions qui se croisaient et des connexions qui avaient tendance à se confondre (si on fait abstraction des anomalies de l'enveloppe connexe).

    Mais le résultat n'est pas exempt de défauts. Tout d'abord, on peut reprocher l'aspect un peu trop régulier du réseau. On peut également remarquer, notamment sur les bords que certaines connexions sont très longues.

    Pour remédier à ces deux défauts, il suffit simplement de rajouter un filtre sur la longueur des connexions au moment où on stocke les connexions de chacune des positions. C'est ce qui dans le jargon est nommé l'alpha shape.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (i = 0; i < triangles.length; i += 3) {
      var p0 = univers[triangles[i + 0]];
      var p1 = univers[triangles[i + 1]];
      var p2 = univers[triangles[i + 2]];
      if (distance(p0.x, p0.y, p1.x, p1.y) < 0.068) p0.links.push(p1);
      if (distance(p0.x, p0.y, p2.x, p2.y) < 0.068) p0.links.push(p2);
      if (distance(p1.x, p1.y, p0.x, p0.y) < 0.068) p1.links.push(p0);
      if (distance(p1.x, p1.y, p2.x, p2.y) < 0.068) p1.links.push(p2);
      if (distance(p2.x, p2.y, p0.x, p0.y) < 0.068) p2.links.push(p0);
      if (distance(p2.x, p2.y, p1.x, p1.y) < 0.068) p2.links.push(p1);
    } // for i
    Avec un seuil à 6,8%, voici le genre de rendu qu'on peut obtenir :


    On constate que l'aspect régulier qui pouvait être gênant dans la version brute de la triangulation de Delaunay, s'estompe en appliquant l'alpha shape. Il est possible d'augmenter les irrégularités en réduisant la valeur du seuil, mais au risque d'isoler certaines parties du réseau.

    A l'issue de toutes ces démarches, nous pouvons générer aléatoirement une multitude d'univers peuplés de lieux reliés entre eux de façon cohérente. Il reste évidemment de nombreuses possibilités d'améliorations et d'enrichissements qui pourront faire l'objet de futurs articles. Si vous avez des propositions, n'hésitez pas.


    Ressources

    Tutoriels et FAQ TypeScript

  9. #9
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Je vous présente deux compléments d'importance concernant ce dossier.

    1. J'ai mis à disposition pour les personnes intéressées les sources sur mon compte GitHub. J'ai un peu remanié certains aspects par rapport à la présentation mais l'essentiel est identique.

    2. Une démonstration est disponible en ligne où vous pouvez vous amuser en changeant divers paramètres (y comprit la couleur ).

    Voici une brève description des paramètres
    • Width (px) : largeur de l'univers en pixel.
    • Height (px) : hauteur de l'univers en pixels.
    • Number of Locations : nombre de positions générées.
    • Margin (%) : marge à partir du bord sans aucune position.
    • Gap (%) : distance minimale entre les positions en %.
    • Connection Length (%) : longueur maximale des connexions en %.
    • Background color (RGB) : couleur de fond de l'univers.
    • Location fill color (RGB) : couleur des positions.
    • Location outline color (RGB) : couleur extérieure des positions.
    • Link color (RGB) : couleur des liens.
    Tutoriels et FAQ TypeScript

  10. #10
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 827
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 827
    Points : 218 287
    Points
    218 287
    Billets dans le blog
    117
    Par défaut
    Bonjour,

    J'ai vu à deux reprises un noeud complètement isolé (sans aucun lien). Je doute que ça soit voulu, si ?
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  11. #11
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par LittleWhite Voir le message
    Bonjour,

    J'ai vu à deux reprises un nœud complètement isolé (sans aucun lien). Je doute que ça soit voulu, si ?
    Disons que ce n'est pas forcément voulu mais plutôt un défaut identifié.
    Pour éviter ce cas de figure et plus généralement le problème du risque des composantes non connexes, il faudrait raffiner un peu le code pour détecter les composantes non connexes et les relier au reste du réseau.
    Sans doute une amélioration à apporter ultérieurement. J'avais prévu de toute façon d'aborder d'autres aspects sur cette génération aléatoire d'Univers, j'en profiterai sans doute pour corriger ces défauts.

    Merci pour ton retour
    Tutoriels et FAQ TypeScript

  12. #12
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 072
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 072
    Points : 7 974
    Points
    7 974
    Par défaut
    Bonne idée ce(s) petit(s) tutos. Pour la version en ligne, y'a pas moyen de mettre un Seed (ou de laisser le seed au hasard comme maintenant) afin de garder certains truc en place (pour voir ce que change les parametres sans que tout le monde soit modifé)
    (Les "ça ne marche pas", même écrits sans faute(s), vous porteront discrédit ad vitam æternam et malheur pendant 7 ans)

    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  13. #13
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par wax78 Voir le message
    Bonne idée ce(s) petit(s) tutos. Pour la version en ligne, y'a pas moyen de mettre un Seed (ou de laisser le seed au hasard comme maintenant) afin de garder certains truc en place (pour voir ce que change les parametres sans que tout le monde soit modifé)
    A croire que tu devines mes intentions. J'avais prévu d'aborder prochainement l'utilisation des RNG dans la génération procédurale.
    Tutoriels et FAQ TypeScript

  14. #14
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 072
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 072
    Points : 7 974
    Points
    7 974
    Par défaut
    Ca se sentait peut être, mais c'est le genre de truc qui me plait bien. (Note d'a coté : En tout cas j'ai perdu des heures sur ce satané FTL )
    (Les "ça ne marche pas", même écrits sans faute(s), vous porteront discrédit ad vitam æternam et malheur pendant 7 ans)

    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  15. #15
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par wax78 Voir le message
    Ca se sentait peut être, mais c'est le genre de truc qui me plait bien. (Note d'a coté : En tout cas j'ai perdu des heures sur ce satané FTL )
    La démonstration en ligne a été mise à jour et inclue gère désormais la seed.
    Tutoriels et FAQ TypeScript

  16. #16
    Modérateur
    Avatar de wax78
    Homme Profil pro
    Chef programmeur
    Inscrit en
    Août 2006
    Messages
    4 072
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Belgique

    Informations professionnelles :
    Activité : Chef programmeur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2006
    Messages : 4 072
    Points : 7 974
    Points
    7 974
    Par défaut
    Nickel. Par contre j'ai le truc qui freeze par moment.
    (Les "ça ne marche pas", même écrits sans faute(s), vous porteront discrédit ad vitam æternam et malheur pendant 7 ans)

    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java

  17. #17
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Citation Envoyé par wax78 Voir le message
    Nickel. Par contre j'ai le truc qui freeze par moment.
    C'est possible, notamment si le nombre de locations est important. Je n'ai pas programmé la démo de façon à rendre la main de temps en temps au navigateur pour éviter les freezes, ce qui n'est pas bien si ce devait être une application professionnelle. Mais pour une démonstration, j'espère que personne ne m'en tiendra rigueur.
    Tutoriels et FAQ TypeScript

  18. #18
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    5. Garantir la Connexité

    5.1. Rappels des défauts

    Tel que laissé précédemment, notre générateur d'Univers comportait un défaut assez ennuyeux qui est que certains points, voire groupes de points peuvent se retrouver isolés du reste. Ce problème est causé par la suppression inconditionnelle des connexions trop longues ; suppression cependant nécessaire pour rendre moins régulier le réseau généré par la triangulation de Delaunay et aussi pour corriger certaines anomalies sur les bords de l'univers.


    Exemples d'univers issus du précédent algorithme comportant des anomalies

    5.2. Filtrage conditionnel

    Une manière à priori intéressante de corriger ces défauts serait après une première création des connexions grâce à la triangulation de Delaunay, d'appliquer un filtre qui ne supprimerait une connexion trop longue qu'à condition qu'il reste encore d'autres connexions pour chaque position situé aux extrémités de la connexion supprimée. Ceci afin d'éviter d'isoler une position.
    1) Sélection de la position courante (bleu) 2) Une connexion est trop longue (rouge) 3) Suppression de la connexion trop longue car ses extrémités avaient plus d'une connexion
    4) Sélection de la position courante (bleu) 5) Une connexion est trop longue (rouge) 6) Conservation de la connexion trop longue car l'une de ses extrémités n'avait plus qu'une seule connexion
    Filtrage conditionnel sur le nombre de connexions

    Dans ce cas, dans le corps de notre programme principal, au lieu d'appliquer le filtrage lors de la construction des connexions entre les positions, comme c'était le cas dans la dernière version plus haut, nous reprendrons la version antérieure, à savoir celle sans filtrage moyennant une légère modification :

    Code javascript : 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
    // Creation of positions
    var nbPositions = 400;
    var univers: Position[] = [];
    var vertices: number[][] = [];
    var i = 0;
    var point = new Point(0, 0);
    while (i < nbPositions) {
      point.x = 0.05 + 0.90 * Math.random();
      point.y = 0.05 + 0.90 * Math.random();
     
      if (isValidLocation(point, univers)) {
        univers.push(new Position(point.x, point.y));
        vertices.push([point.x, point.y]);
        i++;
      }
    } // while
     
    // Delaunay Triangulation 
    var triangles = Delaunay.triangulate(vertices);
     
    // Creation of connections
    for (i = 0; i < triangles.length; i += 3) {
      var p0 = univers[triangles[i + 0]];
      var p1 = univers[triangles[i + 1]];
      var p2 = univers[triangles[i + 2]];
      p0.addLink(p1);
      p0.addLink(p2);
      p1.addLink(p2);
    } // for i

    On remarque que la création des connexions qui se faisait avec un empilement basique des positions voisines via la méthode push sur le tableau des connexions (links) a été remplacée par un appel à une méthode nommée addLink que nous spécifierons un peu plus bas dans la classe Position. Cette méthode addLink permet d'ajouter des connexions dans les deux sens, tout en évitant les doublons ce qui était le cas auparavant bien que pouvant passer inaperçu au premier abord.

    C'est sur ce graphe, connexe par construction grâce à la triangulation de Delaunay, que nous pouvons appliquer notre filtre conditionnel en fonction de la longueur et du nombre de connexions.

    Code javascript : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // Conditional Filtering
    for (i = 0; i < univers.length; i++) {
      var position = univers[i];
     
      for (var j = 0; j < position.links.length; j++) {
        var neighbour = position.links[j];
        if (distance(position, neighbour) > 0.068 &&   // connection's length too long
            position.links.length > 1 && neighbour.links.length > 1) { // not enough connections
          position.delLink(neighbour);
          j--;
        }
      } // for j
    } // for i

    La boucle principale balaye l'ensemble des positions de l'univers. Pour chaque position on examine ses connexions dans la boucle secondaire. Pour une connexion donnée, si sa longueur et trop grande et qu'il existe d'autres connexions pour les deux positions aux extrémités de la connexion concernée, on supprime la connexion courante.

    On notera l'appel à une méthode delLink qui permet de supprimer une connexion dans les deux sens.

    Il ne nous reste plus qu'à redéfinir la classe Position enrichie des méthodes addLink et delLink, ainsi que de l'attribut isVisited qui nous servira plus loin.

    Code javascript : 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
    class Position extends Point {
      links: Position[];
      isVisited: boolean;
      // autres attributs...
     
      constructor(x: number, y: number) {
        super(x, y);
        this.links = [];
        this.isVisited = false;
      }
     
      addLink(neighbour: Position) {
        // Check neighbour is not already linked
        for (var i = 0; i < this.links.length; i++) {
          if (this.links[i].x == neighbour.x && this.links[i].y == neighbour.y) {
            return;
          }
        } // for i
     
        this.links.push(neighbour);
        neighbour.links.push(this);
      }
     
      delLink(neighbour: Position) {
        for (var i = 0; i < this.links.length; i++) {
          if (this.links[i].x == neighbour.x && this.links[i].y == neighbour.y) {
            this.links.splice(i, 1);
            neighbour.delLink(this);
            return;
          }
        } // for i
      }
    }

    Comparons le résultat de cet algorithme avec le précédent :

    Exemples d'univers avec filtrage conditionnel sur le nombre de connexion

    La synthèse de ce code est disponible ici : http://typescript.io/DHD9uE670Qg

    Même si cet algorithme permet de préserver la connexité de certaines positions, on constate cependant que dans certains cas de figure, il supprime à l'instar du filtrage inconditionnel des connexions entraînant la perte de la connexité. Par rapport à l'algorithme précédent, ce nouvel algorithme permet d'éviter le cas d'une position totalement isolée mais ne permet pas d'éviter qu'un groupe de positions soit disjoint du reste du graphe.

    Pour résoudre réellement le problème, il faudra en passer par la définition rigoureuse de la notion de connexité.

    5.3. Garantie de connexité

    On dit qu'un graphe est connexe si tous les sommets de ce graphe sont reliés entre eux d'une manière ou d'une autre. Autrement dit, un graphe connexe est un graphe pour lequel pour tout couple de sommets, il existe un chemin, peu importe sa longueur, reliant ces deux sommets.

    Exemple d'un graphe connexe

    Nous avons donc besoin d'un algorithme permettant de tester l'existence d'un chemin entre deux positions. En effet, si on reprend l'algorithme précédent, lors de la suppression des connexions trop longues, au lieu de s'assurer qu'on ne supprime pas la dernière connexion d'une position, nous pouvons tester l'existence d'un chemin entre cette position et une position de référence qu'on désignera l'origine. Si toutes les positions sont reliées à l'origine, alors le graphe est connexe par transitivité.

    Le choix de l'origine est quelconque. Basiquement ce pourrait être la première position générée dans l'univers qui doit dans ce cas être traitée comme un cas particulier.

    Pour s'assurer de la connexité du graphe, nous ne devons pas supprimer une connexion si cela isole la position concernée de l'origine. La partie concernant le filtrage conditionnel des connexions pourrait être réécrite de la façon suivante :

    Code javascript : 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
    // Conditional Filtering
    var origin = univers[0];
     
    // Process the first position as a special case
    origin.links.sort((a: Position, b: Position) => { return distance(origin, b) - distance(origin, a) });
     
    for (var j = 0; j >= origin.links.length; j++) {
      var neighbour = origin.links[j];
      if (distance(origin, neighbour) > 0.068 && origin.links.length > 1) {
        origin.links.splice(j, 1);
        j--;
      }
    } // for j
     
    // Process the other positions
    for (i = 1; i < univers.length; i++) {
      var position = univers[i];
     
      position.links.sort((a: Position, b: Position) => { return distance(position, b) - distance(position, a) });
     
      for (var j = 0; j < position.links.length; j++) {
        var neighbour = position.links[j];
     
        if (distance(position, neighbour) > 0.068) {
          // Backup links
          var placeLinksOld = position.links.slice(0); // clone array (JS specific)
          var neighbourLinksOld = neighbour.links.slice(0); // clone array (JS specific)
     
          // Delete too long connexions
          position.delLink(neighbour);
          j--;
     
          // Restore deleted connexions if connexity is lost
          if (!isPath(univers, position, origin) || !isPath(univers, neighbour, origin)) {
            position.links = placeLinksOld;
            neighbour.links = neighbourLinksOld
            j++;
          }
        }
        else { // No connexion are too long because of sorting
          break; // so we can leave the connexion loop
        }
     
      } // for j
    } // for i

    La principale subtilité dans ce code est le fait qu'on supprime à priori la connexion pour tester ensuite s'il existe toujours un chemin entre les positions à chaque extrémité de la connexion et l'origine. S'il n'existe plus de chemin ce qui implique la perte de la connexité, un retour en arrière est effectué et la connexion supprimée est restaurée.

    Notons le tris des connexions par longueur décroissante afin de ne supprimer en priorité que les connexions les plus longues.

    Le test de l'existence d'un chemin entre deux positions s'effectue à l'aide d'une fonction nommée isPath que nous allons spécifier à présent.

    L'existence d'un chemin entre deux positions se base sur un algorithme de parcours de graphe qui sera ici l'algorithme de parcours en profondeur (Deep First Search). Il existe d'autres algorithmes de parcours comme le parcours en largeur (Breadth First Search) mais le principe reste fondamentalement le même : à partir d'une position de départ, explorer le graphe en suivant les connexions, jusqu'à découvrir la position de destination souhaitée.

    Exemple de parcours en profondeur

    Le parcours en profondeur parcourt un graphe en suivant la topologie d'un arbre et peut se faire de façon récursive, même si nous préfèrerons ici la méthode itérative légèrement plus performante en pratique.

    Code javascript : 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
    function isPath(univers: Position[], start: Position, end: Position): boolean {
      // Set all positions as unvisited
      for (var i = 0; i < univers.length; i++) {
        univers[i].isVisited = false;
      }
     
      // Initialize the working stack
      var stack: Position[] = [];
      stack.push(start);
     
      // Deep First Search
      while (stack.length > 0) {
        var p = stack.pop();
        if (!p.isVisited) {
          p.isVisited = true;
          for (var i = 0; i < p.links.length; i++) {
            var neighbour = p.links[i];
            if (neighbour.x == end.x && neighbour.y == end.y) {
              return true;
            }
            stack.push(neighbour);
          } // for i
        }
      } // while
     
      return false;
    }

    L'intégralité du code de cette nouvelle approche peut être vue ici : http://typescript.io/mz36EFC70Qg

    En terme de résultat, cet algorithme nous permet de régler les défauts de non connexité de certaines positions comme nous pouvons le constater ci-dessous :

    Exemples d'univers générés avec la garantie de connexité

    En traits bleus sont indiqués les connexions préservées par le nombre de connexions (algorithme précédent), tandis qu'en traits verts sont indiqués les connexions uniquement préservées par la garantie de connexité (nouvel algorithme).

    Notre univers ayant désormais la garantie d'être connexe, il est possible de faire varier à volonté la longueur maximale des connexions, y compris à une valeur nulle puisqu'une connexion même si elle est supérieure à la longueur maximale autorisée sera conservée si elle est nécessaire à la préservation de la connexité de l'univers.

    Longueur maximale des connexions à 5%


    Longueur maximale des connexions à 0%

    5.4. Conclusion

    Garantir la connexité d'un graphe généré aléatoirement est loin d'être aussi simple que cela peut en avoir l'air mais nous avons finalement obtenu un univers à la fois visuellement vraisemblable et topologiquement cohérent. Pour cela nous avons dû systématiquement remettre en cause les approches "naïves" pour utiliser les outils de la théorie des graphes.

    La démonstration en ligne, mise à jour, tient en compte de ce nouvel algorithme et apporte des corrections de bugs et quelques nouveautés comme l'attribution de noms aléatoires pour toutes les positions, visibles via infobulle.

    Le code source de cette démonstration en ligne est disponible sur mon compte GitHub.
    Tutoriels et FAQ TypeScript

Discussions similaires

  1. Encore génération aléatoire
    Par sebdu94 dans le forum C
    Réponses: 22
    Dernier message: 21/05/2007, 10h58
  2. Problème de génération aléatoire
    Par sebdu94 dans le forum C
    Réponses: 13
    Dernier message: 19/05/2007, 19h04
  3. [VBA-E] memmory génération aléatoire d'images
    Par jhonnybegood dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 04/03/2007, 22h09
  4. génération aléatoire
    Par acewb00 dans le forum MFC
    Réponses: 1
    Dernier message: 02/12/2005, 10h46
  5. génération aléatoire de couleur claire
    Par jiraiya dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 25/02/2004, 20h52

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