Modifier les fonctions de distribution aléatoire :: Rendre moins susceptible d'obtenir plusieurs valeurs similaires dans une séquence

Je veux générer une séquence de nombres pour générer des planètes procédurales dans un secteur de galaxie. Chaque planète doit être placée au hasard, mais il est très peu probable que deux planètes soient directement l'une à côté de l'autre. Comment puis-je y parvenir?

Je sais que vous pouvez modifier les chances en appliquant une fonction de distribution, mais comment puis-je les contrôler afin de rendre des valeurs spécifiques plus / moins probables?

Si vous connaissez la distribution souhaitée, vous pouvez utiliser l' échantillonnage de rejet .

Manière la plus simple: dans le graphique ci-dessus, choisissez des points au hasard jusqu'à ce que vous en trouviez un sous la courbe. Ensuite, utilisez simplement la xcoordonnée.

Pour la distribution réelle, il existe différentes approches plausibles. Par exemple, pour le numéro de planète ià l'emplacement pet certains paramètres de force k(par exemple 0.5), définissez une fonction f_i(x)=abs(p-x)^k, puis utilisez la fonction de distribution g(x)=f_1(x)*f_2(x)*...*f_n(x).

En pratique, calculez et stockez les résultats de g(x)to array t( t[x]=g(x)); rappelez-vous hégalement la valeur la plus élevée . Choisissez une position aléatoire xdans t, choisissez une valeur aléatoire yentre 0et h, répétez if y>t[x]; sinon la valeur de retour est x.

Je ne suis pas sûr que le problème soit complètement spécifié par la question, mais je peux fournir quelques idées simples, la seconde d'entre elles fournira des chiffres à peu près conformes à ce que votre photo indique que vous voulez.

Quoi qu'il en soit, comme vous pouvez le constater, la fonction de distribution change après chaque nombre généré et possède une mémoire (c'est-à-dire: elle n'est pas markovienne ) et l'une ou l'autre de ces méthodes peut s'avérer impraticable lorsque la «mémoire» (nombre de nombres précédemment tirés) devient très grand.

1. Simple:
   Générez un nombre aléatoire à partir d'une distribution plate, comparez avec les nombres précédemment tirés, répétez si 'trop près'

2. Cette réponse ressemble plus à votre figure (en supposant que nous voulons tirer de 0..1):

   • créer une nouvelle liste ordonnée, insérer 0 et 1
   • générer un nombre aléatoire à partir d'une fonction de distribution plate: N_0
     • ajouter ce numéro à la liste
   • au prochain appel, tirez un autre numéro N_1,
   • si N_1> N_0
     • dessinez un nouveau nombre aléatoire gaussien avec une moyenne = 1 et un écart-type o de tout ce que vous voulez, un nombre plus petit (par rapport à 1-N_1) gardera les nombres aléatoires plus espacés. Cela ne garantira pas une distance minimale entre les tirages, mais votre figure ne semble pas non plus.
   • cas opposé de N_1 <N_0 traité de la même manière
   • lors des tirages suivants, continuez de générer un nombre aléatoire (N_i) à partir d'une distribution plate
   • parcourez votre liste pour voir de quels deux nombres précédemment tirés le nouveau nombre se situe entre (N_-, N_ +)
   • créer un nouveau nombre aléatoire gaussien avec moyenne (N_- + N _ +) / 2
   • ajoutez le numéro de distribution plat (N_i) à votre liste (liste ordonnée)

Les corbeilles de point de terminaison sont un cas spécial, mais elles devraient être assez simples pour que vous puissiez voir comment les gérer.

Pensez à la différence entre 1 dé et 3 dés . 1 dé vous donne une probabilité égale pour toutes les valeurs, tandis que 3 dés auront tendance à avoir une probabilité plus élevée pour les valeurs vers le milieu.

Plus il y a de "dés" dans votre équation, plus vous avez de chances d'obtenir quelque chose vers le centre. Définissons donc une fonction qui peut gérer n'importe quel nombre uniformément :

