Ultimate Particle Engine v1.20

This bundle is marked as pending. It has not been reviewed by a staff member yet.
Ultimate Particle Engine

Ultimate Particle Engine (UPE) is a heavily-modified version of the Particle Party physics engine. The ability to mediate long-range interactions has been removed to increase performance. In its place, many new features have been added.

UPE is a versatile engine, allowing the user to define and create new particles easily, handle their movement, acceleration, and check for collisions between those particles. Particles can represent bullets, fireballs, shockwaves, vehicles, and much more. By tethering particles to units, you can enable collision checks between units and particles, units and other units, apply knockbacks, or create slippy terrain among other.

The engine supports 2D and 3D movement and collision checks, although not all 3D-features are implemented yet.

With collision functions, you can easily determine the code that will be executed when a particle collision is detected.

This is version 1.0. Bugs are bound to occur. I will update the engine with bug-fixes and finish 3D-features soon™.


Documentation

vJASS:
/**************************************************************************************************
		U L T I M A T E   P A R T I C L E   E N G I N E   V 1.11
				created by Antares
***************************************************************************************************

Ultimate Particle Engine (UPE) is a heavily-modified version of the Particle Party physics engine,
created by Antares.

UPE is a versatile engine, allowing the user to define and create new particles easily, handle their 
movement, acceleration, and check for collisions between those particles. By tethering particles to 
units, you can enable collision checks between units and particles, units and other units, and
apply knockbacks, slippy terrain among other.

The engine supports 2D and 3D movement and collision checks, although not all 3D-features are
implemented yet. I will implement those features on request.

With collision functions, you can easily determine the code that will be executed when a particle 
collision is detected.

UPE uses variable intervals for collision checks to reduce computation load. Each time collision
is checked, the engine estimates a time period in which a collision is very unlikely to occur and
checks for collision only after that period. For lower particle numbers, the intervals can be set
low enough that errors never occur, but for high particle numbers a compromise between accuracy and
performance must be made.

UPE uses special effects to display particles, allowing for more and easier customization than units,
improving performance at low particle numbers, but at the cost of performance at high particle numbers,
as natives cannot be used for distance checks. Effect arrays for particles are possible. I will 
implement them on request.

===================================================================================================
Changelog:
===================================================================================================
V1.20
-Made use of vJASS function interface feature to for particle functions.
-Added additional documentation.

V1.11
-Mitigated the effect of a bug that disabled collision checks.
-Added more comments to particle struct.

V.1.1
-Increased performance of particles.
-"par" globals are now initialized.
-Fixed an oversight that caused projectiles to miss each other after rolling over uneven terrain.


***************************************************************************************************

				H O W   T O   I N S T A L L :

Copy all components of the engine into your map in the same order:
-engine parameters
-collision func declaration
-particle type declaration
-other func declaration
-particle struct

All components have a single library wrapper. You may copy these components into a single trigger,
if you prefer.

All components inside blocks delimited by

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
and
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

can be edited. Variables inside these blocks can be changed. Functions inside these blocks can be 
edited or removed. All other components should not be changed unless you know what you're doing.

***************************************************************************************************

				G E T T I N G   S T A R T E D :

This test map contains various examples of particle classes and interactions. In the test function,
look at how particles are created. Make yourself familiar with how particles behave when you test
the map. There are different methods for creating different particle classes: CreateProjectile, 
CreateStationary, CreateSimple, and CreateTethered.

For each of these functions, there's a regular and a 3D version. 3D functions require you to
declare z-starting-position and z-velocity, while those parameters are set to 0 if the regular 
version is called.

The last argument in the particle creator functions determines the particle type. Particle types are
defined in "particle type declaration (PTD)." This list allows you to predefine certain charactistics 
of particles. By default, only collision radius, as well as collision, movement, and death functions 
are defined in PTD. Other characteristics, such as the visual effect are defined after each instance 
of the particle is created, as can be seen in this test map.

This distinction is somewhat arbitrary and you may choose to define all the characteristics of your
particles in PTD or on a per-instance basis.

In PTD, you see that for many particle types, various functions are declared. These are collision
functions, conditionfunc arrays which determine the code that is executed when particle of type A and 
particle of type B collide with each other. You find these under collision func declaration.

You can also define ground collision functions in PTD. These functions determine the code that is
executed when an airborne particle of type A collides with the ground. These are only relevant with
3D enabled and are also found under collision func declaration.

You can also define death functions, which are executed upon destruction of a particle of type
A. These are found under other func declaration.

Lastly, you can define movement functions, which are executed everytime the particle is moved by
the engine. These are also found under other func declaration.

***************************************************************************************************

				F U N C T I O N   D E C L A R A T I O N :

When the engine detects that two particles that have a collision function set are closer than the
sum of their collision radii, a trigger is evaluated and calls the appropriate collision function.
The two colliding particles can be referenced with the "triggerPar" and "collidingPar" globals.

Since it is, for all intents and purposes, random which particle gets assigned which variable, if 
the collision function is for two particles of different types, you have to make sure that the 
particles are refered correctly. You can do this with the function:

SwitchParticles takes particle A, particle B returns nothing

Ground collision functions, death functions, and movement functions also refer to the triggering
particle with "triggerPar".

This test map contains a number of example functions of each type. You can use or remove these
functions as you please.

***************************************************************************************************

				P A R T I C L E   C L A S S E S :

A particle class determines how the particle is treated by the engine.

Stationary particles, created with "CreateStationary" are ignored by the automatic movement function.
You can still teleport them by changing their position coordinates manually.

Simple particles, created with "CreateSimple" and projectiles differ in how collision checks are 
performed. For simple particles, it is assumed that their movement is erratic and can change at any 
moment. Therefore, the code checks for collisions with all other particles at intervals that increase 
in frequency as particles get closer. In addition, the engine attempts to register all sudden 
accelerations of simple particles and expedite collision checks when a particle is suddenly 
accelerated towards another.

Projectiles, created with "CreateProjectile" are assumed to move with a constant speed in one 
direction until they are either reflected or destroyed. This allows the engine to exactly determine 
the time when the two particles collide, if both are either projectiles or stationary. The downside 
is that the engine must recalculate completely everytime one of the particles' velocities change. For 
that reason, use projectiles with caution and never apply constant acceleration to a projectile. 

Note: Projectiles are not yet particularly optimized and 3D-projectiles are not yet implemented fully.

Tethered particles, created with "CreateTethered", are linked to a unit, refered to as the "host".
This allows to simply check for particle collisions with units, such as bullets or fireballs hitting
a unit, but it also allows to apply, for example, knockbacks to that unit.

The link between the particle and the unit can work in either direction, or in both directions. If
the particle is linked to the unit, it will always follow to the position of the unit whenever it
moves. If the unit is linked to the particle, the unit's own movement will be completely ignored,
and it is completely subject to the movement of the tethered particle. If the link is applied both
ways, the unit can move, but can also feel the forces acted on the tethered particle, as seen
in this test map.

Tethered particles can be projectiles, but use this with caution (it is safe on buildings for example).

***************************************************************************************************

					A P I :

===================================================================================================
As described above. "destroyOnHostDeath" determines whether the particle is destroyed upon death of 
the host unit. If set to false, the particle must be  destroyed manually. If set to true, a new 
particle must be created if the unit is revived.
===================================================================================================
static method CreateSimple takes real x, real y, real vx, real vy, integer particleType returns particle
static method CreateStationary takes real x, real y, integer particleType returns particle
static method CreateProjectile takes real x, real y, real vx, real vy, integer particleType returns particle
static method CreateTethered takes unit whichUnit, integer particleType, boolean particle2Unit, boolean unit2Particle, boolean destroyOnHostDeath returns particle

static method CreateSimple3D takes real x, real y, real z, real vx, real vy, real vz, integer particleType returns particle
static method CreateStationary3D takes real x, real y, real z, integer particleType returns particle
static method CreateProjectile3D takes real x, real y, real z, real vx, real vy, real vz, integer particleType returns particle
static method CreateTethered3D takes unit whichUnit, integer particleType, boolean particle2Unit, boolean unit2Particle, boolean destroyOnHostDeath returns particle


====================================================================================================
Will destroy the particle on the next computation step.
====================================================================================================
method Destroy takes nothing returns nothing

====================================================================================================
With these functions, add a visual effect to the particle or change its appearance. By default, 
particles have no visual effect.
====================================================================================================
method operator Visual= takes string effectPath returns nothing
method operator VisualScale= takes real scale returns nothing
method operator VisualTimeScale= takes real timeScale returns nothing
method operator VisualAlpha= takes integer alpha returns nothing
method SetVisualColor takes integer red, integer green, integer blue returns nothing
method operator VisualColorByPlayer= takes player whichPlayer returns nothing
method operator VisualYaw= takes real yaw returns nothing
method operator VisualPitch= takes real pitch returns nothing
method operator VisualRoll= takes real roll returns nothing
method operator VisualZ= takes real zOffset returns nothing
method operator OrientVisual= takes boolean orientVisual returns nothing
method DestroyVisual takes nothing returns nothing

====================================================================================================
Tether a particle to a unit, change the direction of the links, or change the host. GetTetheredParticle 
returns the last particle that was tethered to a unit (if you ever tether more than one).
====================================================================================================
method Tether2Unit takes unit whichUnit, boolean particle2Unit, boolean unit2Particle returns nothing
method Untether takes nothing returns nothing
static method GetTetheredParticle takes widget whichWidget returns particle

====================================================================================================
Change particle classes after creation.
====================================================================================================
method operator IsStationary= takes boolean isStationary returns nothing
method operator IsProjectile= takes boolean isProjectile returns nothing

====================================================================================================
Add friction to a particle. This is especially useful for tethered particles. Linear friction is
proportional to velocity, while constant friction is not.
====================================================================================================
method SetFriction takes real linearFriction, real constantFriction returns nothing

====================================================================================================
Bind an airborne particle to the ground. During ground collision, you must call this if you wish for 
the particle to remain on the ground.
====================================================================================================
method SetGroundBound takes nothing returns nothing

====================================================================================================
Loops over all particles and executes the callback function for each of them. The particle must be 
refered to as "enumPar" in the callback function.
====================================================================================================
static method ForAllInRange takes real x, real y, real z, real dist, code callback returns nothing
static method ForAllOfType takes integer particleType, code callback returns nothing
static method ForAllOfTypeInRange takes real x, real y, real z, real dist, integer particleType, code callback returns nothing

====================================================================================================
Changes the collision radius of a particle after creation. This is a slow function. Do not use with 
abandon!
====================================================================================================
method operator CollisionRadius= takes real newRadius returns nothing

====================================================================================================
Enable or disable collision checks between two particles. By default, particle pairs that do not have 
a collision function have disabled collision checks.
====================================================================================================
static method EnableInteraction takes particle P1, particle P2 returns nothing
static method DisableInteraction takes particle P1, particle P2 returns nothing

====================================================================================================
Immediately checks collisions between a particle and every other particle. This should be called after 
you significantly displace a particle, change its collision radius significantly, or do anything else 
drastic. This will cause significant lags and overload the engine if used too often! Must not be called 
from within collision functions (use a 0.01s timer instead).
====================================================================================================
method ForceUpdate takes nothing returns nothing

====================================================================================================
Pauses the engine timer or resumes it. Tethered units will be able to move freely again while the 
engine is paused.
====================================================================================================
static method SleepAll takes boolean doSleep returns nothing

====================================================================================================
Destroys all particles on the next computation step.
====================================================================================================
static method DestroyAll takes nothing returns nothing

====================================================================================================
You may change the position coordinates, velocities, and acceleration of particles directly. Velociy 
and acceleration are in units per computation step. To transform to and from units per second, use 
UPE_NormV, UPE_DenormV, UPE_NormA, and UPE_DenormA.
====================================================================================================
real x
real y
real z
real vx
real vy
real vz
real ax
real ay
real az



***************************************************************************************************

				E N G I N E   P A R A M E T E R S :
	
	Name							  Default value

====================================================================================================
Time between engine computation steps.
====================================================================================================
	public constant real TIMESTEP_PARTICLES 			= 0.03

====================================================================================================
If set to true, destroyed particles are removed immediately from the list that the engine loops 
through, but their struct instances persist for PARTICLE_DESTRUCTION_DELAY. This is useful if you 
have functions on periodic timers that need those particles.
====================================================================================================
	public constant boolean DELAY_PARTICLE_DESTRUCTION		= true
	public constant real PARTICLE_DESTRUCTION_DELAY			= 1

====================================================================================================
Enable movement in z-direction. Disable to make the code faster.
====================================================================================================
	public constant boolean INCLUDE_3D				= true

====================================================================================================
Enable if your map has surface elevations. Disable to make the code faster.
====================================================================================================
	public constant boolean INCLUDE_SURFACE_ELEVATIONS		= true

====================================================================================================
Constant acceleration of all airborne particles in -z-direction. Set to 0 to disable.
====================================================================================================
	public constant real SURFACE_GRAVITY				= 0.5

====================================================================================================
Maximum bounds of particle movement. This prevents particles from escaping into infinity and therefore 
"leaking".
====================================================================================================
	public constant real PARTICLE_BOUND_RIGHT			= 2500
	public constant real PARTICLE_BOUND_LEFT			= -2500
	public constant real PARTICLE_BOUND_TOP				= 2500
	public constant real PARTICLE_BOUND_BOTTOM			= -2500

====================================================================================================
If set to true, particles will be reflected on maximum bounds. If set to false, they are destroyed.
====================================================================================================
	public constant boolean REFLECT_PARTICLES_ON_BOUNDS		= true



====================================================================================================
UPE has a hard particle limit of 180. This is due to the maximum array size in JASS.
(180 = SquareRoot(32768) - 1. PM me if you need more particles, I can add more arrays.
====================================================================================================

***************************************************************************************************

					D E B U G :

====================================================================================================
The following parameters are useful for debugging the engine.
====================================================================================================



	Name							  Default value

====================================================================================================
Create a short-lived lightning effect between two particles whenever collisiom is checked between them. 
This will spam the entire map with a sea of lightning effects, so the next parameters allow you to 
limit the effects to be more useful.
====================================================================================================
	public constant boolean VISUALIZE_INTERACTIONS			= false

====================================================================================================
Show only lightning effects for particles that are closer than a distance cutoff.
====================================================================================================
	public constant real VISUALIZATION_DISTANCE_CUTOFF		= 700

====================================================================================================
Show only lightning effects for a single particle. This particle must be set with "debugPar".
====================================================================================================
	public constant boolean VISUALIZE_SINGLE_PARTICLE		= false

====================================================================================================
Show a special effect whenever a particle is accelerated enough to be registered by the acceleration 
detection.
====================================================================================================
	public constant boolean VISUALIZE_ACCELERATION_DETECTIONS	= false

====================================================================================================
Continuously prints out the number of collision checks and the interval increase.
====================================================================================================
	public constant boolean PRINTOUT_COMPUTATIONS			= false

====================================================================================================
Whenever the thread of the main function crashes, for example, due to a bug in the engine, a bad 
collsion function, or a division by zero, a warning is displayed that informs that the thread has 
crashed and where it has crashed. Thread crashes should be avoided at all costs. There is a recovery 
function that prevents the engine from being corrupted after a thread crash, but it is not tested 
for this version of the engine. It may be a good idea to leave this parameter on, even in the release 
version of the map.
====================================================================================================
	public constant boolean FUNCTION_CRASH_WARNINGS			= true

****************************************************************************************************



		C O L L I S I O N   C H E C K   P A R A M E T E R S



Learning the effect of and adjusting these parameters is only necessary if you're attempting to 
push the engine to its limits.



====================================================================================================
The following parameters influence the intervals of collision checks between non-projectile particles. 
By adjusting these parameters, you avoid particles missing each other due to no check being queued, 
while also straining the engine as little as possible. 
====================================================================================================



	Name							  Default value

====================================================================================================
The maximum interval between two collision checks.
====================================================================================================
	public constant integer MAXIMUM_INTERVAL			= 89

====================================================================================================
A higher INTERVAL_FACTOR increases the overall frequency of collision checks.
====================================================================================================
	public constant real INTERVAL_FACTOR				= 350

====================================================================================================
Particles that are moving towards each other have more frequent collision checks. This constant 
determines the strength of this increase.
====================================================================================================
	public constant real INTERVAL_VELOCITY_FACTOR			= 7

====================================================================================================
Enable whether the velocity of particles should be monitored for sudden changes and expedite collision 
checks accordingly.
====================================================================================================
	public constant boolean ENABLE_ACCELERATION_DETECTION		= true

====================================================================================================
Minimum acceleration that needs to be detected before collision checks are expedited. If set too low, 
the slow ExpediteUpdate function will be called too often. If set too high, particles might miss each 
other when one is accelerated suddenly.
====================================================================================================
	public constant real UPDATE_ACCELERATION_THRESHOLD		= 10

====================================================================================================
...Ok, there's not really a way to dumb down what this constant does to a few lines and it make sense.
If you really need to know what this does, PM me.
====================================================================================================
	public constant real UPDATE_ACCELERATION_FACTOR			= 0.0033

====================================================================================================
Over how many steps the acceleration check integrates. If set too low, the engine will react to too 
many minor changes in velocity. If set too high, the engine might react too slowly.
====================================================================================================
	public constant integer STEPS_PER_ACCELERATION_CHECK		= 1

====================================================================================================
Only factor in x- and y-movement during acceleration checks.
====================================================================================================
	public constant boolean ACCELERATION_DETECTION_IGNORE_Z		= true



====================================================================================================
These constants limit the engine and prevent it from overloading and/or slowing down the game due to 
its high CPU requirements. If the number of collision checks exceeds COMPUTATION_LIMIT, the engine 
will add an additional step to each interval. This may occur any number of times.

Note that CPU performance is not the only factor in setting the computation limit. The engine writes
the timestep at which the next collision check is performed for a pair of particles into an array.
This array can be viewed as a 2D-array in which the columns represent the timestep, and the rows are
filled with particle pairs. The array needs MAXIMUM_INTERVAL + 1 columns, so the number of rows is
limited to 32768 / (MAXIMUM_INTERVAL + 1) (= 364 with default parameters.) If all 364 rows of the
array are filled, a particle pair must be placed in the next column, delaying its collision check.
It is best to avoid this by setting the computation limit below that number (multiplied by
COMPUTATION_STEPS).

As a result, increasing MAXIMUM_INTERVAL can paradoxically overload the engine more as the maximum
number of pairs per column decreases.
====================================================================================================

	public constant integer COMPUTATION_LIMIT			= 3500

====================================================================================================
If the engine exceeded the computation limit, the interval increase will relax again when the number 
of computations falls below this number.
====================================================================================================
	public constant integer COMPUTATION_RELAX_THRESHOLD		= 2200

====================================================================================================
Over how many steps the computation limit check integrates. If set too low, the engine will react to 
too many minor spikes in collision checks. If set too high, the engine might react too slowly.
====================================================================================================
	public constant integer COMPUTATION_STEPS			= 10



***************************************************************************************************/



