Particle Array...

BlitzMax Forums/BlitzMax Programming/Particle Array...

Yahfree

(Posted 2008) [#1]

Hey, I'm trying to get an array based on the "auto defragmenting array"

Here's the method, (a quote from ImaginaryHuman):

One thing you can try is what I call a `auto-defragmenting array`. You keep a counter of how many items are stored in the array - ie defined particles. This starts at 0. When you add an item you add it at the counter position and then add 1 to the counter. When you remove/kill an item, instead of trying to wipe it out or delete it you copy the item at position `Count-1` to overwrite the item you are deleting, and then subtract 1 from Count. In other words you're taking the item from the top end of the defined items and moving it to fill the gap created by the item you want to remove. The benefit of this is you then can loop from 0 to Count-1 and you'll know that there are no gaps and you don't have to detect dead objects. You really want to avoid having to skip over stuff if you can. One downside is that because you are defragmenting the space and keeping it compact, any kind of `sort order` goes out the window and your particles become somewhat random order. Presumably since particles move all over the place you probably don't usually care that this happens. The only issue might be that the user sees one particle suddenly jump in front of another.

This will be used in my particle engine to (hopefuly) boost speeds. My particle engine is mathematicly updated in C++, and basicly, feeds info into blitzmax to draw the particles. I've taken a whack at this, and it's causing some really wierd behavior.

C++ code, save as "cParticle.cpp" in the same dir as the bmx source.

#include <math.h>
#define DEGREE_TO_RADIAN 0.0174532925199432957692369076848861

//Functions to grab a Radian sin/cos not in degrees.
double Sin2( double ang ){
	return sin( ang*DEGREE_TO_RADIAN );
}
double Cos2( double ang ){
	return cos( ang*DEGREE_TO_RADIAN );
}

// All the stuff that can be accessed in bmax
extern "C" {

    // our particle class
    class cParticle {
    public:
          // all the variables associated with a particle
          float x;
          float y;
          float a;
          int r;
          float dx;
          float dy;
          float da;
          int maxdistance;
          float speed;
          int dir;
          int fade;
          int z;
          
          // constructor (AKA Create())
          cParticle(float, float, int, float, int, bool, bool, int);
          // destructor have not found a use yet
          ~cParticle();
          
          //Update particle
          void Update(float, float, float, float); 
    };
    
    // Our class functions redefined:
           
    // constuctor
    cParticle::cParticle(float _x, float _y, int _dir = 0, 
                               float _speed = 0, 
                          int frames = 1, bool _fade = false, 
                          bool _autorot = false, int _z = 0) {
                
  		z = _z;
		x = _x;
		y = _y;
		speed = _speed;
		dir = _dir;
		dx = (Sin2(dir) * speed); 
		dy = (-Cos2(dir) * speed);
		da = 1.0 / frames;
		a = 1.0;
		maxdistance = frames;
		if(dir > 0&&_autorot > 0){
			r = dir;
		}

		if(_fade > 0) {
			fade = true;
        }
                               
    
    }
    //destructor
    cParticle::~cParticle() {
        
        // code for destructor
    }      
    
             
    void cParticle::Update(float ax,float ay,float fx, float fy) {
		dx = dx+fx;
		dy = dy+fy;
		x=x+dx+ax;
		y=y+dy+ay;
		if( fade == true ) { a=a-da; }
		maxdistance--;
    }
    
    
    // mainsteam functions:
                 
    // Wrap function to create a particle
    cParticle *cCreateParticle(float _x, float _y, int _dir = 0, 
                               float _speed = 0, 
                          int frames = 1, bool _fade = false, 
                          bool _autorot = false, int _z = 0) {
         cParticle *p; // particle that we will return
         p = new cParticle(_x, _y, _dir, 
                           _speed, frames, 
                           _fade, 
                           _autorot, _z); // basicly shove the arguments of this function into a constructor
         return p;
    }
    
    //Wrap function to delete a particle
    void cDeleteParticle(cParticle *p) {
         if (p != 0) { delete p; }
    }
    
    //Wrap function to update a particle
    void cUpdateParticle(cParticle *p, float ax, float ay, float fx, float fy){
         if (p != 0){ p->Update(ax, ay, fx, fy); }
    }
    
    //functions to get various states of a particle
    float cPX(cParticle *p) {
         if (p != 0){ return p->x; }
    }
    float cPY(cParticle *p) {
         if (p != 0){ return p->y; }
    }
    float cPA(cParticle *p) {
         if (p != 0){ return p->a; }
    }
    int cPR(cParticle *p) {
         if (p != 0){ return p->r; }
    }
    int cPLife(cParticle *p) {
        if (p != 0){ return p->maxdistance; }
    }
}

bmax code:

Import "cParticles.cpp"


'Wrap functions from the particle C++ code
Extern "C"
	Function cCreateParticle:Byte Ptr(_x:Float, _y:Float, _dir:Int = 0, _speed:Float = 0, frames:Int = 1, _fade:Int = False, _autorot:Int = False, _z:Int = 0)
	Function cUpdateParticle(p:Byte Ptr, ax:Float, ay:Float, fx:Float, fy:Float)
	Function cDeleteParticle(p:Byte Ptr)
	Function cPX:Float(p:Byte Ptr)
	Function cPY:Float(p:Byte Ptr)
	Function cPA:Float(p:Byte Ptr)
	Function cPR:Int(p:Byte Ptr)
	Function cPLife:Int(p:Byte Ptr)
End Extern


'TParticle type, basicly a wrapper w/ drawing functions for the class counterpart.
Global ParticleList:TParticle[10000]
Global pCount:Int

Type TParticle
	Field img:TImage 'particle img...
	Field cBuddy:Byte Ptr 'the handle for our c++ counterpart.
	Field z:Int 'an 'ID' that we call on to give us seperate drawing abilities
	Field pos:Int 'position within the particle array
	
	Method Create:TParticle(_x:Float, _y:Float, _img:TImage, _dir:Int = 0, _speed:Float = 0, frames:Int = 1, _fade:Int = False, _autorot:Int = False, _z:Int = 0)
		'create a "c" particle and give it's handle to the cbuddy variable
		cBuddy = cCreateParticle(_x, _y, _dir, _speed, frames, _fade, _autorot, _z)
		'Add some given arguments to the object
		img = _img
		z = _z
		alive = True
		'Add this object to the particle list
		pos = pCount
		ParticleList[pCount] = Self
		pCount:+1
	End Method
	
	Method Update(addx:Float, addy:Float, forcex:Float=0, forcey:Float=0)
		'Update the "c" particle if the cparticle is real
		If cBuddy <> Null 
			cUpdateParticle(cBuddy, addx, addy, forcex, forcey)
			'Grab the new x/y positions of the "c" particle(so we only have to use this function once per loop)
			Local x:Float = cPX(cBuddy)
			Local y:Float = cPY(cBuddy)
		
			'check for conditions for destroying a particle
			If cPLife(cBuddy) = 0 Or x > GraphicsWidth()+ImageWidth(img) Or x < 0-ImageWidth(img) Or y > GraphicsHeight()+ImageHeight(img) Or y < 0-ImageHeight(img)
				Destroy()
				Return
			End If
			'Draw the given img at the "c" Particle's locations 
			SetAlpha cPA(cBuddy)
			SetRotation cPR(cBuddy)
			DrawImage img,x,y
			SetAlpha 1
			SetRotation 0
		End If
	End Method
	
	Method Destroy()
		If cBuddy <> Null cDeleteParticle(cBuddy) 'destroy C++ counterpart if the cparticle is real
		ParticleList[pos] = ParticleList[pCount-1] ' copy newest particle onto dead particle
		pCount:-1 ' drop count by 1
	End Method
	
End Type


Rem
bbdoc: Particle update routine
about: Updates particles at said Z level, you can add a optional force routine for things such as gravity.
returns: Nothing
EndRem
Function UpdateParticlesZ(z:Int = 0, addx:Float = 0, addy:Float = 0, forcex:Float = 0, forcey:Float = 0)
		For Local i:Int = 0 Until pCount
			If ParticleList[i].z = z
				ParticleList[i].Update(addx, addy, forcex, forcey)
			End If
		Next
End Function

Rem
bbdoc: Particle creator
about: Creates a particle at said point with said attributes
returns: Nothing
EndRem
Function EmitParticle(_x:Float, _y:Float, image:TImage, frames:Int, fade:Int = True, dir:Int = 0, speed:Float = 0, ar:Int = False, _z:Int = 0)

	Local part:TParticle = New TParticle.Create(_x, _y, image, dir, speed, frames, fade, ar, _z)

End Function


'-----------------------------------------------------------------------------------
'main program
'-----------------------------------------------------------------------------------

Graphics 800,600
SetBlend LIGHTBLEND

AutoMidHandle True
Local dot:TImage = CreateImage(10,10)
DrawOval 0,0,10,10
GrabImage dot,0,0


While Not KeyHit(KEY_ESCAPE)
	Cls
	
	If MouseHit(1) EmitParticle(MouseX(), MouseY(), dot, 240)'ParticleExplosion(MouseX(),MouseY(),dot,50,80,2)
	UpdateParticlesZ()
	
	DrawText pCount,0,0
	Flip 1
Wend
End

I'm almost 100% certain the problem isnt with the C++ code, as it worked fine with a TList version of this code, it's something to do with the bmax side of things.

Thanks in advance for any help!

ImaginaryHuman

(Posted 2008) [#2]

Hi :-)

The technique mentioned is quite simple and unless you really didn't grasp it or implemented in some peculiar way I would be surprised if it is causing your problems.

An example:

Graphics 640,480,32
Const MaxParticles:Int=100000
Local ParticleX:Float[MaxParticles]
Local ParticleY:Float[MaxParticles]
Local Counter:Int=0
Local Item:Int
Repeat

   Cls
   DrawText Counter + " particles",0,16
	
   'Check for adding a new particle - overwrite the highest new element
   If MouseDown(1) And Counter<=MaxParticles
      'Add particles
      ParticleX[Counter]=MouseX()
      ParticleY[Counter]=MouseY()
      Counter:+1
      DrawText "Added a particle",0,32
   EndIf

   'Check for subtracting a particle - overwrite the deleted particle
   'by copying the highest particle on top of it
   If MouseDown(2) And Counter>0
      'Subtract particles
      Local ToRemove:Int=Rand(0,Counter-1) 'Pretend to delete at random
      DrawLine ParticleX[ToRemove]-10,ParticleY[ToRemove]-10,ParticleX[ToRemove]+10,ParticleY[ToRemove]+10
      DrawLine ParticleX[ToRemove]-10,ParticleY[ToRemove]+10,ParticleX[ToRemove]+10,ParticleY[ToRemove]-10
      ParticleX[ToRemove]=ParticleX[Counter-1]
      ParticleY[ToRemove]=ParticleY[Counter-1]
      Counter:-1 'Dont even need to delete the old data, just copy it
	  DrawText "Subtracted a particle",0,32
   EndIf

   'Little test to wiggle the particles
   For Item=0 Until Counter
      ParticleX[Item]:+Rand(0,2)-1
      ParticleY[Item]:+Rand(0,2)-1
   Next

   'Draw the particles
   For Item=0 Until Counter
      Plot ParticleX[Item],ParticleY[Item]
   Next
   Flip 1
Until KeyHit(KEY_ESCAPE) Or AppTerminate()

You'll notice in my little demo that when you press the right mouse button particles are deleted and an X is drawn to show which one is deleted. I added randomization as to which particle that would be, but you could easily subtract them in any order you like, like from the top of the array down.

So basically you keep track of how many particles you stored in the array(s) so far - that's your counter, it starts at 0. When you insert a new particle you insert it at the position stored in the counter and then add 1 to the counter - provided there's still space in the array. When you want to delete a particle, you copy whatever is the particle at counter-1 and use it to overwrite whatever is stored at the particle you're deleting.

So if you have an array with space for 100 particles and so far you've stored 25 particles, counter will be 26. If you want to delete particle 11 you copy particle 26-1 (25) on top of particle 11 and subtract 1 from the counter.

I haven't really looked at your code to tell if this is what you're doing but anything you're doing beyond the scope of what I just explained is probably not really to do with this technique and more perhaps to do with how you've implemented it, or some other extra feature you've added?

Sorry I don't undertand C++ code, that's why I program in BlitzMax ;-)
I hope this helps.

