wonderwhy-ER on DeviantArthttps://www.deviantart.com/wonderwhy-er/art/Ball-Collision-Study-4-150081329wonderwhy-ER

Deviation Actions

wonderwhy-ER's avatar

Ball Collision Study 4

By
Published:
3.2K Views

Description

So this is continuation to this [link] work.
On a surface it is same Sweep And Prune algorithm but 2 years have passed and a learned a lot of new stuff. About Flash, OOP and optimizing both (sadly by walking away from OOP) and also about some algorithms.

Changes.

1) Data structure and sorting:
Switched from Flash Arrays to LinkedList + MergeSort + dumping comparer and specializing algorithm for sorting special class (particle).

Result:
7x sorting performance boost over Flash Array.sort methods.

Why:
30% of it is from LinkedList+MergeSort combo while other 70% are because of dumping comparer functions and specializing algorithm for the class.

2) Native classes:
Classes like Rectangle, Point, Sprite I used before internally actually use have get/set functions instead of their properties, what that means is that instead of reading/writing memory directly some methods is called that does who knows what. Even if it only does what it should (read/writes memory) it still is 10x slower in Flash. So I dumped all those classes and wrote my own.

Result: many optimizations which are hard to test.
But one place where it was possible to test + native classes were heavily used there. There boost 25x times :omg: Damn I was writing slow code lol :D


Overall results:
Collision study 3 allowed me something like 1K balls with 30Fps. This one allows something like 1.5K. Ah... Not so much.

Why so? Well it is collision detection so in worst algorithms you compare all ball against all other balls. For 1.5K balls we would then have over 1 million of pairs... And with each new ball added 1500+ more pairs are added so unfortunately our 10x optimization is is eaten up pretty quickly.

Conclusions and further plans:
If you check the numbers you will see that now bottleneck is xChecks and yChecks. Those are actually Sweep And Prune axis checks. At 1500 with such density of balls xChecks makes something like 15K of x axis intersection checks so no wonder those are bottlenecks. And it is not a place to optimize... Which probably means that I am at the limit of what is possible with Sweep and Prune.

So if there will be any more Collision studies in the future then I will aether find another more promising algorithm or I will face another directions with them ( not rising amount of overall collisions but say making groups objects that may or my not have collisions inside of groups and between the groups )
Image size
600x600px 22.48 KB
© 2010 - 2024 wonderwhy-ER
Comments35
Join the community to add your comment. Already a deviant? Log In
aspirin111's avatar
Is this flash software limited.

Can i get more balls to be bouncing around if I use a better computer with better CPU and RAM?

If so, I would like to try this on the Playstation 3 console and see how high i can get.