library UPE initializer Init

globals
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Set parameters here that influence the engine behavior.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	
	//=============================================================================
	//Main parameters.
	//=============================================================================
	
	public constant real TIMESTEP_PARTICLES 			= 0.03
	public constant boolean DELAY_PARTICLE_DESTRUCTION		= true
	public constant real PARTICLE_DESTRUCTION_DELAY			= 1
	public constant integer MAXIMUM_INTERVAL			= 89

	public constant boolean INCLUDE_3D				= true
	public constant boolean INCLUDE_SURFACE_ELEVATIONS		= true
	public constant real SURFACE_GRAVITY				= 0.5

	public constant real PARTICLE_BOUND_RIGHT			= 2500
	public constant real PARTICLE_BOUND_LEFT			= -2500
	public constant real PARTICLE_BOUND_TOP				= 2500
	public constant real PARTICLE_BOUND_BOTTOM			= -2500
	public constant boolean REFLECT_PARTICLES_ON_BOUNDS		= true

	//=============================================================================
	//Debug.
	//=============================================================================

	public constant boolean VISUALIZE_INTERACTIONS			= false
	public constant real VISUALIZATION_DISTANCE_CUTOFF		= 800
	public constant boolean VISUALIZE_SINGLE_PARTICLE		= true
	public constant boolean VISUALIZE_ACCELERATION_DETECTIONS	= false
	public constant boolean PRINTOUT_COMPUTATIONS			= false
	public constant boolean FUNCTION_CRASH_WARNINGS			= true

	//=============================================================================
	//Collision check interval parameters.
	//=============================================================================

	public constant real INTERVAL_FACTOR				= 8000
	public constant real INTERVAL_VELOCITY_FACTOR			= 70
	public constant boolean ENABLE_ACCELERATION_DETECTION		= true
	public constant real UPDATE_ACCELERATION_THRESHOLD		= 10
	public constant real UPDATE_ACCELERATION_FACTOR			= 0.0033
	public constant integer STEPS_PER_ACCELERATION_CHECK		= 1
	
	//=============================================================================
	//Computation limit parameters.
	//=============================================================================
	
	public constant integer COMPUTATION_LIMIT			= 3500
	public constant integer COMPUTATION_RELAX_THRESHOLD		= 2200
	public constant integer COMPUTATION_STEPS			= 10
	
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	//End of engine parameter declaration.
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<



	//=============================================================================
	//Derived constants.
	//=============================================================================
	public constant integer PARTICLE_LIMIT				= 180
	public constant integer STEPS_PER_CHECK_CYCLE			= MAXIMUM_INTERVAL + 1
	public constant integer MAXIMUM_PAIRS				= 32768 / STEPS_PER_CHECK_CYCLE
	public constant integer MATRIX_SIZE				= PARTICLE_LIMIT + 1
	public constant real UAT2					= UPDATE_ACCELERATION_THRESHOLD*UPDATE_ACCELERATION_THRESHOLD
	public constant integer MI2					= STEPS_PER_CHECK_CYCLE*STEPS_PER_CHECK_CYCLE