Yahfree

(Posted 2008) [#3]

well, not looking at the C++ code, can you explain why the particles in my example are like jumping all over the screen? I think it has something to do with the deleting/creating routine.

Also your example doesn't run, dup. identifier on line 34

ImaginaryHuman

(Posted 2008) [#4]

I recoded it so try it again. I cannot help with C++ code and I don't see anything obvious in your blitz code.

Yahfree

(Posted 2008) [#5]

Updated the bmax code... still has the same problem..

Imaginary:

The C++ code is fine, I just threw it up so people can run the example.

also, the problem in depth:

If you create one particle and leave it at that, the particle acts fine, but if you create a particle(B) while particle A exists, A disipears, and when B dies, it brings A back to life.

The main changes that may be causing the problem are:

.
.
.
.
'TParticle type, basicly a wrapper w/ drawing functions for the class counterpart.
Global ParticleList:TParticle[10000]
Global pCount:Int
.
.
.
.
.
	Method Create:TParticle(_x:Float, _y:Float, _img:TImage, _dir:Int = 0, _speed:Float = 0, frames:Int = 1, _fade:Int = False, _autorot:Int = False, _z:Int = 0)
.
.
.
.
		'Add this object to the particle list
		ParticleList[pCount] = Self
		pos = pCount
		pCount:+1
	End Method
.
.
.
.
.
	Method Destroy()
		ParticleList[pos] = ParticleList[pCount-1]
		pCount:-1 ' prep bmax particle for overwriting
.
.
.

	End Method
.
.
.
.
.

ImaginaryHuman

(Posted 2008) [#6]

One thing I noticed is that you are storing the `position of the particle in the array`into the variable `pos` within each instance of your particle type. That means that when you delete a particle by overwriting it with the particle from count-1, you also have to then go into that moved particle and update its `pos` value to point to the current overwritten array index.

Otherwise you're going to get `pos` variables pointing to slots that they don't really occupy, ie they will point to the slot they were copied from, and then when you go to remove them they will try to move objects backwards from the slot they're in to the slot they were copied from - this might account for why your objects disappear and then come back to life.

When you destroy your particle it needs to say:

ParticleList[pos]=ParticleList[pCount-1]
ParticleList[pos].pos=pos '(or could be ParticleList[pos].pos=Self.pos)
pCount:-1

That's all I could think of which might be messing with your code.

Yahfree

(Posted 2008) [#7]

hmm, that still didnt do the trick... wierd... updated the bmax code

ImaginaryHuman

(Posted 2008) [#8]

Maybe your C++ code has an issue then?

Yahfree

(Posted 2008) [#9]

the C++ code works fine with TLists, is there any other methods of doing this? I should try those

ImaginaryHuman

(Posted 2008) [#10]

It can't be the method it must be your implementation of the method. Sorry, I mean, this technique is really simple, so it must be that you've coded it in a weird way. I suggest you get back to basics. If it works with TLists then it should be very easy to convert it to array-based.

Where you have:
Local part:TParticle = New TParticle.Create(_x, _y, image, dir, speed, frames, fade, ar, _z)

Shouldn't it be:
Local part:TParticle=TParticle.Create(....

without the `New`, given that the new instance is being created by the Create routine? Otherwise it looks like you're creating it twice? ie you should have a line within your Create() function which actually creates the new instance, and then returns it? Your creation function doesn't appear to return anything. Unless you're somehow creating a blitzmax instance within the C call? It just looks weird to see you trying to create a new particle at the same time as call its create method

Also in your destroy routine, you refer to `Self.pos` to set the pos for the particle you just moved, but after you've overwritten the reference to the dead particle - the garbage collector could potentially have wiped out your old particle given that once you overwrite it there is nothing pointing to it to keep it alive. If it were me I'd ignore the dead particle and just store its pos in a temporary variable like ThisPos=Pos, and then after you overwrite it you set pos=ThisPos.

Yahfree

(Posted 2008) [#11]

Ok, I think i found the problem, when I was updating the particles I was updating "pCount-1" not "i"

Seems to work, but now I'm getting some unhandled memory exception errors. I have an idea on how to solve it, I think it's because it's trying to update a dead C++ pointer

ImaginaryHuman

(Posted 2008) [#12]

Cool man.

Yahfree

(Posted 2008) [#13]

updated the code, now i'm having some problems with the particles not deleting?

it's pretty wierd...

like if you create a bunch of particles slowly, its fine, but if you click really fast you get some wierd bugs..

any ideas?