Author Topic: Particle Engine (Buffer Based)  (Read 2197 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4669
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Particle Engine (Buffer Based)
« on: January 09, 2014, 02:18:22 pm »
When I was working on the Grammer particle engine, I had an idea that I put to the side. I finally got around to testing it, and it was a bit of a success, so I will share it, even though it isn't a project.

If you have seen the Grammer particle engine, it is fast, but it gets slower as you add more particles. Eventually, after 2048 particles, it still gets almost 6FPS, but hope was that this alternative method would have speed independent of the number of particles on screen.

The trick? Instead of adding particles by pushing them on to a stack-like array of coordinates, I would use something like a graph buffer. In grayscale, we have a front buffer and back buffer. For this, we have a "fixed buffer" and a "particle buffer." When updating the LCD, these two get ORed together to show the particles superimposed on the fixed buffer.

Disadvantage:
You have to scan every pixel on the particle buffer to locate particles and move them accordingly.
Advantage:
-The particle buffer is a fixed 768 bytes and can hold up to 6144 particles (compared to 12288 bytes).
-Updating particles takes about teh same time no matter how many particles there are.
-Adding particles can be done with simple drawing commands since it is just a graphics buffer in disguise.
-Deleting particles is done with the same ease. Deleting individual particles with the other method is very slow, having to search through the buffer to locate the particle with the given coordinates.
-Performing large scale operations on a group of particles is very easy


My goal was to implement a simple rule to move down if possible, or move left/right. This is a standard rule. However, scanning each pixel individually would have been very slow. Instead, I scanned one row of pixels at a time, applying some bit logic to see which pixels can move in a given direction. This turns out to be really effective:

In fact, using a circle as the pen tool and updating the LCD cause the biggest speed bottlenecks. The number of particles on screen does not affect the speed at all since every pixel in the particle buffer is treated as a particle and has all of the transformations performed on it.

I decided to keep the pen tool as it is, but interleaving the particle updating with LCD updating gains some FPS.

Readme:
Run it with the Asm( token.
Use [ON] to exit.
Use arrows to move the cursor.
Use [2nd] to draw on the fixed buffer (makes impassable barriers).
Use [Mode] to draw particles.
Use [Del] to delete from the fixed buffer (deletes barriers).
Use [Y=]+[Up] to increase the radius of the circle.
Use [Y=]+[Down] to decrease the radius of the circle.
Multiple key presses are supported.
The F2-F5 keys shadow [up],[right],[left],[down]
15MHz is automatically set if it is supported by your calculator.
6MHz should still expect ~22FPS according to WabbitEmu.

Offline Sorunome

  • Fox Fox Fox Fox Fox Fox Fox!
  • Support Staff
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 7920
  • Rating: +374/-13
  • Derpy Hooves
    • View Profile
    • My website! (You might lose the game)
Re: Particle Engine (Buffer Based)
« Reply #1 on: January 09, 2014, 03:10:29 pm »
Why are you so good at blowing my mind o.o
Seriousley, this is looking awesome! :thumbsup:

THE GAME
Also, check out my website
If OmnomIRC is screwed up, blame me!
Click here to give me an internet!

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4669
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #2 on: January 09, 2014, 08:00:54 pm »
Hehe, thanks :) I was also thinking of a version that uses a lot more RAM (6144 more bytes) to assign each pixel a velocity for each of 8 directions. Then the particles would move based on the velocity of the air currents. It would be very slow on these calculators since I won't be able to do easy bit tricks, though :[ However this would make it easier for tools such as placing bombs, fans, and other effects. Just place the objects, and the physics do the rest. Maybe on a faster calculator I could do it.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #3 on: January 09, 2014, 09:04:38 pm »
One weird effect of storing all of the particles this way is that you can introduce biases based on the direction you loop through the field.  This probably isn't as much of a problem since you are using some bit tricks instead of simulation each pixel individually.  But I have noticed that for example if you want a lot of stacked particles to fall down, the behavior is very different depending if you loop up through the pixels or down.  If you loop down, each particle in the stack will "get in the way" except for the one at the bottom, and it will take a fair amount of time for them all to start falling, and they will also end up all spread out.  If you loop up however, this effect does not happen, since at each row, the one below it has already been simulated.  Something similar also happens if you have particles randomly moving left or right, they will tend to "drift" in one direction depending on how the looping happens.

Additionally, I would like to know how exactly the bit tricks you used to make the physics fast works?  It sounds quite tricky and awesome.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4669
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #4 on: January 09, 2014, 09:45:00 pm »
One weird effect of storing all of the particles this way is that you can introduce biases based on the direction you loop through the field.  This probably isn't as much of a problem since you are using some bit tricks instead of simulation each pixel individually.  But I have noticed that for example if you want a lot of stacked particles to fall down, the behavior is very different depending if you loop up through the pixels or down.  If you loop down, each particle in the stack will "get in the way" except for the one at the bottom, and it will take a fair amount of time for them all to start falling, and they will also end up all spread out.  If you loop up however, this effect does not happen, since at each row, the one below it has already been simulated.  Something similar also happens if you have particles randomly moving left or right, they will tend to "drift" in one direction depending on how the looping happens.

Additionally, I would like to know how exactly the bit tricks you used to make the physics fast works?  It sounds quite tricky and awesome.
Yes, that was tricky and I have worked out a method to make it move up, too, as a last priority rule. I would also like to say that the rule set I used was slightly different from the following:
Move down if possible, else choose to move left or right, randomly, else try the other direction, else do nothing.

I did:
Move down if possible, else choose to move left or right randomly, else do nothing.

I could have made it include the other step, but I decided not to for speed and it looks okay ish. The logic I did was to scan from right to left, from bottom to top. First, I OR the byte below what I am interested in with the corresponding byte on the first layer (the graph screen, non-particles). Then I invert that so that 1 bits correspond to empty spaces available for the pixels above to fall into. I AND this mask with the byte above to figure out which pixels can move down. XOR this value onto that byte to erase the particles, OR the value to the row below to draw them a space below.

To move left/right I basically shift the whole row, copying the 12 bytes to OP1, perform the masking, and see which ones may move left/right. However, you can't just go around and try the other direction again because then the pixels you just move will move again. Instead, if you want to keep a copy mask of the newly moved pixels so that when you move the other direction, you can sieve those particles out of the masking process.

To move up, I thought that the fastest way would be to write a copy of all of the unmoved particles to a new buffer, then after doing the down,left/right movements, see if the so-far unmoved pixels can move up applying similar mask logic.

Also, particles on the bottom row are automatically erased at the beginning.


The checkerboard pattern that you see is caused because of moving whole rows at a time in the same direction. If I added the ability to move in the other direction, too, this would be eliminated. If I added the ability for particles to move up as a last option, this would lead to capillary action type effects when the particles get stuck in a tube.

Offline ClrDraw

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 627
  • Rating: +61/-2
    • View Profile
    • GitHub
Re: Particle Engine (Buffer Based)
« Reply #5 on: January 09, 2014, 09:50:00 pm »
This is really cool  *.* excellent job.
Visit my GitHub for all my TI programs as well as other projects.
Also check out my website.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4669
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #6 on: January 09, 2014, 09:55:37 pm »
Thanks! I'm glad my experiment actually worked and looked decent :)

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #7 on: January 09, 2014, 11:04:10 pm »
I actually think the checkerboard looks quite nice.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4669
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #8 on: January 09, 2014, 11:54:35 pm »
Yeah, it makes a nice, unintended side effect.

Offline chickendude

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 816
  • Rating: +90/-1
  • Pro-Riot Squad
    • View Profile
Re: Particle Engine (Buffer Based)
« Reply #9 on: January 11, 2014, 04:06:47 pm »
That looks really cool, nice work Xeda :D