endglobals

	public function NormV takes real velocity returns real
		return velocity*TIMESTEP_PARTICLES
	endfunction

	public function DenormV takes real velocity returns real
		return velocity/TIMESTEP_PARTICLES
	endfunction

	public function NormA takes real acceleration returns real
		return acceleration*TIMESTEP_PARTICLES*TIMESTEP_PARTICLES
	endfunction

	public function DenormA takes real acceleration returns real
		return acceleration/(TIMESTEP_PARTICLES*TIMESTEP_PARTICLES)
	endfunction
	
	
	
	globals
		particle debugPar = 0
		particle tempPar = 0
		particle enumPar = 0
	endglobals
	
	//! textmacro SwitchParticles
		set T_C = T_A
		set T_A = T_B
		set T_B = T_C
	//! endtextmacro
	
	

	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Declare particle-particle collision functions here.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	 public function BallPeasantContact takes particle T_A, particle T_B returns nothing
		local particle T_C
		if T_A.particleType == BALL then
			//===============================================================================
			//Make sure that T_A and T_B refer to the correct particles.
			//===============================================================================
			//! runtextmacro SwitchParticles()
		endif

		//===============================================================================
		//Transfer momentum to peasant.
		//===============================================================================
		set T_A.vx = T_A.vx + T_B.mass*T_B.vx/(T_A.mass + T_B.mass)
		set T_A.vy = T_A.vy + T_B.mass*T_B.vy/(T_A.mass + T_B.mass)

		//===============================================================================
		//Refer to the unit a particle is tethered to with myParticle.host.
		//===============================================================================
		call SetUnitState( T_A.host , UNIT_STATE_LIFE , GetUnitState( T_A.host , UNIT_STATE_LIFE ) - 10 )
		call T_B.Destroy()
	endfunction



	public function PickupFlower takes particle T_A, particle T_B returns nothing
		local particle T_C
		if T_A.particleType == FLOWER then
			//===============================================================================
			//Make sure that T_A and T_B refer to the correct particles.
			//===============================================================================
			//! runtextmacro SwitchParticles()
		endif

		//===============================================================================
		//Refer to the unit a particle is tethered to with myParticle.host.
		//===============================================================================
		call SetUnitState( T_A.host , UNIT_STATE_LIFE , GetUnitState( T_A.host , UNIT_STATE_LIFE ) + T_B.floweriness*15 )
		call DisplayTextToForce( GetPlayersAll() , "You have picked up a flower. The floweriness of that flower was " + I2S(T_B.floweriness) + "." )
		call T_B.Destroy()
	endfunction



	public function EnterCircle takes particle T_A, particle T_B returns nothing
		call DisplayTextToForce( GetPlayersAll() , "You have entered the circle. This  function will trigger exactly once." )
		call particle.DisableInteraction(T_A,T_B)
	endfunction



	public function BallBallBounce takes particle T_A, particle T_B returns nothing
		local real comx
		local real comy
		local real comvx
		local real comvy
		local real dx
		local real dy
		local real dvx
		local real dvy
		local real angle
		local real dxPrime
		local real dyPrime
		local real dvxPrime
		local real dvyPrime
		local real cosAngle
		local real sinAngle

		if (T_A.x-T_B.x)*(T_A.vx-T_B.vx) + (T_A.y-T_B.y)*(T_A.vy-T_B.vy) > 0 then
			return
		endif

		set comx = (T_A.x*T_A.mass + T_B.x*T_B.mass)/(T_A.mass + T_B.mass)
		set comy = (T_A.y*T_A.mass + T_B.y*T_B.mass)/(T_A.mass + T_B.mass)
		set comvx = (T_A.vx*T_A.mass + T_B.vx*T_B.mass)/(T_A.mass + T_B.mass)
		set comvy = (T_A.vy*T_A.mass + T_B.vy*T_B.mass)/(T_A.mass + T_B.mass)

		call AddSpecialEffect( "Abilities\\Spells\\Other\\Silence\\SilenceAreaBirth.mdl" , comx , comy )

		//! textmacro Collision takes M, N
			set dx = $M$.x - comx
			set dy = $M$.y - comy
			set dvx = $M$.vx - comvx
			set dvy = $M$.vy - comvy
			set angle = Atan2( dy , dx )
			set cosAngle = Cos(angle)
			set sinAngle = Sin(angle)

			set dxPrime = cosAngle*dx + sinAngle*dy
			set dyPrime = -sinAngle*dx + cosAngle*dy
			set dvxPrime = cosAngle*dvx + sinAngle*dvy
			set dvyPrime = -sinAngle*dvx + cosAngle*dvy

			set dvxPrime = -dvxPrime
			set dvx = cosAngle*dvxPrime - sinAngle*dvyPrime
			set dvy = sinAngle*dvxPrime + cosAngle*dvyPrime
	
			set $M$.vx = (dvx + comvx)
			set $M$.vy = (dvy + comvy)
		//! endtextmacro

		//! runtextmacro Collision("T_A","T_B")
		//! runtextmacro Collision("T_B","T_A")

	endfunction

	function BlockMovement takes particle T_A, particle T_B returns nothing
		local real angle
		local particle T_C
		local real collisionDist = PTD_collisionRadius[T_A.particleType] + PTD_collisionRadius[T_B.particleType]
		if T_B.particleType == PEASANT then
			//===============================================================================
			//Make sure that T_A and T_B refer to the correct particles.
			//===============================================================================
			//! runtextmacro SwitchParticles()
		endif
		set angle = Atan2( T_A.y-T_B.y , T_A.x-T_B.x )
		set T_A.x = T_B.x + collisionDist*Cos(angle)
		set T_A.y = T_B.y + collisionDist*Sin(angle)
		call SetUnitX( T_A.host , T_A.x )
		call SetUnitY( T_A.host , T_A.y )
	endfunction

	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	//End of collision function declaration.
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	
	
	
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Declare ground collision, movement, and death functions here.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//===============================================================================
	//Ground collision functions.
	//===============================================================================

	private function Knockback takes nothing returns nothing
		local real dist = SquareRoot((enumPar.x-tempPar.x)*(enumPar.x-tempPar.x) + (enumPar.y-tempPar.y)*(enumPar.y-tempPar.y) + (enumPar.z-tempPar.z)*(enumPar.z-tempPar.z))
		set enumPar.vx = enumPar.vx + (enumPar.x-tempPar.x)/dist*7.5
		set enumPar.vy = enumPar.vy + (enumPar.y-tempPar.y)/dist*7.5
	endfunction

	public function KegGroundBounce takes particle T_A returns nothing
		local real x = T_A.x
		local real y = T_A.y
		local integer P = particle.listSize
		local real dist2
		local real dist
		local particle T_P

		if T_A.vz > -5 then
			call T_A.SetGroundBound()
			return
		endif

		call DestroyEffect(AddSpecialEffect( "Objects\\Spawnmodels\\Other\\NeutralBuildingExplosion\\NeutralBuildingExplosion.mdl" , x , y))
		set T_A.vz = -0.85*T_A.vz
		set T_A.z = -T_A.z

		set tempPar = T_A
		call particle.ForAllOfTypeInRange(x, y, 0, 500, BALL, function Knockback)
	endfunction



	public function AstronautGroundCollision takes particle T_A returns nothing
		call KillUnit(T_A.host)
	endfunction

	//===============================================================================
	//Movement functions.
	//===============================================================================

	public function RocketMovement takes particle T_A returns nothing
		set T_A.az = T_A.az + NormA(1.5)
		if T_A.z > 900 then
			call T_A.Destroy()
		endif
	endfunction

	//===============================================================================
	//Death functions.
	//===============================================================================

	public function RocketDeath takes particle T_A returns nothing
		local effect boom = AddSpecialEffect( "Objects\\Spawnmodels\\Other\\NeutralBuildingExplosion\\NeutralBuildingExplosion.mdl" , T_A.x , T_A.y )
		local particle astronaut = particle.CreateSimple3D( T_A.x , T_A.y , T_A.z , 0 , 0 , 0 , ASTRONAUT )
		local unit murloc = CreateUnit( Player(0) , 'nmrl' , 500 , -500 , 135 )
		call astronaut.Tether2Unit( murloc , false , true , true )
		call BlzSetSpecialEffectZ( boom , T_A.z )
		call DestroyEffect(boom)
		set boom = null
		set murloc = null
	endfunction

	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	//End of other function declaration.
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	
	
	
private function interface collisionFuncInterface takes particle A, particle B returns nothing
private function interface groundCollisionFuncInterface takes particle A returns nothing
private function interface deathFuncInterface takes particle A returns nothing
private function interface moveFuncInterface takes particle A returns nothing

globals
	real array PTD_collisionRadius
	public collisionFuncInterface array collisionFunc[NUMBER_OF_PARTICLE_TYPES][NUMBER_OF_PARTICLE_TYPES]
	public groundCollisionFuncInterface array groundCollisionFunc
	public deathFuncInterface array deathFunc
	public moveFuncInterface array moveFunc
	
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Declare particle properties here.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	constant integer NUMBER_OF_PARTICLE_TYPES		= 7

	real array PTD_mass
	integer PTD_floweriness					= 1

	//=============================================================================
	//If you wish to copy particle type properties to struct instances, or declare
	//additional struct instance properties, do so here.
	//=============================================================================

	//! textmacro DeclareParticleProperties
		real mass
		integer floweriness
	//! endtextmacro

	//! textmacro CopyParticleProperties
		set newParticle.mass = PTD_mass[particleType]
		set newParticle.floweriness = PTD_floweriness
	//! endtextmacro

	//=============================================================================
	//Use these constants to refer to specific particle types. Set them here or
	//during particle declaration.
	//=============================================================================	
	integer PEASANT
	integer BALL
	integer FLOWER
	integer CIRCLE
	integer KEG
	integer ROCKET
	integer ASTRONAUT
	
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	//End of particle property declaration
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
endglobals


private function DefineParticleTypes takes nothing returns nothing
	local integer P
	local integer i
	local integer j

	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
	//Declare particle types here.
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

	//=============================================================================
					//Peasant
					set P = 0
	//=============================================================================
	set PTD_mass[P]						= 80
	set PTD_collisionRadius[P]				= 50
	set PEASANT						= P
		
	//=============================================================================
					//Ball
					set P = 1
	//=============================================================================
	set PTD_mass[P]						= 100
	set PTD_collisionRadius[P]				= 35
	set collisionFunc[P][P]					= BallBallBounce
	set collisionFunc[P][PEASANT]				= BallPeasantContact
	set BALL						= P
		
	//=============================================================================
					//Flower
					set P = 2
	//=============================================================================
	set PTD_collisionRadius[P]				= 25
	set collisionFunc[P][PEASANT]				= PickupFlower
	set FLOWER						= P
		
	//=============================================================================
					//Circle
					set P = 3
	//=============================================================================
	set PTD_collisionRadius[P]				= 100
	set collisionFunc[P][PEASANT]				= EnterCircle
	set CIRCLE						= P

	//=============================================================================
					//Keg
					set P = 4
	//=============================================================================
	set PTD_collisionRadius[P]				= 50
	set groundCollisionFunc[P]				= KegGroundBounce
	set collisionFunc[P][PEASANT]				= BlockMovement
	set KEG							= P

	//=============================================================================
					//Rocket
					set P = 5
	//=============================================================================
	set PTD_collisionRadius[P]				= 50
	set collisionFunc[P][PEASANT]				= BlockMovement
	set moveFunc[P]						= RocketMovement
	set deathFunc[P]					= RocketDeath
	set ROCKET						= P

	//=============================================================================
					//Astronaut
					set P = 6
	//=============================================================================
	set PTD_collisionRadius[P]				= 50
	set groundCollisionFunc[P]				= AstronautGroundCollision
	set ASTRONAUT						= P

	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	//End of particle type declaration.
	//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

	set i = 0
	loop
	exitwhen i == NUMBER_OF_PARTICLE_TYPES
		set j = 0
		loop
		exitwhen j == NUMBER_OF_PARTICLE_TYPES
			if collisionFunc[i][j] != null then
				set collisionFunc[j][i] = collisionFunc[i][j]
			endif
			set j = j + 1
		endloop
		set i = i + 1
	endloop
endfunction

private function Init takes nothing returns nothing
	local integer i = 0
	local integer j
	loop
	exitwhen i == NUMBER_OF_PARTICLE_TYPES
		set deathFunc[i]			= 0
		set moveFunc[i]				= 0
		 if INCLUDE_3D then
			set groundCollisionFunc[i]	= 0
		endif
		set j = 0
		loop
		exitwhen j == NUMBER_OF_PARTICLE_TYPES
			set collisionFunc[i][j]	= 0
			set j = j + 1
		endloop
		set i = i + 1
	endloop
	call DefineParticleTypes()
	call particle.Initialize()
endfunction



struct particle

//Particle movement
//=================
real x							//Position x
real y							//Position y
real z							//Position z
real vx							//Velocity x
real vy							//Velocity y
real vz							//Velocity z
real ax							//Acceleration x
real ay							//Acceleration y
real az							//Acceleration z
readonly real linearFriction				//Velocity-depedendent friction when the particle is groundbound.
readonly real constantFriction				//Velocity-independent friction when the particle is groundbound.
readonly boolean isAirborne				//Particle is in the air or on the ground.
readonly real vxAC					//vx during last acceleration check.
readonly real vyAC					//vy during last acceleration check.
readonly real vzAC					//vz during last acceleration check.

