# Drawing a grid-based particle system

For some time now, I've been working on a game which is superficially similar in appearance to this one. A world is filled with particles that move and change state frequently (per frame, often). Drawing is achieved by finding the locations of particles within the camera's viewport, calculating lighting for the grid locations within the viewport, and then tinting a 1x1 white texture with the appropriate color, based on the particle and the lighting present in the particle's grid space:

public void drawParticles(ParticleBoard particle_board) {
final int cam_min_x = camera.getCameraMinX();
final int cam_min_y = camera.getCameraMinY();
final int cam_max_x = camera.getCameraMaxX();
final int cam_max_y = camera.getCameraMaxY();
final float[][] light = light_manager.calculateLighting();

for (int y = cam_min_y; y < cam_max_y; y++) {
for (int x = cam_min_x; x < cam_max_x; x++) {
final float l = light[x - cam_min_x][y - cam_min_y];
if (l <= 0.05f) continue; // don't draw if it's too dark.

final Particle p = particle_board.getParticle(x, y);

if (p != null) {
final Color c = p.getProperty().getColor();
sprite_batch.setColor(new Color(c.r, c.g, c.b, l));
sprite_batch.draw(texture, x, y);
}
}
}
}


Light calculations are done within an array of floats the size of the current viewport. The approach is somewhat flood-fill-y, in that initial light values are placed at the 'top' of the array and then spread across the rest of the array, changing based on the presence of blocks:

float[][] calculateLighting() {
final int cam_min_x = camera.getCameraMinX();
final int cam_min_y = camera.getCameraMinY();
final int cam_max_x = camera.getCameraMaxX();
final int cam_max_y = camera.getCameraMaxY();
final int light_width = cam_max_x - cam_min_x + 1;
final int light_height = cam_max_y - cam_min_y + 1;
final float[][] ambient_light = new float[light_width][light_height];

for (int y = light_height - 1; y >= 0; y--) {
for (int x = 0; x < light_width; x++) {
final float max = getMaxNeighboringLight(ambient_light, x, y, light_width, light_height);

if (particle_board.getParticle(x + cam_min_x, y + cam_min_y) != null) {
ambient_light[x][y] = max * 0.75f; // TODO: add constant to particle properties for transparency -- use that here.
} else {
ambient_light[x][y] = max;
}
}
}

return ambient_light;
}


Here's how the max neighboring light level is found:

private float getMaxNeighboringLight(float[][] l, int x, int y, int light_width, int light_height) {
float left = 0f, right = 0f, top = 0f, bottom = 0f;

if (x == 0) {
left = 0f;
} else if (x == light_width - 1) {
right = 0f;
} else {
left = l[x - 1][y];
right = l[x + 1][y];
}

if (y == 0) {
bottom = 0f;
} else if (y == light_height - 1) {
top = 1f;
} else {
bottom = l[x][y - 1];
top = l[x][y + 1];
}

return Math.max(left, right, top, bottom);
}


Here's the result: It would be very interesting to hear suggestions as to how these approaches to rendering and lighting calculations could be improved. It seems rather inefficient to create a new lighting array each frame, but I'm not sure how I could do much better, since many of the particles shift around frequently. Similarly, it seems that drawing could be improved, but I lack the knowledge to do so. If any clarification would be useful, please let me know. The approach used to draw particles is based in part on the responses that I got from this question.

From where I sit, this seems to be implemented backwards. You're iterating over every pixel in the viewport and checking to see if it has a particle, then doing something with the particle. It seems like it would be way more efficient to iterate over the particles and calculate the values needed for each particle. You're doing n * m operations for the lighting, then another n * m operations for drawing the textures (so it's essentially O(2n2)). You could do the operations only for the particles and cut it down to O(2q) operations (where q is the number of particles, which looks to always be smaller than m * n).

If instead, a particle held an (x,y) position, and a lighting value, you could simply iterate over the particles and calculate the new lighting value and then draw them.

You say:

One of the difficulties with just doing the operations for all the particles is that the world is rather large. There are many more particles than those just displayed in the viewport. It would be prohibitively slow to calculate lighting and render every particle (> 10,000,000).

The solution to this is to use an appropriate data structure. In this case a k-d tree in 2D might be a good place to start. You would check only particles whose segment of the tree intersected the viewport, and leave out all other particles.

• One of the difficulties with just doing the operations for all the particles is that the world is rather large. There are many more particles than those just displayed in the viewport. It would be prohibitively slow to calculate lighting and render every particle (> 10,000,000). Do you think it would be quicker if I were to first calculate particles in the viewport and then pass those to the lighting and rendering methods? Should I elaborate on the particle system itself in my post? Jul 16 '18 at 2:38
• I've updated my answer with some additional information that may help. Jul 16 '18 at 3:38
• Thanks for updating the answer. I've heard about quadtrees and the like, but was concerned that the cost of constantly updating the data structure to reflect changes in particle positions would be more expensive than iterating over the viewport rectangle and retrieving non-null particles. Do you know of any ways to 'fast update' a quadtree? Jul 16 '18 at 23:32
• I've only used them a little myself. I didn't find the updates to be an issue, but everyone's code is different. A profiler is an essential tool for performance tuning. You need to see what's slow before you can fix it. Jul 17 '18 at 5:11