Simple, Clean Algorithm Wanted

MartinRinehart

So far, I've created plenty of dirty, messy algorithms and I have no confidence that any of them is robust.

I am working on a multi-move animation controller. By multi-move I mean one which allows multiple things to move at different times, times probably overlapping so multiple things can move at once. (move = translate, rotate or scale; more for the camera).

Here's where I am: there exists a single Conductor. Things that implement an act() method are Actionables. Each Actionable instance registers a desired start and stop time with the Conductor. During the specified time, the Conductor calls each Actionable instance every frame of the movie.

Lets say that these are the Actionables and their desired start and stop seconds:

These are the seconds during which the conductor will be calling their act() methods:

seconds array.jpg

As we want the conductor to absorb as few clocks as possible, I've created a Call class. Each Call has a stop time and a list of Actionables to call. This is the list of Call objects:

calls list.jpg

The simple, clean algorithm for going from picture 1 to picture 3 is evading me.

Chris Fullmer

Its not quite clear to me what the 3rd step is. I can't follow the progression from 2 to three I guess.

cjthompson

@chris fullmer said:

Its not quite clear to me what the 3rd step is. I can't follow the progression from 2 to three I guess.

To add on to Chris's post, what is the purpose of the Call class?

if possible, could you do a fairly simple psuedo-code of your current algorithm?

MartinRinehart

@chris fullmer said:

I can't follow the progression from 2 to three I guess.

That makes two of us! I'll re-explain 3.

In second 0 there's no one to call.

In second 1 R2 gets called.

In second 2 R0 and R2 get calls.

In seconds 3 through 6, everybody gets calls.

etc.

@cjthompson said:

if possible, could you do a fairly simple psuedo-code of your current algorithm?

Conductor's job is in three phases
1) While folks are registering, just add them to the list
2) When given a start signal, get organized, then insert self as view.animation
3) When running, do minimum work to call those who need calls

Conductor's nextFrame() method (phase 3) looks like this:
each frame, increment frame
if frame is multiple of frames_per_second
increment second
if we've reached the stop second, grab the next Call
once every few seconds, check speed, adjust delay as needed
call everyone in the current Call's list
call view.show_frame( delay )

I think the call_list structure is close to minimizing the time spent in the conductor after the animation starts.

MartinRinehart

Thanks, guys. I've figured it out.

In each actionable:
def wants_call?( sec )
----return sec ( >= start ) && ( sec < stop )
end

In Conductors get_organized()

call_list = []
previous_list = []
call = Call.new( stop_sec = 1, list = [] )

find the last stop time.
Loop over each second (0..last-1).

Each second asks everyone "do you want a call this second?"

Those who say "yes" get pushed onto a list.
Is this list == previous list?
----Increment current Call's stop time.
Not equal?
----Append current call to call_list.
----call = Call.new( stop_time is this second plus one, list is the current list ).
----previous_list = this list

Done? Push last Call onto call_list.

Fast? No. Robust? Yes.

MartinRinehart

Algorithms based on looping over the registered actionables were impossible. Looping over the seconds made it a piece of cake.


    def organize() # converts list of Registrants to list of Calls
        call_ptr = 0
        @@call_list.push( Calls.new(1, []) )
        last_sec = find_last() - 1
        old_list = []
        
        for sec in 0..last_sec
            list = []
            for reg in @@registrants
                list.push( reg ) if reg.wants_call?( sec ) 
            end
            
            next_sec = sec+1
            if list == old_list
                @@call_list[ call_ptr ].stop_time = next_sec
            else
                @@call_list.push( Calls.new(next_sec, list) )
                call_ptr += 1
                old_list = list
            end
        end # seconds loop
        
    end # of organize()

thomthom

@cjthompson said:

I wonder what the insertion_point= is for.

Was this intended for another thread: http://forums.sketchucation.com/viewtopic.php?f=180&t=28450

Dan Rathbun

@martinrinehart said:

I am working on a multi-move animation controller. By multi-move I mean one which allows multiple things to move at different times, times probably overlapping so multiple things can move at once.

Have you investigated the standard Ruby library class Mutex ?

http://phrogz.net/ProgrammingRuby/tut_threads.html
... and scroll down about 3/4 of the page.

cjthompson

I wonder what the insertion_point= is for.

EDIT:

@thomthom said:

@cjthompson said:

I wonder what the insertion_point= is for.

Was this intended for another thread: http://forums.sketchucation.com/viewtopic.php?f=180&t=28450

Yeah, I think I had multiple tabs open and responded to the wrong one. sorry about that.

MartinRinehart

@dan rathbun said:

@martinrinehart said:

I am working on a multi-move animation controller. By multi-move I mean one which allows multiple things to move at different times, times probably overlapping so multiple things can move at once.

Have you investigated the standard Ruby library class Mutex ?

http://phrogz.net/ProgrammingRuby/tut_threads.html
... and scroll down about 3/4 of the page.

As always, Dan, I learn from your posts.

I tried to work my way through this chapter, but had very little luck replicating the book's results. Gave up before Mutex.