Hands-On Optimization - Collisions

Howdy,

The stickied optimization thread has some great stuff in it, but I always learn better when I get my hands dirty. The point of this thread is to give a place for everyone to actually go in and see if they can optimize working code (or at least watch other people go in and optimize working code :)).

I'm obviously focusing on collision detection here, and for our first run at it I figured we could start with the most straight-forward method I can think of - each object handling its own movement and detection. I'm all for looking at the other approaches (centralized handling w/ bookeeping, tilebased, etc.), but ya gotta start somewhere :).

So without furter adeu...

De-Centralized Method
Basic Description
Each square calls a central function to preform it's collision detection and movement on enterFrame. I've taken all the steps I can think of to remove any redundant checks (squares only check for collisions with objects created after themselves, if they have a collision, they tell the other square to skip it's check, etc.). Regardless, its all pretty basic, so I am sure there is plenty of room for improvement.

Examples
Note - either use the .html or download the .swf and open it in the standalone player for the most consistent results (prevents scaling).

Instructions
*Upper Left Button - Adds a square
*Upper Right Button - Removes a square
*Lower left text - maximum velocity (changable)
*Lower right text - current FPS

Full collision detection: .html .swf
This one has everything turned on.
With 30 objects on screen, my FPS stays around 29-30.

No Physics: .html .swf
Same basic idea, but I commented out the meat of the object-object calculations (still goes through the loops, just doesn't do anything inside of them).
With 30 on screen, I get about 38 fps, which means the physics crap is taking some decent calculation time

Walls Only: .html .swf
This time I skip the object-object checks completely.
I can get a crapload (90-100ish) of objects on the screen before FPS takes a hit.

"Optimized" Full Collision: .html .swf
On this one I went through and stored off any object references (i.e. "object._x") to a variable which I used in place of the actual reference whenever possible. The end result was the FPS taking a severe nose dive to around...
30 objects on screen, 22ish FPS.
Fun stuff :/

.FLA source: Click Me
Just what it sounds like, the original .FLA. This version does not have any of the optimization stuff I did in the last example (since it didn't help FPS, I didn't see much of a point). As for the content, pretty much everything of importance is in frame 1 of the Actions level, main timeline.

Let me know and I'll go through and explain what I did in the code in more depth.

So whadaya say? :)

Edit: Oh yah, and I am using Flash 5 (doing it from the home machine), sorry for any inconvenience :/

I'd say that it's not your blame, it's mainly blame of the graphic engine of Flash...

Cool start TiefighT, and refreshing to see an interesting thread ;)

As soon as I get the chance I'll have a play with the fla.

If it's any help I'm writing an asteriods clone at the moment. For the collision detection I'm using a handler clip for all the rocks ( As opposed to seperate enterFrames, that would really kill the fps ).

I've split the screen into quarters and each rock calculates which quarter it's in after every move. This is just stored in one of four arrays and then I run through a mc -> mc distance loop ( not hitTest ) to check for the collisions ( ie player / player bullets -> rocks ) depending on which quarter the player (etc) is in.

Also I've made the player bullets have a larger radius and decreased the player radius ( It gives that feeling of luck when a rock just skims you ).

It seems to be holding up quite well at the moment ( Both speed wise and accuracy ).

Anyway I hope that's food for thought ;)

Squize.

PS. It may be an idea that when all this is done if it could be re-posted in the sticky. I just like the thought of it all being held in one spot to save people hunting around (?)

Quote:

---

Originally posted by TiefighT
Walls Only: .html .swf
This time I skip the object-object checks completely.
I can get a crapload (90-100ish) of objects on the screen before FPS takes a hit.

---

I wonder if your fps counter is accurate.
You see, it starts fine, around 30, then if I add and add and add objects, it starts to raise. When I have around 80 objects on screen, fps has raised to 45.

If raising fps would be just a matter of adding 80 objects on screen, we wouldnt need optimisation at all :)

http://www.flashkit.com/board/showth...hreadid=280716

this was long time ago..:D
I hope the links work..

ms.

Nice thread. I wish you'd have posted this stuff in both the hittest and the optimization sticky thogh, so that it's always there. Good to see a thread that isnt newbie or rant, though ;)

Update
I got some extra time and decided to start working on a centralized approach, starting with a quartile idea similar to the one Squize spoke of (wanted to get as far away from the previous approach as possible).

