1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 package com.jme3.terrain.heightmap; 33 34 import java.util.logging.Logger; 35 36 /** 37 * <code>ParticleDepositionHeightMap</code> creates a heightmap based on the 38 * Particle Deposition algorithm based on Jason Shankel's paper from 39 * "Game Programming Gems". A heightmap is created using a Molecular beam 40 * epitaxy, or MBE, for depositing thin layers of atoms on a substrate. 41 * We drop a sequence of particles and simulate their flow across a surface 42 * of previously dropped particles. This creates a few high peaks, for further 43 * realism we can define a caldera. Similar to the way volcano's form 44 * islands, rock is deposited via lava, when the lava cools, it recedes 45 * into the volcano, creating the caldera. 46 * 47 * @author Mark Powell 48 * @version $Id$ 49 */ 50 public class ParticleDepositionHeightMap extends AbstractHeightMap { 51 52 private static final Logger logger = Logger.getLogger(ParticleDepositionHeightMap.class.getName()); 53 //Attributes. 54 private int jumps; 55 private int peakWalk; 56 private int minParticles; 57 private int maxParticles; 58 private float caldera; 59 60 /** 61 * Constructor sets the attributes of the Particle Deposition 62 * Height Map and then generates the map. 63 * 64 * @param size the size of the terrain where the area is size x size. 65 * @param jumps number of areas to drop particles. Can also think 66 * of it as the number of peaks. 67 * @param peakWalk determines how much to agitate the drop point 68 * during a creation of a single peak. The lower the number 69 * the more the drop point will be agitated. 1 will insure 70 * agitation every round. 71 * @param minParticles defines the minimum number of particles to 72 * drop during a single jump. 73 * @param maxParticles defines the maximum number of particles to 74 * drop during a single jump. 75 * @param caldera defines the altitude to invert a peak. This is 76 * represented as a percentage, where 0.0 will not invert 77 * anything, and 1.0 will invert all. 78 * 79 * @throws JmeException if any value is less than zero, and 80 * if caldera is not between 0 and 1. If minParticles is greater than 81 * max particles as well. 82 */ 83 public ParticleDepositionHeightMap( 84 int size, 85 int jumps, 86 int peakWalk, 87 int minParticles, 88 int maxParticles, 89 float caldera) throws Exception { 90 91 92 if (size <= 0 93 || jumps < 0 94 || peakWalk < 0 95 || minParticles > maxParticles 96 || minParticles < 0 97 || maxParticles < 0) { 98 99 100 throw new Exception( 101 "values must be greater than zero, " 102 + "and minParticles must be greater than maxParticles"); 103 } 104 if (caldera < 0.0f || caldera > 1.0f) { 105 throw new Exception( 106 "Caldera level must be " + "between 0 and 1"); 107 } 108 109 110 this.size = size; 111 this.jumps = jumps; 112 this.peakWalk = peakWalk; 113 this.minParticles = minParticles; 114 this.maxParticles = maxParticles; 115 this.caldera = caldera; 116 117 118 load(); 119 } 120 121 /** 122 * <code>load</code> generates the heightfield using the Particle Deposition 123 * algorithm. <code>load</code> uses the latest attributes, so a call 124 * to <code>load</code> is recommended if attributes have changed using 125 * the set methods. 126 */ 127 public boolean load() { 128 int x, y; 129 int calderaX, calderaY; 130 int sx, sy; 131 int tx, ty; 132 int m; 133 float calderaStartPoint; 134 float cutoff; 135 int dx[] = {0, 1, 0, size - 1, 1, 1, size - 1, size - 1}; 136 int dy[] = {1, 0, size - 1, 0, size - 1, 1, size - 1, 1}; 137 float[][] tempBuffer = new float[size][size]; 138 //map 0 unmarked, unvisited, 1 marked, unvisited, 2 marked visited. 139 int[][] calderaMap = new int[size][size]; 140 boolean done; 141 142 143 int minx, maxx; 144 int miny, maxy; 145 146 147 if (null != heightData) { 148 unloadHeightMap(); 149 } 150 151 152 heightData = new float[size * size]; 153 154 155 //create peaks. 156 for (int i = 0; i < jumps; i++) { 157 158 159 //pick a random point. 160 x = (int) (Math.rint(Math.random() * (size - 1))); 161 y = (int) (Math.rint(Math.random() * (size - 1))); 162 163 164 //set the caldera point. 165 calderaX = x; 166 calderaY = y; 167 168 169 int numberParticles = 170 (int) (Math.rint( 171 (Math.random() * (maxParticles - minParticles)) 172 + minParticles)); 173 //drop particles. 174 for (int j = 0; j < numberParticles; j++) { 175 //check to see if we should aggitate the drop point. 176 if (peakWalk != 0 && j % peakWalk == 0) { 177 m = (int) (Math.rint(Math.random() * 7)); 178 x = (x + dx[m] + size) % size; 179 y = (y + dy[m] + size) % size; 180 } 181 182 183 //add the particle to the piont. 184 tempBuffer[x][y] += 1; 185 186 187 sx = x; 188 sy = y; 189 done = false; 190 191 192 //cause the particle to "slide" down the slope and settle at 193 //a low point. 194 while (!done) { 195 done = true; 196 197 198 //check neighbors to see if we are higher. 199 m = (int) (Math.rint((Math.random() * 8))); 200 for (int jj = 0; jj < 8; jj++) { 201 tx = (sx + dx[(jj + m) % 8]) % (size); 202 ty = (sy + dy[(jj + m) % 8]) % (size); 203 204 205 //move to the neighbor. 206 if (tempBuffer[tx][ty] + 1.0f < tempBuffer[sx][sy]) { 207 tempBuffer[tx][ty] += 1.0f; 208 tempBuffer[sx][sy] -= 1.0f; 209 sx = tx; 210 sy = ty; 211 done = false; 212 break; 213 } 214 } 215 } 216 217 218 //This point is higher than the current caldera point, 219 //so move the caldera here. 220 if (tempBuffer[sx][sy] > tempBuffer[calderaX][calderaY]) { 221 calderaX = sx; 222 calderaY = sy; 223 } 224 } 225 226 227 //apply the caldera. 228 calderaStartPoint = tempBuffer[calderaX][calderaY]; 229 cutoff = calderaStartPoint * (1.0f - caldera); 230 minx = calderaX; 231 maxx = calderaX; 232 miny = calderaY; 233 maxy = calderaY; 234 235 236 calderaMap[calderaX][calderaY] = 1; 237 238 239 done = false; 240 while (!done) { 241 done = true; 242 sx = minx; 243 sy = miny; 244 tx = maxx; 245 ty = maxy; 246 247 248 for (x = sx; x <= tx; x++) { 249 for (y = sy; y <= ty; y++) { 250 251 252 calderaX = (x + size) % size; 253 calderaY = (y + size) % size; 254 255 256 if (calderaMap[calderaX][calderaY] == 1) { 257 calderaMap[calderaX][calderaY] = 2; 258 259 260 if (tempBuffer[calderaX][calderaY] > cutoff 261 && tempBuffer[calderaX][calderaY] 262 <= calderaStartPoint) { 263 264 265 done = false; 266 tempBuffer[calderaX][calderaY] = 267 2 * cutoff - tempBuffer[calderaX][calderaY]; 268 269 270 //check the left and right neighbors 271 calderaX = (calderaX + 1) % size; 272 if (calderaMap[calderaX][calderaY] == 0) { 273 if (x + 1 > maxx) { 274 maxx = x + 1; 275 } 276 calderaMap[calderaX][calderaY] = 1; 277 } 278 279 280 calderaX = (calderaX + size - 2) % size; 281 if (calderaMap[calderaX][calderaY] == 0) { 282 if (x - 1 < minx) { 283 minx = x - 1; 284 } 285 calderaMap[calderaX][calderaY] = 1; 286 } 287 288 289 //check the upper and lower neighbors. 290 calderaX = (x + size) % size; 291 calderaY = (calderaY + 1) % size; 292 if (calderaMap[calderaX][calderaY] == 0) { 293 if (y + 1 > maxy) { 294 maxy = y + 1; 295 } 296 calderaMap[calderaX][calderaY] = 1; 297 } 298 calderaY = (calderaY + size - 2) % size; 299 if (calderaMap[calderaX][calderaY] == 0) { 300 if (y - 1 < miny) { 301 miny = y - 1; 302 } 303 calderaMap[calderaX][calderaY] = 1; 304 } 305 } 306 } 307 } 308 } 309 } 310 } 311 312 //transfer the new terrain into the height map. 313 for (int i = 0; i < size; i++) { 314 for (int j = 0; j < size; j++) { 315 setHeightAtPoint((float) tempBuffer[i][j], j, i); 316 } 317 } 318 erodeTerrain(); 319 normalizeTerrain(NORMALIZE_RANGE); 320 321 logger.info("Created heightmap using Particle Deposition"); 322 323 324 return false; 325 } 326 327 /** 328 * <code>setJumps</code> sets the number of jumps or peaks that will 329 * be created during the next call to <code>load</code>. 330 * @param jumps the number of jumps to use for next load. 331 * @throws JmeException if jumps is less than zero. 332 */ 333 public void setJumps(int jumps) throws Exception { 334 if (jumps < 0) { 335 throw new Exception("jumps must be positive"); 336 } 337 this.jumps = jumps; 338 } 339 340 /** 341 * <code>setPeakWalk</code> sets how often the jump point will be 342 * aggitated. The lower the peakWalk, the more often the point will 343 * be aggitated. 344 * 345 * @param peakWalk the amount to aggitate the jump point. 346 * @throws JmeException if peakWalk is negative or zero. 347 */ 348 public void setPeakWalk(int peakWalk) throws Exception { 349 if (peakWalk <= 0) { 350 throw new Exception( 351 "peakWalk must be greater than " + "zero"); 352 } 353 this.peakWalk = peakWalk; 354 } 355 356 /** 357 * <code>setCaldera</code> sets the level at which a peak will be 358 * inverted. 359 * 360 * @param caldera the level at which a peak will be inverted. This must be 361 * between 0 and 1, as it is represented as a percentage. 362 * @throws JmeException if caldera is not between 0 and 1. 363 */ 364 public void setCaldera(float caldera) throws Exception { 365 if (caldera < 0.0f || caldera > 1.0f) { 366 throw new Exception( 367 "Caldera level must be " + "between 0 and 1"); 368 } 369 this.caldera = caldera; 370 } 371 372 /** 373 * <code>setMaxParticles</code> sets the maximum number of particles 374 * for a single jump. 375 * @param maxParticles the maximum number of particles for a single jump. 376 * @throws JmeException if maxParticles is negative or less than 377 * the current number of minParticles. 378 */ 379 public void setMaxParticles(int maxParticles) { 380 this.maxParticles = maxParticles; 381 } 382 383 /** 384 * <code>setMinParticles</code> sets the minimum number of particles 385 * for a single jump. 386 * @param minParticles the minimum number of particles for a single jump. 387 * @throws JmeException if minParticles are greater than 388 * the current maxParticles; 389 */ 390 public void setMinParticles(int minParticles) throws Exception { 391 if (minParticles > maxParticles) { 392 throw new Exception( 393 "minParticles must be less " + "than the current maxParticles"); 394 } 395 this.minParticles = minParticles; 396 } 397 } 398