Collision detection comparison with Python and C++

In 2014 I wrote a post about mixing Python with C. At the end I said I wanted to try a comparison to show that, generally, algorithms trump language. The comparison was to have a 'game' where a lot of boxes fly around the screen and if they hit each other or the screen edge, they reverse their direction. We'd see how far we can push a C (now, I'm going to use C++) version of such a program and how far we can push a Python version, each using the same/different collision detection algorithms.

I enlisted ChatGPT to help me with this. I'm quite impressed.

First I asked it: "Can you write a simple C++ program that uses SDL2 to make a bunch of simple boxes fly around the screen? If they collide with the edge of the screen they should react naturally"

Here is the result:

#include <SDL2/SDL.h>

#include <vector>

#include <cstdlib>



const int SCREEN_WIDTH = 800;

const int SCREEN_HEIGHT = 600;

const int BOX_SIZE = 20;



struct Box {

    float x, y;

    float dx, dy;



    Box(float x, float y, float dx, float dy) 

        : x(x), y(y), dx(dx), dy(dy) {}

};



void update(Box& box) {

    box.x += box.dx;

    box.y += box.dy;



    if(box.x < 0 || box.x + BOX_SIZE > SCREEN_WIDTH) box.dx *= -1;

    if(box.y < 0 || box.y + BOX_SIZE > SCREEN_HEIGHT) box.dy *= -1;

}



void draw(SDL_Renderer* renderer, const Box& box) {

    SDL_Rect rect = { (int)box.x, (int)box.y, BOX_SIZE, BOX_SIZE };

    SDL_SetRenderDrawColor(renderer, 255, 0, 0, 255);

    SDL_RenderFillRect(renderer, &rect);

}



int main(int argc, char* args[]) {

    SDL_Init(SDL_INIT_VIDEO);



    SDL_Window* window = SDL_CreateWindow("Bouncing Boxes", 

        SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 

        SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN);



    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);



    std::vector<Box> boxes;

    for(int i = 0; i < 100; ++i) {

        float x = rand() % SCREEN_WIDTH;

        float y = rand() % SCREEN_HEIGHT;

        float dx = ((rand() % 11) - 5) / 5.0f;

        float dy = ((rand() % 11) - 5) / 5.0f;

        boxes.push_back(Box(x, y, dx, dy));

    }



    bool running = true;

    SDL_Event e;

    while(running) {

        while(SDL_PollEvent(&e)) {

            if(e.type == SDL_QUIT) {

                running = false;

            }

        }



        SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);

        SDL_RenderClear(renderer);



        for(auto& box : boxes) {

            update(box);

            draw(renderer, box);

        }



        SDL_RenderPresent(renderer);

    }



    SDL_DestroyRenderer(renderer);

    SDL_DestroyWindow(window);

    SDL_Quit();



    return 0;

}

It also included the helpful note on compiling: "Compile this program with a command like `g++ -std=c++11 -lSDL2 main.cpp -o main`."

And guess what, it works without modification. I don't like its style of not having a space before the opening paren in non-function keywords like for and if, but whatever, I'm not going to tell it to change right now.

Ok, let's add the collision detection with each box:

"Can you add a function that uses an explicitly slow O(N^2) collision detection nested loop for each box to check if it's going to collide with another box and reverse direction + change color if so?"

#include <SDL2/SDL.h>

#include <vector>

#include <cstdlib>



const int SCREEN_WIDTH = 800;

const int SCREEN_HEIGHT = 600;

const int BOX_SIZE = 20;



struct Box {

    float x, y;

    float dx, dy;

    int r, g, b;



    Box(float x, float y, float dx, float dy, int r, int g, int b) 

        : x(x), y(y), dx(dx), dy(dy), r(r), g(g), b(b) {}

};



bool willCollide(const Box& a, const Box& b) {

    // Predict the positions of the boxes in the next frame

    float ax = a.x + a.dx;

    float ay = a.y + a.dy;

    float bx = b.x + b.dx;

    float by = b.y + b.dy;



    // Check for a collision in the next frame

    return ax < bx + BOX_SIZE && ax + BOX_SIZE > bx && ay < by + BOX_SIZE && ay + BOX_SIZE > by;

}



