HOME | DD

Published: 2010-01-24 22:56:57 +0000 UTC; Views: 39760; 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
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
Related content
Comments: 147
TheCosmicMonkey In reply to ??? [2010-03-17 09:43:27 +0000 UTC]
I love it so much and how did you do it?
👍: 0 ⏩: 1
wonderwhy-ER In reply to TheCosmicMonkey [2010-03-17 09:45:12 +0000 UTC]
Hmm... Had idea, sit down, programmed, works Or you are interested in something more specific?
👍: 0 ⏩: 1
wonderwhy-ER In reply to TheCosmicMonkey [2010-03-17 11:11:03 +0000 UTC]
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? Which I will ofcourse will not give
👍: 0 ⏩: 0
ShnitzelKiller [2010-03-13 04:21:38 +0000 UTC]
Why do they sometimes vanish on impact? It's especially noticeable in the example "Geometrical"; it's as if they cancel out.
👍: 0 ⏩: 1
wonderwhy-ER In reply to ShnitzelKiller [2010-03-13 08:05:56 +0000 UTC]
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 Basically as far as I know Varlet approach uses same trick but I never knew what they use for such cases... Basically that's why I intend to read few books about collision math. Am curious how they handle 3 problems with iterational engines
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
wonderwhy-ER In reply to admiral-squee [2010-03-08 22:57:09 +0000 UTC]
Thanks I like tetra best
👍: 0 ⏩: 0
Hafunui [2010-02-13 05:55:13 +0000 UTC]
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
wonderwhy-ER In reply to Hafunui [2010-02-13 08:24:08 +0000 UTC]
Check wiki page for Sweep And Prune.
👍: 0 ⏩: 0
theCheeseGrater In reply to ??? [2010-02-09 10:34:15 +0000 UTC]
This is pretty spectacular stuff ! i wouldn't have thought you could squeeze that kind of collision detection out of flash. any chance of smoothing it over so that the moving things look like solid objects before they collide?
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
wonderwhy-ER In reply to theCheeseGrater [2010-02-09 11:34:09 +0000 UTC]
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
theCheeseGrater In reply to wonderwhy-ER [2010-02-10 05:13:33 +0000 UTC]
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
wonderwhy-ER In reply to theCheeseGrater [2010-02-10 07:27:03 +0000 UTC]
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
theCheeseGrater In reply to wonderwhy-ER [2010-02-12 06:45:48 +0000 UTC]
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
wonderwhy-ER In reply to theCheeseGrater [2010-02-12 09:15:34 +0000 UTC]
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 datayteArray = new theClass();
This way you may embed anything you want Am playing with this tag with my ReCo mini project
👍: 0 ⏩: 1
theCheeseGrater In reply to wonderwhy-ER [2010-02-13 12:02:16 +0000 UTC]
Omg i thought the embed tag would only work in flex! flash has some awesome features that are so very poorly documented... or at least very difficult to find on google
this is awesome... so easy to embed shaders... this is gonna be fun
👍: 0 ⏩: 1
wonderwhy-ER In reply to theCheeseGrater [2010-02-13 16:02:55 +0000 UTC]
Well if you compile it trough Flash IDE with that path it will ask path to Flex SDK
👍: 0 ⏩: 0
eliskan In reply to ??? [2010-01-29 01:43:07 +0000 UTC]
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
wonderwhy-ER In reply to eliskan [2010-01-29 07:15:20 +0000 UTC]
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
Thumaszz In reply to ??? [2010-01-26 20:08:44 +0000 UTC]
This is really awesome!
It would be nice to if you add a static background or other shapes, like squares etc.
👍: 0 ⏩: 1
wonderwhy-ER In reply to Thumaszz [2010-01-26 20:24:23 +0000 UTC]
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
Thumaszz In reply to wonderwhy-ER [2010-01-27 20:42:25 +0000 UTC]
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
wonderwhy-ER In reply to Thumaszz [2010-01-27 21:10:16 +0000 UTC]
Well Box2D like possibilities will not be made soon If even will be done ever though it is possible.
👍: 0 ⏩: 1
Thumaszz In reply to wonderwhy-ER [2010-01-27 21:11:50 +0000 UTC]
Mmm okay, but you allready achieved much :3
👍: 0 ⏩: 1
wonderwhy-ER In reply to Thumaszz [2010-01-27 21:31:08 +0000 UTC]
Haha yeah I don't think I seen such massive ball-ball collisions in flash
👍: 0 ⏩: 0
wonderwhy-ER In reply to Supa-Monky [2010-01-26 13:41:25 +0000 UTC]
Haha Haven't heard from you for a while. How you doing?
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
JohnJensen In reply to wonderwhy-ER [2010-01-26 18:05:51 +0000 UTC]
Hey I just thought about using a method like that the other day!
It's a really nice idea.
👍: 0 ⏩: 1
wonderwhy-ER In reply to JohnJensen [2010-01-26 19:56:59 +0000 UTC]
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
JohnJensen In reply to wonderwhy-ER [2010-01-26 20:20:07 +0000 UTC]
In which situations in an actual game would you recommend this method?
👍: 0 ⏩: 1
wonderwhy-ER In reply to JohnJensen [2010-01-26 20:26:57 +0000 UTC]
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
JohnJensen In reply to wonderwhy-ER [2010-01-26 20:38:15 +0000 UTC]
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
wonderwhy-ER In reply to JohnJensen [2010-01-26 22:30:52 +0000 UTC]
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 You can see difference of growth of those function
👍: 0 ⏩: 0
Supa-Monky In reply to wonderwhy-ER [2010-01-26 17:24:29 +0000 UTC]
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
wonderwhy-ER In reply to Supa-Monky [2010-01-26 19:59:17 +0000 UTC]
Hmm. I guess I can share it if you then will share C++ version back I would gladly be testing such stuff on C#(or may be trying unity) in parallel but kind of am lazy/time restrained for that
Also may be direct port will not perform that well for C++ who knows.
👍: 0 ⏩: 1
Supa-Monky In reply to wonderwhy-ER [2010-01-28 11:35:40 +0000 UTC]
Optimizing for C++ shouldn't be hard, and of course I will share it back
👍: 0 ⏩: 1
wonderwhy-ER In reply to Supa-Monky [2010-01-28 12:30:51 +0000 UTC]
Hehe ok Will need to clean it a little. Most code is in fla though.
👍: 0 ⏩: 0
JohnJensen In reply to Supa-Monky [2010-01-26 18:07:03 +0000 UTC]
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
spacewarp In reply to ??? [2010-01-26 12:32:49 +0000 UTC]
Wow, that's really impressive. You did find something fun to do with the collision system
👍: 0 ⏩: 1
wonderwhy-ER In reply to spacewarp [2010-01-26 12:43:53 +0000 UTC]
Hehe You can do a lot
Just those studies are made for performance testing mostly. Making some fun stays for later reuse
👍: 0 ⏩: 0
YoungLink19 In reply to ??? [2010-01-26 10:42:10 +0000 UTC]
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
wonderwhy-ER In reply to YoungLink19 [2010-01-26 10:49:43 +0000 UTC]
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 Made mistake somewhere while making it
Will be making few more presets this evening for futher tests + will fix it I think
👍: 0 ⏩: 0
ssjskipp In reply to ??? [2010-01-26 00:31:30 +0000 UTC]
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
wonderwhy-ER In reply to ssjskipp [2010-01-26 07:21:31 +0000 UTC]
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
ssjskipp In reply to wonderwhy-ER [2010-01-26 22:21:21 +0000 UTC]
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
wonderwhy-ER In reply to ssjskipp [2010-01-26 23:07:19 +0000 UTC]
Well it gives good overview. No performance info or good examples but good overview.
👍: 0 ⏩: 0
| Next =>