A new kind of loop: the P-loop!


So this almost definitely isn't a new kind of loop, except maybe to me and a few people that will read this. But I think it's cool! I'm sure somebody somewhere has thought of this, but in 15+ years of programming this technique has never occurred to me, and I've never seen it. It's legitimately neat-o!

Complicated-looking diagram showing a space ship and a lazer beam, and a lazer beam bubbles, with many labels.

Say You're Adding Particles...

A lazer beam strikes the air, crackling it and creating little bubbles of pure vacuum. EXCITING!

The lazer beam is going to extend from the space ship position Y to the top of the screen, 0. It's length, therefore, is L = |Y - 0|

Each frame of the lazer beam's update () cycle, we want to add some bubble particles. Each particle will be added at the lazer beam's X position and somewhere between the top of the screen and the space ship's position, Y.

P = new BubbleParticle ()

P.x = SpaceShip.x;

P.y = Math.random () * SpaceShip.y; // choose a point between 0..y

But How Many Particles?

Naievely, we could add 3 particles per frame, or we could add a particle every other frame. But there is a bit of a trick here, in that the beam is changing length each frame. So ideally, we'd like to add ParticleDensity * L new particles each frame.

That is, if the beam is longer, we should add more particles, in order to keep a uniform density relative to how long the beam is. If we always add the same number of particles per frame, a shorter beam will have more tightly clustered particles on it than a longer beam.

ParticleDensity = 1 / 100; // add 1 particle, per 100 pixels of lazer beam, per frame

AddBubbles = ParticleDensity * L; // L is the length of the lazer beam in pixels

for (i = 0; i < AddBubbles; ++i) AddBubble ();

The problem with this approach, is that if AddBubbles evaluates to less than 1, i.e. the lazer beam is less than 100 pixels tall, we won't add any particles at all when we should be adding maybe 1 particle per 2 or 3 frames in order to keep a consistent look.

We could ameleorate this by keeping a counter:

AddBubbles += ParticleDensity * L; // a running count, updated each frame

while (AddBubbles > 0) {

   AddBubble ();

   --AddBubbles;

}

This is my usual way of tackling this problem. Each frame, there might be a little bit "extra" left over, not enough to spawn a new particle (i.e., AddBubbles is < 1) but over three frames, let's say, it will add up to enough and we'll spawn one particle per 3 frames. Likewise, if we are supposed to spawn more than 1 particle per frame, that will be covered by this approach, too.

But Now... The P-Loop!

There is a much cooler way of making this work, that is stateless and awesome and easy, but in spite of the probably-hundreds of times I've solved this particular hitch, I hadn't seen before:

AddProb = ParticleDensity * L; // NOTE: this can be > 1! (that is the whole point)

while (Math.random () < AddProb) {

   AddBubble ();

   --AddProb;

}

2011-06-14


◀ Back