//Particle behaviour
//===================
readonly boolean particleLinked2Host			//Tethered particle follows the movement of the host unit.
readonly boolean hostLinked2Particle			//Host unit follows the movement of the tethered particle.
readonly boolean destroyOnHostDeath			//Tethered particle will be destroyed when host unit dies.
readonly boolean isStationary				//Particle will be ignored by the movement function.
readonly boolean isProjectile				//Particle moves with constant velocity. This simplifies collision checks.
readonly trigger moveFuncCaller				//Function that is executed each movement step.
readonly trigger deathFuncCaller			//Function that is executed on destruction of the particle.
readonly unit host					//The unit a tethered particle is tethered to.

readonly integer particleType
readonly real collisionRadius				//Distance at which particle collides with other particles.
//! runtextmacro DeclareParticleProperties()

//Visual effects
//===============
readonly effect visual					//Special effect attached to the particle.
readonly real zOffset					//z-Offset of visual effect.
readonly boolean orientVisual				//Automatically orient visual effect based on movement direction.

//List utility
//=============
readonly boolean willBeRemoved				//Particle is removed from list and struct instance will be destroyed soon. This makes some functions ignore this particle.
readonly boolean isInList				//Destroyed particles are removed from the list shortly before their struct instance is destroyed.
readonly integer listIndex				//Position in the list of this particle.

//Interaction matrices
//=====================
readonly static real array collisionDist2		//Distance between particles i and j, linear indexed, squared, at which they come into collision.
readonly static integer array pairPosition		//Index in the loop at which this particle pair is loaded for the calculation step at nextRenewal.
readonly static boolean array hasInteraction		//If a particle pair has no interaction (no collision function), the engine will not check collision between them.

//Force renewal
//=============
readonly integer accelerationCheck			//Value of the accelerationCounter at which this particle is checked for acceleration.
readonly static integer array whichPairs		//Which particle pairs are checked for collision at each computation step.
readonly static integer array howManyPairs		//How many particle pair collision checks performed at each computation step.

//Statics
//========
readonly static integer numberOfParticles = 0		//Total number of particles currently on the map.
readonly static integer numberDestroyed = 0		//Number of particles that will be removed from the list before the next calculation step.
readonly static particle array destroyedParticles	//List of particles queued for destruction on the next computation step.
readonly static particle array list			//List of all particles.
readonly static integer listSize = 0			//Highest list index of particle in the list.
readonly static boolean array indexUsed			//If index in list is currently occupied by a particle.
readonly static integer moveCounter = 0			//Number of calculation steps since the start of the game.
readonly static integer renewalCounter = 0		//moveCounter modulo MAXIMUM_INTERVAL
readonly static integer accelerationCounter = 0		//moveCounter modulo STEPS_PER_ACCELERATION_CHECK
readonly static integer computationCounter = 0		//moveCounter modulo COMPUTATION_STEPS
readonly static integer array computations		//Particle pair interactions per step
readonly static integer intervalOffset = 1		//Minimum interval between collision checks. Is increased when engine overloads.
readonly static integer numComputations = 0		//Number of collision checks since last computation check.
private static hashtable hashTable = InitHashtable()
private static trigger particleTrigger = CreateTrigger()
private static triggercondition particleCondition
private static timer timer = CreateTimer()
private static location loc = Location(0,0)

//Crash detection
static integer threadCrash = 0				//Check whether main function crashed and where it crashed.

private static constant integer NO_CRASH = 0
private static constant integer CRASH_CREATION = 1
private static constant integer CRASH_FORCE = 2
private static constant integer CRASH_CONTACT = 3
private static constant integer CRASH_MOVEMENT = 4
private static constant integer CRASH_ACCELERATION = 5
private static constant integer CRASH_INIT = 6



//=================================================================================

//                    		! ! ! A P I ! ! !

//=================================================================================



//=================================================================================
//Creation.
//=================================================================================

	static method CreateSimple3D takes real x, real y, real z, real vx, real vy, real vz, integer particleType returns particle
		return particle.create( x, y, z, vx, vy, vz, particleType , false, false)
	endmethod

	static method CreateStationary3D takes real x, real y, real z, integer particleType returns particle
		return particle.create( x, y, z, 0, 0, 0, particleType, true, true)
	endmethod
	
	static method CreateProjectile3D takes real x, real y, real z, real vx, real vy, real vz, integer particleType returns particle
		return particle.create( x, y, z, vx, vy, vz, particleType, true, false)
	endmethod

	static method CreateTethered3D takes unit whichUnit, integer particleType, boolean particle2Unit, boolean unit2Particle, boolean destroyOnHostDeath returns particle
		static if INCLUDE_SURFACE_ELEVATIONS then
			local particle newParticle
			call MoveLocation(loc , GetUnitX(whichUnit) , GetUnitY(whichUnit))
			set newParticle = particle.create( GetUnitX(whichUnit), GetUnitY(whichUnit), GetLocationZ(loc) + GetUnitFlyHeight(whichUnit), 0, 0, 0, particleType, false, false)
		else
			local particle newParticle = particle.create( GetUnitX(whichUnit), GetUnitY(whichUnit), GetUnitFlyHeight(whichUnit), 0, 0, 0, particleType, false, false)
		endif
		call newParticle.Tether2Unit( whichUnit , particle2Unit , unit2Particle, destroyOnHostDeath )
		return newParticle
	endmethod
	
	
	
	static method CreateSimple takes real x, real y, real vx, real vy, integer particleType returns particle
		static if INCLUDE_SURFACE_ELEVATIONS then
			call MoveLocation(loc , x , y)
			return particle.create( x, y, GetLocationZ(loc), vx, vy, 0, particleType ,false, false)
		else
			return particle.create( x, y, 0, vx, vy, 0, particleType ,false, false)
		endif
	endmethod

	static method CreateStationary takes real x, real y, integer particleType returns particle
		static if INCLUDE_SURFACE_ELEVATIONS then
			call MoveLocation(loc , x , y)
			return particle.create( x, y, GetLocationZ(loc), 0, 0, 0, particleType ,true, true)
		else
			return particle.create( x, y, 0, 0 , 0 , 0, particleType, true, true)
		endif
	endmethod
	
	static method CreateProjectile takes real x, real y, real vx, real vy, integer particleType returns particle
		static if INCLUDE_SURFACE_ELEVATIONS then
			call MoveLocation(loc , x , y)
			return particle.create( x, y, GetLocationZ(loc), vx, vy, 0, particleType ,true, false)
		else
			return particle.create( x, y, 0, vx , vy , 0, particleType, true, false)
		endif
	endmethod
	
	static method CreateTethered takes unit whichUnit, integer particleType, boolean particle2Unit, boolean unit2Particle, boolean destroyOnHostDeath returns particle
		static if INCLUDE_SURFACE_ELEVATIONS then
			local particle newParticle
			call MoveLocation(loc , GetUnitX(whichUnit) , GetUnitY(whichUnit))
			set newParticle = particle.create( GetUnitX(whichUnit), GetUnitY(whichUnit), GetLocationZ(loc), 0, 0, 0, particleType, false, false)
		else
			set newParticle = particle.create( GetUnitX(whichUnit), GetUnitY(whichUnit), 0, 0, 0, 0, particleType, false, false)
		endif
		call newParticle.Tether2Unit( whichUnit , particle2Unit , unit2Particle, destroyOnHostDeath )
		return newParticle
	endmethod

//=================================================================================
//Destruction.
//=================================================================================

method Destroy takes nothing returns nothing
	if not .willBeRemoved then
		set .willBeRemoved = true
		set numberDestroyed = numberDestroyed + 1
		set destroyedParticles[numberDestroyed] = this
	endif
endmethod

//=================================================================================
//Visual effect.
//=================================================================================

method operator Visual= takes string effectPath returns nothing
	if .visual != null then
		call DestroyEffect(.visual)
	endif
	set .visual = AddSpecialEffect( effectPath , .x , .y )
endmethod

method operator VisualScale= takes real scale returns nothing
	call BlzSetSpecialEffectScale( .visual , scale )
endmethod

method operator VisualTimeScale= takes real timeScale returns nothing
	call BlzSetSpecialEffectTimeScale( .visual , timeScale )
endmethod

method operator VisualAlpha= takes integer alpha returns nothing
	call BlzSetSpecialEffectAlpha( .visual , alpha )
endmethod

method SetVisualColor takes integer red, integer green, integer blue returns nothing
	call BlzSetSpecialEffectColor( .visual , red, green, blue )
endmethod

method operator VisualColorByPlayer= takes player whichPlayer returns nothing
	call BlzSetSpecialEffectColorByPlayer( .visual , whichPlayer )
endmethod

method operator VisualYaw= takes real yaw returns nothing
	call BlzSetSpecialEffectYaw( .visual , yaw )
endmethod

method operator VisualPitch= takes real pitch returns nothing
	call BlzSetSpecialEffectPitch( .visual , pitch )
endmethod

method operator VisualRoll= takes real roll returns nothing
	call BlzSetSpecialEffectRoll( .visual , roll )
endmethod

method operator VisualZ= takes real zOffset returns nothing
	call BlzSetSpecialEffectZ( .visual , zOffset )
	set .zOffset = zOffset
endmethod

method operator OrientVisual= takes boolean orientVisual returns nothing
	if orientVisual then
		call BlzSetSpecialEffectYaw( .visual , Atan2( .vy , .vx ) )
	endif
	set .orientVisual = orientVisual
endmethod

method DestroyVisual takes nothing returns nothing
	call DestroyEffect(.visual)
	set .visual = null
endmethod

//=================================================================================
//Tethering.
//=================================================================================

method Tether2Unit takes unit whichUnit, boolean particle2Unit, boolean unit2Particle, boolean destroyOnHostDeath returns nothing
	if (not particle2Unit and not unit2Particle) or whichUnit == null  then
		set .host = null
		set .particleLinked2Host = false
		set .hostLinked2Particle = false
		set .destroyOnHostDeath = false
	else
		set .hostLinked2Particle = unit2Particle
		set .particleLinked2Host = particle2Unit
		set .destroyOnHostDeath = destroyOnHostDeath
		set .host = whichUnit
		if particle2Unit then
			set .x = GetUnitX(whichUnit)
			set .y = GetUnitY(whichUnit)
		elseif unit2Particle then
			call SetUnitX(.host , .x)
			call SetUnitY(.host , .y)
			static if INCLUDE_3D then
				call UnitAddAbility( .host , 'Amrf' )
				call UnitRemoveAbility( .host , 'Amrf' )
				static if INCLUDE_SURFACE_ELEVATIONS then
					call MoveLocation( loc , .x , .y )
					call SetUnitFlyHeight( .host , .z - GetLocationZ(loc) , 0 )
				else
					call SetUnitFlyHeight( . host, .z )
				endif
			endif
		endif
	endif
endmethod

method Untether takes nothing returns nothing
	set .particleLinked2Host = false
	set .hostLinked2Particle = false
	set .destroyOnHostDeath = false
	set .host = null
endmethod

//=================================================================================
//Movement.
//=================================================================================

method operator DeathFunc= takes conditionfunc whichFunc returns nothing
	set .deathFuncCaller = CreateTrigger()
	call TriggerAddCondition( .deathFuncCaller , whichFunc )
endmethod

static method GetTetheredParticle takes widget whichWidget returns particle
	return LoadInteger( particle.hashTable , GetHandleId(whichWidget) , 0 )
endmethod

method operator IsStationary= takes boolean isStationary returns nothing
	set .isStationary = isStationary
	if isStationary then
		set .isProjectile = true
	endif
endmethod

method operator IsProjectile= takes boolean isProjectile returns nothing
	if not .isStationary then
		set .isProjectile = isProjectile
	else
		debug call BJDebugMsg("Cannot change projectile/non-projectile of stationary particle.")
	endif
endmethod

method SetFriction takes real linearFriction, real constantFriction returns nothing
	set .linearFriction = linearFriction
	set .constantFriction = constantFriction
endmethod

method SetGroundBound takes nothing returns nothing
	set .isAirborne = false
endmethod

//=================================================================================
//Other
//=================================================================================

