Several second computation in a game while maintaining 60 FPS

I've got an algorithm that takes more than several seconds 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!

It can be broken into chunks, but what I was trying to figure out was how to calculate how large each chunk should be. If the chunk is too big it will delay the display update - causing an FPS drop. If the chunk is too small then the calculation will take longer to finish and I'll have wasted cycles.

Mahir 2010-07-12 21:28:07

I agree with dash-tom-bang. Senocular wrote a good tutorial on exactly this issue. http://www.senocular.com/flash/tutorials/asyncoperations/

Allan 2010-07-12 22:43:41

Perfect! Exactly what I was looking for Allan!

Mahir 2010-07-12 23:24:15

Though, after actually reading the article it doesn't answer the question of finding an optimal way to break the computation into chunks. I guess I'll stick to the method I suggested.

Mahir 2010-07-12 23:38:06

Yeah. One other suggestion, depending on the nature of calculation, could you offload some/all of it to PixelBender as it runs in a separate thread. I realise that it could only work with some types of calculations but worth a shot :)

Allan 2010-07-13 02:17:42

It's actually a loop that explores the stage for a path around obstacles (but it's not a graph search because the search space is continuous) so that won't be possible. I'll see how implementing the idea I suggested in the original post goes. Seems like setting a conservative estimate on computation time then adjusting that based on the frame rate is a fail-safe idea. Perhaps I'll see 5 - 10 fps drops every so often but that's not horrible.

Mahir 2010-07-13 11:13:52

You can run a few "small" jobs up front to see how long they take, and then scale your chunk size by the time you have available for the computation. E.g. if one chunk takes 1ms to run and you have 5ms available at the end of a frame, queue up five chunks. This would depend on a constant chunk size, but generally you'll need a way to determine how long a body of work will take before you run it. This would be "easy" if you had a proper threading library available, since you could just run it at low priority and yield regularly, sleeping the main thread for the time remaining in the frame.

dash-tom-bang 2010-07-14 01:04:49

Is there any way to determine how much time you have left for computation in AS3? I have several EnterFrame event functions for each object (GameActor, EnemyObject, Bullet... and one for the overall Engine) that I don't know the order of execution. What I could do to remedy this is use the overall Engine EnterFrame handler to fire events for each of the game objects. Hmm... i'll see how this goes.

Mahir 2010-07-14 01:33:08

ansaurus

tags:

views:

answers:

Several second computation in a game while maintaining 60 FPS

related questions