Best data structure for particles?

Monkey Forums/Monkey Programming/Best data structure for particles?

Anatol

(Posted 2011) [#1]

Hi,

I'm still quite new in Monkeycode and game development, so as much as this is about getting to the results I want to achieve using Monkeycode it is also about my own learning process.

From a more experienced game developer's perspective, what would be the best data structure for particles? Stacks, lists or maps? The diddy module uses the (diddy) ArrayList for its particle system.

I found a related post at http://www.monkeycoder.co.nz/Community/posts.php?topic=1314 but it's not yet clear to me.

I tested particles with a slightly modified version of this simple particle engine http://www.monkeycoder.co.nz/Community/posts.php?topic=395 that uses a list and groups particles with a 'z' value. Results are looking good, but I'm uncertain if constantly adding/removing nodes will not create problems later on.

Also, based on the simple particle engine above, I wonder if it's best to have one global list/map/stack/ArrayList that contains all particles (grouped) (e.g. Global allMyParticles:List<Particle> = New List<Particle>), or to use separate data structures for each particle group (something like Field snowFlakes:List<Particle> = New List<Particle> and Field rainDrops:List<Particle> = New List<Particle>).

I might eventually just use diddy, but I'd really like to understand.

Any hint and opinion would be greatly appreciated.

Cheers!
Anatol

matty

(Posted 2011) [#2]

I find that using arrays of objects works efficiently - and when removing an element simply swapping it with the last array element and then resizing the array down by 1 element...and when adding simply resizing the array up by 1 element and putting the new element at the end of the array...

I've made quite a few programs and have not had a problem with speed on any of them yet (in Flash or Android).

JIM	(Posted 2011) [#3]

Arrays of objects work best because they're very cache-friendly. Once the first element is read from memory, a whole buffer comes along with it and that usually includes the next few elements (in this case particles). That reduces costly memory fetches.

Also, make sure to use a pool to avoid resizing the array. This means using a fixed length array and reusing elements in it. Like matty said, except the resizing part.

For example: have an array of 2048 particles. Then have something like iCrtParticleCount that starts as 0 and increments up to a maximum of 2047. Each time you want to remove a particle, swap it with the one at index "iCrtParticleCount" and then decrement the count.

Samah

(Posted 2011) [#4]

The diddy module uses the (diddy) ArrayList for its particle system.

Yes, the sprite-based one does. Take a look at the implementation I used for Diddy's extended particle system.
The ParticleGroup class is basically a series of parallel arrays (one for each field), with two arrays for indexed pointers. The pointers use the swapping technique outlined by matty.

If you have 10000 particles and 10 fields, it's much more efficient to have 10 arrays of size 10000 than 10000 objects with 10 fields. No preallocation needed, and less objects created (only 10). In theory, less objects should give the GC an easier time. Note that the Diddy particle system has a LOT of fields due to all the colour interpolation stuff.

http://code.google.com/p/diddy/source/browse/trunk/src/diddy/psystem.monkey

Anatol

(Posted 2011) [#5]

Thank you all very, very much. It makes a lot more sense to me now! Each comment contributed a lot. As matty said, arrays and swapping particles seems to work best. Then particle pools as suggested by JIM to avoid resizing improves performance. Lastly I had a good look at Samah's diddy sample code that uses arrays for each field such as x and y position, etc., to avoid particle objects (see http://code.google.com/p/diddy/source/browse/trunk/src/diddy/psystem.monkey#1712 ), which at least theoretically I believe performance-wise this is another improvement.

I quickly wrote a simplified test code that's based on the comments and the diddy code above. With a larger amount of particles it already runs much smoother than my previous attempts.

This is not the code I'll eventually use (especially the swapping in RemoveParticle could be nicer) but it helped me to understand how it works. I might just use diddy instead.

Strict

Import mojo

Function Main:Int()
	New ArrayTest
	Return 0
End

Class ArrayTest Extends App
	Field particles:ParticleGroup
	
	Method OnCreate:Int()
		SetUpdateRate(60)
		Local numParticles:Int = 10000
		Local particleImagePath:String = "particle.png"
		particles = New ParticleGroup(numParticles)
		For Local i:=0 Until numParticles
			particles.AddParticle(particleImagePath, Rnd(0, DeviceWidth()), Rnd(0, DeviceHeight()), Rnd(-5, 5), Rnd(-5, 5))
		Next
		Return 0
	End
	
	Method OnUpdate:Int()
		particles.Update()
		Return 0
	End
	
	Method OnRender:Int()
		Cls()
		particles.Render()
		DrawText("alive particles: " + particles.aliveParticles, 0, 0)
		Return 0
	End
End

Class ParticleGroup
	Field particleImage:Image[]
	Field x:Float[]
	Field y:Float[]
	Field speedX:Float[]
	Field speedY:Float[]
	Field dieOffScreen:Bool[]
	Field aliveParticles:Int
	
	Method New(maxParticles%=10000)
		particleImage = New Image[maxParticles]
		x = New Float[maxParticles]
		y = New Float[maxParticles]
		speedX = New Float[maxParticles]
		speedY = New Float[maxParticles]
		dieOffScreen = New Bool[maxParticles]
	End
	
	Method AddParticle:Void(imagePath$, _x#, _y#, _speedX#, _speedY#, _dieOffScreen?=True)
		If aliveParticles < x.Length
			particleImage[aliveParticles] = LoadImage(imagePath,,Image.MidHandle)
			x[aliveParticles] = _x
			y[aliveParticles] = _y
			speedX[aliveParticles] = _speedX
			speedY[aliveParticles] = _speedY
			dieOffScreen[aliveParticles] = _dieOffScreen
			aliveParticles += 1
		EndIf
	End
	
	Method RemoveParticle:Void(index%)
		aliveParticles -= 1
		' swapping the last particle in the 'aliveParticles' range with the one that should be deleted
		particleImage[index] = particleImage[aliveParticles]
		x[index] = x[aliveParticles]
		y[index] = y[aliveParticles]
		speedX[index] = speedX[aliveParticles]
		speedY[index] = speedY[aliveParticles]
		dieOffScreen[index] = dieOffScreen[aliveParticles]
	End
	
	Method Update:Void()
		For Local i:=0 Until aliveParticles
			x[i] += speedX[i]
			y[i] += speedY[i]
			If dieOffScreen[i] And ( x[i] < 0 - particleImage[i].Width()/2 Or x[i] > DeviceWidth() + particleImage[i].Width()/2 Or y[i] < 0 - particleImage[i].Height()/2 Or y[i] > DeviceHeight() + particleImage[i].Height()/2 ) Then RemoveParticle(i)
		Next
	End
	
	Method Render:Void()
		For Local i:=0 Until aliveParticles
			DrawImage(particleImage[i], x[i], y[i])
		Next
	End
End

Thank you very much, everyone!

Cheers!
Anatol

dave.h

(Posted 2011) [#6]

Hi guys
ive been reading your posts and its been very helpfull.Ive put together a very basic particle emitter with gui interface.Its not as fast as samahs and i hope you dont mind me posting it here mate..You can alter the particles properties and choose from several different particles.Im getting big differences with different platforms but i think if i work at it then it will get better.

http://www.gamecentaur.com/free-monkey-stuff.html

Samah

(Posted 2011) [#7]

Hey dave, that looks pretty cool. :)
I've been working on an editor for the Diddy particle system in C#, but it's really tricky due to all the colour interpolation stuff.

dave.h

(Posted 2011) [#8]

@samah

are you trying to fade from one color to another with that.Ive got no idea how to go about that.I even thought about setcolor but thats an absolute non starter due to performance hits.If i keep my effects simple it works really well but colour interpolation is a bit out of my comfort zone yet.I hope you suss it though.

Samah

(Posted 2011) [#9]

@dave
Basically you give it a start and end colour and it changes from one to the other over the course of the particle's life. The Diddy particle system supports RGB and HSL (both of which are available in the default Windows colour dialog).