Several second computation in a game while maintaining 60 FPS

I've got an algorithm that takes more than several seco开发者_高级运维nds to complete. I'm trying to implement it into a 60fps flash game i'm creating. I am wondering if there is some provision in ActionScript3 to interrupt a computation in order to update the frame and continue the computation afterwards. There probably isn't, so I'm assuming the best method would be to perform the computation for x milliseconds, measure what the frame rate is after, then adjust the time the computation will run for next frame if the frame rate is less than or greater than 60 fps. The drawback with this is that the game won't run at a steady 60fps...

Any other ideas on how to (optimally) perform a large computation in AS3 while maintaining the framerate?

EDIT: For the curious (the calculation, perhaps I should have said algorithm): I'm creating a motion planning library for game AI objects (one use for motion planning). The algorithm is along the lines of a RRT (rapidly exploring random tree) that iterates thousands of times.

Demo link: http://www.swfcabin.com/open/1279044355

Click to motion plan. The circle can "thrust" at a fixed magnitude in any direction.

Also - there is no linear velocity damping (i.e. friction).

Can you do the "calculation" in stages, and then just do one stage per frame until it's done? Split it up into chunks that you know can fit into a frame, and do it over time.

A couple of examples:

One game I worked on computed line of sight between entities. It took a long time and the hardware wasn't very powerful, so we only updated the line of sight for one object each frame. The player's line of sight was updated every other frame, and the enemies were updated round-robin in the intervening frames.

If instead you're calculating something based on a large dataset, partition that data into smaller chunks and do only one chunk per frame. For instance, if you need to figure out the closest star to your ship, and there are a million stars, maybe only do a thousand per frame.

Maybe your calculation is not easily mappable to either of these; if you have an example of what you're trying to accomplish it would be very helpful!

Depending on the type of your calculation you could write a Pixel Bender Kernel that does the processing in the background using a ShaderJob:

http://www.boostworthy.com/blog/?p=243

http://www.huesforalice.com/project/47

Alternatively here is another link to a tutorial how to implement pseudo threading in Actionscript: http://blogs.adobe.com/aharui/2008/01/threads_in_actionscript_3.html

UPDATE: flash player has been supporting workers since 11.4

background workers allow to perform tasks in the background without blocking the main worker which seems perfectly suited to your needs. As a nice bonus, on multicore cpu, background workers will be able to run in parallel without slowing down the main worker

AIR mobile doesn't support workers on iOs for the moment though (AIR 4.0 & AIR 13 beta)..

Also, as already said by others, path finding should not be so long ! you should consider using another algorithm, because Rapid does not sound compatible with an algorithm that takes more than several seconds to complete. Most famous path finding algorithm is A star (A*)