001package squidpony.squidmath;
002
003import squidpony.squidai.graph.Heuristic;
004import squidpony.squidai.graph.CostlyGraph;
005import squidpony.squidgrid.mapping.DungeonGenerator;
006import squidpony.squidgrid.mapping.DungeonUtility;
007
008import java.io.Serializable;
009import java.util.ArrayList;
010import java.util.Map;
011
012/**
013 * Performs A* search to find the shortest path between two Coord points.
014 * <br>
015 * A* is a best-first search algorithm for pathfinding. It uses a heuristic
016 * value to reduce the total search space. If the heuristic is too large then
017 * the optimal path is not guaranteed to be returned.
018 * <br>
019 * This implementation is a thin wrapper around {@link squidpony.squidai.graph.CostlyGraph} and the other code in the
020 * {@code squidpony.squidai.graph} package; it replaces an older, much-less-efficient A* implementation with one based
021 * on code from simple-graphs by earlygrey. The current version is quite fast, typically outpacing gdx-ai's more-complex
022 * IndexedAStarPathfinder by a high margin. The only major change in the API is that this version returns an ArrayList
023 * of Coord instead of a Queue of Coord. Typical usage of this class involves either the simpler technique of only using
024 * {@code '#'} for walls or obstructions and calling {@link #AStarSearch(char[][], SearchType)}, or the more complex
025 * technique that allows variable costs for different types of terrain, using
026 * {@link squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][], Map, double)} to generate a cost
027 * map; if you used the old AStarSearch, then be advised that the default cost is now 1.0 instead of 0.0.
028 * @see squidpony.squidai.graph.CostlyGraph the pathfinding class this is based on; CostlyGraph can be used independently
029 * @see squidpony.squidai.DijkstraMap a sometimes-faster pathfinding algorithm that can pathfind to multiple goals
030 * @see squidpony.squidai.CustomDijkstraMap an alternative to DijkstraMap; faster and supports complex adjacency rules
031 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
032 * @author Tommy Ettinger - optimized code
033 * @author earlygrey - wrote and really optimized simple-graphs, which this uses heavily
034 */
035public class AStarSearch implements Serializable {
036    private static final long serialVersionUID = 11L;
037    /**
038     * The type of heuristic to use.
039     */
040    public enum SearchType {
041
042        /**
043         * The distance it takes when only the four primary directions can be
044         * moved in.
045         */
046        MANHATTAN(Heuristic.MANHATTAN),
047        /**
048         * The distance it takes when diagonal movement costs the same as
049         * cardinal movement.
050         */
051        CHEBYSHEV(Heuristic.CHEBYSHEV),
052        /**
053         * The distance it takes as the crow flies.
054         */
055        EUCLIDEAN(Heuristic.EUCLIDEAN),
056        /**
057         * Full space search. Least efficient but guaranteed to return a path if
058         * one exists. See also {@link squidpony.squidai.DijkstraMap}.
059         */
060        DIJKSTRA(Heuristic.DIJKSTRA);
061        Heuristic<Coord> heuristic;
062        SearchType(Heuristic<Coord> heuristic){
063            this.heuristic = heuristic;
064        }
065    }
066
067    protected int width, height;
068    protected Coord start, target;
069    protected SearchType type;
070    
071    protected CostlyGraph graph;
072    protected ArrayList<Coord> path;
073    
074    
075    protected AStarSearch()
076    {
077        width = 0;
078        height = 0;
079        type = SearchType.MANHATTAN;
080    }
081    /**
082     * Builds a pathing object to run searches on.
083     * <br>
084     * Values in the map are treated as positive values being legal weights, with higher values being harder to pass
085     * through. Any negative value is treated as being an impassible space. A weight of 0 can be moved through at no
086     * cost, but this should be used very carefully, if at all. Cost maps are commonly built using the
087     * {@link squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][], Map, double)} and
088     * {@link  squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][])} methods from a 2D char array.
089     * <br>
090     * If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result
091     * based on diagonal and cardinal pathing (8-way).
092     *
093     * @param map the search map, as produced by {@link squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][])}
094     * @param type the manner of search
095     */
096    public AStarSearch(double[][] map, SearchType type) {
097        if (map == null)
098            throw new NullPointerException("map should not be null when building an AStarSearch");
099        width = map.length;
100        height = width == 0 ? 0 : map[0].length;
101        this.type = type == null ? SearchType.EUCLIDEAN : type;         
102        graph = new CostlyGraph(map, (this.type != SearchType.MANHATTAN));
103        path = new ArrayList<>(width + height);
104    }
105    /**
106     * Builds a pathing object to run searches on.
107     * <br>
108     * Values in the map are all considered equally passable unless the char is {@code '#'}, in which case it is
109     * considered an impassable wall. The {@link DungeonGenerator#getBareDungeon()} method is a common way to get a map
110     * where only '#' is used to mean a wall.
111     * <br>
112     * If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result
113     * based on diagonal and cardinal pathing (8-way).
114     *
115     * @param map a 2D char array where only {@code '#'} represents a wall, and anything else is equally passable
116     * @param type the manner of search
117     */
118    public AStarSearch(char[][] map, SearchType type) {
119        if (map == null)
120            throw new NullPointerException("map should not be null when building an AStarSearch");
121        width = map.length;
122        height = width == 0 ? 0 : map[0].length;
123        this.type = type == null ? SearchType.EUCLIDEAN : type;
124        graph = new CostlyGraph(map, (this.type != SearchType.MANHATTAN));
125        path = new ArrayList<>(width + height);
126    }
127
128    /**
129     * Resets this pathing object to use a different map and optionally a different SearchType.
130     * <br>
131     * Values in the map are treated as positive values being legal weights, with higher values being harder to pass
132     * through. Any negative value is treated as being an impassible space. A weight of 0 can be moved through at no
133     * cost, but this should be used very carefully, if at all. Cost maps are commonly built using the
134     * {@link squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][], Map, double)} and
135     * {@link  squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][])} methods from a 2D char array.
136     * <br>
137     * If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result
138     * based on diagonal and cardinal pathing (8-way).
139     *
140     * @param map the search map, as produced by {@link squidpony.squidgrid.mapping.DungeonUtility#generateAStarCostMap(char[][])}
141     * @param type the manner of search
142     */
143    public AStarSearch reinitialize(double[][] map, SearchType type){
144        if (map == null)
145            throw new NullPointerException("map should not be null when building an AStarSearch");
146        width = map.length;
147        height = width == 0 ? 0 : map[0].length;
148        this.type = type == null ? SearchType.EUCLIDEAN : type;
149        graph.init(map, this.type != SearchType.MANHATTAN);
150        return this;
151    }
152
153    /**
154     * Resets this pathing object to use a different map and optionally a different SearchType.
155     * <br>
156     * Values in the map are all considered equally passable unless the char is {@code '#'}, {@code '+'}, or any box
157     * drawing character, in which case it is considered an impassable wall. {@link DungeonGenerator#getBareDungeon()}
158     * is a common way to get a map where only '#' is used to mean a wall.
159     * <br>
160     * If the type is Manhattan, only the cardinal directions will be used. All other search types will return a result
161     * based on diagonal and cardinal pathing (8-way).
162     *
163     * @param map a 2D char array where only {@code '#'} represents a wall, and anything else is equally passable
164     * @param type the manner of search
165     */
166    public AStarSearch reinitialize(char[][] map, SearchType type){
167        if (map == null)
168            throw new NullPointerException("map should not be null when building an AStarSearch");
169        width = map.length;
170        height = width == 0 ? 0 : map[0].length;
171        this.type = type == null ? SearchType.EUCLIDEAN : type;
172        graph.init(DungeonUtility.generateAStarCostMap(map), this.type != SearchType.MANHATTAN);
173        return this;
174    }
175
176    /**
177     * Finds an A* path to the target from the start. If no path is possible,
178     * returns null.
179     *
180     * @param startx the x coordinate of the start location
181     * @param starty the y coordinate of the start location
182     * @param targetx the x coordinate of the target location
183     * @param targety the y coordinate of the target location
184     * @return the shortest path, or null if no path is possible
185     */
186    public ArrayList<Coord> path(int startx, int starty, int targetx, int targety) {
187        return path(Coord.get(startx, starty), Coord.get(targetx, targety));
188    }
189    /**
190     * Finds an A* path to the target from the start. If no path is possible,
191     * returns null.
192     *
193     * @param start the start location
194     * @param target the target location
195     * @return the shortest path, or null if no path is possible
196     */
197    public ArrayList<Coord> path(Coord start, Coord target) {
198        path.clear();
199        this.start = start;
200        this.target = target;
201        if(graph.findShortestPath(start, target, path, type.heuristic)) 
202            return path;
203        else
204            return null;
205    }
206
207        public int getWidth() {
208                return width;
209        }
210
211        public int getHeight() {
212                return height;
213        }
214
215        @Override
216        public String toString() {
217        final int w5 = width * 5;
218        final char[] cs = graph.show();
219        cs[start.y * w5 + start.x * 5] = cs[start.y * w5 + start.x * 5 + 1] =
220                cs[start.y * w5 + start.x * 5 + 2] = cs[start.y * w5 + start.x * 5 + 3] = '@';
221        cs[target.y * w5 + target.x * 5] = cs[target.y * w5 + target.x * 5 + 1] =
222                cs[target.y * w5 + target.x * 5 + 2] = cs[target.y * w5 + target.x * 5 + 3] = '!';
223        return String.valueOf(cs);
224    }
225}