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}