void update(std::vector<Box>& boxes) {

    for(auto& box : boxes) {

        box.x += box.dx;

        box.y += box.dy;



        if(box.x < 0 || box.x + BOX_SIZE > SCREEN_WIDTH) box.dx *= -1;

        if(box.y < 0 || box.y + BOX_SIZE > SCREEN_HEIGHT) box.dy *= -1;

    }



    // O(N^2) collision detection

    for(int i = 0; i < boxes.size(); ++i) {

        for(int j = i + 1; j < boxes.size(); ++j) {

            if(willCollide(boxes[i], boxes[j])) {

                boxes[i].dx *= -1;

                boxes[i].dy *= -1;

                boxes[j].dx *= -1;

                boxes[j].dy *= -1;



                // Change color on collision

                boxes[i].r = rand() % 256;

                boxes[i].g = rand() % 256;

                boxes[i].b = rand() % 256;

                boxes[j].r = rand() % 256;

                boxes[j].g = rand() % 256;

                boxes[j].b = rand() % 256;

            }

        }

    }

}



void draw(SDL_Renderer* renderer, const Box& box) {

    SDL_Rect rect = { (int)box.x, (int)box.y, BOX_SIZE, BOX_SIZE };

    SDL_SetRenderDrawColor(renderer, box.r, box.g, box.b, 255);

    SDL_RenderFillRect(renderer, &rect);

}



int main(int argc, char* args[]) {

    SDL_Init(SDL_INIT_VIDEO);



    SDL_Window* window = SDL_CreateWindow("Bouncing Boxes", 

        SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 

        SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN);



    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);



    std::vector<Box> boxes;

    for(int i = 0; i < 100; ++i) {

        float x = rand() % SCREEN_WIDTH;

        float y = rand() % SCREEN_HEIGHT;

        float dx = ((rand() % 11) - 5) / 5.0f;

        float dy = ((rand() % 11) - 5) / 5.0f;

        int r = rand() % 256;

        int g = rand() % 256;

        int b = rand() % 256;

        boxes.push_back(Box(x, y, dx, dy, r, g, b));

    }



    bool running = true;

    SDL_Event e;

    while(running) {

        while(SDL_PollEvent(&e)) {

            if(e.type == SDL_QUIT) {

                running = false;

            }

        }



        SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);

        SDL_RenderClear(renderer);



        update(boxes);



        for(const auto& box : boxes) {

            draw(renderer, box);

        }



        SDL_RenderPresent(renderer);

    }



    SDL_DestroyRenderer(renderer);

    SDL_DestroyWindow(window);

    SDL_Quit();



    return 0;

}

Excellent. I asked for even more:

"Can you add a snippet to the main loop that prints out the average frame rate every so often?"

It replied with just the main function rewritten. It added a bit of code before the while running line, followed by a bit code after the RenderPresent line:

    int frameCount = 0;

    int startTime = SDL_GetTicks();

    int currentTime = startTime;

...

        frameCount++;



        // Calculate and print average framerate every second

        int elapsedMilliseconds = SDL_GetTicks() - currentTime;

        if(elapsedMilliseconds > 1000) {

            float elapsedSeconds = elapsedMilliseconds / 1000.0f; // convert ms to s

            float fps = frameCount / elapsedSeconds;

            printf("Average Frames Per Second: %.2f\n", fps);



            frameCount = 0;

            currentTime = SDL_GetTicks();

        }

I manually added an N_BOXES constant to replace the 100 in its for loop.

On my machine (I have a very powerful machine) I get around 12,700 average FPS with 100 boxes. I have to bump that to 10,000 boxes to drag down to 1.67 FPS.

"Now can you rewrite the whole program in Python using pygame?"

import pygame

import random



# Constants

SCREEN_WIDTH = 800

SCREEN_HEIGHT = 600

BOX_SIZE = 20

BOX_COUNT = 100



