Make a time machine run with lower time complexity

I'm definitely no H.G. Wells, it goes to show.


Heres the issue. I've written a naive implementation of a 'Time Machine' sort of engine for my current project. It works sort of like the time reversal in Prince of Persia or Braid; by holding down a key, you can actually travel backwards in time for the previous X seconds.

Now this is a nifty thing, but I'm having trouble making it work with large numbers of objects. It works by running a loop every frame that writes to an array the properties of every single object within a qualifier group, which contains most every 'active object'. So once per frame it reads each object one at a time, and saves its X, Y, Angle, Animation, and Alterable Values to the array.

Then, when retrieving it, it simply reads backwards on the Z dimensions and sets each of the objects values accordingly. I have all sorts of other neat and complicated tricks, like saving a list of events that occured each frame which is run in reverse, etc. But that all works perfectly.

The part that DOESN'T work perfectly is the loop that SAVES the values of each object. It looks like this:
http://img26.imageshack.us/img26/3449/loop.png

It might not be immediately obvious WHAT is causing the code to go so slowly. It is this:

http://img26.imageshack.us/img26/5606/loop2.png

Actually, its also the Flag Conditions.

Heres the problem. Each time the loop runs, it wants to pick a single specific object out of all the objects. The order it picks them in isn't important, just that it picks each object a single time. But the way it is set up right now, it must run that value comparison for N^2 times, meaning 10000 comparisons for 100 objects.

This is because when the game has the object selection list, it narrows it down by comparing the D Alterable Value of each single object against the variable. That means N comparisons. But it also runs the code N times, which means N^2. So even though it could theoretically be only "N" complexity, its N^2. All I want to do is pick a single object out of the scope, but I can't think of a way to do this without comparing to ALL objects. Even the Flag events compare at N^2.

I need some sort of way to pick an Nth object from the object selection list, which doesn't use up N comparisons. As we all know, Polynomial timecomplexity is the computer killing bane of mankind. So how can I go about doing this?

I tried the "Select Object" extension, but it simply didn't work at all. Maybe someone has an example of how to use it? I tried discarding the Selecting the first X and Discarding the first X-1 objects, but that didn't work. In fact, no matter what I tried with the extension the code would never actually run no matter what, no matter what code I was using. Is there a newer version, or is it simply completely incompatible with MMF2? I know it doesn't work with qualifiers, but I even tried it with normal objects and it didn't run. Is there any similar extension or any possible way to do the same thing...?

So thats just half the battle.



The other half is less complicated; writing that many values to an array at runtime causes slowdown on its own. Its only a teeny-tiny amount of slowdown though. I'm just curious if theres any 3d array style extension I could use in place of the built in MMF2 array? Its only an issue once theres about 400+ objects, and I doubt I'd ever be over 200. But even so, thats a teeny bit of lag added on top of other teeny bits of lag. I'd prefer something that runs without microscopic time.


So uh yeah, basically, is there any way I can select a single object at a time, from a list of objects (preferably qualifiers) and run an event referencing it, hitting each object once?

Grr, I'd hate to can an engine that took me this long to make, especially one thats just this friggin awesome
Heres a video I captured of it, so you can understand what I mean (this is a much older build):
[video:youtube]http://www.youtube.com/watch?v=2DMXwEkrRgY[/video] http://www.youtube.com/watch?v=2DMXwEkrRgY

Wow that is a really awesome engine! Unfortunately, I don't know the answer to your problem, but I hope someone does, because that is a cool engine.

Actually if you want to play around with the most recent release, you can find a demo here:
http://create-games.com/project.asp?id=1431&view=news&fid=1482

It might not run nearly as fast as my current build

That is one of the coolest things I've seen come out of MMF! I love it! :grin:

By the way, it ran at minimum 50 fps on my computer the whole time, and I only have a NVidia 7150 graphics card.

Make sure you finish this engine! That is awesome!

stephen1980

Yeah, it actually runs just fine at the low amount of objects. I think theres only about 30 objects in that demo. But once you get 100+, it dies :(

I found a newer beta of the select object function, but it still doesn't work on qualifiers :( At least it speeds it up some, but this means I have to have a separate loop event for each object which increases the overhead from sheer # of loops being parsed. Grrrr.

Your method is too complex for me to understand, but if your engine is slow, maybe try HWA.

what is running slow is MMF2's object selection list

Just for the record, the Select Object extension with beta 0.9.2 I found worked like a charm, I can have 300+ objects before I notice any slowdown on my machine, and if I spread those out between different kinds I think it would be even more.

But I'm still iffy about the actual "Writing to Array" part of the code. Are there any more efficient objects then the normal MMF2 array? Because I'm talking about 2500+ 'write to array' actions per frame, which is no small fries. It could be that that is the limiting factor right now.

Quote:

---

Originally Posted by Pixelthief

Just for the record, the Select Object extension with beta 0.9.2 I found worked like a charm, I can have 300+ objects before I notice any slowdown on my machine, and if I spread those out between different kinds I think it would be even more.

But I'm still iffy about the actual "Writing to Array" part of the code. Are there any more efficient objects then the normal MMF2 array? Because I'm talking about 2500+ 'write to array' actions per frame, which is no small fries. It could be that that is the limiting factor right now.

---

i don't think many objects would be any or even a little faster if you're calling 2500 actions per frame; you'd almost be better off by offloading the entire array system (loading and setting positions etc included) into one of the scripting objects or something (one with an mmf interface), since they'd more than likely be much faster at this (as they'd let you insert all those values into the array/table simultaneously)

so you'd be dropping the num_objects * num_variables * (num_frames / second) down to what's basically num_objects * (num_frames / second)

you'd probably want to try that out with a test app, though, before you put the effort into it

EDIT: at least in my case there's a huge difference doing 30,000 function calls in mmf compared to doing the same 30,000 in lua via the mmf interface functions (5fps vs 60fps)