Board index » cppbuilder » algorithm design needed for analyzing probabilities

algorithm design needed for analyzing probabilities


2006-08-18 12:35:33 PM
cppbuilder8
I'm not sure where else to post this. I have a need for a custom algorithm
to analyze probabilities, but I can't work out how best to begin it.
This is for an animation rendering engine that I am writing. And before you
ask, no the design of the animations cannot be changed. I'm writing a
player that displays animations from a third-party file format. Let me give
you a summary how how the animations work.
Each animation is composed of a list of frames, each containing a bitmap
image and a duration. Each frame can optionally also contain a list of 1-3
"branches" that specify the probability of the next frame to be played in
the sequence, based on how many times the frame containing the branches has
been played. When a frame is played, its image is displayed, and then a
timer waits the specified duration before playing the next frame.
Frame branches can skipping frames, reuse shared frames, and loop back on
each other. This way, lengthy and complex animations can be created by
defining alternative playback paths under different scenerios, producing
visual variations each time the same animation is played. The total
percentage for a frame must add up to <= 100%. If the branch list is empty,
or the total percent adds up is 0%, the next frame in the animation's frame
list is played.
For example, lets say that Frame #5 has 3 branches that specify Frame #6 is
played 50% of the time, Frame #7 is played 30% of the time, and Frame #10 is
played 20% of the time. Since Frame #6 has the highest percentage, it is
played more often, but the other frames can be played randomly at reduced
priorities, where Frame #7 is played slightly more often then Frame #10.
Another example, lets say Frame #12 has 1 branch that specifies Frame #20 is
played 100% of the time. Frames #13-19 are always skipped when Frame #12 is
played (other frames may branch to those frames later on).
Another example, lets say Frame #2 has 1 branch that specifies Frame #5 is
played 25% of the time. Frames #3-4 would be skipped 25% of the time, and
Frame #3 would be played the other 75% of the time.
One last example, lets say Frame #1 has 2 branches that specify Frame #2 is
played 50% of the time, and Frame #20 is played the other 50%.
What I need is an algorithm that can decide, based on the number of
available branches in a given frame, which frame is going to be played next
in the animation, repeating for each frame until the last frame is reached
or the animation is stopped.
I hope I explained this clearly enough.
Gambit
 
 

Re:algorithm design needed for analyzing probabilities

"Remy Lebeau (TeamB)" < XXXX@XXXXX.COM >wrote in message
Quote
I'm not sure where else to post this. I have a need for a custom
algorithm to analyze probabilities, but I can't work out how best
to begin it.
Nevermind, I found something that will work for now. Basically, I fill an
array of 100 elements and then pick a random entry. If a frame has branches
for Frame 1 at 50%, Frame 2 at 30%, and Frame 3 at 20%, I fill the array
with 50 1's, 30 2's, and 20 3's (in that order). This way, the higher the
percentage for a given branch, the more array entries will have the
cooresponding frame number in them.
I'd still be interested in hearing what others think about it, though.
Gambit
 

Re:algorithm design needed for analyzing probabilities

Remy Lebeau (TeamB) wrote:
Quote
I'm not sure where else to post this. I have a need for a custom algorithm
to analyze probabilities, but I can't work out how best to begin it.

This is for an animation rendering engine that I am writing. And before you
ask, no the design of the animations cannot be changed. I'm writing a
player that displays animations from a third-party file format. Let me give
you a summary how how the animations work.

Each animation is composed of a list of frames, each containing a bitmap
image and a duration. Each frame can optionally also contain a list of 1-3
"branches" that specify the probability of the next frame to be played in
the sequence, based on how many times the frame containing the branches has
been played. When a frame is played, its image is displayed, and then a
timer waits the specified duration before playing the next frame.

Frame branches can skipping frames, reuse shared frames, and loop back on
each other. This way, lengthy and complex animations can be created by
defining alternative playback paths under different scenerios, producing
visual variations each time the same animation is played. The total
percentage for a frame must add up to <= 100%. If the branch list is empty,
or the total percent adds up is 0%, the next frame in the animation's frame
list is played.

For example, lets say that Frame #5 has 3 branches that specify Frame #6 is
played 50% of the time, Frame #7 is played 30% of the time, and Frame #10 is
played 20% of the time. Since Frame #6 has the highest percentage, it is
played more often, but the other frames can be played randomly at reduced
priorities, where Frame #7 is played slightly more often then Frame #10.

Another example, lets say Frame #12 has 1 branch that specifies Frame #20 is
played 100% of the time. Frames #13-19 are always skipped when Frame #12 is
played (other frames may branch to those frames later on).

Another example, lets say Frame #2 has 1 branch that specifies Frame #5 is
played 25% of the time. Frames #3-4 would be skipped 25% of the time, and
Frame #3 would be played the other 75% of the time.

