Would like to some help/guidance in my C++ project

[hardy mica]

Hey everyone! I am currently working on a school project where I need to implement 3 algorithms in a 2D game. I now implemented all 3 of them. Grid collision, sort and Graham scan to calculate the Convex hull.

Unfortunately only the grid collision implementation made an significant improvement in performance. The other two only made the performance slower. I am trying to understand why, but am having a hard time figuring this out.

I am not sure if this is the way I can ask for help on this channel, but I would really appreciate some guidance. For anyone wanting to take a look, this is my repo: https://github.com/baspieter/c-optimalisation-project

Or if anyone got any informative sources where I can learn how to make my algorithms run more efficiently, please let me know!

[empty sable]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[hearty vigil]

How do you measure the algorithms performance?
For sorting youre probably gonna be fine with std::sort but you can look at https://github.com/Morwenn/cpp-sort/wiki/Benchmarks
for other sorting algorithms

For convex hull I found this https://link.springer.com/content/pdf/10.1007/BF02712873.pdf

But more importantly for both algorithms copying the data back and forth probably takes more time than actually running the algorithm since your tank class is so large which messes up your cache locality

If you switch to structure of arrays youll definitely get a large speed up sorting the hp

Im not sure how it affects the convex hull algorithm but the game dev humans here should know better than me

[hardy mica]

Thanks for your response! Appreciate you taking the time. I am using a timer to see how long the game takes to render 2000 frames. This is what I got from it:

// Start: 5.23m, speedup 0.4, 323866
// Grid collision: 4.40m, speedup 1.2, 280300
// Quick sort: 4.41m, speedup 1.0, 281855
// Convex hull: 4.58, speedup 0.9, 298122 ```

Later I started using these to measure the performance of selected lines of code:

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::duration;
using std::chrono::milliseconds;
auto t1 = high_resolution_clock::now();
forcefield_hull.clear();
forcefield_hull = GrahamScan(tank_positions);
auto t2 = high_resolution_clock::now();

/* Getting number of milliseconds as an integer. */
auto ms_int = duration_cast<milliseconds>(t2 - t1);

I am definitely changing my sort algorithm, the benchmarks show quick sort gets slower with large classes, thanks for that! Also, I am already creating a new vector for the sorting algorithm, I could try to convert this to a array. Will not change the convex hull scan.

Thanks! 😄

[empty sable]

@hardy mica Has your question been resolved? If so, run !solved :)

[hardy mica]

!solved