Experiencing 'coders block' - particle system.

I'm having a serious brain-fart trying to write a particle system.

Goals are:

1) To be nice and modular and use an object-based programming approach.
2) Be adaptive to available resources.

I started off and got to grips with a particle system that worked very nicely, but had no upper bound on the number of particles in use at any one time, which is obviously not a good thing if the number of particles goes >200,000 because no PC is fast enough to update that many in a single frame (or even 2 or 3).

So, I tried to modify things a little and have a hard limit of 50K particles (just for testing purposes). That's where I hit my snag.

Particles are defined as a type, with positional, velocity, colour and time-to-live elements. When a particle is created, it is given a time-to-live number of milliseconds (actually, I'm just using game updates because I've not implemented delta time yet). When all particles are updated, the time-to-live is decreased, if it hits 0 the particle is not displayed.

Simple.

Simple until I want to create a new explosion effect and we already have 50K particles active. The elegant solution is to reassign the oldest (i.e. lowest time-to-live) particles to the new explosion. This would give the best visual experience using the limited number of particles available.

Doing this with custom types is proving difficult, though I'm sure it can be done very simply.

I'm sat here thinking that I should scrap the almost-elegant custom type approach and implement the whole thing using data stored in banks. I can't use arrays because the maximum number of particles in use needs to be dynamic.

Has anyone got a neat solution, or can at least bandy around some arguments for and against a particular method, or alternative way of thinking?

** EDIT: The prooblem with things at the moment is, each new effect reassigns particles, but always starts reassigning the first created particle. This is because when I for-each through the particles to update+display them, the type 'pointer' ends up back at the last particle.

What I could do with is a way to go to the nth particle. I'm guessing that the way things are stored internally is a linked-list, which precludes using anything other then a for-next to step through from the first particle to the desired one.
Code...

; particle.bb

; Particle handler for spheres.bb.

; Copyright 2005 Stefan Holmes.

; This file is part of Spheres.
;
;     Spheres is free software; you can redistribute it and/or modify
;     it under the terms of the GNU General Public License as published by
;     the Free Software Foundation; either version 2 of the License, or
;     (at your option) any later version.
;
;     Spheres is distributed in the hope that it will be useful,
;     but WITHOUT ANY WARRANTY; without even the implied warranty of
;     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;     GNU General Public License for more details.
;
;     You should have received a copy of the GNU General Public License
;     along with Spheres; if not, write to the Free Software
;     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

;-----------------------------------------------------------------------------------------------------
; Globals...

Global game.particle
 
;-----------------------------------------------------------------------------------------------------
; Types...

Type particle
	Field id%

	; Positional elements.
	Field x#
	Field y#
	Field dx#
	Field dy#

	; ## To-do: Convert to using HSL values for 'rainbow' effects.
	Field argb%

	; Control elements.
	Field edge_action%	; 0 = die at edge of screen.
						; 1 = wrap around screen.
						; 2 = bounce off screen edge.
						; ## Not actually implemented yet.
						
	Field ttl%			; Particle's time to live.
End Type

;-----------------------------------------------------------------------------------------------------
; Functions...

Function particleStart.particle()

	this.particle = New particle

;	this\id% = Handle(this)

	this\x# = Rand(10,setting\screen_width%-10)
	this\y# = Rand(10,setting\screen_height%-10)
	this\dx# = Rnd(-0.5,0.5)
	this\dy# = Rnd(-0.5,0.5)
	this\argb% = $FFFFFF00

	this\edge_action% = 0
	this\ttl% = 200

	Return this

End Function

Function particleUpdateRender(this.particle)
	LockBuffer
	For this.particle = Each particle
		If this\ttl% > 0
			If this\x# < 10 Or this\x#>(setting\screen_width%-10) Then this\dx# = -this\dx#
			If this\y# < 10 Or this\y#>(setting\screen_height%-10) Then this\dy# = -this\dy#
		
			this\x# = this\x# + this\dx# : this\y# = this\y# + this\dy#

			
			WritePixelFast this\x#,this\y#,this\argb%
			
			
			this\ttl% = this\ttl% - 1	; ## To-do: implement delta time.

		End If
	Next
	UnlockBuffer
End Function

