Printable View
Thanks guys,
ImprisonedPride - that looks like just what I need, thanks mate :)
walsher - Thanks for the link, Ill try and check that out too.
webgeek - Pretty interesting, thanks. Wouldn’t this have the same drawbacks as were discussed before though where the work done to work out which bullets to check for collision with ends up causing more slowdown than if you just checked all the bullets in the first place?
Ali
Hehe, he called me mate... Anyhow, not a problem. Take no jab from this but, did you try searching FK for something relative to explosions before this?
It's certainly possible. One of those things you have to test to see if it works for you. Flash is piss poor at pure code performance and so it might be bad.Quote:
Wouldn’t this have the same drawbacks as were discussed before though where the work done to work out which bullets to check for collision with ends up causing more slowdown than if you just checked all the bullets in the first place?
*Warning, Flash rant - Little angry at Flash right now...*
In other languages, much of what I described is so fast as to be almost invisible for the number of checks you are talking about. But along those same lines, in other languages doing the straight circle-circle check against all those points would be a trivial hit too. For kicks, I busted out some quick Java code to run a collision check of 1000 circles against 1 circle. All circles were randomly positioned. I then ran that test 50 times. So a total of 50,000 collisions. The results? 11 milliseconds on a bad run, some as low as 8.
Total Tests: 50,000
Hits: 2,900
Misses: 47,100
Duration (nano): 11593652
Duration (milli): 11.593652
So then I tried 10,000 circles and 500 iterations.
Total Tests: 5,000,000
Hits: 168,000
Misses: 4,832,000
Duration (nano): 69040339
Duration (milli): 69.040339
Last test - 100,000 circles, 5000 iterations:
Total Tests: 500,000,000
Hits: 22,885,000
Misses: 477,115,000
Duration (nano): 9794993778
Duration (milli): 9794.993778
Yeah, thats about 10 seconds for five hundred MILLION checks. In your screen shot above I counted 15 bullets as the longest chain with 15 chains. If you take WORST case scenario (which is MUCH more then you have in the shot), thats 225 bullets. Make it an even 250 just to be safe. The results?
Total Tests: 250
Hits: 14
Misses: 236
Duration (nano): 74032
Duration (milli): 0.074032
(I'll post the little tester class if anyone wants to see it)
Flash rant over - please return to your regularly scheduled thread
Circle to circle is INCREDIBLY fast as long as you can lose the sqrt call. I'd love to see this same test performed in AS3 (which does this type of code much faster then 2).
Squize, you mention Iopred proving that hit test is faster. Is that code online somewhere? I'd love to see it.
Nope ;). Setting a great example I know.Quote:
did you try searching FK for something relative to explosions before this?
Yea, Ill have to do some tests if I get round to it.Quote:
It's certainly possible. One of those things you have to test to see if it works for you. Flash is piss poor at pure code performance and so it might be bad.
Nice, if only flash was that fast. Ill do some tests later on my swf and see what kind of speeds I get.Quote:
Yeah, thats about 10 seconds for five hundred MILLION checks. In your screen shot above I counted 15 bullets as the longest chain with 15 chains. If you take WORST case scenario (which is MUCH more then you have in the shot), thats 225 bullets. Make it an even 250 just to be safe. The results?
Total Tests: 250
Hits: 14
Misses: 236
Duration (nano): 74032
Duration (milli): 0.074032
Ali
"Squize, you mention Iopred proving that hit test is faster. Is that code online somewhere?"
I don't honestly think so, from memory it was just a chat we were having and he sent me a fla which just really stumped me ( I'd always been of the opinion, like most people, that hitTest was painfully slow ).
The difference was really huge. From memory it tested getBounds(), a coord based get bounds test and bounding box hitTest, really not sure about circle to circle.
It's be far too long since I've been really anal about things like timing, I'm only doing it now when I've noticed there is a slight slow down when I have around 8-10 baddies on screen ( 64x64 sprites ), which I'm figuring is more from all the collision checks that causes ( Player bullets - 2 - baddies ) than from the screen data.
Squize.
Wow, thats a cool little test there webgeek. Would definitely like to see how you did it.
If you have Flash8 or 9 then you can use bitmapData.hitTest to detect collision. Put all the bullets in 1 bitmapData object and ship in another. Now at each step you only need to perform 1 hitTest between those bitmapData objects to check if any of the bullets hits the ship. For collision it does not matter how many bullets you have, it will always be just 1 single hitTest. Of course after the collision was detected you need to find which of the bullets did hit the ship, but it only happens on the collision and is rare as such games usually are about avoiding enemy bullets.
bitmapData.hitTest is also pixel level meaning you dont need to use points, you can use actual shapes of the bullets and the ship.
But unless you're using bob's for the bullets anyway, won't that mean an additional copyPixel for each and every bullet ( To copy them into the collision bitmap ) ?
I have been thinking about a bitMap approach to doing this, but a good way still escapes me.
Squize.
Yea, I never have much luck with bitmapdata, Tried it with neon, but it ended up twice as slow. I might have a play though because the idea sounds good. Just depends how much of a speed decrease drawing all the bullets to the bitmap each frame takes compared to doing a hitTest for each bullet.
I hate changing my methods of doing things half way through a game though, feels like your ripping out a chunk of code and sticking in a different bit. But it is at least worth a test.
Thanks.
Ali
Just throw this code in a main method to run the test:Quote:
Wow, thats a cool little test there webgeek. Would definitely like to see how you did it.
Code:// Init data
int iterations = 10;
int testSize = 1000;
int width = 500;
int height = 500;
int heroRadius = 50;
int enemyRadius = 10;
int[][] points = new int[testSize][2];
// Setup
Random rand = new Random();
for(int i = 0; i < testSize; i++) {
points[i][0] = rand.nextInt(width); //x
points[i][1] = rand.nextInt(height); //y
}
int heroX = rand.nextInt(width);
int heroY = rand.nextInt(height);
int collisionRange = (heroRadius + enemyRadius) * (heroRadius + enemyRadius);
int hits = 0;
int misses = 0;
// Test
long startTime = System.nanoTime();
for(int j = 0; j < iterations; j++) {
for(int i = 0; i < testSize; i++) {
int distance = ((heroX - points[i][0]) * (heroX - points[i][0])) +
((heroY - points[i][1]) * (heroY - points[i][1]));
if(distance <= collisionRange) {
hits++;
} else {
misses++;
}
}
}
long duration = System.nanoTime() - startTime;
// Results
System.out.println("Total Tests: " + (iterations * testSize));
System.out.println("Hits: " + hits);
System.out.println("Misses: " + misses);
System.out.println("Duration (nano): " + duration);
System.out.println("Duration (milli): " + ((double)duration / 1000000d));
Sweet, thanks for the code. I'll have to try that out later today. Cheers
I think it's been shown before that copyPixels is quite fast (esp. when used as a scrolling/moving method) with bmpdata.....that and the use of bitmaps vs vectors would keep things pretty speedy.....I haven't fully tested it yet with bullets (i.e. as suggested by tony) but I use that method for my scrolling background tiles (about 50 64x64 tiles on two layers (so about 100 tiles)...one background, non-interactive and the other interactive to collisions) and it's quite fast.....Quote:
Originally Posted by Squize
and I want to use a similar approch with bullets and collision.......the only issue would be, once there is a collision between the bullets bmp and player or whatever, is finding which bullet has collided and where in the bmp.....that issue could make that method a bit hard to deal with.....but I need to test it still.... :D
Here is a thread I started a while ago:
http://board.flashkit.com/board/show...hlight=hittest
Ok, this whole "hittest is faster" thing was smelling kinda funny to me so I decided to test it a bit. I've gone ahead and created a simple little AS2 file that will test 4 scenarios; three using hitTest and one using circle to circle tests. The results are very interesting but can be summed up like this:
1) The less movie clips on the screen, the faster the built in hit test will preform.
2) The built in hit test methods scale poorly with more movie clips.
3) The bounding box to bounding box test scales the worst of all.
4) The circle to circle test scales the best but performs poorly at lower numbers of movie clips.
5) Shape to point hit test scales better then any other built-in hit test.
The trick to all this though is that when dealing with a reasonable number of movie clips, the built-in hit test is just plain faster (if only trivially) then circle-to-circle. If you are talking 250 or less movie clips, then the built-in is quick and easy. Here are the results (note that each "test" involved a movie clip on the stage being checked against a hero clip, each "iteration" is simply running the test many times to get more visible results):
HT - Shape to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 1132
HT - Bounding Box to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 1114
HT - Bounding Box to Bounding Box Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 2000
Misses: 48000
Duration (milli): 1348
Math - Circle to Circle Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 1400
Misses: 48600
Duration (milli): 1153
To show how it breaks down with more clips, 1100 in this case:
HT - Shape to Point Test
Iterations: 100
Tests: 1100
Total Tests: 110000
Hits: 200
Misses: 109800
Duration (milli): 3094
HT - Bounding Box to Point Test
Iterations: 100
Tests: 1100
Total Tests: 110000
Hits: 200
Misses: 109800
Duration (milli): 3109
HT - Bounding Box to Bounding Box Test
Iterations: 100
Tests: 1100
Total Tests: 110000
Hits: 3100
Misses: 106900
Duration (milli): 4675
Math - Circle to Circle Test
Iterations: 100
Tests: 1100
Total Tests: 110000
Hits: 2200
Misses: 107800
Duration (milli): 2653
The code isn't pretty or well documented but it's quite simple and available here. I'd love for someone to translate this into AS3 and run it. I expect the programatic approach will be much faster. Have fun!
how much faster is math hitTest to plain hitTest? because taking apart the math hitest into smaller peices (meaning a bunch of if's) would speed it up by...well it depends really
The circle to circle even with sqrt works extremely fast in as3, dont have the actual data but Iv been working on an as3 shooter. I can have 300+ bullets with little lag (rendering adds a lot though...)
Not really, it of course means drawing the bullets into bitmapdata object, but you could use the same bmp to show them so there is no additional bmp for the collision. Unless you would still use old system of having each bullet in separate movie clip and changing movie clip coordinates for each bullet. Still, the main improvement would be performing only 1 hittest instead of hundreds.Quote:
Originally Posted by Squize
Excellent post WG, it is surprising that hitTest performs so well. I think it's almost a reflex arc that most of us say that hitTest is slow ( I know I was anti-hitTest boy for a long while ).
"how much faster is math hitTest to plain hitTest?"
It's not. hitTest is fast mate.
AS3 is going to change the way we look at a lot of things, I think it's going to be a while before we all nail the best way using it.
"Unless you would still use old system of having each bullet in separate movie clip and changing movie clip coordinates for each bullet"
Yeah that's how I do it, 'cause I wasn't happy with the results of using a bob based system.
Possibly that I only spent two days on it, but as I mentioned in the thread about it, after messing around double buffering etc. I still only got about the same performance as using mc's.
Perhaps for the next game with a million bullets in :)
Squize.
yeah, that's very much the same way I'm moving tiles around right now for scrolling.....in addition to that, keeping track of where each bullet is, using objects with x/y coordinates for each active/on-screen bullet would help to figure out, once there is a collision, where that collision happened/which bullet collided with the player, by determining the closest bullet object to the player's coordinnates......at least that the way I thought of it.....Quote:
Originally Posted by tonypa
is that a way you'd go about it, tony?
paul.
Flash 9 Results:
HT - Shape to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 61
HT - Bounding Box to Point Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 0
Misses: 50000
Duration (milli): 60
HT - Bounding Box to Bounding Box Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 200
Misses: 49800
Duration (milli): 78
Math - Circle to Circle Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 3000
Misses: 47000
Duration (milli): 9
Inbuilt - Bound Box to Bounding Box Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 200
Misses: 49800
Duration (milli): 373
Math - Bound Box to Bounding Box Test
Iterations: 200
Tests: 250
Total Tests: 50000
Hits: 200
Misses: 49800
Duration (milli): 280
Inbuilt Bounding box uses getRect() and then the Rectangle.intersects method
Math does the simple if(bounds1.right > bounds2.left) etc. etc.
So as Squize mentioned, bounding box vs bounding box is still faster by using hitTest. But for a space shooter, you guys should be using circle collisions :)
Edit: Just to clear up some confusion with Webgeek, Squize was (I hope) only saying that hitTest is faster than checking for bounding box collisions in code. At least that is all I have ever said.