Мы симулируем гравитационное взаимодействие 100 частиц в 2D-пространстве, используя алгоритм N-Body с оптимизацией Барнса-Хат!

Симуляция галактики:

cpp

#include <avr/random.h>
#include <avr/pgmspace.h>

#define PARTICLE_COUNT 64
#define GRAVITY 10
#define SOFTENING 2
#define TIME_STEP 1

// Структура частицы
struct Particle {
    int16_t x;
    int16_t y;
    int16_t vx;
    int16_t vy;
    int16_t mass;
};

Particle particles[PARTICLE_COUNT];

// Квадродерево (для оптимизации Barnes-Hut)
struct QuadNode {
    int16_t x, y;           // Центр масс
    int16_t mass;           // Суммарная масса
    int16_t minX, maxX;     // Границы
    int16_t minY, maxY;
    uint8_t childCount;
    QuadNode* children[4];  // Используем индексы вместо указателей
};

QuadNode nodes[PARTICLE_COUNT * 4];
uint8_t nodeCount = 0;

// Строим квадродерево
void buildQuadTree(uint8_t nodeIdx, uint8_t* particleList, uint8_t count) {
    QuadNode* node = &nodes[nodeIdx];
    
    // Вычисляем границы
    int16_t minX = 32767, maxX = -32768;
    int16_t minY = 32767, maxY = -32768;
    int32_t totalMass = 0;
    int32_t cx = 0, cy = 0;
    
    for (uint8_t i = 0; i < count; i++) {
        Particle* p = &particles[particleList[i]];
        if (p->x < minX) minX = p->x;
        if (p->x > maxX) maxX = p->x;
        if (p->y < minY) minY = p->y;
        if (p->y > maxY) maxY = p->y;
        totalMass += p->mass;
        cx += p->x * p->mass;
        cy += p->y * p->mass;
    }
    
    node->minX = minX;
    node->maxX = maxX;
    node->minY = minY;
    node->maxY = maxY;
    node->mass = totalMass;
    node->x = cx / totalMass;
    node->y = cy / totalMass;
    
    // Если в узле одна частица или маленький размер - останавливаемся
    if (count <= 1 || (maxX - minX < 5 && maxY - minY < 5)) {
        node->childCount = 0;
        return;
    }
    
    // Разбиваем на 4 подузла
    int16_t midX = (minX + maxX) / 2;
    int16_t midY = (minY + maxY) / 2;
    
    uint8_t childLists[4][PARTICLE_COUNT];
    uint8_t childCounts[4] = {0, 0, 0, 0};
    
    for (uint8_t i = 0; i < count; i++) {
        Particle* p = &particles[particleList[i]];
        uint8_t quadrant = 0;
        if (p->x > midX) quadrant |= 1;
        if (p->y > midY) quadrant |= 2;
        childLists[quadrant][childCounts[quadrant]++] = particleList[i];
    }
    
    // Создаем дочерние узлы
    for (uint8_t i = 0; i < 4; i++) {
        if (childCounts[i] > 0) {
            node->children[i] = &nodes[nodeCount++];
            buildQuadTree(nodeCount - 1, childLists[i], childCounts[i]);
            node->childCount++;
        } else {
            node->children[i] = NULL;
        }
    }
}

// Вычисление силы (алгоритм Барнса-Хат)
void computeGravity(uint8_t particleIdx, uint8_t nodeIdx) {
    Particle* p = &particles[particleIdx];
    QuadNode* node = &nodes[nodeIdx];
    
    // Если это лист или частица достаточно далеко
    int16_t dx = node->x - p->x;
    int16_t dy = node->y - p->y;
    int16_t dist2 = dx * dx + dy * dy + SOFTENING;
    
    if (node->childCount == 0 || 
        (node->maxX - node->minX) * (node->maxX - node->minX) < dist2) {
        // Вычисляем силу как от одной большой массы
        int16_t invDist = 1 / sqrt(dist2);
        int16_t force = node->mass * invDist;
        
        p->vx += dx * force / 1000;
        p->vy += dy * force / 1000;
    } else {
        // Рекурсивно проходим по детям
        for (uint8_t i = 0; i < 4; i++) {
            if (node->children[i] != NULL) {
                computeGravity(particleIdx, node->children[i] - nodes);
            }
        }
    }
}

// Инициализация галактики
void initGalaxy() {
    for (uint8_t i = 0; i < PARTICLE_COUNT; i++) {
        // Спиральная галактика
        float angle = random(0, 360) * 3.14159 / 180;
        float radius = random(0, 100) * random(0, 100) / 100;
        particles[i].x = radius * cos(angle);
        particles[i].y = radius * sin(angle);
        particles[i].vx = -radius * sin(angle) * 0.1;
        particles[i].vy = radius * cos(angle) * 0.1;
        particles[i].mass = random(10, 100);
    }
}

// Симуляция галактики
void simulateGalaxy() {
    // Строим квадродерево
    nodeCount = 0;
    uint8_t allParticles[PARTICLE_COUNT];
    for (uint8_t i = 0; i < PARTICLE_COUNT; i++) {
        allParticles[i] = i;
    }
    buildQuadTree(nodeCount++, allParticles, PARTICLE_COUNT);
    
    // Вычисляем силы
    for (uint8_t i = 0; i < PARTICLE_COUNT; i++) {
        computeGravity(i, 0);
    }
    
    // Обновляем позиции
    for (uint8_t i = 0; i < PARTICLE_COUNT; i++) {
        particles[i].x += particles[i].vx * TIME_STEP / 1000;
        particles[i].y += particles[i].vy * TIME_STEP / 1000;
    }
}

// Отрисовка галактики на OLED
void renderGalaxy() {
    // Очищаем экран
    clearScreen();
    
    for (uint8_t i = 0; i < PARTICLE_COUNT; i++) {
        uint8_t screenX = 64 + particles[i].x / 4;
        uint8_t screenY = 32 + particles[i].y / 4;
        if (screenX < 128 && screenY < 64) {
            drawPixel(screenX, screenY, 1);
        }
    }
    
    updateDisplay();
}

void setup() {
    initGalaxy();
    initOLED();
}

void loop() {
    for (uint8_t i = 0; i < 10; i++) {
        simulateGalaxy();
    }
    renderGalaxy();
    delay(50);
}