Optimized updates of a grid-based particle system

I've been working on a game somewhat similar to this one for a little while now. My game is based around a 'board,' which is filled with different types of particles that react with one another and the environment. With every update of the screen, the board, and all of the particles within it have to be updated (moving, changing state, reacting to one another, producing other particles, destroying other particles, etc.). The 'board' is implemented in a class called ParticleSystem:

package main.java.engine;

import main.java.particle.particles.Particle;

import static main.java.engine.VelocitySystem.VCEL_W;

/**
* In charge of holding and updating particles.
*/
public class ParticleSystem implements IParticleSystem {
private final int width;
private int count;
private Particle[][] particles;

public ParticleSystem(int width) {
if (width <= 0) throw new IllegalArgumentException("width should be greater than zero");

this.width = width;
this.count = 0;
this.particles = new Particle[width][width];
}

/**
* @return The width of this particle system.
*/
public int getWidth() {
return width;
}

/**
* @return The number of non-null particles contained w/in this system.
*/
public int getParticleCount() {
return count;
}

if (p == null) throw new IllegalArgumentException("particle to add should be non-null. " +
"remove particles with removeParticle method.");

int px = p.getX();
int py = p.getY();

if (isOutOfBounds(px, py)) return;
particles[px][py] = p;
}

public void removeParticle(int x, int y) {
if (isOutOfBounds(x, y)) return;
particles[x][y] = null;
}

public Particle getParticle(int x, int y) {
if (isOutOfBounds(x, y)) return null;
return particles[x][y];
}

/**
* @param x x position.
* @param y y position.
* @return The number of particles above the point (x,y) until the first empty spot.
*/
@Override
public int countParticlesAbove(int x, int y) throws IndexOutOfBoundsException {
if (isOutOfBounds(x, y)) throw new IndexOutOfBoundsException("(" + x + ", " + y + ")");
int count = 0;

y++;

while (y < width && particles[x][y] != null) {
count++;
y++;
}

return count;
}

/**
* @param x x position to start at.
* @param y y position to start at.
* @return The number of particles below the starting (x, y) position.
* @throws IndexOutOfBoundsException if the given starting (x, y) position is out of bounds.
*/
@Override
public int countParticlesBelow(int x, int y) throws IndexOutOfBoundsException {
if (isOutOfBounds(x, y)) throw new IndexOutOfBoundsException("(" + x + ", " + y + ")");
int count = 0;

y--;

while (y >= 0 && particles[x][y] != null) {
count++;
y--;
}

return count;
}

public void move(Particle p, float dx, float dy) {
float f_px = p.getExactX();
float f_py = p.getExactY();
float f_new_px = f_px + dx;
float f_new_py = f_py + dy;

int i_px = (int) f_px;
int i_py = (int) f_py;
int i_new_px = (int) f_new_px;
int i_new_py = (int) f_new_py;

if (isOutOfBounds(i_new_px, i_new_py)) return;
if (particles[i_new_px][i_new_py] != p && particles[i_new_px][i_new_py] != null) return;

p.setX(f_new_px);
p.setY(f_new_py);
particles[i_px][i_py] = null;
particles[i_new_px][i_new_py] = p;
}

public void run() {
Particle p;
float vx, vy;

for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
p = particles[i][j];

if (p == null || p.ticked) continue;
p.update(this);
p.ticked = true;
}
}

markUnticked();
}

/**
* Revert the system to its initial state.
*/
public void clear() {
for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
particles[i][j] = null;
}
}
}

private void markUnticked() {
count = 0;

for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
if (particles[i][j] != null) {
particles[i][j].ticked = false;
count++;
}
}
}
}

private boolean isOutOfBounds(int x, int y) {
return (x < 0 || x >= width || y < 0 || y >= width);
}
}


A Particle's update method may look something like:

public void update(ParticleSystem p) {
this.dy += this.properties.getGravity();

p.move(this, dx, dy);

dx = 0;
dy = 0;
}


In the future, update methods may become more complicated -- they may involve looking at neighboring elements, removing elements, or adding new ones.

I've tried implementing the ParticleSystem with data structures other than a 2D array, but have found it to have significantly better performance than both the ArrayList and HashMap classes. It seems that some kind of multithreading might go a long way here, but I'm not really sure how I could do that and still ensure that Particles updated properly.

I've two main questions that I'd like answered:

1. How can I improve the performance of this algorithm?
2. How can I improve the structure of what I've written?

Edit

• The board is currently 300*300 particles wide.
• The number of expected particles could really be anywhere between 0 and 300^2, though I'd say it averages between 1/3 and 1/2 full.
• Iterating one 300*300 board, when full, takes ~0.003 seconds.
• I'm not aiming for any particular speed, I just wanted to see if it could be sped up.

I've not come up with too many Particle movement algorithms yet. However, here are some plausible examples:
Water:

public void update(ParticleSystem p) {
// move the water back and forth at random
if (Math.random() > 0.5) {
dx -= 1;
} else {
dx += 1;
}

p.move(this, dx, dy + this.properties.getGravity());
}