class Box:

    def __init__(self):

        self.x = random.randint(0, SCREEN_WIDTH)

        self.y = random.randint(0, SCREEN_HEIGHT)

        self.dx = random.randint(-5, 5)

        self.dy = random.randint(-5, 5)

        self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



    def update(self, boxes):

        self.x += self.dx

        self.y += self.dy



        if self.x < 0 or self.x + BOX_SIZE > SCREEN_WIDTH:

            self.dx *= -1

            self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))

        

        if self.y < 0 or self.y + BOX_SIZE > SCREEN_HEIGHT:

            self.dy *= -1

            self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



        # O(N^2) collision detection

        for box in boxes:

            if self != box and self.x < box.x + BOX_SIZE and self.x + BOX_SIZE > box.x and self.y < box.y + BOX_SIZE and self.y + BOX_SIZE > box.y:

                self.dx *= -1

                self.dy *= -1

                self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))

                box.dx *= -1

                box.dy *= -1

                box.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



    def draw(self, screen):

        pygame.draw.rect(screen, self.color, pygame.Rect(self.x, self.y, BOX_SIZE, BOX_SIZE))



def main():

    pygame.init()

    screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

    clock = pygame.time.Clock()



    boxes = [Box() for _ in range(BOX_COUNT)]

    frame_count = 0

    start_time = pygame.time.get_ticks()



    running = True

    while running:

        for event in pygame.event.get():

            if event.type == pygame.QUIT:

                running = False



        screen.fill((0, 0, 0))



        for box in boxes:

            box.update(boxes)

            box.draw(screen)



        pygame.display.flip()

        frame_count += 1



        # Calculate and print average framerate every second

        elapsed_milliseconds = pygame.time.get_ticks() - start_time

        if elapsed_milliseconds > 1000:

            fps = frame_count / (elapsed_milliseconds / 1000)

            print("Average Frames Per Second: {:.2f}".format(fps))



            frame_count = 0

            start_time = pygame.time.get_ticks()



        clock.tick()



    pygame.quit()



if __name__ == "__main__":

    main()

It did add a 60 to the tick() function to cap the frame rate, so I manually edited that out but otherwise once again it just works. For 100 boxes I get a respectable ~530 FPS, but that's a lot less than C++'s 12,700. At 1000 boxes we're already at 12 FPS and at 10,000 boxes we're at 0.13 FPS.

Now I asked ChatGPT to modify it again: "Now can you rewrite the python code to use a simple sweep and prune O(N) type of collision algorithm?"

Here's its full response:

The Sweep and Prune algorithm is a computationally efficient method for performing collision detection on multiple objects in a simulation. The basic concept behind the algorithm is to order the objects according to their positions along an axis and then test for collisions between neighbouring objects.

We will define a list of end points which represent the start and end of each box along the x-axis. We will keep this list sorted and update it every frame. While updating, if we find a start point that has an end point behind it in the list, then there is a possible collision. We can then check for collision on the y-axis. This method greatly reduces the number of checks necessary.

Here's how you can modify the Python program to use the Sweep and Prune algorithm:

import pygame

import random



# Constants

SCREEN_WIDTH = 800

SCREEN_HEIGHT = 600

BOX_SIZE = 20

BOX_COUNT = 100



class Box:

    def __init__(self, id):

        self.id = id

        self.x = random.randint(0, SCREEN_WIDTH)

        self.y = random.randint(0, SCREEN_HEIGHT)

        self.dx = random.randint(-5, 5)

        self.dy = random.randint(-5, 5)

        self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



    def update(self):

        self.x += self.dx

        self.y += self.dy



        if self.x < 0 or self.x + BOX_SIZE > SCREEN_WIDTH:

            self.dx *= -1

            self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))

        

        if self.y < 0 or self.y + BOX_SIZE > SCREEN_HEIGHT:

            self.dy *= -1

            self.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



    def draw(self, screen):

        pygame.draw.rect(screen, self.color, pygame.Rect(self.x, self.y, BOX_SIZE, BOX_SIZE))



# Sweep and Prune collision detection

def sweep_and_prune(boxes):

    endpoints = sorted([(box.x, box.id, True) for box in boxes] + [(box.x + BOX_SIZE, box.id, False) for box in boxes])



    active = set()

    for point, id, is_start in endpoints:

        if is_start:

            for active_id in active:

                box1 = boxes[id]

                box2 = boxes[active_id]

                if box1.y < box2.y + BOX_SIZE and box1.y + BOX_SIZE > box2.y:

                    box1.dx *= -1

                    box1.dy *= -1

                    box2.dx *= -1

                    box2.dy *= -1



                    box1.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))

                    box2.color = pygame.Color(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))



            active.add(id)

        else:

            active.remove(id)