Function explosionEffect(numparticles%,x#,y#,time%,edge%,initialradius%=1,lowestspeed#=1,highestspeed#=1.25,argb%=$00FFFF00)
	spread#=360.0/numparticles%
	offset#=Rnd(0,spread#)

	next_particle% = (next_particle% + num_particle%) Mod setting\max_particles%
	
	For i% = 1 To numparticles%

		game.particle = After game
		If game = Null Then game.particle = First particle

		j# = i% * spread# + offset#
		
		game\x# = x#+(Sin(j#)*initialradius%)	; ## To-do: Benchmark sin() against lookup-tables.
		game\y# = y#+(Cos(j#)*initialradius%)

		speed# = Rnd(lowestspeed#,highestspeed#)
		game\dx# = Sin(j#)*speed#
		game\dy# = Cos(j#)*speed#

		game\ttl% = 200

		game\argb% = argb%
	Next

End Function

setting\max_paticles% is fairly self-explanatory. setting\ is a global custom type where I store all game settings (screen res, controls etc etc).

You should use a counter variable to do this ....

global PARTICLEcurrent.particle

Function PARTICLEcreate( x, y, z, etc... )

  p.particle = PARTICLEcurrent

  p\x = x
  p\y = y
 etc....

 PARTICLEcurrent = after PARTICLEcurrent
 if PARTICLEcurrent = null PARTICLEcurrent = first particle

end function

This is how I do it anyway.

I figured that too. You'd think that would be the thing to solve it, but it ends up back at the same old problem; how to address a particular particle.

A perfect system would be to maintain a list of particles, sorted by time-to-live. Of course, that would end up using more CPU resources than rendering a few thousand extra particles, which is counterproductive. The only real way to implement that would be to store particles in a binary tree, rather than a linked-list. Even then I don't think it would be a workable method.

A reasonable system would be to store an array of particles, particle[0 - 50000] for example. All I'd have to do then is maintain an index as to which particle was the last to be assigned to an effect and to assign new particles cyclically around the array. It wouldn't be perfect, because there may be some long-lived particles 'overwritten' before some short-lived ones. Visuals would probably be acceptable though.

The only problem there is; you can't redimension an array. It's also not an elegant way of doing things (and therefore, not a good way IMHO).

What I'm trying to think of is a method whereby the oldest (or expired) particles get reassigned first, not by some complex sorted index, but by an underlying aspect of the implementation. As an analogy, you're designing an airlock door and need to ensure safety. Instead of putting in triple-redundancy and fail-safes, you use a rotating cylindrical chamber with only one opening. It can't fail and it works because there's no way it can't work.

Most people writing a particle system would perhaps not maintain an upper limit on the number of particles in use. Or they would put a hard limit in and would just not render any particles past that limit (new effects would not show up). This just isn't going to cut it for my game though, so I'm going to spend a lot of time getting this right :)

I'm going to crack out the pen and paper tomorrow and try to model the problem at its lowest level. Perhaps a solution will present itself. I'm going to go away now and sleep on it...

The sorted list might be workable, since the list will stay sorted so long as you insert particles in the correct positions, but finding the insertion points would be the tough part.

I'm thinking you could solve this by keeping an array of when your particles were going to die. To do this, you'd need to set an upper limit to a particle's time-to-live. A "cyclical" array of pointers to particles would index them by their time of death. Then, when you need to insert a particle, it's O(1) to find the correct place to put it:

insertion_point.particle = next_particle_to_die_after((current_frame + this_particle\ttl) MOD max_ttl)

Null would mean that no particle will be dying after that time and that any new particles should simply be added to the end of the list. Every frame, you'd need to clean the leading edge of the array by setting next_particle_to_die_after((current_frame + max_ttl) MOD max_ttl) = Null (yes, i know that math's redundant, but i think it better shows the intent.) Also, when you insert a particle, you'll need to update the relevant pointers in the next_particle_to_die_after array.

Ugh. I hope this makes sense. I'll see if I can code up a simple example later, as I have to run out the door now.

A totally different approach would be to replace the oldest particle in each effect in turn. This would even out where the particles came from. This method would likely involve each effect having its own linked list of particles. Effects could have "priority" values so that you might remove particles from less important effects either more often than (or in place of) particles in more important effects. You might also decide to favour removing particles from effects which use more particles than other effects. This method assumes that each effect creates particles with the same time-to-live.

I've come up with this basic framework. Not tested so may need tweaking but shows basic idea. Don't bother running it because it doesn't do anything - I've kept the code bare bones so as not to be confusing. :)

; Particle type. Note that frame_life isn't actually needed - it's only included
; and decremented every update so that we can tell how long a particle has left to live.
; If you never need to find out how long a given particle has left to live, it can be removed.
Type particleT
	Field x%,y%										; Particle's current screen coords.
	; Other fields go here.
	Field frame_life%							; Number of frames particle has left to live.
	Field next_particle.particleT	; Next particle in linked list.
End Type

Const MAX_PARTICLES%			= 10000
Const MAX_PARTICLE_LIFE%	= 60*5	; FPS multiplied by seconds.

; Array of linked lists holding ALL particles.
; Note: plist(0) is list holding all available/free particles.
Dim plist.particleT(MAX_PARTICLE_LIFE)

; Index into plist that represents the current frame. Incremented every update.
Global now_index% = 1

; Create all particles and add them to the 'free' list (plist(0)).
For n = 1 To MAX_PARTICLES
	p.particleT = New particleT
	free_particle(p)
Next

; Main loop
While Not KeyHit(1)
	If KeyDown(57)
		; Hold SPACE to continuously add new particles.
		create_particle(Rand(800),Rand(600),Rand(MAX_PARTICLE_LIFE))
	EndIf
	
	update_particles()
	draw_particles()
	Flip