Here is what I have so far, I am not handling collisions just yet, but I am doing the bookeeping necessary to track which quartile each object is in:

Centralized Calculations - Version 1
.html .swf .fla

Basic Description:
- 4 seperate arrays, one for each quartile

- Each object estimtes the number of frames until it crosses a quartile boundry

- Once that number of frames have passed, the object removes itself from its current array, re-checks position, adds itself to new array, and re-estimates time until next boundry

- The estimate has to be re-calculated every time it hits a wall (or eventually, another object), which is my major concern.

Originally, I was just wiping these arrays out and rebuilding them every time rather than doing the estimate crap, but that was obviously a bit slow.

Once I am a bit more confident in the bookeeping, I will start working on the collisions, and see if I can get a decent (or any) FPS gain using this quartile approach.

Squize: Generally speaking, how did you handle the bookeeping for that astroid game you spoke of? Do you do some similar kind of distance calculation to reduce the number of checks per frame, or are you requerying and reporting quartiles for every object every frame? Also, are you letting astroids hit each other?

Mad-Sci: Yah, I remember that one, very nice :). Does that mothod work well with moving boundries or the like? Or is it best used when testing a single object against a bunch of stationary barriers?

Tonypa: Not sure. The FPS counter is just a chopped down version of moock's. It averages over the last 10 frames, so it may take just a bit to return consisntent results. Also, I have noticed that having a movie set at 50 FPS on my slower work machine causes the FPS of the .swf to be sparratic until you get 10 or so objects bouncing around. Not sure exactly why, but I suppose it could be the slower processor not liking the faster frame rates...

adityadennis: Yah, I was thinking about putting this in the optimization thread, but didn't want to junk it up with the discussion. However, if this one turns into something, then I'll put a summary of the final result in both threads :).

I wish I could sound really clever and make the bookeeping seem very exotic, but I can't.

I just use your original method of rebuilding 4 arrays every frame. As I'm stuck with moving every rock every frame in the update position function I just do a simple check ( I think in the very worst case 2 if conditions are meet ). In saying that I run a simple flip flop test so only the odd or even number rocks are tested each frame.

I was worried about the boundary side of things, where a collision would be missed where a bullet was in one quarter missing a rock ( The large ones are 96x96 pixels which is fairly big for a sprite ) which was overlapping into that quarter but not actually in it ( Have I explained that ok ? Sorry I'm tired ).

It seems to be holding up fairly well and I think the reason is the way I've set the game up. I've made it very fast and in your face ( I'm going for an all out arcade feel. I want it to rock like Defender ;) ) so you don't really notice if the collision is a frame late.

I'm a great believer in cheating if you can get away with it. The method I've used would really suck for say a platformer, you would notice I was cheating to easily.

I was toying with the asteroids colliding with each other but it would make it like a pinball table :) Also I couldn't justify a small rock hitting a large one and just bouncing off, I would have to kill it, and that could mean you could clear a level with out doing very much ( I know it's just a simple blaster and not a simulator, but I've still got to hold on to at least some logic ).
Speed wise I doubt I'd be able to do it anyway. The first level starts with two large rocks, which split into 4 medium and therefore 8 small rocks. Add to that four player bullets, plus collisions with the player himself, I'd be looking at a frightening number of checks and just on the first level. Throw in the baddie ufos with their own bullets and it would just kill the flash player.

I don't think there is a generic way to check for collisions, a one size fits all. I think what you're doing by submitting different approaches is great, because people will be able to use the approach that best suits the game.
For example, in Delta ( Horizontal shooter ), I stored all the baddie x positions in an array and then sorted that array. If the first value in that array was greater than the player's x position then I knew the whole attack wave was to the right of the player so I could skip all the collision checks. If it wasn't the case then I'd just check the baddie sprites near the player. OK there is an overhead sorting a multi-dim array but it would mean the game would hardly ever have to check more than two ( Out of eight ) per frame.

Right, that's enough from me :)

Squize.

PS. Hopefully in a week or so you'll be able to see if I have pulled the collisions off.

Quote:

---

adityadennis: Yah, I was thinking about putting this in the optimization thread, but didn't want to junk it up with the discussion. However, if this one turns into something, then I'll put a summary of the final result in both threads .

---

Cool :)

Quote:

---

Originally posted by Squize
Waaaaay too much stuff to quote.

---

