Small flash program I made, could use some help.

[VijchtiDoodah]

I wrote a quick flash program in AS3 just for fun. I wanted to see if I could program flocking behavior.

But there are some obvious performance issues. At most, I can only get about 17fps, which is still slow enough to be visible. And every 500ms a procedure is called that dramatically destroys the frame rate, so my program looks like it has a pulse. These problems become significantly worse when the .swf is embedded on any page.


The part where I ask for your help:
Is there anyone knowledgeable enough in Actionscript 3.0 to look at the code and suggest some performance improvements specific to the language? Or anyone who might have some general coding advice once I describe how the code works?

The biggest problems right now are two functions that together find the closest n objects to any other (let's call those objects birds, since that's what they should represent). Essentially, the distances between each bird and every other is calculated. Then, for each bird the n minimum distances between it and every other bird are found. The positions and velocities of those closest n birds are then used to set the velocity and heading of the original bird.

All of this is handled by a superclass that represents a collection of all birds. The function to find the distances is called once every step (by some odd quirk that I haven't figured out yet, this is faster than using it only when needed). The function to find the minimum distances and to set a new heading is a loop that runs for each of the 100 birds every 500ms.

There are only two alternatives I can think of: either limit calculations to specific tiles and their neighbors, and I'd rather not if I don't have to, or only process the minimum distances for a fraction of the birds each step. Someone also suggested using a binary heap to find the minimum distances, but I can't figure out what he meant by that and I can't see how it might be more efficient.

Let me know what you think, coding gurus.

[12th_account]

I don't understand why you are constantly performing distance calculations each step if you only change the heading once every 500 ms. Couldn't you just calculate the smallest n distances between other birds every 500 ms?


If I did this myself, my first thought would be to divide the surface into, say, 10x10 tiles and store bird sets as values in either a hash table with each tile object as a key or a 2D-array with the tile's XY-coordinates as indexes. As a bird files over a new tile, assign that bird to the set associated with that tile.

Now when you look for the closest n birds, first look for them in the current tile. If you haven't found n birds yet then expand the search to the neighboring tiles, and continue expanding until you've found n birds.

This way you don't need to perform n^2 distance calculations.

[VijchtiDoodah]

I don't understand why you are constantly performing distance calculations each step if you only change the heading once every 500 ms.

Yeah, that's the strange quirk I was talking about. For some reason, calculating the distance every 500ms slows the entire thing down. But forcing it to calculate the distances more often boosts the fps. I spent an hour or two trying to figure out exactly why that would happen. It makes no sense.

Your tile idea is almost exactly what I was talking about as an alternative method. I just don't want to code for it if I don't absolutely have to. Though I'm beginning to think that it may really be the best option at this point (unless someone can explain what benefit a binary heap might be and how to implement it).

This way you don't need to perform n^2 distance calculations.

It's actually n(n-1)/2 distance calculations. n² distance calculations would be calculating the distance between each bird and every other twice. It's the old cocktail party handshake problem.

Thanks for the input.

[chutem]

May or may not help, but if you do a quick check to see if either the distance in the x or y dimension is greater than the minimum, then you don't need to use pythag to find the exact distance.

Also, a binary heap will be of no use, as the distances keep changing...

Btw, I couldn't view the flash on the site you linked to.

[Toumaz]

The first thing that comes to mind is creating a kd-tree to solve the neighbour problem. It probably takes even more effort than implementing Skoskav's solution, but it could be worth a shot. Here is a post mentioning and to a certain extent explaining why and how the author is using a kd-tree in his boids implementation, in case it would be of any help.

I don't know enough about the boids algorithm to know if it would be feasible and you might be doing this already, but unless you strictly need the actual distance between two boids, calculate the squared distance instead and sort based off of that. Calculating the square root is relatively expensive in terms of performance.

[VijchtiDoodah]

May or may not help, but if you do a quick check to see if either the distance in the x or y dimension is greater than the minimum, then you don't need to use pythag to find the exact distance.

I don't know enough about the boids algorithm to know if it would be feasible and you might be doing this already, but unless you strictly need the actual distance between two boids, calculate the squared distance instead and sort based off of that. Calculating the square root is relatively expensive in terms of performance.

These are great suggestions. I'll implement them as soon as I get home from work. They're so simple, I'm especially surprised that I never considered chutem's idea. Edit: haha...now I remember. I never programmed a minimum distance. I didn't like the idea of a lonely bird just flying straight, so all birds always find their closest neighbors, no matter how far away they are. Thank you for the suggestion anyway, chutem, I might find somewhere else to use it.

Chutem, I've attached a zip file with a quick .html and the .swf I've embedded in it. You're going to end up seeing this thing running with better performance than anyone else is getting since you'll have it stored locally.

Toumaz, I've actually been purposely avoiding reading about or copying anything from any of the other ubiquitous flocking simulations. And, after watching the one you linked to, I'm glad I haven't. Mine has much more interesting movement.

That being said, I'm still interested in that kd-tree idea. I suppose it was only inevitable that I'd turn to one of the existing flocking simulations for help at some point.

Thanks, guys.

[PANZERCATWAGON]

i would just like to say as a programming fresher that i think what you have coded is pretty awesome even despite the frame rate problem. nice work man you should be proud

[chutem]

After seeing the swf in action, it appears that the framerate decreases the longer it is playing. I never got too far into the depths of programming, but from what I have picked up, wouldn't this indicate a memory leak?

Also some pointers if you want to go for a more 'traditional' flocking algorithm:

The birds don't react to other birds being too close. Also, I posted my suggestion, as usually the birds don't base their decisions on the n closest birds, rather, all birds within n distance.

Basic rules that work well here, I came across another more in depth article recently, wish I could find it now.

[VijchtiDoodah]

After seeing the swf in action, it appears that the framerate decreases the longer it is playing. I never got too far into the depths of programming, but from what I have picked up, wouldn't this indicate a memory leak?

It takes some amount of work to get a memory leak in AS3. All garbage handling is automatic, so the instant a variable becomes inaccessible it is put on a list of objects eligible for garbage collection (and garbage collection is run whenever flash decides it's necessary).

However, my program actually runs progressively faster for about the first 10 or 15 seconds until the birds reach a more stable, concentrated pattern (from about 8fps to 17fps). At least it does on the few computers I've tested it on. Yours might be a strange case.

Also some pointers if you want to go for a more 'traditional' flocking algorithm:

Not that I don't appreciate your suggestions, but I don't want to do that.

The flocking models I've seen look unrealistic to me. They aren't nearly dynamic enough. For example, in most flocking models the birds are perfectly comfortable sitting next to each other in a semi-rigid pattern or are at least in some sort of obvious dynamic equilibrium. In mine, however, there is a nice little lag between the times each bird checks it's position relative to all other birds, so they might suddenly realize that they're too close to another bird and, as a result, violently fling themselves away. Then, as a consequence of the fact that my birds choose the n closest birds instead of all birds in a given neighborhood, the nearest birds in the flock may be significantly pulled in the direction of that one outwardly mobile bird. If enough birds do this in quick succession, the flock will split and travel on its own for a while (as long as the various constants describing flock behavior are set to allow this to happen).

That's why I'm staying away from the more "traditional" approach. I have a few interesting ideas to add to the model to make it a bit more realistic (such as setting up a dynamic social hierarchy that determines the strength of following behavior, or having the front bird's heading be much more variable to allow for the kind of rapid flock turning that you see in any field), but it's going to require a drastic boost in performance or else the new code will slow down the program too much.

i would just like to say as a programming fresher that i think what you have coded is pretty awesome even despite the frame rate problem. nice work man you should be proud

Thanks.