Updated ParticleEngineDMapImplementation.

[desert.git] / src / org / sourceforge / desert / ParticleEngineDMapImplementation.java

/*
 * Copyright (c) 2010 The Desert team
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 */
package org.sourceforge.desert;

import java.awt.Dimension;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import static java.lang.Math.*;
import static org.sourceforge.desert.Utilities.*;

/**
 *
 * @author codistmonk (creation 2010-04-25)
 */
public class ParticleEngineDMapImplementation implements ParticleEngine {

    private final DensityMap densityMap;

    private final List<Particle> particles;

    private float gravity;

    private Dimension boardSize;

    public ParticleEngineDMapImplementation() {
        this.densityMap = new DensityMap();
        this.particles = new ArrayList<Particle>();

        this.setGravity(DEFAULT_GRAVITY);
    }

    @Override
    public final Dimension getBoardSize() {
        return this.boardSize;
    }

    @Override
    public final void setBoardSize(final Dimension size) {
        this.boardSize = size;

        if (size != null) {
            this.densityMap.setSize(size.width, size.height);

            for (final Particle particle : this) {
                this.densityMap.addParticle(particle);
            }
        }
        else {
            this.densityMap.setSize(0, 0);
        }
    }

    @Override
    public final float getGravity() {
        return this.gravity;
    }

    @Override
    public final void setGravity(final float gravity) {
        this.gravity = gravity;
    }

    @Override
    public final void removeAllParticles() {
        this.particles.clear();
    }

    @Override
    public final void addParticle(final Particle.Type type, final float x, final float y, final float speedX, final float speedY) {
        final ParticleDefaultImplementation particle = new ParticleDefaultImplementation(type, x, y, speedX, speedY);

        this.particles.add(particle);
        this.densityMap.addParticle(particle);
    }

    @Override
    public final int getParticleCount() {
        return this.particles.size();
    }

    @Override
    public final void update(final float deltaTime) {
        for (final Particle particle : this) {
            if (particle.getType().isMobile()) {
                this.applyForcesAndUpdatePosition((ParticleDefaultImplementation) particle, deltaTime);
            }
        }
    }

    @Override
    public final Iterator<Particle> iterator() {
        return this.particles.iterator();
    }

    /**
     *
     * @param particle A mobile particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void applyForcesAndUpdatePosition(final ParticleDefaultImplementation particle, final float deltaTime) {
        final float pixelCount = max(1F, max(abs(particle.getSpeedX()), particle.getSpeedY()));
        final float step = deltaTime / pixelCount;

        for (float time = 0F; time < deltaTime; time += step) {
            this.densityMap.removeParticle(particle);

            this.applyForces(particle, step);
            constrainSpeed(particle);

            this.updatePosition(particle, step);
            this.constrainPosition(particle);

            this.densityMap.addParticle(particle);
        }
    }

    /**
     *
     * @param particle A mobile particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void updatePosition(final ParticleDefaultImplementation particle, final float deltaTime) {
        particle.setX(particle.getX() + particle.getSpeedX() * deltaTime);
        particle.setY(particle.getY() + particle.getSpeedY() * deltaTime);
    }

    /**
     *
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     */
    private final void constrainPosition(final ParticleDefaultImplementation particle) {
        if (this.getBoardSize() != null) {
            if (particle.getX() < 0F) {
                particle.setX(0F);
                particle.setSpeedX(abs(particle.getSpeedX()));
            }
            else if (particle.getX() >= this.getBoardSize().width) {
                particle.setX(this.getBoardSize().width - 1F);
                particle.setSpeedX(-abs(particle.getSpeedX()));
            }
            if (particle.getY() < 0F) {
                particle.setY(0F);
                particle.setSpeedY(abs(particle.getSpeedY()));
            }
            else if (particle.getY() >= this.getBoardSize().height) {
                particle.setY(this.getBoardSize().height - 1F);
                particle.setSpeedY(-abs(particle.getSpeedY()));
            }
        }
    }

