Devlog #89 – Wave 68: Barnes-Hut, Marching Squares, Próbkowanie Poissona, Nierówność Bella, Obwód Chua i Tłum Pieszych

Nowe Symulacje

N-ciał Barnes-Hut: Grawitacja w Drzewie Czwórkowym

Bezpośrednia grawitacja N-ciał jest piękna, ale brutalna: każda cząstka musi oddziaływać z każdą inną, co daje O(n²) ewaluacji siły na krok czasowy — n(n−1)/2 par dla n=2000 to niemal 2 miliony obliczeń na klatkę przy 60 fps. Barnes-Hut redukuje to do O(n log n), używając rekurencyjnego drzewa czwórkowego (ósemkowego w 3D).

Kryterium θ

Każdy węzeł wewnętrzny przechowuje całkowitą masę i środek masy wszystkich zawartych cząstek. Przy obliczaniu siły na cząstkę, zamiast wchodzić rekurencyjnie w węzeł, zastępujesz go jego agregatem, jeśli stosunek s/d spełnia warunek s² < θ²d² — gdzie s to długość boku węzła, a d to odległość od cząstki do środka masy węzła. Mniejsze θ oznacza większą dokładność, ale więcej ewaluacji; θ = 0,5 to standardowy kompromis.

Całkowanie Velocity-Verlet

Pozycje i prędkości są przesuwane schematem velocity-Verlet: x(t+dt) = x(t) + v(t)dt + ½a(t)dt², następnie siły są ponownie ewaluowane, a na końcu v(t+dt) = v(t) + ½(a(t)+a(t+dt))dt. To integrator symplektyczny — zachowuje cieniowy hamiltonian, zapobiegając sztucznemu dryfowi energii przy długich przebiegach. Drzewo jest przebudowywane co klatkę, ponieważ cząstki poruszają się nieprzerwanie.

• 4 presety: chmura gaussowska, kolizja dwóch galaktyk, pierścień + masa centralna, atraktor centralny + chmura
• Kliknij dowolną cząstkę, by podświetlić jej ścieżkę rozkładu w drzewie czwórkowym
• Żywy licznik: ewaluacje BH wobec naiwnego n(n−1)/2
• Suwak N do 2000 cząstek

Marching Squares: Tabela Odniesień Izokonturów

Marching Squares wydobywa izokontury z 2D pola skalarnego, przetwarzając każdą komórkę siatki niezależnie. Każda komórka ma cztery rogi — każdy albo powyżej, albo poniżej wartości izo — co daje 2⁴ = 16 odrębnych przypadków topologicznych.

Tabela 16 Przypadków i Interpolacja Liniowa

Wstępnie obliczona tabela odniesień mapuje 4-bitową maskę bitową rogów na pary przecięć krawędzi. Dla każdej aktywnej krawędzi przecięcie jest umieszczane za pomocą interpolacji liniowej: t = (iso − v₀) / (v₁ − v₀) wzdłuż krawędzi, dając gładkie kontury zamiast poszarpanych granic pikseli.

Dezambiguacja Punktów Siodłowych

Przypadki 5 i 10 są niejednoznaczne — łączność diagonalna jest niezdefiniowana. Symulacja rozwiązuje to, próbkując bilinearną wartość centralną: jeśli centrum jest powyżej progu, kontur łączy się jednym sposobem; poniżej — drugim. Zapobiega to artefaktom topologicznym, jak fantomowe rozłączenia w polach metabali.

• Cztery pola skalarne: metabale (suma 1/(r²+ε)), szum fBm (6 oktaw), animowany sinus, malowalny przez użytkownika
• Konturowanie wielopoziomowe: rysuj do 8 jednoczesnych wartości izo o odrębnych kolorach
• Nakładka mapy cieplnej bilinearnej pokazuje surowe pole pod konturami

Próbkowanie Dysków Poissona: Algorytm Bridsona

Próbkowanie dysków Poissona produkuje zbiory punktów, w których żadne dwa punkty nie są bliżej niż minimalna odległość r, jednocześnie wypełniając przestrzeń możliwie gęsto. Rezultatem jest „niebieski szum" — widmo mocy płaskie w zakresie średnich częstotliwości, co czyni je percepcyjnie idealnym do ditheringu, kropkowania i generowania terenu.

Siatka Tła O(n)

Algorytm Bridsona z 2007 roku osiąga O(n) (liniowo względem rozmiaru wyjścia) dzięki siatce tła o rozmiarze komórki r/√2. Każda komórka przechowuje co najwyżej jedną próbkę; wyszukiwania sąsiadów wymagają sprawdzenia tylko stałego okna 5×5. Lista aktywna rośnie, gdy każda zaakceptowana próbka generuje do k=30 kandydackich prób pierścieniowych w zakresie [r, 2r].

Weryfikacja Niebieskiego Szumu

Widmo mocy radialnej zbioru próbek jest pokazane obok próbkowania losowego jednorodnego i regularnej siatki. Dyski Poissona wykazują charakterystyczne płaskie plateau w zakresie średnim — to definiująca właściwość niebieskiego szumu, wskazująca brak niskoczęstotliwościowego zbijania się i wysokoczęstotliwościowego aliasingu.

• Animuj generowanie krok po kroku lub uzupełnij wsadowo natychmiast
• Dostosuj minimalny promień r od 8 do 40 pikseli
• Do ~2000 próbek na canvasie 800×600
• Przełącz nakładkę widma mocy radialnej dla porównania jakości szumu

Nierówność Bella: Korelacje Kwantowe Przekraczają Granice Klasyczne