Wend

End
	
	
;
; Create a new particle. The oldest one will be used if no free ones are available.
;
Function create_particle.particleT(x,y,frame_life)

	; Get a particle to use.
	If plist(0) <> Null
		; Get particle from free list.
		p.particleT = plist(0)
		plist(0) = p\next_particle
		;p\next_particle = Null
	Else
		; No free particles available so get the oldest one.
		list_index = now_index
		
		; Look forwards from now_index until we find a list containing a particle.
		; This list will hold the oldest particle(s).
		Repeat
			list_index = list_index + 1
			If list_index > MAX_PARTICLE_LIFE Then list_index = 1
			
			If plist(list_index) <> Null
				; We've found the list containing the oldest particle(s) so
				; remove the first one in the list and use that.
				p.particleT = plist(list_index)
				plist(list_index) = p\next_particle
				;p\next_particle = Null
			EndIf
		Forever
	EndIf

	; Code to initialize new particle p goes here.
	p\x						= x
	p\y						= y
	p\frame_life	= frame_life

	; Add particle to list that is required number of frames ahead of now_index.
	ahead_index = (now_index + frame_life) Mod MAX_PARTICLE_LIFE
	p\next_particle = plist(ahead_index)
	plist(ahead_index) = p
	
	Return p
	
End Function


;
; Frees a particle by adding it to the linked list of free particles (plist(0)).
;
Function free_particle(p.particleT)

	p\next_particle = plist(0)
	plist(0) = p
	
End Function


;
; Frees all particles that expire on this frame then updates all remaining, living particles.
;
Function update_particles()

	If plist(now_index) <> Null
		; Particles in this list have expired so free them.
		p.particleT = plist(now_index)
		
		Repeat
			p_next.particleT = p\next_particle
			free_particle(p)
			p = p_next
		Until p = Null
		
		plist(now_index) = Null
	End If

	; Update all living particles.
	For n = 1 To MAX_PARTICLES
		p.particleT = plist(n)
		If p <> Null
			Repeat
				; Code to update particle p goes here.
				p\x						= p\x + Rand(10)
				p\y						= p\y + Rand(10)
				p\frame_life	= p\frame_life - 1
				
				p = p\next_particle
			Until p = Null
		End If
	Next

	; Increment list index of particle(s) to be killed next time around.
	now_index = now_index + 1
	If now_index > MAX_PARTICLE_LIFE Then now_index = 1

End Function


;
; Draw all living particles.
;
Function draw_particles()

	For n = 1 To MAX_PARTICLES
		p.particleT = plist(n)
		If p <> Null
			Repeat
				; Code to draw particle p goes here.
								
				p = p\next_particle
			Until p = Null
		End If
	Next

End Function

It basically works by creating an array of particle linked lists with a global index variable (now_index) that represents the current frame. This variable is incremented (and cycles back to 1) every update. All particles in the currently indexed list have expired and so get freed.

So, to create a particle with a 10 frame lifespan, we simply add it to the list 10 positions ahead of where now_index is referencing. Thus, it takes now_index 10 updates/increments before it reaches this list and frees all the particles contained within.

Now, when we run out of particles and want to use the oldest one, we can simply walk forwards from now_index until we hit a list containing a particle. Note that by "oldest one" I mean the particle with the shortest time left to live. This may not necessarily be the particle that has been in existence for the longest time.

This system could be converted to work with delta timing, I think, but may not be great in that situation since you'd have to have linked list for each millisec of MAX_PARTICLE_LIFE. Hmmm, i'd have to think about that, tbh.

May not be exactly what you're looking for, not sure. :)

[edit] slight code update.

That's pretty interesting. Could be very handy. From first glance, it looks like it might only need a small edit to handle the case where we need to add 500 particles all with the same lifespan.

Pen and paper are coming out right now (first chance I've had to really get stuck into this today).

Thanks big10p :)

No problem - hope it's of some use. :)

Yeah, you can add any amount of particles with the same lifespan. The particles are kept in a linked list so you're not limited to just one particle per 'slot'.

[edit]I should just explain that the free_particle() function in it's current form can not be used to free an arbitrary particle prior to it's expiration. If you need this functionality, it will involve making the lists doubly-linked. I don't have the time to code this now as I have to go out, but I can do it tomorrow, if needed. Probably better anyway, as I won't be in "Sunday hangover mode" then. :P

No worries, I can grok doubly linked lists.

I got a lot done (on paper) yesterday. My head is fizzing with ideas now.

Going to get the 3D hardware to do a bit of work for some of the effects, and for the players ship and enemies.

Might consider a gameplay mode where instead of the ship spinning around, the screen does. Might be a bit OTT but I'll see how it pans out.

Thanks for your help :)

Oops! I've amended the code above to correct a bug. I had it right in the first place but I changed it at the last minute to something I thought was clever. It wasn't. :)