static method ForAllInRange takes real x, real y, real z, real dist, code callback returns nothing
	local integer P = particle.listSize
	local real dist2 = dist*dist
	local trigger trig = CreateTrigger()
	local conditionfunc conditionFunc = Condition(callback)
	call TriggerAddCondition( trig , conditionFunc )
	loop
	exitwhen P == 0
		if particle.indexUsed[P] then
			set enumPar = particle.list[P]
			if (enumPar.x-x)*(enumPar.x-x) + (enumPar.y-y)*(enumPar.y-y) + (enumPar.z-z)*(enumPar.z-z) < dist2 then
				call TriggerEvaluate(trig)
			endif
		endif
		set P = P - 1
	endloop
	call DestroyCondition(conditionFunc)
	call DestroyTrigger(trig)
	set conditionFunc = null
	set trig = null
endmethod

static method ForAllOfType takes integer particleType, code callback returns nothing
	local integer P = particle.listSize
	local trigger trig = CreateTrigger()
	local conditionfunc conditionFunc = Condition(callback)
	call TriggerAddCondition( trig , conditionFunc )
	loop
	exitwhen P == 0
		if particle.indexUsed[P] then
			set enumPar = particle.list[P]
			if enumPar.particleType == particleType then
				call TriggerEvaluate(trig)
			endif
		endif
		set P = P - 1
	endloop
	call DestroyCondition(conditionFunc)
	call DestroyTrigger(trig)
	set conditionFunc = null
	set trig = null
endmethod

static method ForAllOfTypeInRange takes real x, real y, real z, real dist, integer particleType, code callback returns nothing
	local integer P = particle.listSize
	local real dist2 = dist*dist
	local trigger trig = CreateTrigger()
	local conditionfunc conditionFunc = Condition(callback)
	call TriggerAddCondition( trig , conditionFunc )
	loop
	exitwhen P == 0
		if particle.indexUsed[P] then
			set enumPar = particle.list[P]
			if (enumPar.x-x)*(enumPar.x-x) + (enumPar.y-y)*(enumPar.y-y) + (enumPar.z-z)*(enumPar.z-z) < dist2 and enumPar.particleType == particleType then
				call TriggerEvaluate(trig)
			endif
		endif
		set P = P - 1
	endloop
	call DestroyCondition(conditionFunc)
	call DestroyTrigger(trig)
	set conditionFunc = null
	set trig = null
endmethod

method operator CollisionRadius= takes real newRadius returns nothing
	local integer A = .listIndex
	local integer B = 1
	local integer J = A
	local integer I
	local particle T_B
	local integer T_steps
	local integer T_index

	set .collisionRadius = newRadius
	
	loop
	exitwhen B > listSize
		if indexUsed[B] and B != A then
			set T_B = list[B]

			if hasInteraction[J] then
				set collisionDist2[J] = (.collisionRadius + T_B.collisionRadius)*(.collisionRadius + T_B.collisionRadius)
			endif
		endif
		set B = B + 1
		if B <= A then
			set J = J + MATRIX_SIZE
		else
			set J = J + 1
		endif
	endloop
endmethod

static method EnableInteraction takes particle P1, particle P2 returns nothing
	local integer A = P1.listIndex
	local integer B = P2.listIndex
	local integer J
	local integer T_index
	
	if A > B then
		set J = MATRIX_SIZE*(B-1) + A
	else
		set J = MATRIX_SIZE*(A-1) + B
	endif
	
	set T_index = renewalCounter + 1
	if T_index > MAXIMUM_INTERVAL then
		set T_index = T_index - STEPS_PER_CHECK_CYCLE
	endif

	if howManyPairs[T_index] == MAXIMUM_PAIRS then
		loop
			set T_index = T_index + 1
			if T_index > MAXIMUM_INTERVAL then
				set T_index = T_index - STEPS_PER_CHECK_CYCLE
			endif
			exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
		endloop
	endif

	set howManyPairs[T_index] = howManyPairs[T_index] + 1
	set pairPosition[J] = T_index*MAXIMUM_PAIRS + howManyPairs[T_index]
	set whichPairs[pairPosition[J]] = J

	set hasInteraction[J] = true
endmethod

static method DisableInteraction takes particle P1, particle P2 returns nothing
	local integer A = P1.listIndex
	local integer B = P2.listIndex
	local integer J
	local integer indexOld
	local integer fillerPair

	if A > B then
		set J = MATRIX_SIZE*(B-1) + A
	else
		set J = MATRIX_SIZE*(A-1) + B
	endif

	set indexOld = (pairPosition[J]-1)/MAXIMUM_PAIRS
	set fillerPair = whichPairs[indexOld*MAXIMUM_PAIRS + howManyPairs[indexOld]]
	set pairPosition[fillerPair] = pairPosition[J]
	set whichPairs[pairPosition[fillerPair]] = fillerPair
	if howManyPairs[indexOld] > 0 then
		set howManyPairs[indexOld] = howManyPairs[indexOld] - 1
	endif
	set hasInteraction[J] = false
endmethod

method ForceUpdate takes nothing returns nothing
//=================================================================================
//Immediately updates the force between a particle and each other particle.
//=================================================================================
	local integer A = .listIndex
	local integer B
	local integer J
	local integer indexOld
	local integer T_index
	local integer fillerPair

	if threadCrash == CRASH_CONTACT then
		call BJDebugMsg("Attempted to call ForceUpdate from within collision function. This is not allowed.")
		return
	endif
		
	
	set B = 1
	set J = A
	
	loop
	exitwhen B > listSize
		if indexUsed[B] and hasInteraction[J] and B != A then
			set T_index = renewalCounter + 1
			set indexOld = (pairPosition[J]-1)/MAXIMUM_PAIRS
			if T_index > MAXIMUM_INTERVAL then
				set T_index = T_index - STEPS_PER_CHECK_CYCLE
			endif

			if howManyPairs[T_index] == MAXIMUM_PAIRS then
				loop
					set T_index = T_index + 1
					if T_index > MAXIMUM_INTERVAL then
						set T_index = T_index - STEPS_PER_CHECK_CYCLE
					endif
					exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
				endloop
			endif

			if T_index != indexOld then
				set fillerPair = whichPairs[indexOld*MAXIMUM_PAIRS + howManyPairs[indexOld]]
				set pairPosition[fillerPair] = pairPosition[J]
				set whichPairs[pairPosition[fillerPair]] = fillerPair
				if howManyPairs[indexOld] > 0 then
					set howManyPairs[indexOld] = howManyPairs[indexOld] - 1
				endif

				set howManyPairs[T_index] = howManyPairs[T_index] + 1
				set pairPosition[J] = T_index*MAXIMUM_PAIRS + howManyPairs[T_index]
				set whichPairs[pairPosition[J]] = J
			endif
		endif
		
		set B = B + 1
		if B <= A then
			set J = J + MATRIX_SIZE
		else
			set J = J + 1
		endif
	endloop
endmethod

static method SleepAll takes boolean doSleep returns nothing
	if doSleep then
		call PauseTimer(timer)
	else
		call ResumeTimer(timer)
	endif
endmethod

static method DestroyAll takes nothing returns nothing
	local integer A = 1
	loop
		exitwhen A > listSize
		if indexUsed[A] then
			call list[A].Destroy()
		endif
		set A = A + 1
	endloop
endmethod

//=================================================================================
//End of API.
//=================================================================================

static method Initialize takes nothing returns nothing
	local integer A = 1
	loop
	exitwhen A > MAXIMUM_INTERVAL
		set howManyPairs[A] = 0
		set A = A + 1
	endloop

	set A = 1
	loop
	exitwhen A > PARTICLE_LIMIT
		set indexUsed[A] = false
		set A = A + 1
	endloop

	if COMPUTATION_STEPS > MAXIMUM_PAIRS*COMPUTATION_LIMIT then
		call BJDebugMsg("|cffff0000Warning:|r COMPUTATION_LIMIT exceeds amount allowed by array size." )
	endif

	if PARTICLE_LIMIT > 180 then
		call BJDebugMsg("|cffff0000Warning:|r PARTICLE_LIMIT cannot exceed 180." )
	endif

	call TimerStart( timer , TIMESTEP_PARTICLES , true , function particle.Main )
endmethod

//=================================================================================
//Creator function.
//=================================================================================

private static method create takes real x, real y, real z, real vx, real vy, real vz, integer particleType, boolean isProjectile, boolean isStationary returns particle

	local particle newParticle
	local integer A
	local integer B

	set A = AllocateIndex()

	if A == 0 then
		debug call BJDebugMsg("Particle limit exceeded.")
		return 0
	endif

	set threadCrash = CRASH_CREATION

	set newParticle = particle.allocate()

	set newParticle.x = x
	set newParticle.y = y
	set newParticle.vx = vx
	set newParticle.vy = vy
	set newParticle.vxAC = vx
	set newParticle.vyAC = vy
	set newParticle.ax = 0
	set newParticle.ay = 0
	set newParticle.az = 0
	set newParticle.isProjectile = isProjectile
	set newParticle.isStationary = isStationary
	set newParticle.accelerationCheck = accelerationCounter
	set newParticle.particleType = particleType
	set newParticle.collisionRadius = PTD_collisionRadius[particleType]
	set newParticle.visual = null
	
	//! runtextmacro CopyParticleProperties()
	
	static if INCLUDE_3D then
		set newParticle.z = z
		set newParticle.vz = vz
		set newParticle.vzAC = vz
		static if INCLUDE_SURFACE_ELEVATIONS then
			call MoveLocation(loc , x , y)
			set newParticle.isAirborne = z > GetLocationZ(loc)
		else
			set newParticle.isAirborne = z > 0
		endif
	else
		set newParticle.z = 0
		set newParticle.vz = 0
		set newParticle.vzAC = 0
	endif

	set newParticle.listIndex = A
	set list[A] = newParticle

	set newParticle.willBeRemoved = false
	set newParticle.isInList = true

	call newParticle.SetInteractions()
	set threadCrash = NO_CRASH

	return newParticle
endmethod

private method SetInteractions takes nothing returns nothing
//=================================================================================
//Initialize particle interaction matrices.
//=================================================================================
	local integer A = .listIndex
	local integer B = 1
	local integer J = A
	local particle T_A
	local particle T_B
	local integer T_steps
	local integer T_index
	
	set T_A = list[A]
	loop
	exitwhen B > listSize
		if indexUsed[B] and B != A then
			set T_B = list[B]

			if collisionFunc[T_A.particleType][T_B.particleType] != null then
				set hasInteraction[J] = true
				set collisionDist2[J] = (T_A.collisionRadius + T_B.collisionRadius)*(T_A.collisionRadius + T_B.collisionRadius)
				set T_steps = 1
				set T_index = renewalCounter + 1
				if T_index > MAXIMUM_INTERVAL then
					set T_index = T_index - STEPS_PER_CHECK_CYCLE
				endif
				if howManyPairs[T_index] >= MAXIMUM_PAIRS then
					loop
						set T_index = T_index + 1
						if T_index > MAXIMUM_INTERVAL then
							set T_index = T_index - STEPS_PER_CHECK_CYCLE
						endif
						exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
					endloop
				endif

				set howManyPairs[T_index] = howManyPairs[T_index] + 1
				set pairPosition[J] = MAXIMUM_PAIRS*T_index + howManyPairs[T_index]
				set whichPairs[pairPosition[J]] = J
			else
				set hasInteraction[J] = false
			endif
		endif
		set B = B + 1
		if B <= A then
			set J = J + MATRIX_SIZE
		else
			set J = J + 1
		endif
	endloop
endmethod



//=================================================================================

//                    ! ! ! M A I N   F U N C T I O N ! ! !

//=================================================================================

