Jak wygenerować efekt błyskawicy?

Czy istnieje algorytm generujący błyskawicę?

Chciałbym algorytm, który generuje listę obiektów segmentów lub punktów określających, gdzie wyląduje śruba. Metoda wymagałaby parametru punktu początkowego wraz z punktem końcowym. Pocisk powinien mieć z niego losowe gałęzie i zygzakiem w losowych odstępach czasu. Rezultatem będzie losowy efekt błyskawicy, który wyglądałby mniej więcej tak

_{(źródło: wikimedia.org )}

Jeśli ktoś zna algorytm, dla którego może to działać, pomoc byłaby bardzo mile widziana!

Istnieje dość prosty algorytm, którego można użyć do wygenerowania piorunów.

Zacznij od odcinka linii między początkiem śruby ( O) a punktem końcowym (E )

Wybierz punkt na tej linii (w przybliżeniu lub dokładnie na środku), wywołany Si podziel segment na dwa segmenty linii ( O->Si S->E). WypieraćS się od oryginalnego odcinka linii (wraz normalny segmentu) przez jakiś niewielkiej ilości losowej. To daje ci jeden „zakręt” błyskawicy.

Po obliczeniu zgięcia, na podstawie małej przypadkowej szansy, będziesz chciał dodać segment trzeciego wiersza (zwykle przedłużenie tego O->Ssegmentu). W ten sposób produkujesz „widelce” w błyskawicy. Zazwyczaj będziesz chciał śledzić informacje o intensywności śruby podczas procesu generowania, ponieważ chcesz, aby widelce były ciemniejsze lub miały bardziej subtelne rozmycie:

Następnie powtórz powyższy proces dla wszystkich nowych segmentów linii; musisz wybrać liczbę powtórzeń, która daje kształty, które lubisz:

Jest dość jasne wyjaśnienie tej techniki na blogu mojego przyjaciela tutaj ( tutaj bezwstydnie ukradłem zdjęcia); idzie jeszcze głębiej o dodanie efektu blasku.

Na koniec jest też ten artykuł NVIDIA, który opisuje ten sam podstawowy algorytm (również z dodatkowymi szczegółami).

Poleciłbym alternatywne podejście: szybko eksplorujące losowe drzewo (RRT) . Jedną fajną rzeczą jest to, że możesz ominąć zakręty lub eksplodować we wszystkich kierunkach.

Algorytm jest naprawdę prosty:

// Returns a random tree containing the start and the goal.
// Grows the tree for a maximum number of iterations.
Tree RRT(Node start, Node goal, int maxIters)
{
    // Initialize a tree with a root as the start node.
    Tree t = new Tree();
    t.Root = start;


    bool reachedGoal = false;
    int iter = 0;

    // Keep growing the tree until it contains the goal and we've
    // grown for the required number of iterations.
    while (!reachedGoal || iter < maxIters)
    {
         // Get a random node somewhere near the goal
         Node random = RandomSample(goal);
         // Get the closest node in the tree to the sample.
         Node closest = t.GetClosestNode(random);
         // Create a new node between the closest node and the sample.
         Node extension = ExtendToward(closest, random);
         // If we managed to create a new node, add it to the tree.
         if (extension)
         {
             closest.AddChild(extension);

             // If we haven't yet reached the goal, and the new node
             // is very near the goal, add the goal to the tree.
             if(!reachedGoal && extension.IsNear(goal))
             {
                extension.AddChild(goal);
                reachedGoal = true;
             }
         }
         iter++;
    }
    return t;
}

Modyfikując funkcje RandomSamplei ExtendToward, możesz uzyskać bardzo różne drzewa. Jeśli RandomSamplewszędzie jednolicie próbki, drzewo będzie rosło równomiernie we wszystkich kierunkach. Jeśli jest tendencyjny do celu, drzewo będzie miało tendencję do wzrostu w kierunku celu. Jeśli zawsze próbkuje bramkę, drzewo będzie od początku do linii prostej.

ExtendTowardpozwala także robić interesujące rzeczy na drzewie. Po pierwsze, jeśli masz przeszkody (takie jak ściany), możesz sprawić, aby drzewo rosło wokół nich po prostu odrzucając rozszerzenia kolidujące ze ścianami.

Oto, jak to wygląda, gdy nie przesądzasz próbkowania w kierunku celu:

_{(źródło: uiuc.edu )}

A oto jak to wygląda ze ścianami

Kilka fajnych właściwości RRT po jego zakończeniu:

• RRT nigdy się nie przekroczy
• RRT ostatecznie obejmie całą przestrzeń coraz mniejszymi gałęziami
• Ścieżka od początku do celu może być całkowicie losowa i dziwna.