001package squidpony.squidgrid;
002
003import squidpony.squidmath.Coord;
004import squidpony.squidmath.Coord3D;
005import squidpony.squidmath.RNG;
006
007import java.util.LinkedHashSet;
008import java.util.Set;
009
010/**
011 * Basic radius strategy implementations likely to be used for roguelikes.
012 *
013 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
014 */
015public enum Radius {
016
017    /**
018     * In an unobstructed area the FOV would be a square.
019     *
020     * This is the shape that would represent movement radius in an 8-way
021     * movement scheme with no additional cost for diagonal movement.
022     */
023    SQUARE,
024    /**
025     * In an unobstructed area the FOV would be a diamond.
026     *
027     * This is the shape that would represent movement radius in a 4-way
028     * movement scheme.
029     */
030    DIAMOND,
031    /**
032     * In an unobstructed area the FOV would be a circle.
033     *
034     * This is the shape that would represent movement radius in an 8-way
035     * movement scheme with all movement cost the same based on distance from
036     * the source
037     */
038    CIRCLE,
039    /**
040     * In an unobstructed area the FOV would be a cube.
041     *
042     * This is the shape that would represent movement radius in an 8-way
043     * movement scheme with no additional cost for diagonal movement.
044     */
045    CUBE,
046    /**
047     * In an unobstructed area the FOV would be a octahedron.
048     *
049     * This is the shape that would represent movement radius in a 4-way
050     * movement scheme.
051     */
052    OCTAHEDRON,
053    /**
054     * In an unobstructed area the FOV would be a sphere.
055     *
056     * This is the shape that would represent movement radius in an 8-way
057     * movement scheme with all movement cost the same based on distance from
058     * the source
059     */
060    SPHERE;
061
062    private static final double PI2 = Math.PI * 2;
063    public double radius(int startx, int starty, int startz, int endx, int endy, int endz) {
064        return radius((double) startx, (double) starty, (double) startz, (double) endx, (double) endy, (double) endz);
065    }
066
067    public double radius(double startx, double starty, double startz, double endx, double endy, double endz) {
068        double dx = Math.abs(startx - endx);
069        double dy = Math.abs(starty - endy);
070        double dz = Math.abs(startz - endz);
071        return radius(dx, dy, dz);
072    }
073
074    public double radius(int dx, int dy, int dz) {
075        return radius((float) dx, (float) dy, (float) dz);
076    }
077
078    public double radius(double dx, double dy, double dz) {
079        dx = Math.abs(dx);
080        dy = Math.abs(dy);
081        dz = Math.abs(dz);
082        double radius = 0;
083        switch (this) {
084            case SQUARE:
085            case CUBE:
086                radius = Math.max(dx, Math.max(dy, dz));//radius is longest axial distance
087                break;
088            case DIAMOND:
089            case OCTAHEDRON:
090                radius = dx + dy + dz;//radius is the manhattan distance
091                break;
092            case CIRCLE:
093            case SPHERE:
094                radius = Math.sqrt(dx * dx + dy * dy + dz * dz);//standard spherical radius
095        }
096        return radius;
097    }
098
099    public double radius(int startx, int starty, int endx, int endy) {
100        return radius((double) startx, (double) starty, (double) endx, (double) endy);
101    }
102    public double radius(Coord start, Coord end) {
103        return radius((double) start.x, (double) start.y, (double) end.x, (double) end.y);
104    }
105    public double radius(Coord end) {
106        return radius(0.0, 0.0, (double) end.x, (double) end.y);
107    }
108
109    public double radius(double startx, double starty, double endx, double endy) {
110        double dx = startx - endx;
111        double dy = starty - endy;
112        return radius(dx, dy);
113    }
114
115    public double radius(int dx, int dy) {
116        return radius((double) dx, (double) dy);
117    }
118
119    public double radius(double dx, double dy) {
120        return radius(dx, dy, 0);
121    }
122
123    public Coord onUnitShape(double distance, RNG rng) {
124        int x = 0, y = 0;
125        switch (this) {
126            case SQUARE:
127            case CUBE:
128                x = rng.between((int) -distance, (int) distance + 1);
129                y = rng.between((int) -distance, (int) distance + 1);
130                break;
131            case DIAMOND:
132            case OCTAHEDRON:
133                x = rng.between((int) -distance, (int) distance + 1);
134                y = rng.between((int) -distance, (int) distance + 1);
135                if (radius(x, y) > distance) {
136                    if (x > 0) {
137                        if (y > 0) {
138                            x = (int) (distance - x);
139                            y = (int) (distance - y);
140                        } else {
141                            x = (int) (distance - x);
142                            y = (int) (-distance - y);
143                        }
144                    } else {
145                        if (y > 0) {
146                            x = (int) (-distance - x);
147                            y = (int) (distance - y);
148                        } else {
149                            x = (int) (-distance - x);
150                            y = (int) (-distance - y);
151                        }
152                    }
153                }
154                break;
155            case CIRCLE:
156            case SPHERE:
157                double radius = distance * Math.sqrt(rng.between(0.0, 1.0));
158                double theta = rng.between(0, PI2);
159                x = (int) Math.round(Math.cos(theta) * radius);
160                y = (int) Math.round(Math.sin(theta) * radius);
161        }
162
163        return Coord.get(x, y);
164    }
165
166    public Coord3D onUnitShape3D(double distance, RNG rng) {
167        int x = 0, y = 0, z = 0;
168        switch (this) {
169            case SQUARE:
170            case DIAMOND:
171            case CIRCLE:
172                Coord p = onUnitShape(distance, rng);
173                return new Coord3D(p.x, p.y, 0);//2D strategies
174            case CUBE:
175                x = rng.between((int) -distance, (int) distance + 1);
176                y = rng.between((int) -distance, (int) distance + 1);
177                z = rng.between((int) -distance, (int) distance + 1);
178                break;
179            case OCTAHEDRON:
180            case SPHERE:
181                do {
182                    x = rng.between((int) -distance, (int) distance + 1);
183                    y = rng.between((int) -distance, (int) distance + 1);
184                    z = rng.between((int) -distance, (int) distance + 1);
185                } while (radius(x, y, z) > distance);
186        }
187
188        return new Coord3D(x, y, z);
189    }
190    public double volume2D(double radiusLength)
191    {
192        switch (this) {
193            case SQUARE:
194            case CUBE:
195                return (radiusLength * 2 + 1) * (radiusLength * 2 + 1);
196            case DIAMOND:
197            case OCTAHEDRON:
198                return radiusLength * (radiusLength + 1) * 2 + 1;
199            default:
200                return Math.PI * radiusLength * radiusLength + 1;
201        }
202    }
203    public double volume3D(double radiusLength)
204    {
205        switch (this) {
206            case SQUARE:
207            case CUBE:
208                return (radiusLength * 2 + 1) * (radiusLength * 2 + 1) * (radiusLength * 2 + 1);
209            case DIAMOND:
210            case OCTAHEDRON:
211                double total = radiusLength * (radiusLength + 1) * 2 + 1;
212                for(double i = radiusLength - 1; i >= 0; i--)
213                {
214                    total += (i * (i + 1) * 2 + 1) * 2;
215                }
216                return total;
217            default:
218                return Math.PI * radiusLength * radiusLength * radiusLength * 4.0 / 3.0 + 1;
219        }
220    }
221
222
223
224
225    private int clamp(int n, int min, int max)
226    {
227        return Math.min(Math.max(min, n), max - 1);
228    }
229
230    public Set<Coord> perimeter(Coord center, int radiusLength, boolean surpassEdges, int width, int height)
231    {
232        LinkedHashSet<Coord> rim = new LinkedHashSet<>(4 * radiusLength);
233        if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y > height))
234            return rim;
235        if(radiusLength < 1) {
236            rim.add(center);
237            return rim;
238        }
239        switch (this) {
240            case SQUARE:
241            case CUBE:
242            {
243                for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) {
244                    int x = i;
245                    if(!surpassEdges) x = clamp(i, 0, width);
246                    rim.add(Coord.get(x, clamp(center.y - radiusLength, 0, height)));
247                    rim.add(Coord.get(x, clamp(center.y + radiusLength, 0, height)));
248                }
249                for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) {
250                    int y = j;
251                    if(!surpassEdges) y = clamp(j, 0, height);
252                    rim.add(Coord.get(clamp(center.x - radiusLength, 0, height), y));
253                    rim.add(Coord.get(clamp(center.x + radiusLength, 0, height), y));
254                }
255            }
256            break;
257            case DIAMOND:
258            case OCTAHEDRON: {
259                int xUp = center.x + radiusLength, xDown = center.x - radiusLength,
260                        yUp = center.y + radiusLength, yDown = center.y - radiusLength;
261                if(!surpassEdges) {
262                    xDown = clamp(xDown, 0, width);
263                    xUp = clamp(xUp, 0, width);
264                    yDown = clamp(yDown, 0, height);
265                    yUp = clamp(yUp, 0, height);
266                }
267
268                rim.add(Coord.get(xDown, center.y));
269                rim.add(Coord.get(xUp, center.y));
270                rim.add(Coord.get(center.x, yDown));
271                rim.add(Coord.get(center.x, yUp));
272
273                for (int i = xDown + 1, c = 1; i < center.x; i++, c++) {
274                    int x = i;
275                    if(!surpassEdges) x = clamp(i, 0, width);
276                    rim.add(Coord.get(x, clamp(center.y - c, 0, height)));
277                    rim.add(Coord.get(x, clamp(center.y + c, 0, height)));
278                }
279                for (int i = center.x + 1, c = 1; i < center.x + radiusLength; i++, c++) {
280                    int x = i;
281                    if(!surpassEdges) x = clamp(i, 0, width);
282                    rim.add(Coord.get(x, clamp(center.y + radiusLength - c, 0, height)));
283                    rim.add(Coord.get(x, clamp(center.y - radiusLength + c, 0, height)));
284                }
285            }
286            break;
287            default:
288            {
289                double theta;
290                int x, y, denom = 1;
291                boolean anySuccesses;
292                while(denom <= 256) {
293                    anySuccesses = false;
294                    for (int i = 1; i <= denom; i+=2)
295                    {
296                        theta = i * (PI2 / denom);
297                        x = (int) Math.round(Math.cos(theta) * radiusLength) + center.x;
298                        y = (int) Math.round(Math.sin(theta) * radiusLength) + center.y;
299                        if (!surpassEdges) {
300                            x = clamp(x, 0, width);
301                            y = clamp(y, 0, height);
302                        }
303                        Coord p = Coord.get(x, y);
304                        boolean test = rim.contains(p);
305
306                        rim.add(p);
307                        anySuccesses = test || anySuccesses;
308                    }
309                    if(!anySuccesses)
310                        break;
311                    denom *= 2;
312                }
313
314            }
315        }
316        return rim;
317    }
318    public Coord extend(Coord center, Coord middle, int radiusLength, boolean surpassEdges, int width, int height)
319    {
320        if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y > height ||
321                middle.x < 0 || middle.x >= width || middle.y < 0 || middle.y > height))
322            return Coord.get(0, 0);
323        if(radiusLength < 1) {
324            return center;
325        }
326        double theta = Math.atan2(middle.y - center.y, middle.x - center.x),
327                cosTheta = Math.cos(theta), sinTheta = Math.sin(theta);
328
329        Coord end = Coord.get(middle.x, middle.y);
330        switch (this) {
331            case SQUARE:
332            case CUBE:
333            case DIAMOND:
334            case OCTAHEDRON:
335            {
336                int rad2 = 0;
337                if(surpassEdges)
338                {
339                    while (radius(center.x, center.y, end.x, end.y) < radiusLength) {
340                        rad2++;
341                        end = Coord.get((int) Math.round(cosTheta * rad2) + center.x
342                                , (int) Math.round(sinTheta * rad2) + center.y);
343                    }
344                }
345                else {
346                    while (radius(center.x, center.y, end.x, end.y) < radiusLength) {
347                        rad2++;
348                        end = Coord.get(clamp((int) Math.round(cosTheta * rad2) + center.x, 0, width)
349                                      , clamp((int) Math.round(sinTheta * rad2) + center.y, 0, height));
350                        if (end.x == 0 || end.x == width - 1 || end.y == 0 || end.y == height - 1)
351                            return end;
352                    }
353                }
354
355                return end;
356            }
357            default:
358            {
359                end = Coord.get(clamp( (int) Math.round(cosTheta * radiusLength) + center.x, 0, width)
360                        , clamp( (int) Math.round(sinTheta * radiusLength) + center.y, 0, height));
361                if(!surpassEdges) {
362                    long edgeLength = 0;
363//                    if (end.x == 0 || end.x == width - 1 || end.y == 0 || end.y == height - 1)
364                    if (end.x < 0)
365                    {
366                        // wow, we lucked out here. the only situation where cos(angle) is 0 is if the angle aims
367                        // straight up or down, and then x cannot be < 0 or >= width.
368                        edgeLength = Math.round((0 - center.x) / cosTheta);
369                        end = end.setY(clamp((int) Math.round(sinTheta * edgeLength) + center.y, 0, height));
370                    }
371                    else if(end.x >= width)
372                    {
373                        // wow, we lucked out here. the only situation where cos(angle) is 0 is if the angle aims
374                        // straight up or down, and then x cannot be < 0 or >= width.
375                        edgeLength = Math.round((width - 1 - center.x) / cosTheta);
376                        end = end.setY(clamp((int) Math.round(sinTheta * edgeLength) + center.y, 0, height));
377                    }
378
379                    if (end.y < 0)
380                    {
381                        // wow, we lucked out here. the only situation where sin(angle) is 0 is if the angle aims
382                        // straight left or right, and then y cannot be < 0 or >= height.
383                        edgeLength = Math.round((0 - center.y) / sinTheta);
384                        end = end.setX(clamp((int) Math.round(cosTheta * edgeLength) + center.x, 0, width));
385                    }
386                    else if(end.y >= height)
387                    {
388                        // wow, we lucked out here. the only situation where sin(angle) is 0 is if the angle aims
389                        // straight left or right, and then y cannot be < 0 or >= height.
390                        edgeLength = Math.round((height - 1 - center.y) / sinTheta);
391                        end = end.setX(clamp((int) Math.round(cosTheta * edgeLength) + center.x, 0, width));
392                    }
393                }
394                return end;
395            }
396        }
397    }
398
399    /**
400     * Compares two Radius enums as if they are both in a 2D plane; that is, Radius.SPHERE is treated as equal to
401     * Radius.CIRCLE, Radius.CUBE is equal to Radius.SQUARE, and Radius.OCTAHEDRON is equal to Radius.DIAMOND.
402     * @param other the Radius to compare this to
403     * @return true if the 2D versions of both Radius enums are the same shape.
404     */
405    public boolean equals2D(Radius other)
406    {
407        switch (this)
408        {
409            case CIRCLE:
410            case SPHERE:
411                return (other == CIRCLE || other == SPHERE);
412            case SQUARE:
413            case CUBE:
414                return (other == SQUARE || other == CUBE);
415            default:
416                return (other == DIAMOND || other == OCTAHEDRON);
417        }
418    }
419    public boolean inRange(int startx, int starty, int endx, int endy, int minRange, int maxRange)
420    {
421        double dist = radius(startx, starty, endx, endy);
422        return dist >= minRange - 0.001 && dist <= maxRange + 0.001;
423    }
424
425    public int roughDistance(int xPos, int yPos) {
426        int x = Math.abs(xPos), y = Math.abs(yPos);
427        switch (this) {
428            case CIRCLE:
429            case SPHERE:
430            {
431                if(x == y)
432                    return 3 * x;
433                else if(x < y)
434                    return 3 * x + 2 * (y - x);
435                else
436                    return 3 * y + 2 * (x - y);
437            }
438            case DIAMOND:
439            case OCTAHEDRON:
440                return 2 * (x + y);
441            default:
442                return 2 * Math.max(x, y);
443        }
444    }
445
446    public Set<Coord> pointsInside(Coord center, int radiusLength, boolean surpassEdges, int width, int height)
447    {
448        LinkedHashSet<Coord> contents = new LinkedHashSet<Coord>((int)Math.ceil(volume2D(radiusLength)));
449        if(!surpassEdges && (center.x < 0 || center.x >= width || center.y < 0 || center.y >= height))
450            return contents;
451        if(radiusLength < 1) {
452            contents.add(center);
453            return contents;
454        }
455        switch (this) {
456            case SQUARE:
457            case CUBE:
458            {
459                for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) {
460                    for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) {
461                        if(!surpassEdges && (i < 0 || j < 0 || i >= width || j >= height))
462                            continue;
463                        contents.add(Coord.get(i, j));
464                    }
465                }
466            }
467            break;
468            case DIAMOND:
469            case OCTAHEDRON: {
470                for (int i = center.x - radiusLength; i <= center.x + radiusLength; i++) {
471                    for (int j = center.y - radiusLength; j <= center.y + radiusLength; j++) {
472                        if ((Math.abs(center.x - i) + Math.abs(center.y- j) > radiusLength) ||
473                                (!surpassEdges && (i < 0 || j < 0 || i >= width || j >= height)))
474                            continue;
475                        contents.add(Coord.get(i, j));
476                    }
477                }
478            }
479            break;
480            default:
481            {
482                int high;
483                for (int dx = -radiusLength; dx <= radiusLength; ++dx) {
484                    high = (int) Math.floor(Math.sqrt(radiusLength * radiusLength - dx * dx));
485                    for (int dy = -high; dy <= high; ++dy) {
486                        if (!surpassEdges && (center.x + dx < 0 || center.y + dy < 0 ||
487                                center.x + dx >= width || center.y + dy >= height))
488                            continue;
489                        contents.add(Coord.get(center.x + dx, center.y + dy));
490                    }
491                }
492            }
493        }
494        return contents;
495    }
496
497    /**
498     * Given an Iterable of Coord (such as a List or Set), a distance to expand outward by (using this Radius), and the
499     * bounding height and width of the map, gets a "thickened" group of Coord as a Set where each Coord in points has
500     * been expanded out by an amount no greater than distance. As an example, you could call this on a line generated
501     * by Bresenham, OrthoLine, or an LOS object's getLastPath() method, and expand the line into a thick "brush stroke"
502     * where this Radius affects the shape of the ends. This will never produce a Coord with negative x or y, a Coord
503     * with x greater than or equal to width, or a Coord with y greater than or equal to height.
504     * @param distance the distance, as measured by this Radius, to expand each Coord on points up to
505     * @param width the bounding width of the map (exclusive)
506     * @param height the bounding height of the map (exclusive)
507     * @param points an Iterable (such as a List or Set) of Coord that this will make a "thickened" version of
508     * @return a Set of Coord that covers a wider area than what points covers; each Coord will be unique (it's a Set)
509     */
510    public Set<Coord> expand(int distance, int width, int height, Iterable<Coord> points)
511    {
512        Set<Coord> around = pointsInside(Coord.get(distance, distance), distance, false, width, height),
513                expanded = new LinkedHashSet<>(around.size() * 16);
514        int tx, ty;
515        for(Coord pt : points)
516        {
517            for(Coord ar : around)
518            {
519                tx = pt.x + ar.x - distance;
520                ty = pt.y + ar.y - distance;
521                if(tx >= 0 && tx < width && ty >= 0 && ty < height)
522                    expanded.add(Coord.get(tx, ty));
523            }
524        }
525        return expanded;
526    }
527}