static method Main takes nothing returns nothing

	local integer A = numberDestroyed
	local integer B
	local integer C
	local integer I
	local integer J
	local integer P
	local integer L

	local real T_dx
	local real T_dy
	local real T_dvx
	local real T_dvy
	local real T_dist
	local real T_dist2
	local real T_dvT
	local real T_vdotd
	local real T_adotd
	local real T_vT
	local real T_aT2
	local real T_dvT2
	local real T_d2min
	local real T_t
	
	static if INCLUDE_3D then
		local real T_dz
		local real T_dvz
	endif

	local integer T_index
	local integer T_steps = 1
	local real T_factor = 1
	local integer indexOld
	local integer howManySteps
	local integer fillerPair
	
	local particle T_A
	local particle T_B

	static if VISUALIZE_INTERACTIONS then
		local timer t
	endif

	//=================================================================================
	//Remove all particles from the list that were destroyed by external functions.
	//=================================================================================
	loop
	exitwhen A == 0
		call destroyedParticles[A].RemoveFromList()
		set A = A - 1
	endloop
	set numberDestroyed = 0
	
	set moveCounter = moveCounter + 1

	if accelerationCounter < STEPS_PER_ACCELERATION_CHECK - 1 then
		set accelerationCounter = accelerationCounter + 1
	else
		set accelerationCounter = 0
	endif

	if computationCounter < COMPUTATION_STEPS then
		set computationCounter = computationCounter + 1
	else
		set computationCounter = 1
		set A = COMPUTATION_STEPS
		set numComputations = 0
		loop
		exitwhen A == 0
			set numComputations = numComputations + computations[A]
			set A = A - 1
		endloop

		static if PRINTOUT_COMPUTATIONS then
			call BJDebugMsg("Interactions: " + I2S(numComputations) + "/" + I2S(COMPUTATION_LIMIT))
			if intervalOffset > 1 then
				call BJDebugMsg("Intervals +" + I2S(intervalOffset-1))
			endif
		endif
		if numComputations > COMPUTATION_LIMIT then
			set intervalOffset = intervalOffset + 1
		elseif intervalOffset > 1 and numComputations < COMPUTATION_RELAX_THRESHOLD then
			set intervalOffset = intervalOffset - 1
		endif
	endif

	set computations[computationCounter] = 0

	if renewalCounter < MAXIMUM_INTERVAL then
		set renewalCounter = renewalCounter + 1
	else
		set renewalCounter = 0
	endif

	if threadCrash != NO_CRASH then
		static if FUNCTION_CRASH_WARNINGS then
			if threadCrash == CRASH_FORCE then
				call BJDebugMsg("|cffff0000Warning:|r Particle function crashed during collision check.")
			elseif threadCrash == CRASH_CONTACT then
				call BJDebugMsg("|cffff0000Warning:|r Particle function crashed during particle contact.")
			elseif threadCrash == CRASH_MOVEMENT then
				call BJDebugMsg("|cffff0000Warning:|r Particle function crashed during particle movement.")
			elseif threadCrash == CRASH_ACCELERATION then
				call BJDebugMsg("|cffff0000Warning:|r Particle function crashed during acceleration check.")
			elseif threadCrash == CRASH_CREATION then
				call BJDebugMsg("|cffff0000Warning:|r Function crash during particle creation.")
			endif
		endif
		call CompleteWipe()
		set threadCrash = NO_CRASH
		return
	endif

	set threadCrash = CRASH_FORCE

	//=================================================================================
	//Collision check.
	//=================================================================================

	set P = MAXIMUM_PAIRS*renewalCounter + 1
	set L = MAXIMUM_PAIRS*renewalCounter + howManyPairs[renewalCounter]

	loop
	exitwhen P > L
		set I = whichPairs[P]
		set A = I/MATRIX_SIZE
		set T_A = list[A+1]
		set T_B = list[I - MATRIX_SIZE*A]

		set T_dx = T_A.x - T_B.x
		set T_dy = T_A.y - T_B.y

		static if INCLUDE_3D then
			if T_A.isAirborne or T_B.isAirborne then
				set T_dz = T_A.z - T_B.z
				set T_dist2 = T_dx*T_dx + T_dy*T_dy + T_dz*T_dz
			else
				set T_dz = 0
				set T_dist2 = T_dx*T_dx + T_dy*T_dy
			endif
		else
			set T_dist2 = T_dx*T_dx + T_dy*T_dy
		endif

		set T_dvx = T_A.vx - T_B.vx
		set T_dvy = T_A.vy - T_B.vy

		static if INCLUDE_3D then
			set T_dvz = T_A.vz - T_B.vz
		endif
		
		if T_A.isProjectile and T_B.isProjectile then
			static if INCLUDE_3D then
				set T_dvT2 = (T_dvx*T_dvx + T_dvy*T_dvy + T_dvz*T_dvz)
			else
				set T_dvT2 = (T_dvx*T_dvx + T_dvy*T_dvy)
			endif
			
			if T_dist2 < MI2*T_dvT2 then
				static if INCLUDE_3D then
					set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy + T_dvz*T_dz)
				else
					set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy)
				endif

				if T_vdotd < 0 then
					set T_d2min = T_dist2 - T_vdotd*T_vdotd/T_dvT2
					if T_d2min < collisionDist2[I] then
						set T_steps = R2I((-T_vdotd - SquareRoot(T_vdotd*T_vdotd - (T_dist2 - collisionDist2[I])*T_dvT2))/T_dvT2) + 1
						if T_steps > MAXIMUM_INTERVAL then
							set T_steps = MAXIMUM_INTERVAL
						endif
					else
						set T_steps = MAXIMUM_INTERVAL
					endif
				else
					set T_steps = MAXIMUM_INTERVAL
				endif
			else
				set T_steps = MAXIMUM_INTERVAL
			endif
		else
			static if INCLUDE_3D then
				set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy + T_dvz*T_dz)
			else
				set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy)
			endif
			if T_vdotd > 0 then
				set T_vdotd = 0
			endif

			set T_steps = R2I(T_dist2/(INTERVAL_FACTOR + INTERVAL_VELOCITY_FACTOR*T_vdotd*T_vdotd/T_dist2)) + intervalOffset
			if T_steps > MAXIMUM_INTERVAL then
				set T_steps = MAXIMUM_INTERVAL
			endif
		endif

		set T_index = renewalCounter + T_steps
		if T_index > MAXIMUM_INTERVAL then
			set T_index = T_index - STEPS_PER_CHECK_CYCLE
		endif
	
		if howManyPairs[T_index] == MAXIMUM_PAIRS then
			loop
				set T_index = T_index + 1
				if T_index > MAXIMUM_INTERVAL then
					set T_index = T_index - STEPS_PER_CHECK_CYCLE
				endif
				exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
			endloop
		endif

		set howManyPairs[T_index] = howManyPairs[T_index] + 1
		set pairPosition[I] = MAXIMUM_PAIRS*T_index + howManyPairs[T_index]
		set whichPairs[pairPosition[I]] = I

		if collisionDist2[I] > T_dist2 then
			set threadCrash = CRASH_CONTACT
			call collisionFunc[T_A.particleType][T_B.particleType].evaluate(T_A,T_B)
			set threadCrash = CRASH_FORCE
		endif

		static if VISUALIZE_INTERACTIONS then
			if not VISUALIZE_SINGLE_PARTICLE or T_A == debugPar or T_B == debugPar then
				if T_dist2 < VISUALIZATION_DISTANCE_CUTOFF*VISUALIZATION_DISTANCE_CUTOFF then
					set t = CreateTimer()
					call SaveLightningHandle( hashTable , GetHandleId(t) , 1 , AddLightningEx( "DRAM" , true , T_A.x , T_A.y , T_A.z + 50 , T_B.x , T_B.y , T_B.z + 50) )
					call TimerStart( t , TIMESTEP_PARTICLES , false , function particle.RemoveDebugLightning )
					set t = null
				endif
			endif
		endif

		set P = P + 1
	endloop
	
	//=================================================================================
	//Move particles
	//=================================================================================

	set threadCrash = CRASH_MOVEMENT
	set A = listSize
	loop
	exitwhen A == 0
		if indexUsed[A] then
			set T_A = list[A]
		
			if not T_A.willBeRemoved then
				if T_A.host != null then
					if T_A.destroyOnHostDeath and not UnitAlive(T_A.host) then
						call T_A.Destroy()
					elseif T_A.particleLinked2Host then
						set T_A.x = GetUnitX(T_A.host)
						set T_A.y = GetUnitY(T_A.host)
					endif
				endif

				if not T_A.isStationary then
					set T_A.x = T_A.x + T_A.vx + 0.5*T_A.ax
					set T_A.y = T_A.y + T_A.vy + 0.5*T_A.ay
					set T_A.vx = T_A.vx + T_A.ax
					set T_A.vy = T_A.vy + T_A.ay
					static if INCLUDE_3D then
						if not T_A.isAirborne and T_A.az > SURFACE_GRAVITY then
							set T_A.isAirborne = true
						endif
						if T_A.isAirborne then
							set T_A.z = T_A.z + T_A.vz + 0.5*(T_A.az - SURFACE_GRAVITY)
							set T_A.vz = T_A.vz - SURFACE_GRAVITY + T_A.az
							static if INCLUDE_SURFACE_ELEVATIONS then
								call MoveLocation(loc , T_A.x, T_A.y)
								if T_A.z - GetLocationZ(loc) < 0 then
									call groundCollisionFunc[T_A.particleType].evaluate(T_A)
								endif
							else
								if T_A.z < 0 then
									call groundCollisionFunc[T_A.particleType].evaluate(T_A)
								endif
							endif
						else
							static if INCLUDE_SURFACE_ELEVATIONS then
								call MoveLocation(loc , T_A.x, T_A.y)
								set T_A.z = GetLocationZ(loc)
							else
								set T_A.z = 0
							endif
							//! runtextmacro Friction()
						endif
					else
						//! runtextmacro Friction()
					endif
				endif

				if moveFunc[T_A.particleType] != 0 then
					call moveFunc[T_A.particleType].evaluate(T_A)
				endif

				if T_A.hostLinked2Particle then
					call SetUnitX( T_A.host , T_A.x )
					call SetUnitY( T_A.host , T_A.y )
					static if INCLUDE_3D then
						if T_A.isAirborne then
							static if INCLUDE_SURFACE_ELEVATIONS then
								call SetUnitFlyHeight( T_A.host , T_A.z - GetLocationZ(loc) , 0 )
							else
								call SetUnitFlyHeight( T_A.host , T_A.z , 0 )
							endif
						endif
					endif
				endif

				if T_A.visual != null then
					call BlzSetSpecialEffectPosition( T_A.visual , T_A.x , T_A.y , T_A.z + T_A.zOffset )
					if T_A.orientVisual then
						call BlzSetSpecialEffectYaw( T_A.visual , Atan2( T_A.vy , T_A.vx ) )
					endif
				endif

				static if REFLECT_PARTICLES_ON_BOUNDS then
					if T_A.x > PARTICLE_BOUND_RIGHT then
						set T_A.vx = -T_A.vx
						set T_A.x = 2*PARTICLE_BOUND_RIGHT - T_A.x
					elseif T_A.x < PARTICLE_BOUND_LEFT then
						set T_A.vx = -T_A.vx
						set T_A.x = 2*PARTICLE_BOUND_LEFT - T_A.x
					elseif T_A.y > PARTICLE_BOUND_TOP then
						set T_A.vy = -T_A.vy
						set T_A.y = 2*PARTICLE_BOUND_TOP - T_A.y
					elseif T_A.y < PARTICLE_BOUND_BOTTOM then
						set T_A.vy = -T_A.vy
						set T_A.y = 2*PARTICLE_BOUND_BOTTOM - T_A.y
					endif
				else
					if T_A.x > PARTICLE_BOUND_RIGHT or T_A.x < PARTICLE_BOUND_LEFT or T_A.y > PARTICLE_BOUND_TOP or T_A.y < PARTICLE_BOUND_BOTTOM then
						call T_A.Destroy()
					endif
				endif
				
				if T_A.isProjectile then
					static if INCLUDE_3D then
						if T_A.vx != T_A.vxAC or T_A.vy != T_A.vyAC or T_A.vz != T_A.vzAC then
							//! runtextmacro RecalculateProjectile()
						endif
						set T_A.vxAC = T_A.vx
						set T_A.vyAC = T_A.vy
						set T_A.vzAC = T_A.vz
					else
						if T_A.vx != T_A.vxAC or T_A.vy != T_A.vyAC then
							//! runtextmacro RecalculateProjectile()
						endif
						set T_A.vxAC = T_A.vx
						set T_A.vyAC = T_A.vy
					endif
				else
					set threadCrash = CRASH_ACCELERATION
					//! runtextmacro AccelerationDetection()
					set threadCrash = CRASH_MOVEMENT
				endif
			endif
		endif

		set A = A - 1
	endloop
	
	//=================================================================================
	//Destroy particles that were set to be destroyed in main loop. The main loop 
	//is exited so that all interaction calculations are finished before particles are 
	//removed.
	//=================================================================================
	
	set A = numberDestroyed
	loop
	exitwhen A == 0
		call destroyedParticles[A].RemoveFromList()
		set A = A - 1
	endloop
	set numberDestroyed = 0

	set computations[computationCounter] = computations[computationCounter] + howManyPairs[renewalCounter]
	set howManyPairs[renewalCounter] = 0
	set threadCrash = NO_CRASH
	
