src/net/sourceforge/desert/ParticleEngine.java

   1 /*
   2  * Copyright (c) 2010 The Desert team
   3  *
   4  * Permission is hereby granted, free of charge, to any person
   5  * obtaining a copy of this software and associated documentation
   6  * files (the "Software"), to deal in the Software without
   7  * restriction, including without limitation the rights to use,
   8  * copy, modify, merge, publish, distribute, sublicense, and/or sell
   9  * copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following
  11  * conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be
  14  * included in all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  18  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  20  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  21  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  22  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  23  * OTHER DEALINGS IN THE SOFTWARE.
  24  *
  25  */
  26 package net.sourceforge.desert;
  27
  28 import static java.lang.Math.*;
  29
  30 import java.awt.Dimension;
  31 import java.util.ArrayList;
  32 import java.util.Arrays;
  33 import java.util.Iterator;
  34 import java.util.List;
  35
  36 /**
  37  * A particle engine is an object responsible for the creation, storage, enumeration and update of particles.
  38  * <br>Warning: for engines that don't use Particle internally, the recommended way to implement
  39  * iteration is is to always return the same particle object updated for each actual particle.
  40  * <br>This is to avoid creating and destroying temporary objects, thus improving memory usage and speed.
  41  * <br>Therefore, when iterating over a ParticleEngine, users shouldn't expect a particle to be a different
  42  * object than the previous one (only the state might change).
  43  * <br>The same caution is required with the iterator objects: concurrent iteration is generally not supported.
  44  * @author codistmonk (creation 2010-04-17)
  45  */
  46 public class ParticleEngine implements Iterable<Particle> {
  47
  48     private final List<Particle> particles;
  49
  50     private float gravity;
  51
  52     private Dimension boardSize;
  53
  54     private long newParticleId;
  55
  56     private ParticleCellularImplementation[][] cells;
  57
  58     private final ParticleCellularImplementation borderParticle;
  59
  60     /**
  61      * This variable is part of a temporary measure to detect particle deletion.
  62      * <br>TODO remove when deletion is handled correctly
  63      */
  64     private int lastParticleCount;
  65
  66     public ParticleEngine() {
  67         this.particles = new ArrayList<Particle>();
  68         this.newParticleId = Long.MIN_VALUE;
  69         this.borderParticle = this.new ParticleCellularImplementation(Particle.Type.IMMOBILE,
  70                 Float.POSITIVE_INFINITY, Float.POSITIVE_INFINITY, 0F, 0F);
  71
  72         this.setGravity(MAXIMUM_SPEED * signum(DEFAULT_GRAVITY));
  73     }
  74
  75     /**
  76      *
  77      * @return a non-null value iff bounds are defined
  78      * <br>A possibly null value
  79      * <br>Can be a reference
  80      */
  81     public final Dimension getBoardSize() {
  82         return this.boardSize;
  83     }
  84
  85     /**
  86      * Sets the size of the rectangle enclosing the board and thus limiting the movements of the particles;
  87      * if it is <code>null</code> then these limits are removed and the particle are free to go outside of the board.
  88      * <br>If the size is set to a non-null value while some particles are outside the board,
  89      * then these particles should be brought back inside in a limited amount of time.
  90      * @param size
  91      * <br>Can be null
  92      * <br>Can be a reference parameter
  93      * <br>Can be a new value
  94      */
  95     public final void setBoardSize(final Dimension size) {
  96         this.boardSize = size;
  97         this.boardSizeChanged();
  98     }
  99
 100     /**
 101      *
 102      * @return
 103      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 104      */
 105     public final float getGravity() {
 106         return this.gravity;
 107     }
 108
 109     /**
 110      * The gravity is vertical.
 111      * <br>Positive values are upward.
 112      * @param gravity
 113      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 114      */
 115     public final void setGravity(final float gravity) {
 116         this.gravity = gravity;
 117     }
 118
 119     public final void removeAllParticles() {
 120         this.particles.clear();
 121     }
 122
 123     /**
 124      *
 125      * @param type
 126      * <br>Should not be null
 127      * @param x
 128      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 129      * @param y
 130      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 131      * @param speedX
 132      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 133      * @param speedY
 134      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 135      */
 136     public final void addParticle(final Particle.Type type, final float x, final float y,
 137             final float speedX, final float speedY, final float mass) {
 138         final ParticleDefaultImplementation particle = this.createParticle(type, x, y, speedX, speedY);
 139
 140         this.particles.add(particle);
 141         this.particleAdded(particle);
 142     }
 143
 144     /**
 145      *
 146      * @return
 147      * <br>Range: <code>[0 .. Integer.MAX_VALUE]</code>
 148      */
 149     public final int getParticleCount() {
 150         return this.particles.size();
 151     }
 152
 153     @Override
 154     public final Iterator<Particle> iterator() {
 155         return ((Iterable<Particle>) this.particles).iterator();
 156     }
 157
 158     /**
 159      * Updates the positions and speeds of all the particles.
 160      * @param deltaTime in seconds
 161      * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
 162      */
 163     public final void update(float deltaTime) {
 164         this.updateCells();
 165
 166         this.applyForces(deltaTime);
 167
 168         this.updatePositions(deltaTime);
 169     }
 170
 171     /**
 172      * The default implementation returns an instance of ParticleDefaultImplementation.
 173      * @param type
 174      * <br>Should not be null
 175      * @param x
 176      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 177      * @param y
 178      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 179      * @param speedX
 180      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 181      * @param speedY
 182      * <br>Range: <code>]Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY[</code>
 183      * @return
 184      * <br>A non-null value
 185      * <br>A new value
 186      */
 187     protected final ParticleDefaultImplementation createParticle(final Particle.Type type, final float x, final float y,
 188             final float speedX, final float speedY) {
 189         return new ParticleCellularImplementation(type, x, y, speedX, speedY);
 190     }
 191
 192     /**
 193      * This method should be overriden if a special action must be executed just
 194      * after a particle has been added.
 195      * @param particle
 196      * <br>Should not be null
 197      * <br>Reference parameter
 198      */
 199     protected final void particleAdded(final ParticleDefaultImplementation particle) {
 200         this.setCell(particle.getX(), particle.getY(), (ParticleCellularImplementation) particle);
 201     }
 202
 203     /**
 204      * This method should be overriden if a special action must be executed just
 205      * after the board size has been changed.
 206      */
 207     protected final void boardSizeChanged() {
 208         if (this.getBoardSize() != null && this.getBoardSize().width > 0 && this.getBoardSize().height > 0) {
 209             this.cells = new ParticleCellularImplementation[this.getBoardSize().width][this.getBoardSize().height];
 210
 211             this.fillCells();
 212         } else {
 213             this.cells = null;
 214         }
 215     }
 216
 217     /**
 218      * Constrains the particle inside the bounding rectangle if it exists.
 219      * @param particle
 220      * <br>Should not be null
 221      * <br>Input-output parameter
 222      */
 223     protected final void constrainPosition(final ParticleDefaultImplementation particle) {
 224         if (this.getBoardSize() != null) {
 225             // Left bound
 226             if (particle.getX() < 0F) {
 227                 particle.setX(0F);
 228                 particle.setSpeedX(abs(particle.getSpeedX()));
 229             }
 230             // Top bound
 231             if (particle.getY() < 0F) {
 232                 particle.setY(0F);
 233                 particle.setSpeedY(abs(particle.getSpeedY()));
 234             }
 235             // Right bound
 236             if (particle.getX() >= this.getBoardSize().width) {
 237                 particle.setX(this.getBoardSize().width - 1F);
 238                 particle.setSpeedX(-abs(particle.getSpeedX()));
 239             }
 240             // Bottom bound
 241             if (particle.getY() >= this.getBoardSize().height) {
 242                 particle.setY(this.getBoardSize().height - 1F);
 243                 particle.setSpeedY(-abs(particle.getSpeedY()));
 244             }
 245         }
 246     }
 247
 248     /**
 249      *
 250      * @return
 251      * <br>Range: any long
 252      */
 253     final long generateNewId() {
 254         return this.newParticleId++;
 255     }
 256
 257     /**
 258      * Does nothing if <code>x</code> and <code>y</code> do not locate a valid cell
 259      * that contains no particle or a mobile particle.
 260      * @param x
 261      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 262      * @param y
 263      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 264      * @param particle
 265      * <br>Can be null
 266      * <br>Reference parameter
 267      */
 268     final void setCell(final float x, final float y, final ParticleCellularImplementation particle) {
 269         assert particle == null || (int) x == (int) particle.getX() : x + " " + y + " " + particle;
 270         assert particle == null || (int) y == (int) particle.getY() : x + " " + y + " " + particle;
 271
 272         if (this.isInGrid(x, y) &&
 273                 (this.cells[(int) x][(int) y] == null || this.cells[(int) x][(int) y].getType().isMobile())) {
 274             this.cells[(int) x][(int) y] = particle;
 275         }
 276     }
 277
 278     /**
 279      * TODO add more elements to act more earth-like
 280      * @param deltaTime in seconds
 281      * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
 282      */
 283     private void applyForces(final float deltaTime) {
 284         for (final ParticleCellularImplementation particle : this.getParticles()) {
 285             if (particle.getType().isMobile()) {
 286                 if (particle.getType() == Particle.Type.WATER || particle.getType() == Particle.Type.LAVA ||
 287                         particle.getType() == Particle.Type.SAND || particle.getType() == Particle.Type.OIL) {
 288                     if (particle.getSpeedX() == 0F && particle.getSpeedY() == 0F) {
 289                         final float direction = (random() * 4) > 2 ? 1F : -1F;
 290
 291                         if (this.isCellTraversable(particle.getX() + direction, particle.getY(), particle)) {
 292                             particle.setSpeedX(direction * MAXIMUM_SPEED * (0.50F + (float) random()) - particle.getMass());
 293                         }
 294                         else if (this.isCellTraversable(particle.getX() - direction, particle.getY(), particle)) {
 295                             particle.setSpeedX(-direction * MAXIMUM_SPEED * (0.50F + (float) random()) - particle.getMass());
 296                         }
 297                     }
 298                 }
 299
 300                 particle.setSpeedY(particle.getSpeedY() +
 301                         deltaTime * (this.getGravity() - particle.getMass() * AIR_FRICTION_COEFFICIENT));
 302
 303                 if (abs(particle.getSpeedY()) > MAXIMUM_SPEED) {
 304                     particle.setSpeedY(signum(particle.getSpeedY()) * MAXIMUM_SPEED);
 305                 }
 306             }
 307         }
 308     }
 309
 310     /**
 311      *
 312      * @param deltaTime
 313      * <br>Range: <code>[0F .. Float.POSITIVE_INFINITY[</code>
 314      */
 315     private void updatePositions(final float deltaTime) {
 316         for (final ParticleCellularImplementation particle : this.getParticles()) {
 317             if (particle.getType().isMobile()) {
 318                 final float dX = signum(particle.getSpeedX());
 319                 final float dY = signum(particle.getSpeedY());
 320                 final float deltaX = particle.getSpeedX() * deltaTime;
 321                 final float deltaY = particle.getSpeedY() * deltaTime;
 322                 final float oldX = particle.getX();
 323                 final float oldY = particle.getY();
 324                 final float newX = max(0F, min(this.getWidth() - 1F, oldX + deltaX));
 325                 final float newY = max(0F, min(this.getHeight() - 1F, oldY + deltaY));
 326
 327                 if (oldX == newX || ((int) oldX != (int) newX && !this.isCellTraversable(oldX + dX, oldY, particle))) {
 328                     particle.setSpeedX(0F);
 329                 }
 330
 331                 if (oldY == newY || ((int) oldY != (int) newY && !this.isCellTraversable(oldX, oldY + dY, particle))) {
 332                     particle.setSpeedY(0F);
 333                 }
 334
 335                 this.tryAndMove(particle,
 336                         particle.getSpeedX() == 0F ? oldX : newX,
 337                         particle.getSpeedY() == 0F ? oldY : newY);
 338             }
 339         }
 340     }
 341
 342     private void fillCells() {
 343         for (final ParticleCellularImplementation particle : this.getParticles()) {
 344             this.setCell(particle.getX(), particle.getY(), particle);
 345         }
 346     }
 347
 348     /**
 349      * This method returns <code>this.borderParticle</code> if the coordinates do not locate a valid cell.
 350      * @param x
 351      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 352      * @param y
 353      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 354      * @return
 355      * <br>A non-null value
 356      * <br>A reference
 357      */
 358     private ParticleCellularImplementation getParticle(final float x, final float y) {
 359         return this.isInGrid(x, y) ? this.cells[(int) x][(int) y] : this.borderParticle;
 360     }
 361
 362     /**
 363      *
 364      * @return
 365      * <br>A non-null value
 366      * <br>A reference
 367      */
 368     @SuppressWarnings("unchecked")
 369     private Iterable<ParticleCellularImplementation> getParticles() {
 370         return (Iterable) this;
 371     }
 372
 373     /**
 374      *
 375      * @return
 376      * <br>Range: <code>[1 .. Integer.MAX_VALUE]</code>
 377      */
 378     private int getHeight() {
 379         return this.cells != null ? this.cells[0].length : Integer.MAX_VALUE;
 380     }
 381
 382     /**
 383      *
 384      * @return
 385      * <br>Range: <code>[1 .. Integer.MAX_VALUE]</code>
 386      */
 387     private int getWidth() {
 388         return this.cells != null ? this.cells.length : Integer.MAX_VALUE;
 389     }
 390
 391     private void updateCells() {
 392         if (this.cells != null && this.getParticleCount() != this.lastParticleCount) {
 393             for (int x = 0; x < this.cells.length; ++x) {
 394                 Arrays.fill(this.cells[x], null);
 395             }
 396
 397             this.fillCells();
 398
 399             this.lastParticleCount = this.getParticleCount();
 400         }
 401     }
 402
 403     /**
 404      *
 405      * @param particle
 406      * <br>Should not be null
 407      * <br>Input-output parameter
 408      * <br>Reference parameter
 409      * @param newX
 410      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 411      * @param newY
 412      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 413      */
 414     private void tryAndMove(final ParticleCellularImplementation particle, final float newX, final float newY) {
 415         particle.setTargetLocation(newX, newY);
 416
 417         final ParticleCellularImplementation target = this.getParticle(newX, newY);
 418
 419         if (target == null) {
 420             particle.processReplacementCandidate(particle);
 421         } else {
 422             target.processReplacementCandidate(particle);
 423         }
 424     }
 425
 426     /**
 427      *
 428      * @param x
 429      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 430      * @param y
 431      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 432      * @param particle
 433      * <br>Should not be null
 434      * @return
 435      */
 436     private boolean isCellTraversable(final float x, final float y, final Particle particle) {
 437         return this.isInGrid(x, y) && (this.cells[(int) x][(int) y] == null ||
 438                 this.cells[(int) x][(int) y].getType().getMass() < particle.getType().getMass());
 439     }
 440
 441     /**
 442      *
 443      * @param x
 444      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 445      * @param y
 446      * <br>Range: <code>[Float.NEGATIVE_INFINITY .. Float.POSITIVE_INFINITY]</code>
 447      * @return
 448      */
 449     private boolean isInGrid(final float x, final float y) {
 450         return this.cells != null && 0F <= x && x < this.cells.length && 0F <= y && y < this.cells[0].length;
 451     }
 452
 453     /**
 454      *
 455      * @author codistmonk (creation 2010-05-06)
 456      */
 457     private final class ParticleCellularImplementation extends ParticleDefaultImplementation {
 458
 459         private final long id;
 460
 461         private final List<ParticleCellularImplementation> replacementCandidates;
 462
 463         private float targetX;
 464
 465         private float targetY;
 466
 467         /**
 468          *
 469          * @param type
 470          * <br>Should not be null
 471          * @param x
 472          * <br>Should not be null
 473          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 474          * @param y
 475          * <br>Should not be null
 476          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 477          * @param speedX
 478          * <br>Should not be null
 479          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 480          * @param speedY
 481          * <br>Should not be null
 482          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 483          */
 484         public ParticleCellularImplementation(final Type type, final float x, final float y,
 485                 final float speedX, final float speedY) {
 486             super(type, x, y, speedX, speedY);
 487             this.id = ParticleEngine.this.generateNewId();
 488             this.replacementCandidates = new ArrayList<ParticleCellularImplementation>(4);
 489         }
 490
 491         public ParticleCellularImplementation() {
 492             this(Type.values()[0], 0F, 0F, 0F, 0F);
 493         }
 494
 495         /**
 496          *
 497          * @param particle
 498          * <br>Should not be null
 499          * <br>Input-output parameter
 500          * <br>Reference parameter
 501          */
 502         public final void processReplacementCandidate(final ParticleCellularImplementation particle) {
 503             assert this == particle || (int) particle.targetX == (int) this.getX() : this + " " + particle;
 504             assert this == particle || (int) particle.targetY == (int) this.getY() : this + " " + particle;
 505
 506             if (!this.getType().isMobile()) {
 507                 return;
 508             }
 509
 510             if (particle.getType().getMass() > this.getType().getMass()) {
 511                 this.replacementCandidates.clear();
 512                 this.replacementCandidates.addAll(particle.replacementCandidates);
 513                 particle.replacementCandidates.clear();
 514                 this.setTargetLocation(particle.getX(), particle.getY());
 515                 this.move();
 516                 particle.updateNewLocation(particle.targetX, particle.targetY);
 517             } else if (particle.id < this.id) {
 518                 this.replacementCandidates.add(particle);
 519             } else if (particle.id == this.id) {
 520                 this.move();
 521             }
 522         }
 523
 524         /**
 525          *
 526          * @param targetX
 527          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 528          * @param targetY
 529          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 530          */
 531         public final void setTargetLocation(final float targetX, final float targetY) {
 532             this.targetX = targetX;
 533             this.targetY = targetY;
 534         }
 535
 536         private void move() {
 537             if ((int) this.targetX != this.getX() || (int) this.targetY != this.getY()) {
 538                 this.updateOldAndNewLocation(this.targetX, this.targetY);
 539
 540                 if (!this.replacementCandidates.isEmpty()) {
 541                     final ParticleCellularImplementation replacement = this.replacementCandidates.get(0);
 542
 543                     this.replacementCandidates.clear();
 544
 545                     replacement.move();
 546                 }
 547             } else {
 548                 this.updateOldAndNewLocation(this.targetX, this.targetY);
 549             }
 550         }
 551
 552         /**
 553          *
 554          * @param newX
 555          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 556          * @param newY
 557          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 558          */
 559         private void updateOldAndNewLocation(final float newX, final float newY) {
 560             ParticleEngine.this.setCell(this.getX(), this.getY(), null);
 561
 562             this.updateNewLocation(newX, newY);
 563         }
 564
 565         /**
 566          *
 567          * @param newX
 568          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 569          * @param newY
 570          * <br>Range: <code>]float.NEGATIVE_INFINITY .. float.POSITIVE_INFINITY[</code>
 571          */
 572         private void updateNewLocation(final float newX, final float newY) {
 573             this.setX(newX);
 574             this.setY(newY);
 575
 576             ParticleEngine.this.setCell(this.getX(), this.getY(), this);
 577         }
 578
 579     }
 580
 581     private static final float MAXIMUM_SPEED = 25F;
 582
 583     private static final float AIR_FRICTION_COEFFICIENT = 25F;
 584
 585     public static final float DEFAULT_GRAVITY = -8F;
 586
 587 }