    /**
     *
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void applyForces(final ParticleDefaultImplementation particle, final float deltaTime) {
        this.applyGravity(particle, deltaTime);
        this.applyBuyoancy(particle, deltaTime);
        this.applyPressure(particle, deltaTime);
    }

    /**
     * 
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void applyGravity(final ParticleDefaultImplementation particle, final float deltaTime) {
        particle.setSpeedY(particle.getSpeedY() + this.getGravity() * deltaTime);
    }

    /**
     *
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void applyBuyoancy(final ParticleDefaultImplementation particle, final float deltaTime) {
        // TODO consider the particle size
        float localDensity = this.densityMap.getDensity(particle.getX(), particle.getY());

        if (Float.isInfinite(localDensity)) {
            localDensity = signum(localDensity) * ARBIRARY_MAXIMUM_DENSITY_DIFFERENCE;
        }

        final float accelerationY = localDensity * -this.getGravity() / particle.getType().getMass();
        
        particle.setSpeedY(particle.getSpeedY() + accelerationY * deltaTime);
    }

    /**
     *
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     * @param deltaTime
     * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
     */
    private final void applyPressure(final ParticleDefaultImplementation particle, final float deltaTime) {
        // If we see the density map as a 3D height field, then we can compute an average normal at each point
        // This normal can then be projected on a horizontal plane to get the direction of the pressure force
        // To compute the normal, we sum the normals of the eight triangles that can be formed with the center
        // and each consecutive pair of surrounding points
        // Here is an illustration of how to get the average normal at some point A:
        // E-D-C
        // |\|/|
        // F-A-B
        // |/|\|
        // G-H-I
        // For the first triangle (ABC), u = B - A, v = C - A and normal(ABC) = u x v (3D cross product)
        // For the next triangle (ACD),  u = C - A, v = D - A and normal(ACD) = u x v
        // etc. until the last triangle AIB
        // The sum of all these normals will give us the direction of the normal at the point A
        // Note that in each pair (u, v) on vector is of length 1 and the other is of length sqrt(2)
        // This means that the computation does not favor the contribution of any particular triangle
        // TODO if more precision is needed, then replace C with (A+B+C+D)/4, E with (A+D+E+F)/4, etc.
        float normalX = 0F;
        float normalY = 0F;
        // We don't need normalZ be cause we only care about the projection on a horizontal plane
        final float centerDensity = this.densityMap.getDensity(particle.getX(), particle.getY());
        float uX = DENSITY_CELL_OFFSETS[0][0];
        float uY = DENSITY_CELL_OFFSETS[0][1];
        float uZ = difference(this.densityMap.getDensity(particle.getX() + uX, particle.getY() + uY), centerDensity);

        for (int i = 1; i < DENSITY_CELL_OFFSETS.length; ++i) {
            final float vX = DENSITY_CELL_OFFSETS[i][0];
            final float vY = DENSITY_CELL_OFFSETS[i][1];
            final float vZ = difference(this.densityMap.getDensity(particle.getX() + vX, particle.getY() + vY), centerDensity);

            normalX += uY * vZ - uZ * vY;
            normalY -= uX * vZ - uZ * vX;

            uX = vX;
            uY = vY;
            uZ = vZ;
        }

        particle.setSpeedX(particle.getSpeedX() + normalX * ARBITRARY_PRESSURE_COEFFICIENT * deltaTime);
        particle.setSpeedY(particle.getSpeedY() + normalY * ARBITRARY_PRESSURE_COEFFICIENT * deltaTime);
    }

    private static final float ARBIRARY_MAXIMUM_DENSITY_DIFFERENCE = 1000F;

    private static final float ARBITRARY_PRESSURE_COEFFICIENT = 1F;

    private static final int[][] DENSITY_CELL_OFFSETS = new int[][] {
        {  1,  0 },
        {  1,  1 },
        {  0,  1 },
        { -1,  1 },
        { -1,  0 },
        { -1, -1 },
        {  0, -1 },
        {  1, -1 },
        {  1,  0 },
    };

    private static final float ARBITRARY_MAXIMUM_SPEED = 64F;

    /**
     *
     * @param density1
     * <br>Range: any float
     * @param density2
     * <br>Range: any float
     * @return
     * <br>Range: <code>[-ARBIRARY_MAXIMUM_DENSITY_DIFFERENCE .. ARBIRARY_MAXIMUM_DENSITY_DIFFERENCE]</code>
     */
    private static final float difference(final float density1, final float density2) {
        final float result = density1 - density2;

        if (Float.isNaN(result)) {
            return 0F;
        }

        if (Float.isInfinite(result)) {
            return signum(result) * ARBIRARY_MAXIMUM_DENSITY_DIFFERENCE;
        }

        return result;
    }

    /**
     *
     * @param particle
     * <br>Should not be null
     * <br>Input-output parameter
     */
    private static final void constrainSpeed(final ParticleDefaultImplementation particle) {
        final float speed = length(particle.getSpeedX(), particle.getSpeedY());

        if (speed > ARBITRARY_MAXIMUM_SPEED) {
            particle.setSpeedX(particle.getSpeedX() / speed * ARBITRARY_MAXIMUM_SPEED);
            particle.setSpeedY(particle.getSpeedY() / speed * ARBITRARY_MAXIMUM_SPEED);
        }
        else {
            particle.setSpeedX(particle.getSpeedX() * ARBITRARY_SPEED_DECAY);
            particle.setSpeedY(particle.getSpeedY() * ARBITRARY_SPEED_DECAY);
        }
    }

