Глосарій алгоритмів

A* (A-Star) Search ↗ Пошук шляху

Евристичний пошук на графі, що знаходить найкоротший шлях, поєднуючи фактичну вартість g(n) з допустимою евристичною оцінкою h(n). Черга з пріоритетами, впорядкована за f(n) = g(n) + h(n). Гарантує оптимальні шляхи, коли евристика ніколи не завищує оцінку.

Agent-Based Model (ABM) — агентна модель

Парадигма симуляції, у якій окремі сутності (агенти) дотримуються локальних правил і взаємодіють із сусідами. Емерджентна макроповедінка виникає із взаємодій на мікрорівні. Поширена в симуляціях натовпу, трафіку, екології та соціальних процесів.

Attractor — атрактор

Набір числових значень, до яких із часом еволюціонує динамічна система. Точкові атрактори стабілізуються на одному значенні; граничні цикли повторюються періодично; дивні атрактори (наприклад, Лоренца) мають фрактальну структуру та чутливу залежність від початкових умов. ↗ Лоренц

Barnes-Hut Algorithm ↗ N-Body

Ієрархічний деревоподібний метод (квадродерево у 2D, октодерево у 3D), що зменшує гравітаційну/електростатичну N-body симуляцію з O(N²) до O(N log N). Віддалені кластери частинок апроксимуються як одне тіло в їхньому центрі мас, коли кут розкриття θ < порогу.

BFS — Breadth-First Search (пошук у ширину) ↗ Пошук шляху

Обхід графа, що досліджує всі вузли на глибині d перед глибиною d+1, використовуючи чергу FIFO. Гарантує найкоротший шлях у незважених графах. Часова складність O(V+E).

Boids ↗ Boids

Алгоритм зграйної поведінки Крейга Рейнольдса 1986 року. Кожен агент дотримується трьох правил: розділення (уникання скупчення), вирівнювання (рух у напрямку середнього курсу), згуртування (рух до середньої позиції). Разом вони створюють природну поведінку зграї. Часто прискорюється просторовою хеш-ґраткою.

Brownian Motion — броунівський рух

Випадкове блукання, де зміщення частинки на кожному кроці береться з гаусового розподілу з дисперсією, пропорційною dt. Моделює молекулярні зіткнення в рідинах. Дискретно: x += randn() * sqrt(2D·dt), де D — коефіцієнт дифузії.

Cellular Automaton (CA) — клітинний автомат ↗ Клітинні автомати

Дискретна модель на ґратці, де наступний стан кожної клітинки залежить від правила локального околу, застосованого одночасно до всіх клітинок. «Гра життя» Конвея використовує окіл Мура 3×3. Елементарні клітинні автомати (1D) використовують 3-клітинні коди Вольфрама. Складні глобальні візерунки виникають із простих локальних правил.

Collision Detection & Response — виявлення та обробка зіткнень ↗ Більярд

Виявлення перекриття між об'єктами (широка фаза: просторовий хеш, BVH; вузька фаза: GJK, SAT) та обчислення імпульсних реакцій. Для пружних сфер: обмін складовими швидкості вздовж нормалі контакту з використанням збереження імпульсу та кінетичної енергії.

Constraint Solving (XPBD) — розв'язання обмежень

