001package squidpony.squidgrid;
002
003import squidpony.annotation.GwtIncompatible;
004import squidpony.squidmath.*;
005
006import java.util.*;
007
008/**
009 * Line of Sight (LOS) algorithms find if there is or is not a path between two
010 * given points.
011 *
012 * The line found between two points will end at either the target, the
013 * obstruction closest to the start, or the edge of the map.
014 *
015 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
016 */
017public class LOS {
018
019    //constants to indicate desired type of solving algorithm to use
020    /**
021     * A Bresenham-based line-of-sight algorithm.
022     */
023    public static final int BRESENHAM = 1;
024    /**
025     * Uses Wu's Algorithm as modified by Elias to draw the line. Does
026     * not end at an obstruction but rather returns one of the possible
027     * attempted paths in full.
028     *
029     * <p>
030     * Beware it is Gwt incompatible.
031     * </p>
032     */
033    public static final int ELIAS = 2;
034    /**
035     * Uses a series of rays internal to the start and end point to
036     * determine visibility. Does not respect translucency.
037     */
038    public static final int RAY = 3;
039    /**
040     * Draws a line using only North/South/East/West movement.
041     */
042    public static final int ORTHO = 4;
043    /**
044     * Optimized algorithm for Bresenham-like lines. There are slight
045     * differences in many parts of the lines this draws when compared
046     * to Bresenham lines, but it may also perform significantly better,
047     * and may also be useful as a building block for more complex LOS.
048     */
049    public static final int DDA = 5;
050    /**
051     * Draws a line as if with a thick brush, going from a point between
052     * a corner of the starting cell and the center of the starting cell
053     * to the corresponding corner of the target cell, and considers the
054     * target visible if any portion of the thick stroke reached it. Will
055     * result in 1-width lines for exactly-orthogonal or exactly-diagonal
056     * lines and some parts of other lines, but usually is 2 cells wide.
057     */
058    public static final int THICK = 6;
059    private Queue<Coord> lastPath = new LinkedList<>();
060    private int type;
061    private double[][] resistanceMap;
062    private int startx, starty, targetx, targety;
063    private Elias elias = null;
064
065    /**
066     * Gets the radius strategy this uses.
067     * @return the current Radius enum used to measure distance; starts at CIRCLE if not specified
068     */
069    public Radius getRadiusStrategy() {
070        return radiusStrategy;
071    }
072
073    /**
074     * Set the radius strategy to the given Radius; the default is CIRCLE if this is not called.
075     * @param radiusStrategy a Radius enum to determine how distances are measured
076     */
077    public void setRadiusStrategy(Radius radiusStrategy) {
078        this.radiusStrategy = radiusStrategy;
079    }
080
081    private Radius radiusStrategy = Radius.CIRCLE;
082
083    /**
084     * Constructs an LOS that will draw Bresenham lines and measure distances using the CIRCLE radius strategy.
085     */
086    public LOS() {
087        this(BRESENHAM);
088    }
089
090    /**
091     * Constructs an LOS with the given type number, which must equal a static field in this class such as BRESENHAM.
092     * @param type an int that must correspond to the value of a static field in this class (such as BRESENHAM)
093     */
094    public LOS(int type) {
095        this.type = type;
096        if(type == ELIAS)
097            elias = new Elias();
098    }
099
100    /**
101     * Returns true if a line can be drawn from the start point to the target
102     * point without intervening obstructions.
103     *
104     * Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy .
105     *
106     * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
107     * @param startx starting x position on the grid
108     * @param starty starting y position on the grid
109     * @param targetx ending x position on the grid
110     * @param targety ending y position on the grid
111     * @return true if a line can be drawn without being obstructed, false otherwise
112     */
113    public boolean isReachable(char[][] walls, int startx, int starty, int targetx, int targety) {
114        if(walls.length < 1) return false;
115        double[][] resMap = new double[walls.length][walls[0].length];
116        for(int x = 0; x < walls.length; x++)
117        {
118            for(int y = 0; y < walls[0].length; y++)
119            {
120                resMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0;
121            }
122        }
123        return isReachable(resMap, startx, starty, targetx, targety, radiusStrategy);
124    }
125
126    /**
127     * Returns true if a line can be drawn from the start point to the target
128     * point without intervening obstructions.
129     *
130     * Does not take into account resistance less than opaque or distance cost.
131     *
132     * Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy .
133     *
134     * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
135     * @param startx starting x position on the grid
136     * @param starty starting y position on the grid
137     * @param targetx ending x position on the grid
138     * @param targety ending y position on the grid
139     * @return true if a line can be drawn without being obstructed, false otherwise
140     */
141    public boolean isReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety) {
142        return isReachable(resistanceMap, startx, starty, targetx, targety, radiusStrategy);
143    }
144
145    /**
146     * Returns true if a line can be drawn from the start point to the target
147     * point without intervening obstructions.
148     *
149     * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
150     * @param startx starting x position on the grid
151     * @param starty starting y position on the grid
152     * @param targetx ending x position on the grid
153     * @param targety ending y position on the grid
154     * @param radiusStrategy the strategy to use in computing unit distance
155     * @return true if a line can be drawn without being obstructed, false otherwise
156     */
157    public boolean isReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy) {
158        if(resistanceMap.length < 1) return false;
159        this.resistanceMap = resistanceMap;
160        this.startx = startx;
161        this.starty = starty;
162        this.targetx = targetx;
163        this.targety = targety;
164        switch (type) {
165            case BRESENHAM:
166                return bresenhamReachable(radiusStrategy);
167            case ELIAS:
168                throw new IllegalStateException("Elias LOS is Gwt Incompatible");
169                /* FIXME Find a way around that */
170                // Required to compile with GWT:
171                // return eliasReachable(radiusStrategy);
172            case RAY:
173                return rayReachable(radiusStrategy);
174            case ORTHO:
175                return orthoReachable(radiusStrategy);
176            case DDA:
177                return ddaReachable(radiusStrategy);
178            case THICK:
179                return thickReachable(radiusStrategy);
180        }
181        return false;
182    }
183
184    /**
185     * Returns true if a line can be drawn from the start point to the target
186     * point without intervening obstructions.
187     *
188     * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
189     * @param startx starting x position on the grid
190     * @param starty starting y position on the grid
191     * @param targetx ending x position on the grid
192     * @param targety ending y position on the grid
193     * @param radiusStrategy the strategy to use in computing unit distance
194     * @return true if a line can be drawn without being obstructed, false otherwise
195     */
196    public boolean isReachable(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy) {
197        if(walls.length < 1) return false;
198        double[][] resMap = new double[walls.length][walls[0].length];
199        for(int x = 0; x < walls.length; x++)
200        {
201            for(int y = 0; y < walls[0].length; y++)
202            {
203                resMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0;
204            }
205        }
206        return isReachable(resMap, startx, starty, targetx, targety, radiusStrategy);
207    }
208
209    /**
210     * Returns true if a line can be drawn from the any of the points within spread cells of the start point,
211     * to any of the corresponding points at the same direction and distance from the target point, without
212     * intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath.
213     *
214     * @param walls '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
215     * @param startx starting x position on the grid
216     * @param starty starting y position on the grid
217     * @param targetx ending x position on the grid
218     * @param targety ending y position on the grid
219     * @param radiusStrategy the strategy to use in computing unit distance
220     * @param spread the number of cells outward, measured by radiusStrategy, to place extra start and target points
221     * @return true if a line can be drawn without being obstructed, false otherwise
222     */
223    public boolean spreadReachable(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread) {
224        if(walls.length < 1) return false;
225        resistanceMap = new double[walls.length][walls[0].length];
226        for(int x = 0; x < walls.length; x++)
227        {
228            for(int y = 0; y < walls[0].length; y++)
229            {
230                resistanceMap[x][y] = (walls[x][y] == '#') ? 1.0 : 0.0;
231            }
232        }
233        this.startx = startx;
234        this.starty = starty;
235        this.targetx = targetx;
236        this.targety = targety;
237
238        return brushReachable(radiusStrategy, spread);
239    }
240    /**
241     * Returns true if a line can be drawn from the any of the points within spread cells of the start point,
242     * to any of the corresponding points at the same direction and distance from the target point, without
243     * intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath.
244     *
245     * @param resistanceMap 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
246     * @param startx starting x position on the grid
247     * @param starty starting y position on the grid
248     * @param targetx ending x position on the grid
249     * @param targety ending y position on the grid
250     * @param radiusStrategy the strategy to use in computing unit distance
251     * @param spread the number of cells outward, measured by radiusStrategy, to place extra start and target points
252     * @return true if a line can be drawn without being obstructed, false otherwise
253     */
254    public boolean spreadReachable(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread) {
255        if(resistanceMap.length < 1) return false;
256        this.resistanceMap = resistanceMap;
257        this.startx = startx;
258        this.starty = starty;
259        this.targetx = targetx;
260        this.targety = targety;
261
262        return brushReachable(radiusStrategy, spread);
263    }
264    /**
265     * Returns the path of the last LOS calculation, with the starting point as
266     * the head of the queue.
267     *
268     * @return
269     */
270    public Queue<Coord> getLastPath() {
271        return lastPath;
272    }
273
274    private boolean bresenhamReachable(Radius radiusStrategy) {
275        Queue<Coord> path = Bresenham.line2D(startx, starty, targetx, targety);
276        lastPath = new LinkedList<>();
277        lastPath.add(Coord.get(startx, starty));
278        double decay = 1 / radiusStrategy.radius(startx, starty, targetx, targety);
279        double currentForce = 1;
280        for (Coord p : path) {
281            lastPath.offer(p);
282            if (p.x == targetx && p.y == targety) {
283                return true;//reached the end 
284            }
285            if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell
286                currentForce -= resistanceMap[p.x][p.y];
287            }
288            double r = radiusStrategy.radius(startx, starty, p.x, p.y);
289            if (currentForce - (r * decay) <= 0) {
290                return false;//too much resistance
291            }
292        }
293        return false;//never got to the target point
294    }
295
296    private boolean orthoReachable(Radius radiusStrategy) {
297        List<Coord> path = OrthoLine.line(startx, starty, targetx, targety);
298        lastPath = new LinkedList<>();
299        double decay = 1 / radiusStrategy.radius(startx, starty, targetx, targety);
300        double currentForce = 1;
301        for (Coord p : path) {
302            lastPath.offer(p);
303            if (p.x == targetx && p.y == targety) {
304                return true;//reached the end
305            }
306            if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell
307                currentForce -= resistanceMap[p.x][p.y];
308            }
309            double r = radiusStrategy.radius(startx, starty, p.x, p.y);
310            if (currentForce - (r * decay) <= 0) {
311                return false;//too much resistance
312            }
313        }
314        return false;//never got to the target point
315    }
316
317    private boolean ddaReachable(Radius radiusStrategy) {
318        List<Coord> path = DDALine.line(startx, starty, targetx, targety);
319        lastPath = new LinkedList<>();
320        double decay = 1 / radiusStrategy.radius(startx, starty, targetx, targety);
321        double currentForce = 1;
322        for (Coord p : path) {
323            if (p.x == targetx && p.y == targety) {
324                lastPath.offer(p);
325                return true;//reached the end
326            }
327            if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell
328                currentForce -= resistanceMap[p.x][p.y];
329            }
330            double r = radiusStrategy.radius(startx, starty, p.x, p.y);
331            if (currentForce - (r * decay) <= 0) {
332                return false;//too much resistance
333            }
334            lastPath.offer(p);
335        }
336        return false;//never got to the target point
337    }
338
339    private boolean thickReachable(Radius radiusStrategy) {
340        lastPath = new LinkedList<>();
341        double dist = radiusStrategy.radius(startx, starty, targetx, targety), decay = 1 / dist;
342        LinkedHashSet<Coord> visited = new LinkedHashSet<>((int) dist + 3);
343        List<List<Coord>> paths = new ArrayList<>(4);
344        /* // actual corners
345        paths.add(DDALine.line(startx, starty, targetx, targety, 0, 0));
346        paths.add(DDALine.line(startx, starty, targetx, targety, 0, 0xffff));
347        paths.add(DDALine.line(startx, starty, targetx, targety, 0xffff, 0));
348        paths.add(DDALine.line(startx, starty, targetx, targety, 0xffff, 0xffff));
349        */
350        // halfway between the center and a corner
351        paths.add(DDALine.line(startx, starty, targetx, targety, 0x3fff, 0x3fff));
352        paths.add(DDALine.line(startx, starty, targetx, targety, 0x3fff, 0xbfff));
353        paths.add(DDALine.line(startx, starty, targetx, targety, 0xbfff, 0x3fff));
354        paths.add(DDALine.line(startx, starty, targetx, targety, 0xbfff, 0xbfff));
355
356        int length = Math.max(paths.get(0).size(), Math.max(paths.get(1).size(),
357                Math.max(paths.get(2).size(), paths.get(3).size())));
358        double[] forces = new double[]{1,1,1,1};
359        boolean[] go = new boolean[]{true, true, true, true};
360        Coord p;
361        for (int d = 0; d < length; d++) {
362            for (int pc = 0; pc < 4; pc++) {
363                List<Coord> path = paths.get(pc);
364                if(d < path.size() && go[pc])
365                    p = path.get(d);
366                else continue;
367                if (p.x == targetx && p.y == targety) {
368                    visited.add(p);
369                    lastPath.addAll(visited);
370                    return true;//reached the end
371                }
372                if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell
373                    forces[pc] -= resistanceMap[p.x][p.y];
374                }
375                double r = radiusStrategy.radius(startx, starty, p.x, p.y);
376                if (forces[pc] - (r * decay) <= 0) {
377                    go[pc] = false;
378                    continue;//too much resistance
379                }
380                visited.add(p);
381            }
382        }
383        lastPath.addAll(visited);
384        return false;//never got to the target point
385    }
386
387    private boolean brushReachable(Radius radiusStrategy, int spread) {
388        lastPath = new LinkedList<>();
389        double dist = radiusStrategy.radius(startx, starty, targetx, targety) + spread * 2, decay = 1 / dist;
390        LinkedHashSet<Coord> visited = new LinkedHashSet<>((int) (dist + 3) * spread);
391        List<List<Coord>> paths = new ArrayList<>((int) (radiusStrategy.volume2D(spread) * 1.25));
392        int length = 0;
393        List<Coord> currentPath;
394        for (int i = -spread; i <= spread; i++) {
395            for (int j = -spread; j <= spread; j++) {
396                if(radiusStrategy.inRange(startx, starty, startx + i, starty + j, 0, spread)
397                        && startx + i >= 0 && starty + j >= 0
398                        && startx + i < resistanceMap.length && starty + j < resistanceMap[0].length
399                        && targetx + i >= 0 && targety + j >= 0
400                        && targetx + i < resistanceMap.length && targety + j < resistanceMap[0].length) {
401                    for (int q = 0x3fff; q < 0xffff; q += 0x8000) {
402                        for (int r = 0x3fff; r < 0xffff; r += 0x8000) {
403                            currentPath = DDALine.line(startx+i, starty+j, targetx+i, targety+j, q, r);
404                            paths.add(currentPath);
405                            length = Math.max(length, currentPath.size());
406                        }
407                    }
408                }
409            }
410        }
411        double[] forces = new double[paths.size()];
412        Arrays.fill(forces, 1.0);
413        boolean[] go = new boolean[paths.size()];
414        Arrays.fill(go, true);
415        Coord p;
416        boolean found = false;
417        for (int d = 0; d < length; d++) {
418            for (int pc = 0; pc < paths.size(); pc++) {
419                List<Coord> path = paths.get(pc);
420                if(d < path.size() && go[pc])
421                    p = path.get(d);
422                else continue;
423                if (p.x == targetx && p.y == targety) {
424                    found = true;
425                }
426                if (p.x != startx || p.y != starty) {//don't discount the start location even if on resistant cell
427                    forces[pc] -= resistanceMap[p.x][p.y];
428                }
429                double r = radiusStrategy.radius(startx, starty, p.x, p.y);
430                if (forces[pc] - (r * decay) <= 0) {
431                    go[pc] = false;
432                    continue;//too much resistance
433                }
434                visited.add(p);
435            }
436        }
437        lastPath.addAll(visited);
438        return found;//never got to the target point
439    }
440
441    private boolean rayReachable(Radius radiusStrategy) {
442        lastPath = new LinkedList<>();//save path for later retreival
443        lastPath.add(Coord.get(startx, starty));
444        if (startx == targetx && starty == targety) {//already there!
445            return true;
446        }
447
448        int width = resistanceMap.length;
449        int height = resistanceMap[0].length;
450
451        CoordDouble start = new CoordDouble(startx, starty);
452        CoordDouble end = new CoordDouble(targetx, targety);
453        //find out which direction to step, on each axis
454        int stepX = (int) Math.signum(end.x - start.x);
455        int stepY = (int) Math.signum(end.y - start.y);
456
457        double deltaY = end.x - start.x;
458        double deltaX = end.y - start.y;
459
460        deltaX = Math.abs(deltaX);
461        deltaY = Math.abs(deltaY);
462
463        int testX = (int) start.x;
464        int testY = (int) start.y;
465
466        double maxX = (float) (start.x % 1);
467        double maxY = (float) (start.y % 1);
468
469        int endTileX = (int) end.x;
470        int endTileY = (int) end.y;
471
472        CoordDouble collisionPoint = new CoordDouble();
473        while (testX >= 0 && testX < width && testY >= 0 && testY < height && (testX != endTileX || testY != endTileY)) {
474            lastPath.add(Coord.get(testX, testY));
475            if (maxX < maxY) {
476                maxX += deltaX;
477                testX += stepX;
478                if (resistanceMap[testX][testY] >= 1f) {
479                    collisionPoint.y = testY;
480                    collisionPoint.x = testX;
481                    end = collisionPoint;
482                    break;
483                }
484            } else if (maxY < maxX) {
485                maxY += deltaY;
486                testY += stepY;
487                if (resistanceMap[testX][testY] >= 1f) {
488                    collisionPoint.y = testY;
489                    collisionPoint.x = testX;
490                    end = collisionPoint;
491                    break;
492                }
493            } else {//directly on diagonal, move both full step
494                maxY += deltaY;
495                testY += stepY;
496                maxX += deltaX;
497                testX += stepX;
498                if (resistanceMap[testX][testY] >= 1f) {
499                    collisionPoint.y = testY;
500                    collisionPoint.x = testX;
501                    end = collisionPoint;
502                    break;
503                }
504            }
505            if (radiusStrategy.radius(testX, testY, start.x, start.y) > radiusStrategy.radius(startx, starty, targetx, targety)) {//went too far
506                break;
507            }
508        }
509
510        if (end.x >= 0 && end.x < width && end.y >= 0 && end.y < height) {
511            lastPath.add(Coord.get((int) end.x, (int) end.y));
512        }
513
514        return (int) end.x == targetx && (int) end.y == targety;
515    }
516
517    @GwtIncompatible /* Because of Thread */
518    private boolean eliasReachable(Radius radiusStrategy) {
519        if(elias == null)
520            elias = new Elias();
521        List<Coord> ePath = elias.line(startx, starty, targetx, targety);
522        lastPath = new LinkedList<>(ePath);//save path for later retreival
523
524        HashMap<eliasWorker, Thread> pool = new HashMap<>();
525
526        for (Coord p : ePath) {
527            eliasWorker worker = new eliasWorker(p.x, p.y, radiusStrategy);
528            Thread thread = new Thread(worker);
529            thread.start();
530            pool.put(worker, thread);
531        }
532
533        for (eliasWorker w : pool.keySet()) {
534            try {
535                pool.get(w).join();
536            } catch (InterruptedException ex) {
537            }
538            if (w.succeeded) {
539                lastPath = w.path;
540                return true;
541            }
542        }
543
544        return false;//never got to the target point
545    }
546
547    private class eliasWorker implements Runnable {
548
549        private Queue<Coord> path;
550        private boolean succeeded = false;
551        private int testx, testy;
552        private Radius radiusStrategy;
553        eliasWorker(int testx, int testy, Radius radiusStrategy) {
554            this.testx = testx;
555            this.testy = testy;
556            this.radiusStrategy = radiusStrategy;
557        }
558
559        @Override
560        public void run() {
561            LOS los1 = new LOS(BRESENHAM);
562            LOS los2 = new LOS(BRESENHAM);
563            //if a non-solid midpoint on the path can see both the start and end, consider the two ends to be able to see each other
564            if (resistanceMap[testx][testy] < 1
565                    && radiusStrategy.radius(startx, starty, testx, testy) <= radiusStrategy.radius(startx, starty, targetx, targety)
566                    && los1.isReachable(resistanceMap, testx, testy, targetx, targety, radiusStrategy)
567                    && los2.isReachable(resistanceMap, startx, starty, testx, testy, radiusStrategy)) {
568
569                //record actual sight path used
570                path = new LinkedList<>(los2.lastPath);
571                path.addAll(los1.lastPath);
572                succeeded = true;
573            }
574        }
575    }
576}