// Takes a random number between floor and ceil
// pow defines how strongly these results should gravitate towards the middle
// We also define a function TrueRand(floor, ceil) elsewhere where you should substitute your own random function
int CenterRandom(int floor, int ceil, int pow = 3)
{
    if(ceil == floor)
        return ceil; // don't care to compare

    int total = 0;
    for(int x = 0; x < pow; x++)
    {
       total += TrueRand(floor, ceil);
    }
    return total / pow;
}

Maintenant, nous pouvons définir un exemple de fonction à utiliser:

// Distribues a number of points between floor and ceil
// We assume a function PlotPoint(int) exists to aid in creating the planet, etc...
void DistributePoints(int floor, int ceil, int numPoints)
{
    // Could easily output this in the function parameters, but language wasn't specified
    int[numPoints] breaks;
    int numBreaks = 0;

    // Special case for first pair
    breaks[0] = CenterRandom(floor, ceil);
    numBreaks++;

    for(int x = 0; x < numPoints - 1; x++)
    {
        // Generate a random number linearly, this will be used for picking
        // This way we have a greater chance of choosing a random value between larger pairs
        int picker = TrueRandom(floor, ceil);

        // Now we first find the pair of points that our picker exists on
        // For simplicity, we handle the first and last pair separately

        if(picker >= floor && picker < breaks[0])
        {
            breaks[x] = CenterRandom(floor, breaks[0] - 1);
        }
        for(int i = 0; i < numBreaks; i++)
        {
            if(picker > breaks[i] && picker < breaks[i+1])
            {
                breaks[x] = CenterRandom(breaks[i] + 1, breaks[i+1] - 1);
            }
        }
        if(picker > breaks[numBreaks] && picker <= ceil)
        {
            breaks[x] = CenterRandom(breaks[numBreaks] + 1, ceil);
        }

        PlotPoint(breaks[x]); // Plot the point
    }
}

Maintenant, le premier à noter est que ce code ne vérifie vraiment pas si le sélecteur correspond déjà à l'un des points. Si c'est le cas, cela ne générera tout simplement pas de point, peut-être quelque chose que vous aimeriez.

Pour expliquer ce qui se passe ici, CenterRandom génère une sorte de courbe en cloche. Cette fonction décompose l'avion en plusieurs courbes en cloche, une par paire de points existants. Le sélecteur nous indique à partir de quelle courbe de cloche générer. Étant donné que nous choisissons linéairement, nous pouvons nous assurer que les paires avec des écarts plus importants entre elles seront choisies plus souvent, mais nous laissons tout de même complètement aléatoire.

J'espère que ça vous indique la bonne direction.

Je sais que vous posez des questions sur une séquence de positions aléatoires, mais si vous n'êtes pas limité à la génération séquentielle de l'ensemble, il existe une autre approche: générer un ensemble de points qui a l'espacement souhaité.

Ce que je pense que vous voulez, c'est un ensemble de planètes qui sont raisonnablement espacées avec un certain hasard. Au lieu de générer des positions de planète avec un générateur de nombres aléatoires, générez un espacement de planète avec un générateur de nombres aléatoires. Cela vous permettra de contrôler directement la distribution de l'espacement, en utilisant un générateur de nombres aléatoires qui sélectionne cette distribution. C'est simple en 1 dimension.

En 2 dimensions, j'ai vu des approches qui génèrent du «bruit bleu» mais je ne sais pas comment générer un espacement avec une distribution arbitraire. Cet article couvre l'approche standard «essayez de le placer et de le rejeter s'il est trop proche», mais vous pouvez les générer tous en même temps, avec une solution «plus douce» en plaçant tous vos points, puis en utilisant Lloyd Relaxation pour déplacer toutes les planètes vers plus positions souhaitables. Cela éloignera les planètes trop proches. Les tuiles Wang récursives sont une autre approche qui pourrait être utile. Ce papierétend le problème à la génération de planètes avec une densité et d'autres objets comme des astéroïdes avec une autre densité. Vous pourriez également être en mesure de générer du bruit bleu en utilisant la série de Fourier; Je ne suis pas sûr. L'approche de la série de Fourier vous permettrait également d'utiliser des distributions arbitraires au lieu du seul bruit bleu.