Cool :).

Yep, I understand what you mean by the quarter hanging over thing, I was worried about that earlier but I think I can handle it. My ideas to get around it so far are to:

1) if an object is hanging over, add it to both quartile arrays.
2) Keep a couple extra "gutter" arrays that check for collisions between objects that are within width/2 or height/2 of the quartile boundries. I would think that just keeping 2, one for the horizontal gutter, and one for the verticle gutter would be plenty since the number if items in the gutter would normally be somewhat small.

And yah, I'm going overboard on making the collisions rock-solid. I just want to see how fast I can get it with everything ramped up.

Thanks :)

Sorry bout the huge post, the mood just takes me sometimes :)

Getting fast 100% collision detection is the holy grail. I think it's on par with good AI and can make or break a game ( Once I get killed when I know I haven't been hit I'm clicking on the next link ).

Just a quick thought about your ideas, instead of having an almost kludge fix (ie gutter arrays, multiple copies when on the boundary ) could the boundaries themselves be flexible ?

Using pac man as an example, rather than split the screen into straight quarters but split it around the ghosts ( Perhaps I should phrase it as still quarters, just not symmetrical ones ) then the additional workload could be avoided ?

One thing I've never really played with is distance checking and calculating the number of frames before the collision should occur. With that approach you could really spread the workload throughout the whole game engine ( A prime example that springs to mind is with a scroller engine. Any frame the tiles are updated ( The usual scroller._x>tileWidth type check ) all the collisions are skipped to even out the processor load ).

Squize.

PS Sorry I still haven't looked at your fla's yet. I'm kinda Flashed out at the moment.

Hey, no sweat, I'm greatful to be getting some good input :)

I don't think I am getting the movable boundries thing. You mean scooting the boundries up/down or left/right until there isn't an object crossing them, then using the resulting "quarters"? If so, that would be awsome, but I can't think of a good way to avoid all of the objects once you get a bunch of them bouncing around :/.

And yah, I didn't really expect everyone to just dive into the .fla files, seeing as how collision optimization is such a supar fun fun way to spend an afternoon, I just put them there in case someone got the urge ;).

I got the collision implimented using the quartiles + 2 gutter approach, still not sure whether or not its solid yet. The FPS improvement seems decent, albeit a little hard to gauge (jumps around alot). Alot of my added code is still pretty chunky, so I should be able to shave some more off with the next revision.

Central Collisions Using "Quartiles" - Rev 1
.html .fla .swf

And I went ahead and tried one without the gutter crap to see how much they are hurting performance...
.html .fla .swf

Later :)

Edit: Oh yah, and it looks like the delete button on the most recent versions is borked. I'll get it fixed with the next one ;).

All right, last update, I'm done *crowd cheers*

I added some timers to find the bottlenecks in the code, and ended up mading two major revisions:

1) Tightened up the quartile-crossing prediction, saved me about 5 queries per object every time it crosses a quartile barrier.

2) When queried, I changed it so the quartile arrays didn't get updated until after I was sure it actually changed (common sense I know, but I just didn't think of it the first time around).

In the end, I get a pretty consistent 10 FPS gain on my machine over the pure object based collision I had in my first post, without any loss of quality :). Thats running the .swf in the standalone player with 30 objects bouncing around.

Here are the final files, in case anyone is still paying attention to this:
Central Collisions - Final
.html .swf .fla

And here are the timers I used, for reference (will be slower):
Central Collisions - Final w/ Timers
.html .swf .fla
A "100" on the timers = 1 millesecond, a "50" = .50 milleseconds, and so on.

One thing I found interesting is that when I tried to speed up my collisions by using "while(i++<array.length)" rather than "while(i<array.length)...i++;", I actually lost an average of 2-3 milleseconds per frame in the check (meaning the collion checks took an average of 2-3 milleseconds longer per frame).

Anyway, it's been fun, thanks for the input, I'm done :D

With Central Collisions movie I get sometimes loose objects on screen that doesnt hit any other. Dont think it affects speed, but you know, maybe it does...

But for really testing speed of your routines you should use an empty graphic movieclip... or not?

This way the slow display visualization of Flash influence too much the results... or not?

I think you could see much more the differences between the various optimizations if you put an empty movie clip. Sure you cannot check that way if the collisions are working properly :D

