Particle Engines

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
Due to a comment from LongJumper in another thread, I've decided to plan out what I want my particle engine to look like. Anyone who feels they could put in their two-cents as far as using dynamic memory vs. having a big array and anything else can feel free to chime in and put stuff here. I really want to get going learning physics type stuff so I need a good base right here with my particles. If they are inefficient, I can only imagine how crappy my program will be when I'm trying to compute the collision between an octagonal convex shape and the ground.

Please put any advice, code snippets, or warnings here about particle engines, particle effects, or physics involving particles. Thanks.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #2
What you need to do is make a program similar to mine(which you can find in the Work in Progress area somewhere, entirely too lazy to get the link). It doesn't have to be super-advanced with trails and accelerated vector math, but just the basics. Try and get something to work, then play with the numbers in your program to see how they change how it looks. Expand from there. Good luck, designing and creating my particle program was the most rewarding programming experience I've ever had, even though it caused me the most headaches. (And the new Cocoa version is incredibly sexy, once I get it done)

Oh, and just a semantics issue, regardless of you are using dynamic or static memory, anytime you have multiple instances of a class/structure/data type stored in such a way you can iterate through it, it's an array. "Dynamic memory" is usually allocated to make an array, not all the time, but nearly all the time. So dynamic memory vs. having a big array is like saying: food vs. a hamburger.

The reason you use a static array(or a one-time dynamically allocated array), is so you aren't constantly creating/trashing memory. What you need to do is have a maximum number of particles and a current number of particles, when you first load the particle system into RAM, you dynamically allocate enough space to hold the maximum # of particles. Current particles is incremented as you go along, but always kept below max particles, and your update function is something like this:
Code:
while( i < currentparticles)
    if( this particle needs to be updated )
       do updates; i ++;
    else //(this particle needs to die)
       particles [i] = particles[--currentparticles];

It just takes the particle at the end of the list, and plugs it in where you want to delete the current one. Voila.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #3
I think now would be a great time to learn about data structures. If you have a list, you can add and remove certain particles at whim without having to effect the entire list. Its size is limited only to the amount of memory you have on your system, and it's never larger than you need it. I'm also a fan of having all of your particles self-sufficent. That means that once you create a particle, you just leave it alone and let it do its thing. (assuming you remember to step it each frame, that is Wink) It can also delete itself from the list when it's done.
Quote this message in a reply
Moderator
Posts: 771
Joined: 2003.04
Post: #4
Hmmm... No. The linked list would be a very bad idea ™ in this case! A fixed size array(*) is the usual approach.

*(usually a "one-time dynamically allocated array", as LongJumper indicated)
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #5
And why would it be a "very bad ideaâ„¢"? A fixed size array would not be very good for constantly changing the number of particles, since you would either need to resize it (copying all the objects) or make it humongous.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #6
I think you mean a linked list, as opposed to a "data structure", since an array is a data structure. My only issue with using a linked list is that you are doing a lot of memory management per frame. On today's computers, RAM is not going to be an issue, valuable processor time is. If you ever got to a particle system to 512 MB of RAM, you're doing something really wrong. Reserving 3MB(taking from a 10,000 particle system in my engine, at 320 bytes a piece) of your gigabyte of RAM for a ginormous particle effect isn't going to be as detrimental as maintaining a linked list in real time.

akb825 Wrote:And why would it be a "very bad ideaâ„¢"? A fixed size array would not be very good for constantly changing the number of particles, since you would either need to resize it (copying all the objects) or make it humongous.


Maybe you didn't read my post. There is no resizing, there is no copying of all the objects. It is not humongous. Here it is in action, 10.3.9 required.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #7
I mean it would be useful to learn about data structures in general, and a linked list would be one data structure that would be useful for this project. I don't see why it would be so detrimental to maintain a linked list. Iterating through a linked list would be only marginally slower than iterating through an array. Moving the pointers around for an insertion or deletion is only a few assignments. It's also easier and quicker to have a list of particles at 10,000 and then add 5,000 more than to have an array of 10,000 particles, decide you need more, so you get a new array, copy all the old elements, then add the 5,000 more.

Edit: (in regard to your edit Rasp) Your particle system has a set maximum, than does everything based on that. With a linked list, you don't need to set a maximum (unless you want to), and you can reach as high or low as you want without using up way more memory than you need. (might as well not waste it when you don't have to) Also, a linked list is more versatile for adding things other than particles. For example, I'm creating a game engine that's basically revolving around a linked list. It contains all the objects sorted from back to front so alpha blending is as accurate as possible.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #8
It would be pure idiocy to create a particle system not knowing how many particles you will have at max.

You're going to tell me that calling new or malloc, then filling in data, a few hundred times in a frame is faster than just filling data into already allocated memory, not to mention the amount of delete calls that you wouldn't have to deal with a couple hundred times a frame as well?
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #9
First of all, it depends on the format of your particle system. I'm thinking of a particle system where you create maybe a 10 a second, and they last a few seconds. Also, I'm thinking about a more dynamic system, where you'd have several particle systems integrated into a larger project. For doing many many thousands of particles in one system where you know how many you would have, it would be faster with your method. For constantly changing numbers of systems with changing numbers of particles, I think a more dynamic system such as utilizing a linked list with self-sufficient particles would be more practical.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #10
I think you're preaching to the wrong choir about this one.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #11
Sneaky

I kinda assumed that this particle system was more for a part of a larger, more dynamic system.
Quote this message in a reply
Moderator
Posts: 133
Joined: 2008.05
Post: #12
That's really not what I meant. I think you should click on that link I put a few posts up.

Or this one:
http://www.idevgames.com/forum/showthread.php?t=9637
Or maybe this one:
http://www.idevgames.com/forum/showthrea...ge=2&pp=15

Regardless, I'm going to bed.
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #13
Yes, I know about your particle writer. I'm talking about what Nick wants to do.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #14
I'm just working on stuff for my engine. I need to get to physics but I need a solid particle down before I move to something involving shapes. If I can't control points, I'm not going to be able to handle boxes.

And I have made particle engines before using a static array. They work just fine. I wasn't aware of all the downsides of using the dynamic memory (for this anyway). I could just go ahead and use a static array.

But onto more about particle engines, how do you (personally) code things like explosions, fountains, and other effects? My explosions (I just used a lot of colored particles, not textures) were just a lot of particles created in one frame and released the next so they all move at the same time. For fountains and such, I created a timer of sorts that said "let it emit particles for X amount of time, then stop it". What approaches do you take?
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #15
Im not sure how good an idea this is but it seems pretty cool in my head. Im going to implement it later anyway so If it works super ill tell you!
My idea is too have the particle engine split in two, if the distibution is too large. That way you have a bounding box of predefined size to detect your collisions in. The customisation of the bounding box will im sure allow you to fine tune the particles to run really fast.

edit: But do have some bounding box optimisation methods of some form, because other wise it will be s l o w.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  osg::Particle how to change de texture of each particle zinbawe 1 2,982 Jul 14, 2009 12:46 AM
Last Post: DoG
  Particle groups unknown 4 3,324 Nov 4, 2005 10:27 AM
Last Post: Zekaric
  How to do (2D) Particle Systems? Taxxodium 8 5,651 Oct 21, 2002 04:16 PM
Last Post: w_reade