Did you encounter difficulties when it comes to designing your minigames? Is the random outcome you mentioned earlier (due to parallelization issues) restricting when it comes to designing mini-games?

It still awes me to think that the engine behavior is dictated by the chaotic movement of electrons - it somehow feels you are truly connected with reality.

To answer your question - when play testing, unpredictable things do crop up, however I've taken the mind set that this is actually fun. Take this for example:

If you are determined you can get the car to jump over the obstacle if it rebounds in a certain way - but it might take 100 or more attempts. I watched my sons play this and they got so excited when this happened. They also invented there own game by stretching the slingshot all the way across the screen and then balancing the balls into the upper nets. It got really intense and I didn't plan any of it. I think this is the great thing about physics simulations - the opportunity to explore the simulated reality in your own way.

It would be great to hear some of the technical details of your implementation. How do you find particles which influence each other? Do you use space-partitioning on the GPU? etc...

The entire engine resides on the GPU and the particle array is completely isolated from the CPU (except for saving and loading). All gui input is communicated through a small storage buffer. With regards to spatial awareness I use a

quadtree for both collisions and non rigid forces.

The tricky part for particle awareness was developing a parallel approach that was fast. I eventually came up with this:

#define MAX_PARTICLES_PER_QUAD 8

struct QuadtreeStruct

{

int sub_quad[4]; // index to next level in quadtree

int count [4]; // number of particles in each node

int particle[4][MAX_PARTICLES_PER_QUAD]; // particle indexes for each node

};

layout (std430, binding=1) buffer Quad_array

{

QuadtreeStruct quad_array[];

};

void main()

{

int particle_index = int (gl_GlobalInvocationID.x);

// make sure we cover all possible contacting particles of similar size

for (int y2 = -1; y2 <= 1; y2++)

{

for (int x2 = -1; x2 <= 1; x2++)

{

float x = particle_position.x + (particle_diameter * x2);

float y = particle_position.y + (particle_diameter * y2);

int quad_base = 0;

float quad_size = g.quad_size; // global largest quad size

for (;;)

{

int quad = (int (y / quad_size) % 2) * 2 + (int (x / quad_size) % 2);

if (particle_diameter >= quad_size / 2.0)

{

// check particle not already added to quad

int limit = min (quad_array[quad_base].count[quad], MAX_PARTICLES_PER_QUAD);

int j = 0; for (; j < limit; j++) if (quad_array[quad_base].particle[quad][j] == particle_index) break;

// add to quad and exit this traversal

if (j == limit) quad_array[quad_base].particle[quad][atomicAdd (quad_array[quad_base].count[quad], 1) % MAX_PARTICLES_PER_QUAD] = particle_index;

break;

}

// go to next level - zero return implies this particle is the first to enter the quad

int sub_quad = atomicCompSwap (quad_array[quad_base].sub_quad[quad], 0, -(particle_index+1));

if (sub_quad == 0)

{

// fetch a new quad from the global array

sub_quad = atomicAdd (g.quad_count, 1) + 1;

if (sub_quad >= MAX_QUADS) break; // oops

// initialize

for (int i=0; i<4; i++)

{

quad_array[sub_quad].count[i] = 0;

quad_array[sub_quad].sub_quad[i] = 0;

}

// add to quadtree

quad_array[quad_base].sub_quad[quad] = sub_quad;

}

if (sub_quad < 0) break; // safety check

// go to next level in tree

quad_size = quad_size / 2;

quad_base = sub_quad;

}

}

}

}

Note the use of

atomicCompSwap to decide which invocation allocates the next node. All particles of similar size sit at the same level in the tree.

To check for collisions we traverse the quadtree at the particles position:

int particle_index = int (gl_GlobalInvocationID.x);

int quad_base = 0;

float quad_size = g.quad_size;

for (;;)

{

int quad = (int (particle_position.y / quad_size) % 2) * 2 + (int (particle_position.x / quad_size) % 2);

for (int i=0; i < quad_array[quad_base].count[quad] && i < MAX_PARTICLES_PER_QUAD; i++)

{

int p2 = quad_array[quad_base].particle[quad][i];

if (particle_index != p2) collide (particle_index, p2);

}

quad_base = quad_array[quad_base].sub_quad[quad];

if (quad_base == 0) break;

quad_size = quad_size / 2;

}

For forces I swap the particle diameter for the force range and build a corresponding quadtree. The same traversal is then used to determine which particles are exerting a force - and then apply the corresponding force equation.