Yah, i've noticed the miss thing, I think its a flaw in one of my collision optimizations. Basically, if 2 objects strike a third object at the very same time (in the same frame) from different angles, there is a chance that the second object won't get checked for a collision. I think its there in the original as well, its just harder to see without the numbers (the boxes blend in more).

And re: speed: Yep, if I removed all of the graphics, I should be able to gauge the raw speed of the functions. As is, I was more interested about how much of an improvement I could make, rather than how big a raw FPS I can push. I was just interested in getting both the final and the original on the same playing field, and noting the difference (the quartile numbers don't have much of an effect) ;).

You guys do get somewhat better framerates on the final, then on the original though, right?

Thanks :)

Quote:

---

Originally posted by TiefighT
You guys do get somewhat better framerates on the final, then on the original though, right?

---

Tested all of them on stand-alone player (Flash Player 6, CPU 1,7GHz, 256MB RAM, XP) 30 objects, max velocity 3

full fps 13-14
rev1 fps 19-22
rev1b fps 22-26
rev2final 23-26

I dont see much difference between rev1b and rev2final, sorry.

Quote:

---

Originally posted by tonypa
I dont see much difference between rev1b and rev2final, sorry.

---

That's what I say: you can work hard as much as you want, but if 90% of the cpu that flash uses goes for graphics you can increment and optimize only for a mere 10% (I exagerate, ok).

I mean that you should optimize, but loose weeks behind optimization and making miracles for 3 fps looks to me a bit a loss of time...

No, I'm not absolutely a guru here, but I see that flash is REALLY slow in drawing (or maybe fast, when you see how it works...) so IMHO the biggest effort should be put in graphics to make it nice BUT not heavy...

Rev1b is a trimmed down version (less collision checks), so that sounds about right as far as the difference.

The actual FPS varies a lot more from machine to machine than I would have guessed, which is good to know.

So far I know that my work machine (PIII 500MHz, 768MB RAM) gets 9-10 FPS, your machine (1.7 GHz, 256MB RAM) gets 23-26 FPS, and my home machine (Athalon+ 1.8GHz, 256MB DDR RAM) gets 36-39 FPS, all of which were running rev2final in the standalone flash 6 player w/ 30 objects.

The gap between the last two was the most surprising, I'd be curious to see exactly what component in the machine had the biggest effect...maybe that will be my next little experiment ;).

Thanks for testing it out, I appreciate it :).

Edit:
gilga: Your right, an inconsistent 3 fps gain probably wouldn't be worth it. Rev1b has to be kind of thrown out since it doesn't have as solid a collision check as the others (it doesn't register collisions if objects are overlapping the boundries between borders).

If you throw that one out, then I got about a 5 FPS gain going from a purely object based approach to a centralized approach, which took me something like 2 or 3 hours of coding and playing.

From there I got another 4 or 5 FPS gain by optimizing the centralized code, which took me around 1 hour of coding and playing.

But yes, I totally agree with you, spend your time where the bottelnecks are in your game. On that last revision I didn't even touch the actuall collision code since I was happy with it's speed, I only looked at and changed the housekeeping code, which is where the bottlenecks were. On the same note, if this were a full-blown game rather than just a coding experiment, then yah, you have to look at where the big slowdowns are coming from, and work on those, regardless of whether it is the coding, graphics, sound, etc.

Of course, you also have to take into account that the engine for the game is almost always going to be used everywhere, whereas your heavy graphics may be slowing the game down in only a couple of places. In that case spending 3 hours optimizing the engine, then an hour going through an tweaking the graphics only where they are slowing down the gameplay could give you the best results overall.

But I digress...

Thanks :)

Quote:

---

Originally posted by TiefighT
The actual FPS varies a lot more from machine to machine than I would have guessed, which is good to know.

So far I know that my work machine (PIII 500MHz, 768MB RAM) gets 9-10 FPS, your machine (1.7 GHz, 256MB RAM) gets 23-26 FPS, and my home machine (Athalon+ 1.8GHz, 256MB DDR RAM) gets 36-39 FPS, all of which were running rev2final in the standalone flash 6 player w/ 30 objects.

The gap between the last two was the most surprising, I'd be curious to see exactly what component in the machine had the biggest effect...maybe that will be my next little experiment ;).

---

Its not only about machine, its also about what programs you have open. I had several IE windows, and music player opened when I tested them.

When I close all those, fps raises to 26-30, but wont go over 30.