Twierdzenie Johna Bella z 1964 roku dowiodło, że żadna lokalna teoria zmiennych ukrytych nie może odtworzyć wszystkich przewidywań mechaniki kwantowej. Nierówność CHSH (Clausera-Horne'a-Shimony'ego-Holta) czyni to eksperymentalnie testowalnym: zmierz kombinację S = |E(a,b) − E(a,b') + E(a',b) + E(a',b')|.

Granice Kwantowe vs Klasyczne

Dla stanu singletowego |ψ⁻⟩ = (|01⟩ − |10⟩)/√2 kwantowa funkcja korelacji to E(a,b) = −cos(a − b). Przy optymalnych kątach pomiaru a=0°, a'=45°, b=22,5°, b'=67,5° daje to S = 2√2 ≈ 2,828 — granicę Tsirelsona, maksimum dozwolone przez mechanikę kwantową. Każdy klasyczny model zmiennych ukrytych jest ograniczony do |S| ≤ 2.

Żywy Eksperyment

Symulacja próbkuje losowe wartości λ dla modelu klasycznego oraz kwantowe losowe rotacje dla modelu kwantowego. Obie wartości S są śledzone przez N prób i zbiegają do swoich teoretycznych granic w miarę wzrostu N, wizualnie demonstrując lukę, której żaden model klasyczny nie może pokonać.

• Suwak do zmiany kątów pomiaru i obserwowania zmian S w czasie rzeczywistym
• Histogram iloczynów par E = A·B akumuluje się w czasie prób
• Klasyczna i kwantowa wartość S wyświetlane ze średnią kroczącą

Obwód Chua: Najprostszy Obwód Chaotyczny

Obwód Leona Chua z 1983 roku to kanoniczne laboratorium elektronicznego chaosu. Produkuje atraktor dziwny podwójnej spirali — dwie splecione spirale w przestrzeni fazowej — z zaledwie trzech elementów pasywnych i jednego nieliniowego rezystora (diody Chua).

ODE i Dioda Chua

Dynamiką rządzą trzy sprzężone ODE:

dV_C1/dt = (1/C1) · [G(V_C2 − V_C1) − f(V_C1)]
dV_C2/dt = (1/C2) · [G(V_C1 − V_C2) + I_L]
dI_L/dt  = −(1/L) · V_C2

gdzie f(V) to przedziałami liniowa charakterystyka I-V diody Chua: f(V) = m₁V + ½(m₀−m₁)(|V+1|−|V−1|). Symulacja całkuje metodą RK4 ze stałym krokiem czasowym, renderując trajektorie bezpośrednio na canvas.

Wykładnik Lapunowa i Bifurkacja

Największy wykładnik Lapunowa λ₁ jest estymowany metodą dwóch trajektorii Benettina: druga trajektoria startuje z nieskończenie małym przesunięciem, a jej logarytmiczna dywergencja jest uśredniana i okresowo renormalizowana. λ₁ > 0 potwierdza chaos. Gdy parametr C1 jest przemiatany, symulacja pokazuje sekwencję okres-1 → okres-2 → okres-4 → chaos (kaskada podwajania okresu).

• Portrety fazowe: płaszczyzna (V_C1, V_C2) i płaszczyzna (V_C1, I_L) obok siebie
• Odczyt wykładnika Lapunowa w czasie rzeczywistym
• Suwak przemiatania parametru do obserwacji podwajania okresu

Tłum Pieszych: Model Siły Społecznej

Model siły społecznej Helbinga-Molnara (1995) traktuje ruch pieszych jako dynamikę newtonowską z siłami psychospołecznymi. Każdy agent ma pożądaną prędkość w stronę celu i doświadcza odpychania od innych pieszych i ścian.

Składowe Siły

Całkowita siła na agenta i to suma trzech wyrazów:

• Motywacja: F_motywacja = m·(v₀·ê − v) / τ — napędza agenta w kierunku pożądanej prędkości v₀ w pożądanym kierunku ê z czasem relaksacji τ
• Odpychanie społeczne: wykładniczy zanik A·exp((r_ij − d_ij)/B)·n̂_ij — miękkie odpychanie z korektą twardego rdzenia kontaktu, gdy agenci się nakładają
• Odpychanie od ściany: ta sama forma wykładnicza zastosowana do najbliższego punktu ściany

Zjawiska Emergentne

Magia modelu siły społecznej polega na tym, co wyłania się bez jawnych reguł. W dwukierunkowym korytarzu przeciwne strumienie samoistnie segregują się w stabilne pasy — minimalizując czołowe spotkania. Przy wąskim gardle powstaje łuk wywołany ciśnieniem u wyjścia, uwalniający się okresowo w falach. W trybie paniki podniesienie pożądanej prędkości (efekt „szybciej znaczy wolniej") zmniejsza przepustowość, ponieważ łukowanie staje się poważniejsze, a agenci blokują się nawzajem mocniej.

• Do 200 pieszych; siatka haszowania przestrzennego dla zapytań sąsiedzkich O(n)
• Trzy presety scenariuszy: korytarz, wąskie gardło, otwarte pomieszczenie
• Przełącz tryb paniki, by zademonstrować „szybciej znaczy wolniej"
• Licznik przepływu: agentów na sekundę przez wyjście

Co Dalej

Wave 69 przynosi algorytmy otoczki wypukłej (skan Grahama vs marsz Jarvisa vs Quickhull porównane obok siebie), kwantowe wyszukiwanie Grovera z geometryczną wizualizacją amplitudy, dynamikę meandrowania rzeki z formowaniem jezior starorzeczy, fizykę liny Verlet, klasyczny perceptron Rosenblatta oraz rezonans orbitalny Keplera z grupowaniem koniunkcji.