001package squidpony.squidmath;
002
003import squidpony.squidgrid.Radius;
004
005import java.util.ArrayList;
006import java.util.Collections;
007import java.util.HashSet;
008import java.util.LinkedHashSet;
009
010/**
011 * This provides a Uniform Poisson Disk Sampling technique that can be used to generate random points that have a
012 * uniform minimum distance between each other. Due to Coord in SquidLib using ints and most Poisson Disk algorithms
013 * using floating-point numbers, some imprecision is to be expected from rounding to the nearest integers x and y.
014 *
015 * The algorithm is from the "Fast Poisson Disk Sampling in Arbitrary Dimensions" paper by Robert Bridson
016 * http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf
017 *
018 * Adapted from C# by Renaud Bedard, which was adapted from Java source by Herman Tulleken
019 * http://theinstructionlimit.com/fast-uniform-poisson-disk-sampling-in-c
020 * Created by Tommy Ettinger on 10/20/2015.
021 */
022public class PoissonDisk {
023    private static final float rootTwo = (float) Math.sqrt(2),
024            pi = (float) Math.PI, pi2 = pi * 2f, halfPi = pi * 0.5f;
025    
026    private static final int defaultPointsPlaced = 10;
027    private static final Radius disk = Radius.CIRCLE;
028
029    private PoissonDisk() {
030    }
031
032    /**
033     * Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with
034     * Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list.
035     * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have
036     * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have
037     * negative x or y.
038     * @param center the center of the circle to spray Coords into
039     * @param radius the radius of the circle to spray Coords into
040     * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float.
041     * @param maxX one more than the highest x that can be assigned; typically an array length
042     * @param maxY one more than the highest y that can be assigned; typically an array length
043     * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary
044     */
045    public static ArrayList<Coord> sampleCircle(Coord center, float radius, float minimumDistance,
046                                                int maxX, int maxY)
047    {
048        return sampleCircle(center, radius, minimumDistance, maxX, maxY, defaultPointsPlaced, new StatefulRNG());
049    }
050
051    /**
052     * Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with
053     * Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list.
054     * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have
055     * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have
056     * negative x or y.
057     * @param center the center of the circle to spray Coords into
058     * @param radius the radius of the circle to spray Coords into
059     * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float.
060     * @param maxX one more than the highest x that can be assigned; typically an array length
061     * @param maxY one more than the highest y that can be assigned; typically an array length
062     * @param pointsPerIteration with small radii, this can be around 5; with larger ones, 30 is reasonable
063     * @param rng an RNG to use for all random sampling.
064     * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary
065     */
066    public static ArrayList<Coord> sampleCircle(Coord center, float radius, float minimumDistance,
067                                                int maxX, int maxY, int pointsPerIteration, RNG rng)
068    {
069        int radius2 = Math.round(radius);
070        return sample(center.translate(-radius2, -radius2), center.translate(radius2, radius2), radius, minimumDistance, maxX, maxY, pointsPerIteration, rng);
071    }
072
073    /**
074     * Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and
075     * maxPosition, but with the given minimum distance from any other Coord in the list.
076     * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have
077     * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have
078     * negative x or y.
079     * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box
080     * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box
081     * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float.
082     * @param maxX one more than the highest x that can be assigned; typically an array length
083     * @param maxY one more than the highest y that can be assigned; typically an array length
084     * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary
085     */
086    public static ArrayList<Coord> sampleRectangle(Coord minPosition, Coord maxPosition, float minimumDistance,
087                                                   int maxX, int maxY)
088    {
089        return sampleRectangle(minPosition, maxPosition, minimumDistance, maxX, maxY, defaultPointsPlaced, new StatefulRNG());
090    }
091
092    /**
093     * Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and
094     * maxPosition, but with the given minimum distance from any other Coord in the list.
095     * The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have
096     * positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have
097     * negative x or y.
098     * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box
099     * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box
100     * @param minimumDistance the minimum distance between Coords, in Euclidean distance as a float.
101     * @param maxX one more than the highest x that can be assigned; typically an array length
102     * @param maxY one more than the highest y that can be assigned; typically an array length
103     * @param pointsPerIteration with small areas, this can be around 5; with larger ones, 30 is reasonable
104     * @param rng an RNG to use for all random sampling.
105     * @return an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary
106     */
107    public static ArrayList<Coord> sampleRectangle(Coord minPosition, Coord maxPosition, float minimumDistance,
108                                                   int maxX, int maxY, int pointsPerIteration, RNG rng)
109    {
110        return sample(minPosition, maxPosition, 0f, minimumDistance, maxX, maxY, pointsPerIteration, rng);
111    }
112
113    private static ArrayList<Coord> sample(Coord minPosition, Coord maxPosition, float rejectionDistance,
114                                           float minimumDistance, int maxX, int maxY, int pointsPerIteration, RNG rng)
115    {
116
117        Coord center = minPosition.average(maxPosition);
118        Coord dimensions = maxPosition.subtract(minPosition);
119        float cellSize = Math.max(minimumDistance / rootTwo, 0.25f);
120        int gridWidth = (int)(dimensions.x / cellSize) + 1;
121        int gridHeight = (int)(dimensions.y / cellSize) + 1;
122        Coord[][] grid = new Coord[gridWidth][gridHeight];
123        ArrayList<Coord> activePoints = new ArrayList<>();
124        LinkedHashSet<Coord> points = new LinkedHashSet<>(128);
125
126        //add first point
127        boolean added = false;
128        while (!added)
129        {
130            float d = rng.nextFloat();
131            int xr = Math.round(minPosition.x + dimensions.x * d);
132
133            d = rng.nextFloat();
134            int yr = Math.round(minPosition.y + dimensions.y * d);
135
136            if (rejectionDistance > 0 && disk.radius(center.x, center.y, xr, yr) > rejectionDistance)
137                continue;
138            added = true;
139            Coord p = Coord.get(Math.min(xr, maxX - 1), Math.min(yr, maxY - 1));
140            Coord index = p.subtract(minPosition).divide(cellSize);
141
142            grid[index.x][index.y] = p;
143
144            activePoints.add(p);
145            points.add(p);
146        }
147        //end add first point
148
149        while (activePoints.size() != 0)
150        {
151            int listIndex = rng.nextInt(activePoints.size());
152
153            Coord point = activePoints.get(listIndex);
154            boolean found = false;
155
156            for (int k = 0; k < pointsPerIteration; k++)
157            {
158                //add next point
159                //get random point around
160                float d = rng.nextFloat();
161                float radius = minimumDistance + minimumDistance * d;
162                d = rng.nextFloat();
163                float angle = pi2 * d;
164
165                float newX = radius * (float)Math.sin(angle);
166                float newY = radius * (float)Math.cos(angle);
167                Coord q = point.translateCapped(Math.round(newX), Math.round(newY), maxX, maxY);
168                //end get random point around
169
170                if (q.x >= minPosition.x && q.x <= maxPosition.x &&
171                        q.y >= minPosition.y && q.y <= maxPosition.y &&
172                        (rejectionDistance <= 0 || disk.radius(center.x, center.y, q.x, q.y) <= rejectionDistance))
173                {
174                    Coord qIndex = q.subtract(minPosition).divide((int)Math.ceil(cellSize));
175                    boolean tooClose = false;
176
177                    for (int i = Math.max(0, qIndex.x - 2); i < Math.min(gridWidth, qIndex.x + 3) && !tooClose; i++) {
178                        for (int j = Math.max(0, qIndex.y - 2); j < Math.min(gridHeight, qIndex.y + 3); j++) {
179                            if (grid[i][j] != null && disk.radius(grid[i][j], q) < minimumDistance) {
180                                tooClose = true;
181                                break;
182                            }
183                        }
184                    }
185                    if (!tooClose)
186                    {
187                        found = true;
188                        activePoints.add(q);
189                        points.add(q);
190                        grid[qIndex.x][qIndex.y] = q;
191                    }
192                }
193                //end add next point
194            }
195
196            if (!found)
197                activePoints.remove(listIndex);
198        }
199        activePoints = new ArrayList<>(points);
200        return activePoints;
201    }
202
203    public static ArrayList<Coord> sampleMap(char[][] map,
204                                             float minimumDistance, RNG rng, Character... blocking)
205    {
206        return sampleMap(Coord.get(1, 1), Coord.get(map.length - 2, map[0].length - 2),
207                map, minimumDistance, rng, blocking);
208    }
209
210    public static ArrayList<Coord> sampleMap(Coord minPosition, Coord maxPosition, char[][] map,
211                                             float minimumDistance, RNG rng, Character... blocking) {
212        int width = map.length;
213        int height = map[0].length;
214        HashSet<Character> blocked = new HashSet<>();
215        Collections.addAll(blocked, blocking);
216        boolean restricted = false;
217        if (blocked.size() > 0) {
218            restricted = true;
219        }
220        Coord dimensions = maxPosition.subtract(minPosition);
221        float cellSize = Math.max(minimumDistance / rootTwo, 1f);
222        int gridWidth = (int) (dimensions.x / cellSize) + 1;
223        int gridHeight = (int) (dimensions.y / cellSize) + 1;
224        Coord[][] grid = new Coord[gridWidth][gridHeight];
225        ArrayList<Coord> activePoints = new ArrayList<>();
226        LinkedHashSet<Coord> points = new LinkedHashSet<>(128);
227
228        //add first point
229
230        Coord p = randomUnblockedTile(minPosition, maxPosition, map, rng, blocked);
231        if (p == null)
232            return activePoints;
233        Coord index = p.subtract(minPosition).divide(cellSize);
234
235        grid[index.x][index.y] = p;
236
237        activePoints.add(p);
238        points.add(p);
239
240        //end add first point
241
242        while (activePoints.size() != 0) {
243            int listIndex = rng.nextInt(activePoints.size());
244
245            Coord point = activePoints.get(listIndex);
246            boolean found = false;
247
248            for (int k = 0; k < 20; k++) {
249                //add next point
250                //get random point around
251                float d = rng.nextFloat();
252                float radius = minimumDistance + minimumDistance * d;
253                d = rng.nextFloat();
254                float angle = pi2 * d;
255
256                float newX = radius * (float) Math.sin(angle);
257                float newY = radius * (float) Math.cos(angle);
258                Coord q = point.translateCapped(Math.round(newX), Math.round(newY), width, height);
259                int frustration = 0;
260                while(blocked.contains(map[q.x][q.y]) && frustration < 8)
261                {
262                    d = rng.nextFloat();
263                    angle = pi2 * d;
264                    newX = radius * (float) Math.sin(angle);
265                    newY = radius * (float) Math.cos(angle);
266                    q = point.translateCapped(Math.round(newX), Math.round(newY), width, height);
267                    frustration++;
268                }
269
270                //end get random point around
271
272                if (q.x >= minPosition.x && q.x <= maxPosition.x &&
273                        q.y >= minPosition.y && q.y <= maxPosition.y) {
274                    Coord qIndex = q.subtract(minPosition).divide((int) Math.ceil(cellSize));
275                    boolean tooClose = false;
276
277                    for (int i = Math.max(0, qIndex.x - 2); i < Math.min(gridWidth, qIndex.x + 3) && !tooClose; i++) {
278                        for (int j = Math.max(0, qIndex.y - 2); j < Math.min(gridHeight, qIndex.y + 3); j++) {
279                            if (grid[i][j] != null && disk.radius(grid[i][j], q) < minimumDistance) {
280                                tooClose = true;
281                                break;
282                            }
283                        }
284                    }
285                    if (!tooClose) {
286                        found = true;
287                        activePoints.add(q);
288                        if(!blocked.contains(map[q.x][q.y]))
289                            points.add(q);
290                        grid[qIndex.x][qIndex.y] = q;
291                    }
292                }
293                //end add next point
294            }
295
296            if (!found)
297                activePoints.remove(listIndex);
298        }
299        activePoints = new ArrayList<>(points);
300        return activePoints;
301    }
302    /**
303     * Finds a random Coord where the x and y match up to a [x][y] location on map that has any value not in blocking.
304     * Uses the given RNG for pseudo-random number generation.
305     * @param minPosition the Coord with the lowest x and lowest y to be used as a corner for the bounding box
306     * @param maxPosition the Coord with the highest x and highest y to be used as a corner for the bounding box
307     * @param map a dungeon map or something, x then y
308     * @param rng a RNG to generate random choices
309     * @param blocked a Set of Characters that block a tile from being chosen
310     * @return a Coord that corresponds to a map element equal to tile, or null if tile cannot be found or if map is too small.
311     */
312    public static Coord randomUnblockedTile(Coord minPosition, Coord maxPosition, char[][] map, RNG rng, HashSet<Character> blocked)
313    {
314        int width = map.length;
315        int height = map[0].length;
316        if(width < 3 || height < 3)
317            return null;
318        if(blocked.size() == 0) {
319            return Coord.get(rng.between(minPosition.x, maxPosition.x), rng.between(minPosition.y, maxPosition.y));
320        }
321
322        int x = rng.between(minPosition.x, maxPosition.x), y = rng.between(minPosition.y, maxPosition.y);
323        for(int i = 0; i < (width + height) / 4; i++)
324        {
325            if(!blocked.contains(map[x][y]))
326            {
327                return Coord.get(x, y);
328            }
329            else
330            {
331                x = rng.between(minPosition.x, maxPosition.x);
332                y = rng.between(minPosition.y, maxPosition.y);
333            }
334        }
335        x = 1;
336        y = 1;
337        if(!blocked.contains(map[x][y]))
338            return Coord.get(x, y);
339
340        while(blocked.contains(map[x][y]))
341        {
342            x += 1;
343            if(x >= width - 1)
344            {
345                x = 1;
346                y += 1;
347            }
348            if(y >= height - 1)
349                return null;
350        }
351        return Coord.get(x, y);
352    }
353
354}