def main():

    pygame.init()

    screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

    clock = pygame.time.Clock()



    boxes = [Box(i) for i in range(BOX_COUNT)]

    frame_count = 0

    start_time = pygame.time.get_ticks()



    running = True

    while running:

        for event in pygame.event.get():

            if event.type == pygame.QUIT:

                running = False



        screen.fill((0, 0, 0))



        sweep_and_prune(boxes)



        for box in boxes:

            box.update()

            box.draw(screen)



        pygame.display.flip()

        frame_count += 1



        # Calculate and print average framerate every second

        elapsed_milliseconds = pygame.time.get_ticks() - start_time

        if elapsed_milliseconds > 1000:

            fps = frame_count / (elapsed_milliseconds / 1000)

            print("Average Frames Per Second: {:.2f}".format(fps))



            frame_count = 0

            start_time = pygame.time.get_ticks()



        clock.tick()



    pygame.quit()



if __name__ == "__main__":

    main()

In this code, we introduce a new sweep_and_prune function that creates a sorted list of end points for each box along the x-axis. This function then iterates over the end points, maintaining a set of "active" boxes which are currently overlapping along the x-axis. If a start point is encountered, it checks for collisions with all active boxes along the y-axis. If an end point is encountered, it removes the box from the active set. This allows us to perform collision detection in roughly O(N) time, as opposed to the O(N^2) time of the previous method.

I actually would have implemented this somewhat differently. Instead of constructing a new sorted list every frame, I would let the update() function run as usual and every box adds itself to a shared list, which maintains a sort order by putting the box at the correct index on insert. Then after the update has completed, just have to iterate through the sorted list. But whatever, let's leave it this way and test.

This one gets 882 FPS for the 100 box case, and 1.7 FPS for the 10,000 box case. In other words, Python needs to use the superior algorithm just to keep pace with C++ using the naive algorithm.

Let's let C++ use the better algorithm too:

#include <SDL2/SDL.h>

#include <algorithm>

#include <vector>

#include <iostream>



const int SCREEN_WIDTH = 800;

const int SCREEN_HEIGHT = 600;

const int BOX_SIZE = 20;

const int BOX_COUNT = 100;



struct Box {

    int id;

    int x, y;

    int dx, dy;

    SDL_Color color;

};



bool compare_start(std::pair<int, std::pair<int, bool>> a, std::pair<int, std::pair<int, bool>> b) {

    return a.second.first < b.second.first;

}



void sweep_and_prune(std::vector<Box>& boxes) {

    std::vector<std::pair<int, std::pair<int, bool>>> endpoints;

    for (Box& box : boxes) {

        endpoints.push_back({ box.id, { box.x, true } });

        endpoints.push_back({ box.id, { box.x + BOX_SIZE, false } });

    }

    std::sort(endpoints.begin(), endpoints.end(), compare_start);



    std::vector<int> active;

    for (std::pair<int, std::pair<int, bool>> endpoint : endpoints) {

        int id = endpoint.first;

        if (endpoint.second.second) {

            for (int active_id : active) {

                Box& box1 = boxes[id];

                Box& box2 = boxes[active_id];

                if (box1.y < box2.y + BOX_SIZE && box1.y + BOX_SIZE > box2.y) {

                    box1.dx *= -1;

                    box1.dy *= -1;

                    box2.dx *= -1;

                    box2.dy *= -1;



                    box1.color = { (Uint8)rand(), (Uint8)rand(), (Uint8)rand(), 255 };

                    box2.color = { (Uint8)rand(), (Uint8)rand(), (Uint8)rand(), 255 };

                }

            }

            active.push_back(id);

        } else {

            active.erase(std::remove(active.begin(), active.end(), id), active.end());

        }

    }

}