    private static final float ARBITRARY_SPEED_DECAY = 0.99F;

    /**
     * 
     * @author codistmonk (2010-04-26)
     */
    private static final class DensityMap {

        private float[][] data;

        public DensityMap() {
            this.setSize(0, 0);
        }

        /**
         *
         * @param data
         * <br>Should not be null
         * <br>Reference parameter
         */
        private DensityMap(final float[][] data) {
            this.data = data;
        }

        /**
         *
         * @param particle
         * <br>Should not be null
         */
        public final void addParticle(final Particle particle) {
            for (int i = 0; i < PARTICLE_MASS_DISTRIBUTION.getWidth(); ++i) {
                for (int j = 0; j < PARTICLE_MASS_DISTRIBUTION.getHeight(); ++j) {
                    final float x = particle.getX() - PARTICLE_MASS_DISTRIBUTION_HALF_WIDTH + i;
                    final float y = particle.getY() - PARTICLE_MASS_DISTRIBUTION_HALF_HEIGHT + j;

                    this.setDensity(x, y, this.getDensity(x, y) + particle.getType().getMass() * PARTICLE_MASS_DISTRIBUTION.getDensity(i, j));
                }
            }
        }

        /**
         *
         * @param particle
         * <br>Should not be null
         */
        public final void removeParticle(final Particle particle) {
            for (int i = 0; i < PARTICLE_MASS_DISTRIBUTION.getWidth(); ++i) {
                for (int j = 0; j < PARTICLE_MASS_DISTRIBUTION.getHeight(); ++j) {
                    final float x = particle.getX() - PARTICLE_MASS_DISTRIBUTION_HALF_WIDTH + i;
                    final float y = particle.getY() - PARTICLE_MASS_DISTRIBUTION_HALF_HEIGHT + j;
                    
                    this.setDensity(x, y, this.getDensity(x, y) - particle.getType().getMass() * PARTICLE_MASS_DISTRIBUTION.getDensity(i, j));
                }
            }
        }

        /**
         * 
         * @param width
         * <br>Range: <code>[0 .. Integer.MAX_VALUE]</code>
         * @param height
         * <br>Range: <code>[0 .. Integer.MAX_VALUE]</code>
         */
        public final void setSize(final int width, final int height) {
            this.data = new float[width][height];
        }

        /**
         *
         * @param x
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @param y
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @return
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         */
        public final float getDensity(final float x, final float y) {
            return this.isSingular() ? 0F : (this.isInside(x, y) ? this.data[(int) x][(int) y] : Float.POSITIVE_INFINITY);
        }

        /**
         *
         * @param x
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @param y
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @param value
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         */
        public final void setDensity(final float x, final float y, final float value) {
            if (this.isInside(x, y)) {
                this.data[(int) x][(int) y] = value;
            }
        }

        /**
         *
         * @param x
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @param y
         * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
         * @return
         */
        public final boolean isInside(final float x, final float y) {
            return 0 <= x && x < this.getWidth() && 0 <= y && y < this.getHeight();
        }

        /**
         *
         * @return
         * Range: <code>[0 .. Integer.MAX_VALUE]</code>
         */
        public final int getWidth() {
            return this.data.length;
        }

        /**
         *
         * @return
         * Range: <code>[0 .. Integer.MAX_VALUE]</code>
         */
        public final int getHeight() {
            return this.data.length == 0 ? 0 : this.data[0].length;
        }

        /**
         * 
         * @return <code>true</code> if <code>this</code> width or height is 0
         */
        private final boolean isSingular() {
            return this.getWidth() == 0 || this.getHeight() == 0;
        }

        private static final float SQRT2 = (float) sqrt(2.0);

        private static final DensityMap PARTICLE_MASS_DISTRIBUTION;

        private static final int PARTICLE_MASS_DISTRIBUTION_HALF_WIDTH;

        private static final int PARTICLE_MASS_DISTRIBUTION_HALF_HEIGHT;

        static {
            final float corner = 1F / (8F * (1F + SQRT2));
            final float border = SQRT2 * corner;
            final float center = 0.5F;

            assert 4F * (corner + border) + center == 1F;

            PARTICLE_MASS_DISTRIBUTION = new DensityMap(new float[][] {
                { corner, border, corner },
                { border, center, border },
                { corner, border, corner },
            });
            PARTICLE_MASS_DISTRIBUTION_HALF_WIDTH = PARTICLE_MASS_DISTRIBUTION.getWidth() / 2;
            PARTICLE_MASS_DISTRIBUTION_HALF_HEIGHT = PARTICLE_MASS_DISTRIBUTION.getHeight() / 2;
        }

    }

}