One last example, lets say Frame #1 has 2 branches that specify Frame #2 is
played 50% of the time, and Frame #20 is played the other 50%.

What I need is an algorithm that can decide, based on the number of
available branches in a given frame, which frame is going to be played next
in the animation, repeating for each frame until the last frame is reached
or the animation is stopped.

I hope I explained this clearly enough.


Gambit
Maybe I missed something, but it seems easy: you pick a random number
between 0 and 100, and then add branch probabilities until add>=
number. The last branch probability added is the one to take. If they
don't add up to number you jump to the next frame in sequence. This
includes the cases "branch list empty" and "total percent < 100%"
Best regards
Miguel Gimenez
 

{smallsort}

Re:algorithm design needed for analyzing probabilities

Sample code to show my approach:
int i, n, sum;
n = 1+random(100);
for (i = 0, sum = 0; (i < NumBranchs) && (sum < n); ++i)
sum += Branch[i].Probability;
return (i == NumBranchs ? CONSECUTIVE_FRAME : Branch[i].Frame);
Best regards
Miguel Gimenez
 

Re:algorithm design needed for analyzing probabilities

"Miguel Gimenez" < XXXX@XXXXX.COM >wrote in message
Quote
Sample code to show my approach:

int i, n, sum;

n = 1+random(100);
for (i = 0, sum = 0; (i < NumBranchs) && (sum < n); ++i)
sum += Branch[i].Probability;

return (i == NumBranchs ? CONSECUTIVE_FRAME : Branch[i].Frame);

Elegant. But don't you want:
for (i = 0, sum = 0; (i < NumBranchs); ++i){
sum += Branch[i].Probability;
if (sum>= n)
break;
}
otherwise you'll never take Branch[0]
--
Bruce
 

Re:algorithm design needed for analyzing probabilities

"Miguel Gimenez" < XXXX@XXXXX.COM >wrote in message
Quote
you pick a random number between 0 and 100, and then add
branch probabilities until add>= number. The last branch
probability added is the one to take. If they don't add up to
number you jump to the next frame in sequence. This includes
the cases "branch list empty" and "total percent < 100%"
Very interesting. I like it. It is a little bit smaller than the algorithm
I came up with last night:
USHORT BranchArray[100] = {0};
int idx = 0, PercentAvailable = 100;
for(BYTE i = 0; i < NumBranches; ++i)
{
USHORT Probability = Branches[i].Probability;
USHORT FrameIndex = Branches[i].Frame;
for(USHORT j = 0; j < Probability; ++j)
BranchArray[idx++] = BranchIndex;
PercentAvailable -= Probability;
}
for(int i = 0; i < PercentAvailable; ++i)
BranchArray[idx++] = (CurrentFrame + 1);
USHORT NextFrame = BranchArray[random(100)];
if( (NextFrame == 0xFFFF) || (NextFrame == CurrentFrame) )
NextFrame = (CurrentFrame + 1);
Gambit
 

Re:algorithm design needed for analyzing probabilities

Remy Lebeau (TeamB) wrote:
Quote
I'd still be interested in hearing what others think about it, though.
This will definitely work. Another option is to have as many bins as
there are branches. Each bin contains the probability of its branch,
plus the previous branch's probability. You generate a random number
from [0, 100) and see what bin its value lands in. Based on that you
pick a branch.
For example, you have 3 branches with probabilities 50, 20 and 30. You
create 3 bins with the following values.
50, 70, 100
You generate 65, take second branch.
The main advantage of this approach is memory saving (and maybe some
initialization time is shorter).
.a
 

Re:algorithm design needed for analyzing probabilities

"Alex Bakaev [TeamB]" < XXXX@XXXXX.COM >wrote in message
Quote
Another option is to have as many bins as there are branches.
Each bin contains the probability of its branch, plus the previous
branch's probability. You generate a random number from [0, 100)
and see what bin its value lands in. Based on that you pick a branch.
I think that is essentially the same approach that Miguel suggested, only he
used a loop to add the probabilities together instead of using bins.
Gambit
 

Re:algorithm design needed for analyzing probabilities

Remy Lebeau (TeamB) wrote:
Quote

I think that is essentially the same approach that Miguel suggested, only he
used a loop to add the probabilities together instead of using bins.
So his suggestion is less efficient, eh? :)
 

Re:algorithm design needed for analyzing probabilities

"Alex Bakaev [TeamB]" < XXXX@XXXXX.COM >wrote in message
Quote
So his suggestion is less efficient, eh? :)
Well, if you can show a more efficient implementation than what he showed,
I'll use it ;-)
Gambit
 

Re:algorithm design needed for analyzing probabilities

Remy Lebeau (TeamB) wrote:
Quote

Well, if you can show a more efficient implementation than what he showed,
I'll use it ;-)

There is no addition in my method ;)
.a