Ice:

public void update(ParticleSystem p) {
for (int i = this.x - 1; i <= this.x + 1; i++) {
for (int j = this.y - 1; j <= this.y + 1; j++) {
if (p.getParticle(i, j).getProperties().getID() == Water_ID) {
if (Math.random < 0.01) {
}
}
}
}
}


Some rather obvious stuff...

General

• You're violating the Java "braces everywhere" style the same way I do. What should I say? :D
• Shortcuts like p are usually frown upon; I find them fine for short-lived local variables, but less acceptable for parameters. Especially with p used for both Particle and ParticleSystem.
• A null check should throw an NPE rather than IAE (IIRC according to J. Bloch).
• Your naming getExactX vs. setX sounds inconsistent.
• markUnticked has a second job of computing count, which is strange. You could update count whenever it changes instead.
• Your width is also height, so maybe size would be better.

Your code is pretty clear, but count (although private) could use some comment (or a more verbose name). I'm unsure, how you decide to throw IndexOutOfBoundsException or not.

You definitely should switch warnings on. run declares unused vx and vy.

Optimizations

I've tried implementing the ParticleSystem with data structures other than a 2D array, but have found it to have significantly better performance than both the ArrayList and HashMap classes.

This surely depends on the density of your data. With 1 particle on a 1000x1000 board, a sparse structure would surely be faster. Arrays are the fastest as long as they're used to a non-negligible fraction and you need no search.

A 1D array would probably be even faster as long as you can avoid division (in bounds checks). Using a power of two size can make it fast at the cost of some wasted memory. This is a low-level optimization, which may complicate your code for minor gain.

Your move using floating point sounds rather complicated. I guess, you could speed it up by using fixed point instead (work with dx<<10 instead of dx). Again, this is a low-level optimization, even worse than the 1D array.

It seems that some kind of multithreading might go a long way here, but I'm not really sure how I could do that and still ensure that Particles updated properly.

Multithreading is rather complicated and the gain is limited by the number of cores you have. Given you current code, I guess, it should not be hard to split the computation into horizontal stripes (vertical doesn't sound good because of countParticlesAbove and below). There's also some horizontal interaction due to moving particles, but only local. I'd go for multithreading only after examining other possibilities.

There's one simple high-level optimization possible: In case your particle typically move only a fraction of the pixel size (i.e., dx, dy << 1), then you may want to replace ticked by a variable counting how long it takes to leave the current pixel. This may interact with accelerating or alike, but may lead to smoother movement for equal computation overhead.

So, I can't give you any good advice at the moment. Let us know

• how big is your board
• how many particles are there
• how long does an iteration take
• how much faster it should get

Also give us more Particle rules, ideally exactly the code you want to optimize. Some particle kinds are probably slower to compute than others. Maybe you're wasting time in scanning through nearly empty arrays? We don't know.

I'll add more if you do (Note that adding details to reviewed code is OK, improving it on the fly is not).

Do not use Math.random() in anything but throwaway code. Oftentimes you need reproducibility and you can get it with using random.nextDouble() instead. You can get reproducibility by seeding the random and randomness otherwise.

For 50% booleans, there's nextBoolean(), for n%, there's random.nextInt(100) < n. Using double is fine, too.

 p.getParticle(i, j).getProperties().getID() == Water_ID


This looks too complicated for something as important as the particle type. Having general properties in the particle sound flexible, but maybe particles should have no properties besides their type and coordinates (as you probably can't show more, anyway). I'd never call something non-unique for a particle "ID", "type" sounds better. Using an enum, there's no need for an "ID" of the "type". The test should probably be as simple as

 p.getParticle(i, j).getType() == Particle.Type.WATER


(You won't believe how long I was clicking around the app you linked, that thing is somewhat satisfying... )

This is very interesting! If you got a github repo, I'd be happy to play around with it. If not, I'd be happy if you would make a github repo =)

Performance in general

Well, to improve performance for future requirements, which are not specified, can often results in a step backwards: Requirements can change or are not required anymore. Then, you're sitting on code wich is implemented for requirements, which are, well, not required. "By definition", more code makes your app slower. That's why I argue, that measuring is the most important thing to do, when it comes improving performance, because sometimes you get the opposite. And: The more flexibility you have, the less I'd invest time for potential performance problems. Less flexible would be stuff like, geographical aspects (e.g. where is the data center located) or scalability aspects (the software must perform the same for customers who want to analyze gigabytes of data as it would for customers who want to analayze peta bytes of data, just by adding more servers) or any given restrictions, like bandwidth.

FPS

One thing I want to mention: Since you visually display your data, you should have a component which renders the particles. So all your calculations must be finished within 1/'Amount of FPS you want to render' seconds. If you haven't finished the calculations, just skip a frame.

And: At least decouple rendering from calculation, if you haven't done that yet, it shouldn't be too hard to achieve and it should improve performance (which should be verified/measured).