int main(int argc, char** argv) {

    SDL_Init(SDL_INIT_VIDEO);



    SDL_Window* window = SDL_CreateWindow("Sweep and Prune", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN);

    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, 0);



    std::vector<Box> boxes;

    for (int i = 0; i < BOX_COUNT; i++) {

        Box box;

        box.id = i;

        box.x = rand() % SCREEN_WIDTH;

        box.y = rand() % SCREEN_HEIGHT;

        box.dx = rand() % 11 - 5;

        box.dy = rand() % 11 - 5;

        box.color = { (Uint8)rand(), (Uint8)rand(), (Uint8)rand(), 255 };

        boxes.push_back(box);

    }



    Uint32 start_time = SDL_GetTicks();

    int frame_count = 0;



    bool running = true;

    SDL_Event event;

    while (running) {

        while (SDL_PollEvent(&event)) {

            if (event.type == SDL_QUIT) {

                running = false;

            }

        }



        sweep_and_prune(boxes);



        SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);

        SDL_RenderClear(renderer);



        for (Box& box : boxes) {

            box.x += box.dx;

            box.y += box.dy;



            if (box.x < 0 || box.x + BOX_SIZE > SCREEN_WIDTH) {

                box.dx *= -1;

                box.color = { (Uint8)rand(), (Uint8)rand(), (Uint8)rand(), 255 };

            }

            if (box.y < 0 || box.y + BOX_SIZE > SCREEN_HEIGHT) {

                box.dy *= -1;

                box.color = { (Uint8)rand(), (Uint8)rand(), (Uint8)rand(), 255 };

            }



            SDL_SetRenderDrawColor(renderer, box.color.r, box.color.g, box.color.b, box.color.a);

            SDL_Rect rect = { box.x, box.y, BOX_SIZE, BOX_SIZE };

            SDL_RenderFillRect(renderer, &rect);

        }



        SDL_RenderPresent(renderer);

        frame_count++;



        Uint32 elapsed_milliseconds = SDL_GetTicks() - start_time;

        if (elapsed_milliseconds > 1000) {

            float fps = frame_count / (elapsed_milliseconds / 1000.0f);

            std::cout << "Average Frames Per Second: " << fps << std::endl;

            frame_count = 0;

            start_time = SDL_GetTicks();

        }

    }



    SDL_DestroyRenderer(renderer);

    SDL_DestroyWindow(window);

    SDL_Quit();



    return 0;

}

Here I edited it to remove the 60 FPS limiter it had inserted (SDL_Delay(1000/60)) and for some reason it tried to include just SDL.h instead of the full SDL2/SDL.h, the first error it made that resulted in non-compilation. Anyway, at 100 boxes, this now does worse than before at a "mere" 10,000 FPS. But at 10,000 boxes it's now a not-totally-unplayable 17 FPS. If I bump it to 100,000 boxes then I can match Python's worst performance of 0.17 FPS.

Here is a table to summarize:

Language	Collision	Boxes	FPS
C++	N^2	100	12,700
C++	N^2	10,000	1.67
Python	N^2	100	530
Python	N^2	1,000	12
Python	N^2	10,000	0.13
Python	sweep/prune	100	882
Python	sweep/prune	10,000	1.7
C++	sweep/prune	100	10,000
C++	sweep/prune	10,000	17
C++	sweep/prune	100,000	0.17

What can we conclude from this (besides GPT is freaking cool)? I feel like 10 years ago my argument on algorithms trumping languages was still pretty good, but if you asked me in recent years I would have more qualms, especially if one of those languages happens to be Python. Python has basically not gotten any faster at all in the last 10 years. Meanwhile compilers keep improving, and new hardware capabilities tend to be most easily accessible to them over high level Python code. If the comparison language was Java or Common Lisp I'd be more than willing to make the tradeoff against C++'s performance (especially since both those alternatives routinely beat C++ from time to time depending on the benchmark), but choosing something like Python or Ruby leaves a lot of performance on the table. Make sure you know that before committing on such a choice.

---

Posted on 2023-06-17 by Jach

Tags: c++, programming, python

Permalink: https://www.thejach.com/view/id/415

Trackback URL: https://www.thejach.com/view/2023/6/collision_detection_comparison_with_python_and_c

Back to the top