001package squidpony.squidmath;
002
003import squidpony.squidai.DijkstraMap;
004import squidpony.squidgrid.mapping.DungeonUtility;
005
006/**
007 * (SLOW) Modified version of AStarSearch that does some pre-planning and uses that to speed up pathfinding later on.
008 * Pre-planning is in the form of full distance calculations using DijkstraMap, with each centered on an infrequent
009 * landmark somewhere on a walkable tile on the map. This affects the A* heuristic and allows it to establish a better
010 * lower bound for distance. Landmark placement is non-random; 1 out of 85 walkable tiles will be made into a landmark,
011 * and they will be considered in Hilbert Curve order (which helps prevent nearby areas from being chosen twice).
012 * <br>
013 * Idea can be credited independently to Joshua Day, who mentioned this long before I understood it, and Amit Patel,
014 * http://www.redblobgames.com/pathfinding/heuristics/differential.html
015 * <br>
016 * NOTE: Due to implementation problems that seem to also be present in AStarSearch, this class does not offer any speed
017 * improvements or any other benefits. It may be fixed in future versions, but for now you should strongly prefer
018 * DijkstraMap for pathfinding.
019 * @see squidpony.squidai.DijkstraMap a much faster pathfinding algorithm with more features.
020 * Created by Tommy Ettinger on 5/5/2016.
021 */
022public class PlannedAStar extends AStarSearch {
023    protected DijkstraMap dm;
024    protected double[][][] plans;
025    protected Coord[] landmarks;
026    protected PlannedAStar() {
027    }
028
029    public PlannedAStar(double[][] map, SearchType type) {
030        super(map, type);
031        dm = new DijkstraMap(DungeonUtility.translateAStarToDijkstra(map), translateSearchType(type));
032        landmarks = CoordPacker.fractionPacked(CoordPacker.pack(dm.physicalMap, DijkstraMap.FLOOR),
033                Math.round((width + height) * 3.7f));
034        plans = new double[landmarks.length][][];
035        for (int i = 0; i < landmarks.length; i++) {
036            dm.setGoal(landmarks[i]);
037            plans[i] = dm.scan(null);
038            dm.reset();
039        }
040    }
041
042    protected static DijkstraMap.Measurement translateSearchType(SearchType type)
043    {
044        if(type == null)
045            return DijkstraMap.Measurement.MANHATTAN;
046        switch (type)
047        {
048            case EUCLIDEAN: return DijkstraMap.Measurement.EUCLIDEAN;
049            case MANHATTAN: return DijkstraMap.Measurement.MANHATTAN;
050            default: return DijkstraMap.Measurement.CHEBYSHEV;
051        }
052    }
053
054    @Override
055    protected double h(int x, int y) {
056        double d = super.h(x, y);
057        for (int i = 0; i < plans.length; i++) {
058            d = Math.max(d, plans[i][target.x][target.y] - plans[i][x][y]);
059        }
060        return d;
061    }
062}