001package squidpony.squidgrid;
002
003import squidpony.squidgrid.mapping.DungeonUtility;
004import squidpony.squidmath.Coord;
005import squidpony.squidmath.RNG;
006
007import java.util.*;
008
009/**
010 * A alternative to {@link Spill}, whose purpose is to have a simpler API. You
011 * can specify the characters that are impassable (in other words: that should
012 * not be spilled on) using {@link #addImpassableChar(char)} and
013 * {@link #removeImpassableChar(char)}. By default the set of impassable characters
014 * is {@code '#'}.
015 * 
016 * @author smelC
017 * 
018 * @see Spill An alternative implementation of spilling.
019 */
020public class Splash {
021
022        private static Splash splashCache = null;
023        private static int splashHash = -1;
024        protected final Set<Character> impassable;
025
026        /**
027         * A fresh instance, whose only impassable character is '#'.
028         */
029        public Splash() {
030                this.impassable = new HashSet<>();
031                /* The default */
032                addImpassableChar('#');
033        }
034        /**
035         * A fresh instance, adding the chars in blocked to the set of impassable characters,
036         * then also adding '#' if it isn't present. You can remove '#' with
037         * {@link #removeImpassableChar(char)} if you use '#' to mean something non-blocking.
038         */
039        public Splash(Set<Character> blocked) {
040                this.impassable = new HashSet<>(blocked);
041                /* The default */
042                addImpassableChar('#');
043        }
044
045        /**
046         * Adds {@code c} to the set of impassable characters.
047         * 
048         * @param c
049         *            The character to add.
050         */
051        public void addImpassableChar(char c) {
052                this.impassable.add(c);
053        }
054
055        /**
056         * Removes {@code c} from the set of impassable characters.
057         * 
058         * @param c
059         *            The character to remove.
060         * @return Whether it was in there.
061         */
062        public boolean removeImpassableChar(char c) {
063                return this.impassable.remove(c);
064        }
065
066        /**
067         * @param rng used to randomize the floodfill
068         * @param level char 2D array with x, y indices for the dungeon/map level
069         * @param start
070         *            Where the spill should start. It should be passable, otherwise
071         *            an empty list gets returned. Consider using
072         *            {@link DungeonUtility#getRandomCell(RNG, char[][], Set, int)}
073         *            to find it.
074         * @param volume
075         *            The number of cells to spill on.
076         * @return The spill. It is a list of coordinates (containing {@code start})
077         *         valid in {@code level} that are all adjacent and whose symbol is
078         *         passable. If non-empty, this is guaranteed to be an
079         *         {@link ArrayList}.
080         */
081        public List<Coord> spill(RNG rng, char[][] level, Coord start, int volume) {
082                if (!DungeonUtility.inLevel(level, start) || !passable(level[start.x][start.y]))
083                        return Collections.emptyList();
084
085                final List<Coord> result = new ArrayList<>(volume);
086
087                Direction[] dirs = new Direction[Direction.OUTWARDS.length];
088
089                final LinkedList<Coord> toTry = new LinkedList<>();
090                toTry.add(start);
091                final Set<Coord> trieds = new HashSet<>();
092
093                while (!toTry.isEmpty()) {
094                        assert result.size() < volume;
095                        final Coord current = toTry.removeFirst();
096                        assert DungeonUtility.inLevel(level, current);
097                        assert passable(level[current.x][current.y]);
098                        if (trieds.contains(current))
099                                continue;
100                        trieds.add(current);
101                        /*
102                         * Here it holds that either 'current == start' or there's a Coord
103                         * in 'result' that is adjacent to 'current'.
104                         */
105                        result.add(current);
106                        if (result.size() == volume)
107                                /* We're done */
108                                break;
109                        /* Now prepare data for next iterations */
110                        /* Randomize directions */
111                        dirs = rng.shuffle(Direction.OUTWARDS, dirs);
112                        for (Direction d : dirs) {
113                                final Coord next = current.translate(d);
114                                if (DungeonUtility.inLevel(level, next) && !trieds.contains(next)
115                                                && passable(level[next.x][next.y]))
116                                        /* A valid cell for trying to be spilled on */
117                                        toTry.add(next);
118                        }
119                }
120
121                return result;
122        }
123
124        protected boolean passable(char c) {
125                return !impassable.contains(c);
126        }
127
128        /**
129         * @param rng used to randomize the floodfill
130         * @param level char 2D array with x, y indices for the dungeon/map level
131         * @param start
132         *            Where the spill should start. It should be passable, otherwise
133         *            an empty list gets returned. Consider using
134         *            {@link DungeonUtility#getRandomCell(RNG, char[][], Set, int)}
135         *            to find it.
136         * @param volume
137         *            The number of cells to spill on.
138         * @param impassable the set of chars on the level that block the spill, such
139         *                   as walls or maybe other spilled things (oil and water).
140         *                   May be null, which makes this treat '#' as impassable.
141         * @return The spill. It is a list of coordinates (containing {@code start})
142         *         valid in {@code level} that are all adjacent and whose symbol is
143         *         passable. If non-empty, this is guaranteed to be an
144         *         {@link ArrayList}.
145         */
146        public static List<Coord> spill(RNG rng, char[][] level, Coord start, int volume, Set<Character> impassable)
147        {
148                Set<Character> blocked;
149                if(impassable == null)
150                        blocked = new HashSet<>(2);
151                else
152                        blocked = impassable;
153                if(splashCache == null || blocked.hashCode() != splashHash)
154                {
155                        splashHash = blocked.hashCode();
156                        splashCache = new Splash(blocked);
157                }
158                return splashCache.spill(rng, level, start, volume);
159        }
160
161}