endmethod

//! textmacro Friction
	if T_A.linearFriction > 0 then
		set T_A.vx = T_A.vx * (1 - T_A.linearFriction)
		set T_A.vy = T_A.vy * (1 - T_A.linearFriction)
	endif
	if T_A.constantFriction > 0 then
		set T_vT = SquareRoot(T_A.vx*T_A.vx + T_A.vy*T_A.vy)
		if T_vT > T_A.constantFriction then
			set T_A.vx = T_A.vx - T_A.constantFriction*T_A.vx/T_vT
			set T_A.vy = T_A.vy - T_A.constantFriction*T_A.vy/T_vT
		else
			set T_A.vx = 0
			set T_A.vy = 0
		endif
	endif
//! endtextmacro

//! textmacro RecalculateProjectile
	set B = 1
	set J = A

	loop
	exitwhen B > listSize
		if indexUsed[B] and hasInteraction[J] and B != A then
			set T_B = list[B]
			if T_B.isProjectile then
				set T_dx = T_A.x - T_B.x
				set T_dy = T_A.y - T_B.y

				static if INCLUDE_3D then
					if T_A.isAirborne or T_B.isAirborne then
						set T_dz = T_A.z - T_B.z
						set T_dist2 = T_dx*T_dx + T_dy*T_dy + T_dz*T_dz
					else
						set T_dz = 0
						set T_dist2 = T_dx*T_dx + T_dy*T_dy
					endif
				else
					set T_dist2 = T_dx*T_dx + T_dy*T_dy
				endif

				set T_dvx = T_A.vx - T_B.vx
				set T_dvy = T_A.vy - T_B.vy

				static if INCLUDE_3D then
					set T_dvz = T_A.vz - T_B.vz
					set T_dvT2 = (T_dvx*T_dvx + T_dvy*T_dvy + T_dvz*T_dvz)
				else
					set T_dvT2 = (T_dvx*T_dvx + T_dvy*T_dvy)
				endif
				
				if T_dist2 < MI2*T_dvT2 then
					static if INCLUDE_3D then
						set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy + T_dvz*T_dz)
					else
						set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy)
					endif

					if T_vdotd < 0 then
						set T_d2min = T_dist2 - T_vdotd*T_vdotd/T_dvT2
						if T_d2min < collisionDist2[J] then
							set T_steps = R2I((-T_vdotd - SquareRoot(T_vdotd*T_vdotd - (T_dist2 - collisionDist2[J])*T_dvT2))/T_dvT2) + 1
							if T_steps > MAXIMUM_INTERVAL then
								set T_steps = MAXIMUM_INTERVAL
							endif
						else
							set T_steps = MAXIMUM_INTERVAL
						endif
					else
						set T_steps = MAXIMUM_INTERVAL
					endif
				else
					set T_steps = MAXIMUM_INTERVAL
				endif
			else
				set T_steps = 1
			endif
			
			set T_index = renewalCounter + T_steps
			if T_index > MAXIMUM_INTERVAL then
				set T_index = T_index - STEPS_PER_CHECK_CYCLE
			endif
			
			set indexOld = (pairPosition[J]-1)/MAXIMUM_PAIRS

			if howManyPairs[T_index] == MAXIMUM_PAIRS then
				loop
					set T_index = T_index + 1
					if T_index > MAXIMUM_INTERVAL then
						set T_index = T_index - STEPS_PER_CHECK_CYCLE
					endif
					exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
				endloop
			endif

			if T_index != indexOld then
				set fillerPair = whichPairs[indexOld*MAXIMUM_PAIRS + howManyPairs[indexOld]]
				set pairPosition[fillerPair] = pairPosition[J]
				set whichPairs[pairPosition[fillerPair]] = fillerPair
				if howManyPairs[indexOld] > 0 then
					set howManyPairs[indexOld] = howManyPairs[indexOld] - 1
				endif

				set howManyPairs[T_index] = howManyPairs[T_index] + 1
				set pairPosition[J] = T_index*MAXIMUM_PAIRS + howManyPairs[T_index]
				set whichPairs[pairPosition[J]] = J
			endif
		endif
		
		set B = B + 1
		if B <= A then
			set J = J + MATRIX_SIZE
		else
			set J = J + 1
		endif
	endloop
//! endtextmacro

//! textmacro AccelerationDetection
	static if ENABLE_ACCELERATION_DETECTION then
		if accelerationCounter == T_A.accelerationCheck then
			static if INCLUDE_3D then
				static if ACCELERATION_DETECTION_IGNORE_Z then
					set T_aT2 = (T_A.vx-T_A.vxAC)*(T_A.vx-T_A.vxAC) + (T_A.vy-T_A.vyAC)*(T_A.vy-T_A.vyAC)
				else
					set T_aT2 = (T_A.vx-T_A.vxAC)*(T_A.vx-T_A.vxAC) + (T_A.vy-T_A.vyAC)*(T_A.vy-T_A.vyAC) + (T_A.vz-T_A.vzAC)*(T_A.vz-T_A.vzAC)
				endif
			else
				set T_aT2 = (T_A.vx-T_A.vxAC)*(T_A.vx-T_A.vxAC) + (T_A.vy-T_A.vyAC)*(T_A.vy-T_A.vyAC)
			endif
			if T_aT2 > UAT2 then
				//=================================================================================
				//Expedite next check due to rapid acceleration of one particle.
				//=================================================================================

				static if VISUALIZE_ACCELERATION_DETECTIONS then
					call AddSpecialEffect( "Abilities\\Spells\\Orc\\Disenchant\\DisenchantSpecialArt.mdl" , T_A.x , T_A.y )
				endif
				
				set B = 1
				set J = A
				
				loop
				exitwhen B > listSize
					if indexUsed[B] and hasInteraction[J] and A != B then
						
						static if INCLUDE_3D then
							set T_adotd = (T_A.vx-T_A.vxAC)*(T_A.x-list[B].x) + (T_A.vy-T_A.vyAC)*(T_A.y-list[B].y) + (T_A.vz-T_A.vzAC)*(T_A.z-list[B].z)
						else
							set T_adotd = (T_A.vx-T_A.vxAC)*(T_A.x-list[B].x) + (T_A.vy-T_A.vyAC)*(T_A.y-list[B].y)
						endif
						if T_adotd < 0 then
							set indexOld = (pairPosition[J]-1)/MAXIMUM_PAIRS
							set T_index = renewalCounter + 1
							if T_index > MAXIMUM_INTERVAL then
								set T_index = T_index - STEPS_PER_CHECK_CYCLE
							endif

							if howManyPairs[T_index] == MAXIMUM_PAIRS then
								loop
									set T_index = T_index + 1
									if T_index > MAXIMUM_INTERVAL then
										set T_index = T_index - STEPS_PER_CHECK_CYCLE
									endif
									exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
								endloop
							endif

							set fillerPair = whichPairs[indexOld*MAXIMUM_PAIRS + howManyPairs[indexOld]]
							set pairPosition[fillerPair] = pairPosition[J]
							set whichPairs[pairPosition[fillerPair]] = fillerPair
							if howManyPairs[indexOld] > 0 then
								set howManyPairs[indexOld] = howManyPairs[indexOld] - 1
							endif

							set howManyPairs[T_index] = howManyPairs[T_index] + 1
							set pairPosition[J] = T_index*MAXIMUM_PAIRS + howManyPairs[T_index]
							set whichPairs[pairPosition[J]] = J

							static if VISUALIZE_ACCELERATION_DETECTIONS then
								set t2 = CreateTimer()
								call SaveLightningHandle( hashTable , GetHandleId(t2) , 1 , AddLightningEx( "DRAL" , true , T_A.x , T_A.y , T_A.z + 50 , list[B].x , list[B].y , list[B].z + 50) )
								call TimerStart( t2 , 0.03 , false , function particle.RemoveDebugLightning )
								set t2 = null
							endif
						endif
					endif
					
					set B = B + 1
					if B <= A then
						set J = J + MATRIX_SIZE
					else
						set J = J + 1
					endif
				endloop
			endif
			set T_A.vxAC = T_A.vx
			set T_A.vyAC = T_A.vy
		endif
	endif
//! endtextmacro

//=================================================================================
//Indexing
//=================================================================================

private static method DestroyInstance takes nothing returns nothing
	local timer t = GetExpiredTimer()
	local integer H = GetHandleId(t)
	local particle P = LoadInteger( hashTable , H , 1 )
	call FlushChildHashtable( hashTable , H )
	call DestroyTimer(t)
	call P.destroy()
	set t = null
endmethod

private method RemoveFromList takes nothing returns nothing
//=================================================================================
//This function replaces onDestroy. Struct instances must persist for a short time
//so that some functions can detect that they were destroyed. Since Main function 
//uses particle.list, the particle no longer affects anything.
//=================================================================================

	local integer A = .listIndex
	local integer B
	local integer N
	local integer I
	local integer J
	local integer index
	local timer t

	set numberOfParticles = numberOfParticles - 1

	call DestroyEffect(.visual)

	if deathFunc[.particleType] != 0 then
		call deathFunc[.particleType].evaluate(this)
	endif
	
	set B = 1
	
	loop
	exitwhen B > listSize
		if indexUsed[B] and B != A then
			if B > A then
				set I = MATRIX_SIZE*(A-1) + B
			else
				set I = MATRIX_SIZE*(B-1) + A
			endif
			if hasInteraction[I] then
				set index = (pairPosition[I]-1)/MAXIMUM_PAIRS
				set J = whichPairs[index*MAXIMUM_PAIRS + howManyPairs[index]]

				set pairPosition[J] = pairPosition[I]
				set pairPosition[I] = 0
				set whichPairs[pairPosition[J]] = J
				if howManyPairs[index] > 0 then
					set howManyPairs[index] = howManyPairs[index] - 1
				endif
			endif
		endif
		set B = B + 1
	endloop
	
	set .isInList = false
	set indexUsed[.listIndex] = false
	if listSize == .listIndex then
		set listSize = listSize - 1
	endif

	static if DELAY_PARTICLE_DESTRUCTION then
		set t = CreateTimer()
		call TimerStart( t , PARTICLE_DESTRUCTION_DELAY , false , function particle.DestroyInstance )
		call SaveInteger( hashTable , GetHandleId(t) , 1 , this )
		set t = null
	else
		call .destroy()
	endif
	
endmethod

