HOME | DD
wonderwhy-ER — Collision study 5
by-nc
Published: 2010-01-24 22:56:57 +0000 UTC; Views: 39761; Favourites: 178; Downloads: 392
Redirect to original
Description
How to useAll you can do in this version is to change amount of balls (first stepper), change partitioning algorithm step(second stepper, do not recommend as it seems to perform well with that),
forces dumping (third stepper, can lead to pretty different results).
And finally you can pick some presets I made using combobox.
Have fun.
Background story
So after making Collision Study 4 and checking it's bottleneck I started to think on how to fix it (Sweep And Prune algorithm was used there). Well did not come up with ways of improving Sweep And Prune.
Ended up checking this book [link] which I recommend to anyone who wants to write alike stuff.
Well it turned out I already knew all types of broad phase collision detection techniques probably except for k-d/bsd trees which are kind of expensive in some ways. Good to store static level but probably not that good with moving stuff.
Anyways in the end come up with idea of kind merging some parts of uniform grid partitioning and Sweep And Prune loosing some benefits of SAP but in same time hopefully fixing big SAP weakness. It was tricky and code is little bit messy. But in the end it almost doubled performance with right tuning
I think there still is room for optimization + making it more stable but it is already very good 
Further plans
Well this work mostly serves as algorithm performance test but after playing with presets I am thinking on making something like little sandbox thing where you could create/share/reuse presets yourself using range of small easy tools
Still thinking.
Related content
Comments: 147
I love it so much and how did you do it?
👍: 0 ⏩: 1
Hmm... Had idea, sit down, programmed, works
👍: 0 ⏩: 1
Well I asked what specific? There is a lot what you may want to know... Technologies, algorithms or something like "how I got to know those technologies and algorithms"? Or you want whole essay for 3 pages?
👍: 0 ⏩: 0
Why do they sometimes vanish on impact? It's especially noticeable in the example "Geometrical"; it's as if they cancel out.
👍: 0 ⏩: 1
Well it is iteration and on impact I project them out of each other but if they accidentally end in precisely on same position I can't project them from each other... In truth in that case projection backfires and returns NaN distance
1) if two objects move so fast they do not intersect on any iteration but between them...
2) if two objects got on same spot on some iteration(guess just need to change projection out to something else, like move both objects back in time to moment of collision, but there is risk of moving them back in to other objects and it is more costly in computation even for pair, I can move back more then a pair but all objects but I will need to move them forward afterwards and for so many it will be tremendously costly... sooo I want to read to see if there are some interesting tricks
3) group collisions, I think there are such schemes where I collect many collisions pairs, collect them in to collision groups and resolve them all as one big complex collision. Could help with some problems.
4) check impulse based collision resolution schemes, could help with some problems.
👍: 0 ⏩: 0
Thanks
👍: 0 ⏩: 0
This is so cool, didn't think this was possible with flash.
It's even inspired me to have a go at it
So far I've only implemented brute-force collisions with the sides, and it goes at a reasonable pace with 20,000 particles. (just trying to find the best drawing method, I'm sure once I add particle collisions the performance will drop 
What is the sweep and prune thing anyway? Sounds like something I should learn. I'm only familiar with the grid partitioning.
👍: 0 ⏩: 1
Check wiki page for Sweep And Prune.
👍: 0 ⏩: 0
This is pretty spectacular stuff 
Im attempting to create an isometric game in flash... the lighting mode i added is a lot like some of your work in lighting effects... i wonder if you have any advice to offer 
[link]
👍: 0 ⏩: 1
Yeah 3K is pretty far
And yeah I need to work more on it. Realized later that have some mistakes in it but luckily it happens when one ball collides multiple times in one step so human eye can't really see as a lot is happening very quickly
By solids you probably mean that they are kind of connected?
Still have it in my message box unchecked. Will comment later
Hmm lightning in isometrics... Well I was mostly doing it by different displacement/blur stuff in my 2D experiment. For isometric you may need 3D variation no?
P.S And thanks for
👍: 0 ⏩: 1
Yeah... maybe if you rendered them as squares instead of circles and added some sort of low quality blur... a meta-ball effect would be awesome but i'd say it wouldn't cope with the number of particles
The lighting in isometrics thing is going to be a big optimization problem... one the one hand, it fixes many of its drawbacks such as the depth problem [link] which i think is awesome... but on the other hand it makes all obvious optimization techniques redundant. i was thinking of pre-rendering the blocks into several 'layers' starting from the furthest corner moving to the nearest if you know what i mean... but that doesn't allow for lighting... you have to render each individual block every time.
my current idea is to only render the blocks brighter than a certain threshold... but then i cant have ambient lighting
👍: 0 ⏩: 1
Well honestly any technique there is goes trough some objects to adjust light to them be it pixels, polygons or something like voxels in your case. So yeah in any case you will need to go trough each and reset their state based on distance or something. Or kind of ray-tracing trough to make it more realistic.
👍: 0 ⏩: 1
yeah true... my latest plan involves pre-rendering the same cube several times onto a sprite-sheet with different brightness levels. then in game, use the lightning fast copyPixels() with an alpha mask to get the cubes onto the screen as fast as possible. As long as i don't need many cube types this shouldn't need that much memory.
on a side note... i'm not sure if you have ever played with pixel blender? i think i have found a method to embed the kernel files in flash by converting the file to a series of uint's. then reproducing a byte array from them at runtime. The processing power is quite impressive... i want to see how quickly it can run something like Langton's ant or game of life
👍: 0 ⏩: 1
I see
Hmm so it is possible to load Pixel Bender stuff from ByteArray? I never got to play with it. Have a lot of fun stuff to do without it but that could be a good thing to drop different filters on as it can use more CPU cores.
As for loading from ByteArray. There is BinnaryDataTag in flash format. You can embed any file in to the flash using Embed directive. It looks something like that:
[Embed(source='filepath/filename.type', mimeType="application/octet-stream")]
private var theClass:Class;
Then use like that:
var data
This way you may embed anything you want 
👍: 0 ⏩: 1
Omg
👍: 0 ⏩: 1
Well if you compile it trough Flash IDE with that path it will ask path to Flex SDK
👍: 0 ⏩: 0
This is awesome, you're getting better and better at making effective particle collision algorithms
Now you should make a game with these!
👍: 0 ⏩: 1
Well I need to make some tests. Firstly I think it is possible to make it even faster + I actually though right now that it may not work that well. It's just that I resolve collisions at the moment I detect them which may lead to some situations where balls that got in to many collisions in one step may miss some of them in a bad way.
👍: 0 ⏩: 0
This is really awesome!
It would be nice to if you add a static background or other shapes, like squares etc.
👍: 0 ⏩: 1
Well adding squires will need adding of rotational momentum. This add many problems especially if I have different shapes. Firstly bounding of object changes with rotation. Then graphics change with rotation (tough at cost of memory I think I can make as fast still), and final collision check/resolve becomes more complex. Tough I am planing on playing with all that anyways. It just that I was researching performance first. Well those experiments are almost over. Btw Box2D as far as I heard uses Sweep and Prune (one I used in CollStud 3 and 4) so getting Box2D complexity is possible
👍: 0 ⏩: 1
Yeah, it might reduce the amount of objects more, but it really gives great possabilitys ;D
And if you can achieve a kind of Box2D with what you allready have, I think it would be more awesome!
👍: 0 ⏩: 1
Well Box2D like possibilities will not be made soon
👍: 0 ⏩: 1
Mmm okay, but you allready achieved much :3
👍: 0 ⏩: 1
Haha yeah I don't think I seen such massive ball-ball collisions in flash
👍: 0 ⏩: 0
Haha
As for source. Hmm. It is quite easy actually.
Just store objects bounds in a way where x,y for bounds is top left corner + width/height of bounds.
Then on each frame create new array for uniform grid(Say 10x10 pixels, so all particles whose top left fits in 10x10 goes to that grid cell).
Then in same loop where you move particles hash then in to the grid. Then loop again through particles and for each particle check their grid cells + iterate trough cells to the right and to the bottom from cell they ended up in until their x+width or/and y+height bounds do not become smaller then neighbor cells in that direction.
Very simple, no particle duplicates are stored in a grid, each pair is checked only once (you do not check neighbor cells to the left top because balls in those cells will check their bottom/right later or already checked), base structure is simple (not hierarchical grid or trees).
I am actually thinking on making some modifications and tests to may be even further enhance performance. Still thinking if it is possible.
👍: 0 ⏩: 2
Hey I just thought about using a method like that the other day!
It's a really nice idea.
👍: 0 ⏩: 1
Well I used it before in some of my experiments but with differences... Actually so much differences that it was only handled somewhere near 700 balls. Not it can handle up to 3k
👍: 0 ⏩: 1
In which situations in an actual game would you recommend this method?
👍: 0 ⏩: 1
It rather depends on collision model then game situations. I am just testing best performing broad phase filtering which allows bringing this problem down from n^2 to like of n*log(n). Tough I guess this one can perform even better.
👍: 0 ⏩: 1
What does log() do? And what is it used for? I'm only 15, I haven't learned about log at school or researched it...
👍: 0 ⏩: 1
Mmm. Well it is operation connected to raising to power.
Like log 8 by 2 is 3 because 8 is 2^3.
So it is operand that takes in number and base and returns power to which you need to raise base to get that number. Useful thing.
As for stuff I wrote above it represents how fast algorithm computational needs raise with raise of input elements.
n^2 computational complexity that computational demand raises pretty quickly. While n*log n is a lot slower raise.
Actually here [link] *logx%2C+x^2+from+0+to+100
👍: 0 ⏩: 0
I'm good, I have read about the method in the past, but few things I'm still not sure about.
Any change in me having a look through your source and porting to C++?
Would like to see how performance goes.
👍: 0 ⏩: 2
Hmm. I guess I can share it if you then will share C++ version back 
Also may be direct port will not perform that well for C++ who knows.
👍: 0 ⏩: 1
Optimizing for C++ shouldn't be hard, and of course I will share it back
👍: 0 ⏩: 1
Hehe ok
👍: 0 ⏩: 0
You could just have a vector in a vector with each particle.. :D
and then store the particles in that against the grid
idk if I'm making sense
👍: 0 ⏩: 0
Wow, that's really impressive. You did find something fun to do with the collision system
👍: 0 ⏩: 1
Hehe
👍: 0 ⏩: 0
Geometrical features disappearing particles! Notice somewhere mid-high in the red/green and yellow/cyan parts!
And the hard landing one features a somehow weird ground. Looks like the particles are overlapping at the start.
👍: 0 ⏩: 1
Yeah I know. I know why particles disappear sometimes (it just that with this system particles may sometimes end up being on same place and that's where resolution algorithm fails.
There is some other bug where particles kind of merge together and dribble. I know why that usually happens but my algorithm should not produce this bug. I actually made geometric for testing purpose to create many particles in a way where it is easy to see glitches. So I create many. See which pair produced glitch, create only that pair and see try to understand why. Will be fixing it slowly I think.
As for ground yeah
👍: 0 ⏩: 0
Very very cool. I've been interested in collision detection lately, and although I don't know any algorithms or techniques, I've still been trying to create something hopefully good. I'll look into some of the methods you used to make this... They seem pretty neat sources.
👍: 0 ⏩: 1
Check the book. May be it is not enough if you do not have background knowledge on things like sorting but it overviews almost everything there is on high performance collision detection.
👍: 0 ⏩: 1
I skimmed through what I could see on Google Books, and it's really interesting... If I have some money to spare I may go out and buy it. Well, order it x.x, looks like an interesting read regardless if I can apply it
👍: 0 ⏩: 1
Well it gives good overview. No performance info or good examples but good overview.
👍: 0 ⏩: 0
| Next =>