eXtended Position-Based Dynamics (розширена динаміка на основі позицій). Ітеративно проектує позиції частинок для задоволення геометричних обмежень (відстань, об'єм, зіткнення). Стійкий до великих кроків часу, безумовно стабільний; застосовується в симуляціях тканини, м'яких тіл і ragdoll. ↗ Тканина

DFS — Depth-First Search (пошук у глибину) ↗ Лабіринт

Обхід графа з використанням стека (або рекурсії), що повністю досліджує одну гілку перед поверненням назад. O(V+E). Застосовується для генерації лабіринтів (рекурсивний backtracking), топологічного сортування, пошуку компонент сильної зв'язності.

Diffusion-Limited Aggregation (DLA) — агрегація, обмежена дифузією

Частинки здійснюють випадкові блукання, доки не торкнуться кластера, що росте, і не прилипнуть. Утворює фрактальні дендритні структури. Розмірність Гаусдорфа кластерів DLA становить ≈ 1.71 у 2D.

Dijkstra's Algorithm — алгоритм Дейкстри ↗ Пошук шляху

Найкоротший шлях з одного джерела на графах із невід'ємними вагами. Використовує чергу з мінімальним пріоритетом; розширює найдешевший невідвіданий вузол. O((V + E) log V) з бінарною купою. A* — це алгоритм Дейкстри з евристикою, що спрямовує пошук до цілі.

Euler Integration — інтегрування Ейлера

Найпростіший явний інтегратор ОДР: x += v·dt, v += a·dt. Точність першого порядку — похибка накопичується O(dt) на крок. Енергія схильна зростати (нестабільний за великих dt). Корисний для швидких чернеток; для точності замініть на Верле або RK4.

Emergence — емерджентність

Явища макрорівня, що виникають із взаємодій на мікрорівні без центрального контролера. Класичні приклади: зграйна поведінка (Boids), формування мурашиних стежок, дорожні затори, свідомість. Ключова тема в теорії складних систем та агентному моделюванні.

Flood Fill — заливка

Обхід графа (BFS або DFS) від початкової клітинки, що зафарбовує всі зв'язані клітинки з однаковим значенням. Застосовується для розв'язання лабіринтів, маркування регіонів рельєфу, інструментів заливки та симуляції повеней. O(N), де N = відвідані клітинки.

Force-Directed Layout — силове розташування

Метод компонування графа, де вузли відштовхуються один від одного (подібно до кулонівського), ребра притягують з'єднані вузли (пружина/закон Гука), а система ітерується до рівноваги з низькою енергією. Barnes-Hut прискорює попарне відштовхування з O(N²) до O(N log N).

Fourier Transform (DFT / FFT) — перетворення Фур'є

Розкладає сигнал на синусоїдальні частотні складові. Швидке перетворення Фур'є (Кулі-Тьюкі) обчислює DFT за O(N log N). Фундаментальне для симуляції хвиль, аналізу звуку, згортки зображень та спектрального рендерингу. ↗ Хвиля

Frustum Culling — відсікання за пірамідою видимості

Оптимізація рендерингу, що відкидає об'єкти, обмежувальні об'єми яких повністю лежать поза пірамідою видимості камери. Перевіряється щодо шести напівплощин (ближня, дальня, ліва, права, верхня, нижня). Three.js робить це автоматично, коли object.frustumCulled = true.

Gerstner Waves — хвилі Ґерстнера ↗ Океан

Трохоїдальна модель хвиль, де точки водної поверхні рухаються по колових орбітах. Кожна хвиля i дає горизонтальне зміщення Q·A·D·sin(k·D·x − ω·t) і вертикальне A·cos(...). Сумування кількох хвиль створює реалістичні брижі відкритого океану. Застосовується на GPU через вершинні шейдери.

Genetic Algorithm (GA) — генетичний алгоритм ↗ Генетичний

Метаевристика, натхненна природним добором. Популяція кандидатів-розв'язків еволюціонує за допомогою відбору (пропорційного до пристосованості), схрещування (рекомбінація генів батьків) та мутації (випадкове збурення). Збігається до оптимальних або близьких до оптимальних розв'язків без інформації про градієнт.

Gray-Scott Model — модель Грея-Скотта ↗ Реакція-дифузія

Реакційно-дифузійна система двох хімічних речовин U і V. U утворюється рівномірно (швидкість подачі f); U+2V→3V (автокаталітично); V вилучається (швидкість знищення k). Варіювання f/k дає плями, смуги, лабіринти, солітони та інші тюрінгоподібні візерунки.

Hash Grid (Spatial Hashing) — хеш-ґратка (просторове хешування)

Відображає 3D-координати світу у плоску хеш-таблицю через hash(cell) = (ix·p1 XOR iy·p2 XOR iz·p3) mod tableSize. Уможливлює запити найближчого сусіда із середнім O(1), замінюючи попарні перевірки O(N²). Застосовується в Boids, SPH та зіткненнях тканини. Потребує перебудови щокадру, якщо частинки рухаються.

Instanced Rendering — інстансований рендеринг

Техніка GPU для відмалювання N копій однієї геометрії за один виклик відмалювання шляхом передавання буферів трансформацій/кольорів для кожного екземпляра. У Three.js: InstancedMesh(geo, mat, count). Незамінна для сцен із тисячами частинок, дерев чи агентів натовпу.

Inverse Kinematics (IK) — обернена кінематика

Обчислює кути суглобів у ланцюзі кісток, щоб розмістити кінцевий ефектор у цільовій позиції. FABRIK (Forward And Backward Reaching IK) чергує прямі та зворотні проходи до збіжності. Не потребує обернення матриці — стійка та швидка для симуляцій у реальному часі. ↗ Механізми

Jacobi Iteration — ітерація Якобі

Ітеративний метод розв'язання лінійних систем Ax = b. Кожна змінна оновлюється паралельно з використанням значень із попередньої ітерації. Застосовується в проекції тиску рідини та розв'язанні обмежень тканини. Збігається для діагонально домінантних матриць; метод Гаусса-Зейделя (послідовне оновлення) збігається швидше, але гірше паралелізується.

k-d Tree (k-dimensional tree) — k-вимірне дерево

BSP-дерево, що рекурсивно розбиває простір, чергуючи осі поділу. Запити найближчого сусіда та пошук за діапазоном у середньому O(log N). Ефективне для статичних хмар точок; просторові хеш-ґратки швидші для динамічних частинок, що рухаються щокадру.

Leapfrog / Störmer-Verlet Integration — інтегрування «чехарда» / Штермера-Верле

Симплектичний інтегратор другого порядку: v_{n+½} = v_{n-½} + a·dt, x_{n+1} = x_n + v_{n+½}·dt. Енергія коливається, але не дрейфує протягом тривалих симуляцій — ідеальний для N-body, орбітальної механіки та молекулярної динаміки. ↗ Орбіта

L-System (Lindenmayer System) — L-система (система Ліндемаєра) ↗ L-системи

Формальна система переписування на основі граматики, що моделює ріст рослин і фрактальну геометрію. Рядок-аксіома багаторазово розгортається продукційними правилами (наприклад, F→FF+[+F-F-F]-[-F+F+F]). Отриманий рядок інтерпретується як команди черепашачої графіки для малювання гілок і листя.

Lorenz System — система Лоренца ↗ Лоренц

Три зв'язані ОДР (dx/dt = σ(y−x), dy/dt = x(ρ−z)−y, dz/dt = xy−βz), вперше досліджені Едвардом Лоренцом у 1963 році. За σ=10, ρ=28, β=8/3 розв'язок є хаотичним — дивний атрактор у формі метелика. Засадничá система теорії хаосу.

Marching Cubes — крокуючі куби

Алгоритм видобування трикутникової сітки зі скалярного поля (ізоповерхні). Кожен куб із 8 вокселів має таблицю пошуку на 256 випадків, що зіставляє комбінації знаків поля з конфігураціями трикутників. Застосовується для рельєфу, поверхні рідини та рендерингу медичних зображень. Оригінальний алгоритм 1987 року має 15 окремих трикутникових шаблонів.

Monte Carlo Methods — методи Монте-Карло

Розв'язують задачі за допомогою випадкової вибірки. У фізичному рендерингу запускають випадкові промені й усереднюють результати для апроксимації глобального освітлення. У симуляціях вибирають з розподілів імовірностей для моделювання стохастичних процесів. Похибка масштабується як 1/√N незалежно від вимірності — перевага над детермінованою квадратурою у високих вимірностях.

N-Body Simulation — симуляція N тіл ↗ N-Body

Обчислення гравітаційних (або кулонівських) сил між усіма N частинками. Наївно: O(N²) пар. Barnes-Hut: O(N log N) з октодеревом. Швидкий мультипольний метод: O(N), але складний. Інтегрування «чехарда» добре зберігає енергію на тривалих часових масштабах.

Noise Functions (Perlin, Simplex) — функції шуму

Когерентні псевдовипадкові функції, що плавно змінюються у просторі/часі. Шум Перліна інтерполює градієнтні вектори на кубічній ґратці. Шум Simplex використовує симпліційну ґратку — менше артефактів і швидше у вищих вимірностях (O(N²) проти O(2^N)). Застосовується для рельєфу, хмар та органічних текстур. ↗ Рельєф

Octree / Quadtree — октодерево / квадродерево

Ієрархічне просторове розбиття. Квадродерева ділять 2D-простір на чотири рівні квадранти; октодерева роблять те саме у 3D. Кожен вузол поділяється, коли містить більше за порогову кількість об'єктів. Підтримує точкові запити O(log N) та діапазонні запити O(k + log N). Базова структура даних у Barnes-Hut та відсіканні за пірамідою видимості.

ODE — Ordinary Differential Equation (звичайне диференціальне рівняння)

Рівняння, що пов'язує функцію з її похідними: dx/dt = f(x,t). Більшість фізичних симуляцій зводиться до системи ОДР. Розв'язується чисельно інтеграторами: Ейлера (1-й порядок), Верле (2-й порядок, симплектичний), RK4 (4-й порядок, загального призначення).

Particle System — система частинок

Велика сукупність дрібних примітивів (квадів, точок, спрайтів), кожен з позицією, швидкістю, часом життя та візуальними властивостями. Породжуються емітером, еволюціонують щокадру й видаляються після «смерті». Застосовуються для вогню, диму, іскор, галактик і дощу. GPU-системи частинок оновлюють трансформації в обчислювальних шейдерах або через transform feedback. ↗ Феєрверк

Ping-Pong Rendering (Double Buffering) — пінг-понг рендеринг (подвійна буферизація)

Техніка для симуляцій, обчислюваних на GPU, де стан зберігається у двох цілях рендерингу (A і B). Щокадру читається з однієї та записується в іншу, потім вони міняються місцями. Уникає одночасного читання та запису однієї текстури. Застосовується в симуляціях реакції-дифузії, рідини та піску на GPU.

Prey-Predator (Lotka-Volterra) — хижак-жертва (Лотки-Вольтерри) ↗ Хижак-жертва

Система двох зв'язаних ОДР: ẋ = αx − βxy (жертви), ẏ = δxy − γy (хижаки). Розв'язки — замкнені періодичні орбіти у фазовому просторі. Розширюються просторовою дифузією або агентними моделями для реалістичнішої динаміки популяцій.

Quaternion — кватерніон

4-компонентне число q = w + xi + yj + zk, що представляє 3D-оберт. Одиничні кватерніони уникають gimbal lock, плавно інтерполюються через SLERP і компонуються множенням. Three.js: new THREE.Quaternion().setFromAxisAngle(axis, angle). Для фізики інтегруйте кутову швидкість як q += 0.5·Ω⊗q·dt.

Reaction-Diffusion — реакція-дифузія ↗ Реакція-дифузія

Система рівнянь у частинних похідних, де дві чи більше речовин дифундують і реагують. Загальна форма: ∂u/∂t = Dᵤ∇²u + f(u,v). Тюрінг (1952) показав, що такі системи можуть спонтанно порушувати симетрію, утворюючи стабільні просторові візерунки. GPU-реалізації використовують пінг-понг текстури з ядром реакції у фрагментному шейдері.

RK4 — Runge-Kutta 4th Order (Рунге-Кутти 4-го порядку)

Класичний явний інтегратор із 4-стадійним зваженим усередненням: k1=f(y,t), k2=f(y+k1·dt/2, t+dt/2), k3=f(y+k2·dt/2, t+dt/2), k4=f(y+k3·dt, t+dt); y += (k1+2k2+2k3+k4)·dt/6. Точність 4-го порядку, 4 обчислення функції на крок. Підходить для системи Лоренца, подвійного маятника та n-body.

SDF — Signed Distance Field (поле знакових відстаней)

Функція sd(p), що повертає відстань від точки p до поверхні фігури — від'ємну всередині, додатну зовні. SDF компонуються через smooth-min (плавне змішування), об'єднання (min), перетин (max), віднімання (max/neg). Застосовуються для ray-marching, виявлення зіткнень та рендерингу шрифтів. ↗ Шаблони GLSL

SIR Model — модель SIR ↗ SIR

Компартментна епідеміологічна модель: сприйнятливі (Susceptible) → інфіковані (Infected) → одужалі (Recovered). ОДР: dS/dt = −βSI, dI/dt = βSI − γI, dR/dt = γI. Базове репродуктивне число R₀ = β/γ. Якщо R₀ > 1, епідемія зростає. Розширені моделі додають експонованих (SEIR), вакцинацію, вікову структуру чи просторове поширення.

SPH — Smoothed Particle Hydrodynamics (згладжена гідродинаміка частинок) ↗ Рідина

Безсітковий лагранжів метод рідини. Властивості рідини інтерполюються сумуванням зважених внесків сусідніх частинок: A(r) = Σ(mⱼ/ρⱼ)·Aⱼ·W(r−rⱼ,h). Згладжувальне ядро W зазвичай є кубічним сплайном. Сили обчислюються з градієнтів густини, тиску (рівняння стану Тейта) та в'язкості.

Spatial Hash Grid — просторова хеш-ґратка

Див. Hash Grid. Ефективний пошук клітинки O(1) для динамічних даних частинок. Перебудовується щокадру шляхом очищення таблиці та повторного вставлення всіх точок.

Symplectic Integration — симплектичне інтегрування

Геометричні інтегратори, що точно зберігають модифікований гамільтоніан (повну енергію). Методи «чехарда»/Верле та Штермера-Верле є симплектичними. Вони обмежують похибку енергії протягом експоненціально довгих часів — критично для орбітальної механіки та молекулярної динаміки, де несимплектичні методи накопичують дрейф.

Travelling Salesman Problem (TSP) — задача комівояжера ↗ TSP

NP-складна комбінаторна оптимізація: знайти найкоротший маршрут, що відвідує всі міста рівно один раз. Точні розв'язки неможливі понад ~20 міст. Поширені евристики: найближчий сусід, локальний пошук 2-opt і 3-opt, Ліна-Кернігана, генетичні алгоритми, оптимізація мурашиними колоніями та імітація відпалу.

Turing Instability — нестійкість Тюрінга

Механізм, за яким просторово однорідний стаціонарний стан дестабілізується дифузією в реакційно-дифузійних системах. Уперше запропонований Аланом Тюрінгом у 1952 році для пояснення морфогенезу (візерунки смуг/плям на шкірі тварин). Потребує активатора (повільна дифузія) та інгібітора (швидка дифузія).

UV Mapping — UV-розгортка

2D-параметризація поверхні 3D-сітки на одиничний квадрат [0,1]². Кожна вершина несе координати (u,v), що індексують текстуру. Three.js надає UV-атрибути для всіх вбудованих геометрій; для власних геометрій задають geometry.setAttribute('uv', ...).

Verlet Integration — інтегрування Верле

Інтегратор на основі позицій: x_{n+1} = 2x_n − x_{n-1} + a·dt². Швидкість неявна (різниця позицій). Простий, точний другого порядку та оборотний у часі. Velocity Verlet зберігає v явно: v_{n+1} = v_n + ½(a_n + a_{n+1})·dt. Стандартний вибір для тканини, м'яких тіл і молекулярної динаміки. ↗ Тканина

Voronoi Diagram — діаграма Вороного

Розбиття площини на клітинки, що визначаються найближчою опорною точкою. Межі клітинок рівновіддалені між двома опорними точками. Обчислюється за O(N log N) алгоритмом замітної прямої Форчуна. Застосовується в тектонічному моделюванні рельєфу, рості біологічних клітин і процедурній генерації текстур. ↗ Тектонічні плити

Wave Equation — хвильове рівняння ↗ Хвиля

Гіперболічне рівняння в частинних похідних другого порядку: ∂²u/∂t² = c²∇²u. Дискретизується як u(x,t+dt) = 2u(x,t) − u(x,t−dt) + c²·dt²·Δu з використанням скінченних різниць. Число Куранта c·dt/dx має бути ≤ 1 для числової стабільності (умова CFL).