Existe-t-il une (famille de) fonction (s) de bruit monotone non décroissante?

J'aimerais qu'une fonction anime un objet se déplaçant d'un point A à un point B au fil du temps, de sorte qu'il atteigne B à un moment fixe, mais sa position à tout moment est perturbée de manière aléatoire et continue, mais ne recule jamais. Les objets se déplacent le long de lignes droites, donc je n'ai besoin que d'une dimension.

Mathématiquement, cela signifie que je recherche des f (x), x ∈ [0,1] continus, tels que:

• f (0) = 0
• f (1) = 1
• x <y → f (x) ≤ f (y)
• En «la plupart» des points f (x + d) - f (x) n'a pas de relation évidente avec d. (La fonction n'est pas uniformément croissante ou autrement prévisible; je pense que cela équivaut également à dire qu'aucun degré de dérivée n'est une constante.)

Idéalement, je voudrais en fait un moyen d'avoir une famille de ces fonctions, fournissant un certain état de départ. J'aurais besoin d'au moins 4 bits de graine (16 fonctions possibles), pour mon utilisation actuelle, mais comme ce n'est pas beaucoup, n'hésitez pas à en fournir encore plus.

Pour éviter divers problèmes d'erreurs d'accumulation, je préférerais que la fonction ne nécessite aucun type d'état interne. C'est-à-dire que je veux que ce soit une vraie fonction, pas une "fonction" de programmation.

Pour ce post, y = f (t) où t est le paramètre que vous modifiez (temps / progression) et y est la distance à atteindre. Je vais donc parler en termes de points sur des tracés 2D où l'axe horizontal est le temps / progrès et la verticale est la distance.

Je pense que vous pouvez faire une courbe de Bézier cubique avec le premier point à (0, 1) et le quatrième (dernier) point à (1, 0). Les deux points médians peuvent être placés au hasard (x = rand, y = rand) dans ce rectangle 1 par 1. Je ne peux pas vérifier cela analytiquement, mais juste en jouant avec une applet (ouais, allez-y et riez), il semble que la courbe de Bézier ne diminuera jamais avec une telle contrainte.

Ce sera votre fonction élémentaire b (p1, p2) qui fournit un chemin non décroissant du point p1 au point p2.

Vous pouvez maintenant générer ab (p (1) = (0, 1), p (n) = (1, 0)) et choisir un certain nombre de p (i) le long de cette courbe de telle sorte que 1

Essentiellement, vous générez un chemin "général", puis vous le divisez en segments et régénérez chaque segment.

Puisque vous voulez une fonction mathématique: Supposons que la procédure ci-dessus soit regroupée dans une fonction y = f (t, s) qui vous donne la distance à t pour la fonction de la graine s. Tu auras besoin de:

• 4 nombres aléatoires pour placer les 2 points médians de la spline de Bézier principale (de (0, 1) à (1, 0))
• n-1 nombres pour les limites de chaque segment si vous avez n segments (le premier segment commence toujours à (0, 1) c'est-à-dire t = 0 et le dernier se termine à (1,0) c'est-à-dire t = 1)
• 1 numéro si vous voulez randomiser le nombre de segments
• 4 numéros supplémentaires pour placer les points médians de la spline du segment auquel votre t atterrit

Ainsi, chaque graine doit fournir l'un des éléments suivants:

• 7 + n nombres réels compris entre 0 et 1 (si vous souhaitez contrôler le nombre de segments)
• 7 nombres réels et un entier supérieur à 1 (pour un nombre aléatoire de segments)

J'imagine que vous pouvez accomplir l'un ou l'autre de ces éléments en fournissant simplement un tableau de nombres comme graines de départ. Alternativement, vous pouvez faire quelque chose comme fournir un nombre s comme graine, puis appeler le générateur de nombres aléatoires intégré avec rand (s), rand (s + 1), rand (s + 2) et ainsi de suite (ou initialiser avec s, puis continuez d'appeler rand.NextNumber).

Notez que même si la fonction entière f (t, s) est composée de plusieurs segments, vous n'évaluez qu'un segment pour chaque t. Vous aurez besoin de calculer de façon répétée les limites des segments avec cette méthode, car vous devrez les trier pour se assurer qu'aucun deux segments se chevauchent. Vous pouvez probablement optimiser et vous débarrasser de ce travail supplémentaire et ne trouver que les points de terminaison d'un segment pour chaque appel, mais ce n'est pas évident pour moi en ce moment.

De plus, les courbes de Bézier ne sont pas nécessaires, toute spline ayant un comportement approprié fera l'affaire.

