Algorithme pour générer des arêtes et des sommets vers l'extérieur à partir de l'origine avec une multiplicité maximale de 3

Je crée un jeu 2D pour un site Web où l'univers peut devenir extrêmement grand (essentiellement infiniment grand). Initialement, l'univers est composé de 6 étoiles qui sont à égale distance de l'origine (0, 0). Ma tâche est de pouvoir générer plus d'étoiles qui auront des "chemins" (bords) qui se connecteront les uns aux autres. Comment puis-je concevoir un algorithme qui respecte ces restrictions:

1. Les étoiles sont générées au hasard vers l'extérieur. (par exemple, les coordonnées (x, y) pour les nouvelles étoiles sortiront lentement de (0, 0) dans toutes les directions, de préférence en format spirale)
2. Les bords ne se croiseront PAS.
3. Bien qu'il devrait y avoir une certaine variance, les nouvelles étoiles ne devraient pas être trop éloignées ou trop proches des autres étoiles. (Par exemple, il doit y avoir un rayon minimum)
4. Aucune étoile / point ne doit avoir une multiplicité supérieure à 3.
5. Étant donné que tout cela sera stocké dans une base de données, l'algorithme ne peut pas être trop coûteux. En d'autres termes, j'aimerais réaliser quelque chose de complexité O (n) (je ne sais pas si c'est faisable).

Essentiellement, ce que je veux, c'est une galaxie en spirale où les étoiles sont des points sur le graphique et le voyage entre les étoiles est représenté par les bords entre ces étoiles.

Les étapes particulières que je dois résoudre sont les suivantes:

1. Génère aléatoirement un point dans le voisinage voisin d'autres étoiles qui n'ont pas encore une multiplicité de 3.
2. Trouvez la première étoile qui n'a pas encore une multiplicité de 3 qui ne générera pas de conflit de bord.
3. Si l'étoile est à une distance minimale de x unités, créez un bord entre les deux points.

J'ai essayé de chercher des solutions, mais mes compétences en mathématiques (et mes connaissances sur la théorie des graphes) nécessitent beaucoup de travail. De plus, toute ressource / lien sur ce sujet serait grandement apprécié.

Voici un pseudo-code auquel je pensais, mais je ne sais pas si cela fonctionnerait même et je suis sûr qu'il ne fonctionnerait pas terriblement bien après quelques 10 000, etc. étoiles.

newStar = randomly generated (x, y) within radius of last star from origin
while(newStar has not been connected):
    for (star in the known universe):
        if(distance between newStar and star > x units):
            if(star has < 3 multiplicity):
                if(path from newStar to star does not intersect another path):
                    connect the star to the other star
                    break;

    newStar = new random (x, y) coordinate

De plus, si quelqu'un a des conseils sur la façon de stocker cela sur une base de données MySQL, je l'apprécierais également.

Enfin, au cas où rien n'aurait de sens ci-dessus, j'ai inclus une image de ce que j'aimerais réaliser ci-dessous:

Suggestion: Gardez le réseau de l'univers interne parfaitement ordonné, algorithmique et relativement simple. Vous avez seulement besoin que l'univers ait l'air aléatoire lorsqu'il est affiché sur l'écran de l'utilisateur . Appliquez uniquement des décalages aléatoires aux positions des étoiles pour l'affichage par l'utilisateur.

Problème: L'approche la plus évidente du calcul d'un décalage aléatoire pour chaque étoile ne fera pas un très bon travail pour cacher la vraie structure sous-jacente. Vous ne pouvez randomiser les étoiles que légèrement avant qu'elles ne se heurtent ou ne se croisent.

Solution: vous pouvez appliquer de grandes distorsions aléatoires et obtenir un univers beaucoup plus aléatoire et intéressant si vous appliquez un caractère aléatoire non local coordonné. Imaginez que vous placez les étoiles sur une feuille de caoutchouc et imaginez étirer et écraser au hasard différentes parties de la feuille. Cela peut déplacer un groupe entier d'étoiles sur une longue distance. Ils ne se heurteront ou ne se croiseront jamais parce que les étoiles proches s'étirent et écrasent les unes par rapport aux autres.

Comment faire: recherchez des générateurs de terrain fractal. Il y a beaucoup de code libre et ouvert pour cela. Vous avez seulement besoin d'un code de base qui génère une valeur de hauteur pour chaque point sur une carte. Nous allons l'utiliser d'une manière différente. Utilisez ce code pour générer DEUX cartes indépendantes de la hauteur du terrain. Commencez par la véritable position X, Y de l'étoile, regardez cet emplacement sur chaque carte, utilisez une valeur de carte pour décaler la position d'affichage X de l'étoile et utilisez l'autre valeur de carte pour décaler la position d'affichage Y de l'étoile. Vous devrez jouer avec certains des facteurs d'échelle, mais cela peut vous donner l'effet de feuille de caoutchouc déformé au hasard. Les grandes variations de position des étoiles devraient masquer complètement les positions ordonnées sous-jacentes. La nature fractale du caractère aléatoire donnera un effet très naturel,