Brute-Force Broad Phase

Overview

This lab builds a small SFML project that measures how expensive collision detection gets as the number of moving objects grows. Working across a Ball class and a bruteForcePairs function, you will represent each moving object as a small struct with just enough state to bounce around a window, write a function that checks every ball against every other ball exactly once, and wire the result into a live SFML window that reports how many candidate pairs were found and how long the check took each frame. By the end, clicking to add balls or pressing a key to add fifty at once visibly drives both the reported pair count and the per-frame timing upward, and the connecting lines drawn between every candidate pair make the sheer number of comparisons something you can see rather than only read as a number.

Learning Objectives

By the end of this lab you will be able to:

• Explain what broad-phase collision detection is and why checking every possible pair of objects is the simplest, but most expensive, way to find them
• Implement a Ball struct that stores enough state to move and bounce inside a window without performing any collision detection itself
• Implement bruteForcePairs so it returns exactly one pair for every combination of two balls, using a nested loop that never revisits a pair or checks a ball against itself
• Measure and report the number of candidate pairs and the time a broad-phase pass takes, and relate the growth in both to the O(n^2) shape of the algorithm as ball count increases

Concept

A game with many moving objects cannot afford to test every object against every other object for a precise, expensive collision check every frame. Broad phase collision detection exists to answer a cheaper, earlier question first: which pairs of objects are even worth checking closely? Objects that pass the broad-phase test become candidate pairs, and only those pairs go on to a more expensive precise check. The simplest possible broad phase does no filtering at all: it treats every single pair of objects as a candidate, which is exactly what makes it the brute-force approach and the baseline every smarter broad-phase structure is measured against.

Generating every pair exactly once, with no repeats and no pair of an object with itself, is a nested loop where the inner loop always starts one position ahead of the outer loop. For an outer index i running from 0 to n-1, the inner index j runs from i + 1 to n-1, so (i, j) is produced but (j, i) never is, and i is never paired with itself. Counting how many pairs that produces reveals the cost. For n objects, the total pair count is n * (n - 1) / 2, a quantity that grows with the square of n. Doubling the number of objects roughly quadruples the number of pairs, which is what the phrase O(n^2) describes: the work grows proportionally to n squared, not to n itself.

The function that does this pairing takes a std::vector<Ball> and returns a std::vector of pairs, using std::pair<const Ball*, const Ball*> so each entry points back at the two balls involved rather than copying them. Timing the function itself, separately from any rendering, uses std::chrono::high_resolution_clock::now() before and after the call, with the difference converted to microseconds through std::chrono::duration<double, std::micro>.

Tasks

#pragma once
#include <SFML/Graphics.hpp>

class Ball {
public:
    Ball(sf::Vector2f pos, sf::Vector2f vel, float r, sf::Color col)
        : position(pos), velocity(vel), radius(r), colour(col) {}

    void update(float deltaTime, float worldWidth, float worldHeight) {
        // TODO: advance position by velocity * deltaTime, then bounce off
        // each edge of the world by clamping position back inside it and
        // flipping the matching component of velocity
    }

    void draw(sf::RenderWindow& window) const {
        sf::CircleShape shape(radius);
        shape.setOrigin(sf::Vector2f(radius, radius));
        shape.setPosition(position);
        shape.setFillColor(colour);
        window.draw(shape);
    }

    sf::Vector2f position;
    sf::Vector2f velocity;
    float radius;
    sf::Color colour;
};

#pragma once
#include <vector>
#include <utility>
#include "Ball.h"

inline std::vector<std::pair<const Ball*, const Ball*>> bruteForcePairs(const std::vector<Ball>& balls) {
    std::vector<std::pair<const Ball*, const Ball*>> pairs;

    // TODO: loop i from 0 to balls.size() - 1, and inside that loop j from
    // i + 1 to balls.size() - 1, adding a pair of pointers (&balls[i],
    // &balls[j]) to pairs for every (i, j) combination

    return pairs;
}

#include <SFML/Graphics.hpp>
#include <vector>
#include <random>
#include "Ball.h"
#include "BruteForce.h"

namespace {
    constexpr unsigned int WORLD_WIDTH = 800;
    constexpr unsigned int WORLD_HEIGHT = 800;
    constexpr std::size_t DEFAULT_BALL_COUNT = 30;

    std::mt19937 rng(std::random_device{}());

    Ball makeRandomBall(float worldWidth, float worldHeight) {
        std::uniform_real_distribution<float> posX(20.0f, worldWidth - 20.0f);
        std::uniform_real_distribution<float> posY(20.0f, worldHeight - 20.0f);
        std::uniform_real_distribution<float> vel(-120.0f, 120.0f);
        std::uniform_real_distribution<float> radiusDist(4.0f, 10.0f);
        std::uniform_int_distribution<int> colourDist(100, 255);

        return Ball(
            sf::Vector2f(posX(rng), posY(rng)),
            sf::Vector2f(vel(rng), vel(rng)),
            radiusDist(rng),
            sf::Color(colourDist(rng), colourDist(rng), colourDist(rng)));
    }
}

int main() {
    sf::VideoMode videoMode(sf::Vector2u(WORLD_WIDTH, WORLD_HEIGHT));
    sf::RenderWindow window(videoMode, "Brute-Force Broad Phase");
    window.setFramerateLimit(60);

    std::vector<Ball> balls;
    for (std::size_t i = 0; i < DEFAULT_BALL_COUNT; ++i) {
        balls.push_back(makeRandomBall(static_cast<float>(WORLD_WIDTH), static_cast<float>(WORLD_HEIGHT)));
    }

    sf::Clock clock;

    while (window.isOpen()) {
        float deltaTime = clock.restart().asSeconds();

        while (const std::optional event = window.pollEvent()) {
            if (event->is<sf::Event::Closed>()) {
                window.close();
            }
        }

        // TODO: call ball.update(deltaTime, WORLD_WIDTH, WORLD_HEIGHT) for
        // every ball in balls

        // The pair count and timing are added in the next task.

        window.clear(sf::Color(12, 12, 18));

        for (const auto& ball : balls) {
            ball.draw(window);
        }

        window.display();
    }

    return 0;
}

while (window.isOpen()) {
    float deltaTime = clock.restart().asSeconds();

    while (const std::optional event = window.pollEvent()) {
        if (event->is<sf::Event::Closed>()) {
            window.close();
        }
    }

    // Ball updates (Task 3, already solved).
    for (auto& ball : balls) {
        ball.update(deltaTime, static_cast<float>(WORLD_WIDTH), static_cast<float>(WORLD_HEIGHT));
    }

    // TODO: time a call to bruteForcePairs(balls) using
    // std::chrono::high_resolution_clock, convert the elapsed time to
    // microseconds, then build and draw an sf::Text reporting balls.size(),
    // the pair count, and the microsecond timing

    window.clear(sf::Color(12, 12, 18));

    for (const auto& ball : balls) {
        ball.draw(window);
    }

    window.display();
}

window.clear(sf::Color(12, 12, 18));

for (const auto& ball : balls) {
    ball.draw(window);
}

// TODO: loop over pairs and draw a two-point sf::Vertex line between
// pairs[i].first->position and pairs[i].second->position for every pair,
// using sf::PrimitiveType::Lines and a soft translucent colour

window.display();

while (const std::optional event = window.pollEvent()) {
    if (event->is<sf::Event::Closed>()) {
        window.close();
    }

    // TODO: check for an sf::Event::KeyPressed event with getIf, and when
    // keyPressed->scancode is sf::Keyboard::Scancode::A, push fifty new
    // balls from makeRandomBall onto balls
}