J'ai créé un exemple d'implémentation Matlab.

La fonction de Bézier (vectorisée):

function p = bezier(t, points)
% p = bezier(t, points) takes 4 2-dimensional points defined by 2-by-4 matrix
% points and gives the value of the Bezier curve between these points at t.
% 
% t can be a number or 1-by-n vector. p will be an n-by-2 matrix.
    coeffs = [
        (1-t').^3, ...
        3*(1-t').^2.*t', ...
        3*(1-t').*t'.^2, ...
        t'.^3
    ];

    p = coeffs * points;
end

La fonction composée de Bézier décrite ci-dessus (laissée délibérément non vectorisée pour indiquer clairement combien d'évaluation est nécessaire pour chaque appel):

function p = bezier_compound(t, ends, s)
% p = bezier(t, points) takes 2 2-dimensional endpoints defined by a 2-by-2
% matrix ends and gives the value of a "compound" Bezier curve between
% these points at t.
% 
% t can be a number or 1-by-n vector. s must be a 1-by-7+m vector of random
% numbers from 0 to 1. p will be an n-by-2 matrix. 
    %% Generate a list of segment boundaries
    seg_bounds = [0, sort(s(9:end)), 1];

    %% Find which segment t falls on
    seg = find(seg_bounds(1:end-1)<=t, 1, 'last');

    %% Find the points that segment boundaries evaluate to
    points(1, :) = ends(1, :);
    points(2, :) = [s(1), s(2)];
    points(3, :) = [s(3), s(4)];
    points(4, :) = ends(2, :);

    p1 = bezier(seg_bounds(seg), points);
    p4 = bezier(seg_bounds(seg+1), points);

    %% Random middle points
    p2 = [s(5), s(6)] .* (p4-p1) + p1;
    p3 = [s(7), s(8)] .* (p4-p1) + p1;

    %% Gather together these points
    p_seg = [p1; p2; p3; p4];

    %% Find what part of this segment t falls on
    t_seg = (t-seg_bounds(seg))/(seg_bounds(seg+1)-seg_bounds(seg));

    %% Evaluate
    p = bezier(t_seg, p_seg);    
end

Le script qui trace la fonction pour une graine aléatoire (notez que c'est le seul endroit où une fonction aléatoire est appelée, les variables aléatoires vers tous les autres codes sont propagées à partir de ce seul tableau aléatoire):

clear
clc

% How many samples of the function to plot (higher = higher resolution)
points = 1000;

ends = [
    0, 0;
    1, 1;
    ];

% a row vector of 12 random points
r = rand(1, 12);

p = zeros(points, 2);

for i=0:points-1
    t = i/points;
    p(i+1, :) = bezier_compound(t, ends, r);
end

% We take a 1-p to invert along y-axis here because it was easier to
% implement a function for slowly moving away from a point towards another.
scatter(p(:, 1), 1-p(:, 2), '.');
xlabel('Time');
ylabel('Distance to target');

Voici un exemple de sortie:

Il semble répondre à la plupart de vos critères. Toutefois:

• Il y a des "coins". Cela peut être possible en utilisant les courbes de Bézier de manière plus appropriée.
• Il ressemble "évidemment" à des splines, bien que vous ne puissiez pas vraiment deviner ce qu'il fera après une période de temps non triviale à moins que vous ne connaissiez la graine.
• Il s'écarte très rarement trop vers le coin (peut être corrigé en jouant avec la distribution du générateur de graines).
• La fonction cubique de Bézier ne peut pas atteindre une zone proche du coin étant donné ces contraintes.

Je suppose qu'au lieu de mélanger un tas de cosinus transformés (comme les produits scalaires dans le bruit Perlin), vous pouvez mélanger plusieurs fonctions monotones qui commencent à f (0) = 0, comme f (x) = x, ou 2x, ou x ^ 2, etc. En fait, puisque votre domaine est limité à 0 => 1, vous pouvez également mélanger des fonctions trigonométriques qui correspondent à la facture dans ce domaine comme cos (90 * x + 270). Pour normaliser vos méthodes pour finir à 1, vous pouvez simplement diviser la somme pondérée de ces méthodes monotones à partir de f (0) = 0 par f (1). Quelque chose comme ça devrait également être assez facile à inverser (ce que je suppose que vous voulez du peu sur les fonctions réelles sans état par rapport aux fonctions de programmation).

J'espère que cela t'aides.

On peut analyser cette image brute. Vous pouvez vous retrouver avec une fonction qui exécute votre animation à la volée, en utilisant une fonction Rand uniforme. Je sais que ce n'est pas la formule mathématique exacte, mais il n'y a en fait aucune formule mathématique pour une fonction aléatoire, et même s'il y en avait une, vous coderiez beaucoup pour y parvenir. Étant donné que vous n'avez spécifié aucune condition de douceur, le profil de vitesse est continu $ C ^ 0 $ (mais comme vous ne traitez pas avec des robots, pas besoin de vous soucier des profils d'accélération discontinus).

La façon habituelle de générer une séquence croissante de N nombres aléatoires à partir de [0,1] est de générer N nombres aléatoires dans n'importe quelle plage, puis de les diviser tous par leur somme totale, puis de les additionner un par un pour obtenir le séquence.

Générez la séquence 2, 2, 5, 8, 6.
Leur somme est 23, donc nos chiffres à additionner sont 2/23, 2/23, 5/23, 8/23 et 6/23.
Notre séquence finale est le 2/23, 4/23, 9/23, 17/23, 23/23

Cela peut être étendu à 2D en générant ces valeurs pour X et Y. Vous pouvez augmenter N pour obtenir la granularité souhaitée.

Dans la réponse similaire de @ teodron, vous avez cité des problèmes d'efficacité à grande échelle de temps. Sans connaître le problème réel auquel vous êtes confronté, je ne peux pas dire si cette préoccupation est valable; mais une autre option serait de générer pour le petit N, et de simplement lisser le résultat. Selon l'application, cela peut en fait donner de meilleurs résultats.

N = 100, pas de lissage

N = 15, avec lissage

Je suggère cette implémentation inspirée de la somme des octaves trouvées dans le bruit fractal, avec un peu de cul bon marché ici et là. Je pense qu'il est raisonnablement rapide et peut être réglé en demandant moins d'octaves que stockées dans les paramètres avec une perte de précision d'environ 1/2^octave.

Vous pouvez le voir comme une implémentation par morceaux qui ne nécessite que du temps O (log (pieces)) . Le tableau de paramètres est utilisé à la fois pour la position de pivot diviser pour mieux régner et pour la distance parcourue en atteignant le pivot.

template<int N> struct Trajectory
{
    Trajectory(int seed = 0)
    {
        /* The behaviour can be tuned by changing 0.2 and 0.6 below. */
        if (seed)
            srand(seed);
        for (int i = 0; i < N; i++)
            m_params[i] = 0.2 + 0.6 * (double)(rand() % 4096) / 4096;
    }

    double Get(double t, int depth = N)
    {
        double min = 0.0, max = 1.0;
        for (int i = 0, dir = 0; i < N && i < depth; i++)
        {
            int j = (dir + 1 + i) % N;
            double mid = min + (max - min) * m_params[j];
            if (t < m_params[i])
            {
                dir += 1;
                t = t / m_params[i];
                max = mid;
            }
            else
            {
                dir ^= i;
                t = (t - m_params[i]) / (1.0 - m_params[i]);
                min = mid;
            }
        }
        t = (3.0 - 2.0 * t) * t * t; // Optional smoothing
        return min + (max - min) * t;
    }

    double m_params[N];
};

Il pourrait être rendu plus rapide en pré-calculant les divisions en virgule flottante, au prix de stocker trois fois plus d'informations.

Voici un exemple rapide:

L'exemple a été obtenu avec le code suivant:

for (int run = 0; run < 5; run++)
{
    /* Create a new shuffled trajectory */
    Trajectory<12> traj;

    /* Print dots */
    for (double t = 0; t <= 1.0; t += 0.0001)
        printf("%g %g\n", t, traj.Get(t));
}

Penser à haute voix et admettre le calcul n'est pas mon point fort ... n'est-ce pas possible? Pour éviter tout schéma évident, la moyenne de la fonction de bruit sur tout changement de x doit être proche de zéro, et pour garantir la monotonie, l'amplitude du bruit sur ce changement de x doit être plus petite que le changement de x, comme toute amplitude plus grande pourrait se traduisent par une valeur inférieure à x 'par rapport à x. Mais cela signifierait que lorsque vous réduisez dx vers 0, une telle fonction doit également réduire dA (où A est l'amplitude) vers zéro, ce qui signifie que vous n'obtenez aucune contribution d'une fonction de bruit conforme.

Je peux imaginer qu'il soit possible de formuler une fonction qui diminue progressivement la contribution au bruit lorsque x approche 1, mais cela vous donnera une fonction courbe qui décélère lorsque x approche 1, ce qui n'est pas ce que je pense que vous voulez.