static method CompleteWipe takes nothing returns nothing
	local integer A = 0
	local integer B
	local integer I
	local integer J
	local integer T_index
	loop
	exitwhen A == 32768
		set pairPosition[A] = 0
		set whichPairs[A] = 0
		set A = A + 1
	endloop
	set A = 0
	loop
	exitwhen A > MAXIMUM_INTERVAL
		set howManyPairs[A] = 0
		set A = A + 1
	endloop
	
	set T_index = renewalCounter + 1
	set A = 1
	loop
	exitwhen A > listSize
		if indexUsed[A] then
			set B = A + 1
			loop
			exitwhen B > listSize
				if indexUsed[B] then
					if T_index > MAXIMUM_INTERVAL then
						set T_index = T_index - STEPS_PER_CHECK_CYCLE
					endif

					if howManyPairs[T_index] == MAXIMUM_PAIRS then
						loop
							set T_index = T_index + 1
							if T_index > MAXIMUM_INTERVAL then
								set T_index = T_index - STEPS_PER_CHECK_CYCLE
							endif
							exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS and T_index != renewalCounter
						endloop
					endif

					set I = MATRIX_SIZE*(A-1) + B
					set howManyPairs[T_index] = howManyPairs[T_index] + 1
					set pairPosition[I] = T_index*MAXIMUM_PAIRS + howManyPairs[T_index]
					set whichPairs[pairPosition[I]] = I
				endif
				set B = B + 1
			endloop
		endif
		set A = A + 1
	endloop
endmethod

private static method AllocateIndex takes nothing returns integer
//=================================================================================
//Return index in list for newly created particle.
//=================================================================================

	local integer A = 1
	loop
	exitwhen A > PARTICLE_LIMIT
		if not indexUsed[A] then
			set indexUsed[A] = true
			if A > listSize then
				set listSize = A
			endif
			set numberOfParticles = numberOfParticles + 1
			return A
		endif
		set A = A + 1
	endloop

	return 0
endmethod

static method RemoveDebugLightning takes nothing returns nothing
	local timer t = GetExpiredTimer()
	local lightning L = LoadLightningHandle( hashTable , GetHandleId(t) , 1 )
	call DestroyLightning(L)
	set L = null
	call DestroyTimer(t)
	set t = null
endmethod

endstruct

endlibrary
Contents

Ultimate Particle Engine v1.11 (Map)

There is a similar system called Simple Entity Engine in the database.

Despite using dummy units, it has a better much performance than yours. Perhaps, you can take away something from it.
It's because it's using dummy units, that it's fast, as it can use natives to do the distance checks (in x-y direction), while I have to use slow JASS math. Because the engine this is based on did more stuff than collision checks, I couldn't do that. I think my method will be faster for lower particle counts, but slower at high particle counts because the computations rise faster (at ~100 both seem to be even).

Maybe I'll try a dummy unit version or add it as an option. But I think I can also optimize a lot more. And I don't know if it will be faster if the engine has to move dummy units as well as special effects.
 
Level 31
Joined
Feb 27, 2007
Messages
4,356
it can use natives to do the distance checks (in x-y direction)
You could reduce the math burden by comparing to the square of the distance (removing the SquareRoot call), or by automatically filtering out particles whose delta-X or delta-Y component is greater than the distance, since those could never be close enough to be in range in the first place.
 
You could reduce the math burden by comparing to the square of the distance (removing the SquareRoot call), or by automatically filtering out particles whose delta-X or delta-Y component is greater than the distance, since those could never be close enough to be in range in the first place.
I do that actually, but I'm calculating the SquareRoot for absolutely no reason anyway haha. But that's only a minor part of what's slowing everything down. I should have an update later today.
 
As I understand it's the main difference between the two systems; you both have to use trig functions and you both have to do algebra, so what else could bog yours down more than the other?
This here is the crux in SEE:
vJASS:
                // Enum'ing through the entities in a cylindrical range first;
                // speed*2.0 is an added term due to a logical constraint (thanks to grim001);
                // RADIUS is the largest current radius of all entities;
                // e.collGroup contains entities with which collisions have already been
                // dealt. Thus, calculating a second collision would be redundant.
                // Entities are properly sifted considering this.
                call GroupEnumUnitsInRange(entity.COLL, e.xP, e.yP, e.data.radius + RADIUS + s*2.0, filter)
                call GroupRemoveUnit(entity.COLL, e.dummy)
                call GroupClear(e.collGroup)
                // --
                
                loop
                    set c = entity(GetUnitUserData(FirstOfGroup(entity.COLL)))
                    exitwhen c.dummy == null
The GroupEnumUnitsInRange filters out all particles that are not in a small, cylindrical area around the checked particle, and then the engine performs the distance calculation algebra on those that are in range. I don't know if any other major optimization is going on, because that's still like 3000-4000? GroupEnumUnitsInRange per second if it's done for every particle every step, and I have a hard time believing that could be fast.

I filter out most particle pairs by checking only every few steps.

Here is my main loop with added comments:
vJASS:
//Each step, only a small fraction of all particle pairs are checked against each other. The amount is howManyPairs.
set P = MAXIMUM_PAIRS*renewalCounter + 1
set L = MAXIMUM_PAIRS*renewalCounter + howManyPairs[renewalCounter]

loop
exitwhen P > L	//Loop over all particle pairs that are queried to be checked this computation step.

	//Extract particles A and B from particle pair index.
	set I = whichPairs[P]
	set A = I/MATRIX_SIZE
	set T_A = list[A+1]
	set T_B = list[I - MATRIX_SIZE*A]

	//Get relative position and distance-square.
	set T_dx = T_A.x - T_B.x
	set T_dy = T_A.y - T_B.y
	set T_dz = T_A.z - T_B.z
	set T_dist2 = T_dx*T_dx + T_dy*T_dy + T_dz*T_dz

	//Get relative velocity.
	set T_dvx = T_A.vx - T_B.vx
	set T_dvy = T_A.vy - T_B.vy
	set T_dvz = T_A.vz - T_B.vz
	
	//Scalar product of relative distance and velocity vector. If it is positive, particles are moving away from each other and won't collide anytime soon.
	set T_vdotd = (T_dvx*T_dx + T_dvy*T_dy + T_dvz*T_dz)
	
	if T_A.isProjectile and T_B.isProjectile then	//Particles can be created as projectiles for better performance if their movement speed is constant for most steps.
		if T_vdotd < 0 then	//Particles are moving towards each other.
			set T_dvT2 = (T_dvx*T_dvx + T_dvy*T_dvy)	//Square of relative velocity.
			set T_d2min = T_dist2 - T_vdotd*T_vdotd/T_dvT2	//Distance-square at closest approach.
			if T_d2min < collisionDist2[I] then	//Check closest approach against collision distance.
				set T_steps = R2I((-T_vdotd - SquareRoot(T_vdotd*T_vdotd - (T_dist2 - collisionDist2[I])*T_dvT2))/T_dvT2) + 1	//Time steps until particles are within collision distance.
				if T_steps > MAXIMUM_INTERVAL then	//Cap time until next check at MAXIMUM_INTERVAL
					set T_steps = MAXIMUM_INTERVAL
				endif
			else
				set T_steps = MAXIMUM_INTERVAL
			endif
		else
			set T_steps = MAXIMUM_INTERVAL
		endif
		//Write the particle pair into the array to store where the next collision check is performed.
		//! runtextmacro AssignNextIndex()
	else	//If both particles aren't projectiles, their movement could change at any moment, so a periodic check is performed, increasing with frequency as they get closer.
		if T_vdotd > 0 then
			set T_vdotd = 0
		endif

		set T_steps = R2I(Pow(T_dist2,0.75)/(INTERVAL_FACTOR + INTERVAL_VELOCITY_FACTOR*T_vdotd*T_vdotd)) + intervalOffset	//Empirical formula. Optimized for Particle Party, but not really for this engine. Can be improved a lot.
		if T_steps > MAXIMUM_INTERVAL then
			set T_steps = MAXIMUM_INTERVAL
		elseif T_steps < 1 then
			set T_steps = 1
		endif
		
		//! runtextmacro AssignNextIndex()
	endif

	if collisionDist2[I] > T_dist2 then	//Collision occured this step. Execute collision function.
		set threadCrash = CRASH_CONTACT
		set triggerPar = T_A
		set collidingPar = T_B
		set whichCollisionDist = SquareRoot(collisionDist2[I])
		set particleCondition = TriggerAddCondition( particleTrigger , PTD_collisionFunc[T_A.particleType][T_B.particleType] )
		call TriggerEvaluate(particleTrigger)
		call TriggerRemoveCondition(particleTrigger , particleCondition)
		set threadCrash = CRASH_FORCE
	endif
	
	set P = P + 1
endloop



//! textmacro AssignNextIndex
	set T_index = renewalCounter + T_steps
	if T_index > MAXIMUM_INTERVAL then
		set T_index = T_index - STEPS_PER_CHECK_CYCLE
	endif
	
	if howManyPairs[T_index] == MAXIMUM_PAIRS then
		loop
			set T_steps = T_steps + 1
			set T_index = renewalCounter + T_steps
			if T_index > MAXIMUM_INTERVAL then
				set T_index = T_index - STEPS_PER_CHECK_CYCLE
			endif
			exitwhen howManyPairs[T_index] < MAXIMUM_PAIRS
		endloop
	endif

	set howManyPairs[T_index] = howManyPairs[T_index] + 1
	set pairPosition[I] = MAXIMUM_PAIRS*T_index + howManyPairs[T_index]
	set whichPairs[pairPosition[I]] = I

	set lastRenewal[I] = moveCounter
	set renewalTime[I] = T_steps
//! endtextmacro

If you want to get a visualization of how this works, under engine parameters enable "VISUALIZE INTERACTIONS" and "VISUALIZE_SINGLE_PARTICLE", then in the test script, "set debugPar = peasantMessenger."

Edit: oops, it's still refered to as "debugParticle" in the main function. You have to replace that, sorry.
Edit2: Ok, something is not working correctly here. Let me fix that first.
 
Last edited:
Level 17
Joined
Jan 1, 2018
Messages
715
Haven't looked at the implementation but the most important performance optimization in systems like this is filtering out pairs to check.
If you always check all pairs your system is O(n^2) which will become very slow when there are a lot of particles.
Instead you could use something like a quadtree (haven't looked into collision detection in a while so not sure what's the best to use).
Wikipedia may also have some useful information: Collision detection - Wikipedia
 
Impressive system! :thumbs_up:
Thank you! <3

Haven't looked at the implementation but the most important performance optimization in systems like this is filtering out pairs to check.
If you always check all pairs your system is O(n^2) which will become very slow when there are a lot of particles.
Instead you could use something like a quadtree (haven't looked into collision detection in a while so not sure what's the best to use).
Wikipedia may also have some useful information: Collision detection - Wikipedia
I filter out pairs by having variable check intervals for each pair. The further away they are the longer the intervals. With 100 particles (4950 pairs) only about 300 will be checked each step. I know of the quadtree (or octree in the case of 3D), but I haven't worked on such a system myself yet, and I'd rather go through hell and back than do that in JASS for the first time -.-

I have two types of particles that are treated differently. For projectiles with a constant velocity (or a ballistic curve under constant gravity, just no intrinsic acceleration), I can predetermine when a particle pair collides. I have optimized them quite a lot in the latest update. I would upload it, but I have introduced a bug somewhere else and I can't seem to find it.

Collision boxes rather than collision spheres would be faster I think in most programming languages, but I have the feeling that in JASS, complicated math isn't really the problem, but the lines of code being run, and collision boxes require more lines of code than spheres. Maybe I'm wrong, but I think, because it is so slow, reducing overhead is often more important than reducing the complexity of the math.
 
I couldn't locate the bug but I put a band-aid on it. Basically, the engine constantly shifts around particle pairs and writes them into the columns of a 2D-array and keeps track of how many pairs are in each column. Sometimes, that number becomes negative, which shouldn't happen, and then the next pair that gets written in that column is lost forever and the collision checks between the particles of that pair are turned off. I prevented that from happening, but it would be better to find what causes the number of pairs in that column to become negative in the first place.

I also think this bug has been in the engine since forever, but it doesn't manifest itself as directly in Particle Party. Not sure though.
 
Last edited:
Top