Drawing a grid-based particle system

Question

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.

Answer 1

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(2n²)). 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.