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;
}
public void addParticle(Particle p) {
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:
- How can I improve the performance of this algorithm?
- How can I improve the structure of what I've written?
Edit
Answers to some questions asked:
- 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) {
p.addParticle(new Particle(ICE_ID, i, j));
}
}
}
}
}
