Page MenuHomeWildfire Games
Paste P131

Poisson disc sampling.
ActivePublic

Authored by lyv on Sep 14 2018, 8:12 PM.
Index: binaries/data/mods/public/maps/random/rmgen/math.js
===================================================================
--- binaries/data/mods/public/maps/random/rmgen/math.js (revision 21862)
+++ binaries/data/mods/public/maps/random/rmgen/math.js (working copy)
@@ -173,3 +173,58 @@
return order;
}
+
+function poissondiskSamples(width, height, r, k = 30)
+{
+ let cellSize = r / Math.sqrt(2); // sqrt of the dimension of the grid.
+ let gridWidth = Math.ceil(width / cellSize);
+ let gridHeight = Math.ceil(height / cellSize);
+ let grid = new Array(gridWidth * gridHeight);
+
+ let point = new Vector2D(width * Math.random(), height * Math.random());
+ let queue = [point];
+ let gridX = Math.floor(point.x / cellSize);
+ let gridY = Math.floor(point.y / cellSize);
+
+ grid[gridX + gridY * gridWidth] = point;
+
+ let ret = [];
+ ret.push(point);
+
+ while (queue.length)
+ {
+ let randPoint = pickRandom(queue);
+ queue.splice(0, 1);
+
+ for (let i = 0; i < k; ++i)
+ {
+ let randAngle = randomAngle();
+ let randDist = r * Math.sqrt(3 * Math.random() + 1);
+
+ let newPoint = new Vector2D(randPoint.x + randDist * Math.cos(randAngle), randPoint.y + randDist * Math.sin(randAngle));
+ if (newPoint.x < 0 || newPoint.x > width || newPoint.y < 0 || newPoint.y > height)
+ continue;
+
+ let [gridx, gridy] = [Math.floor(newPoint.x / cellSize), Math.floor(newPoint.y / cellSize)];
+ let gridPoints = [];
+
+ for (let x = Math.max(gridx - 2, 0); x < Math.min(gridx + 3, gridWidth); ++x)
+ for (let y = Math.max(gridy - 2, 0); y < Math.min(gridy + 3, gridHeight); ++y)
+ {
+ let gridPoint = grid[x + y * gridWidth]
+ if (!gridPoint)
+ continue;
+ gridPoints.push(gridPoint);
+ }
+
+ if (gridPoints.every(point => point.distanceTo(newPoint) > r))
+ {
+ queue.push(newPoint);
+ grid[gridx + gridy * gridWidth] = newPoint;
+ ret.push(newPoint);
+ }
+ }
+ }
+
+ return ret;
+}

Event Timeline

lyv created this paste.Sep 14 2018, 8:12 PM

An interesting thing which can be useful. Used for distributing points uniformly (with slight random variations) in a given area.

nani added a subscriber: nani.Sep 15 2018, 12:37 AM

@FeXoR @elexis , is this worth having?

While this might be useful IMO this implementation is a bit over the top in terms of line numbers, resource use and complexity since a difference to other distributions like linear drop with distance or squarerooting (and at some point cutting) the radial parameter of a random roll will likely go unnoticed ;p

So I don't really see a need for this but if it's used in a map I'm OK to add it.

OFC I'm always happy to be educated (e.g. that it makes a notable difference) ;)

elexis changed the visibility from "All Users" to "Public (No Login Required)".Mar 20 2019, 4:17 PM