Want more features on Pastebin? Sign Up, it's FREE!
Guest

aStar

By: rftz on Jan 30th, 2013  |  syntax: Java  |  size: 3.05 KB  |  views: 408  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2.  
  3. public class ShortestPath {
  4.        
  5.         Point[][] grid;
  6.        
  7.         public static void main(String[] args){
  8.                 new ShortestPath().doMain(args);
  9.         }
  10.  
  11.         void doMain(String[] args) {
  12.                 if (args==null || args.length < 2)
  13.                         args = new Scanner(System.in).nextLine().split(" ");
  14.                 int size = Integer.parseInt(args[0]);
  15.                 grid = new Point[size][size];
  16.                 Point start = null, end = null;
  17.                 for (int i=0; i<grid.length; i++){
  18.                         for(int j=0; j<grid[i].length; j++){
  19.                                 grid[i][j] = new Point(i, j, args[i+1].charAt(j));
  20.                                 if (grid[i][j].c == 'S') start = grid[i][j];
  21.                                 if (grid[i][j].c == 'E') end = grid[i][j];
  22.                         }
  23.                 }
  24.                 System.out.println(aStar(start, end).toStringAndDrawPath(grid));
  25.         }
  26.        
  27.         private Path aStar(Point start, Point end) {
  28.                 PriorityQueue<Path> q = new PriorityQueue<Path>();
  29.                 Set<Point> closed = new HashSet<Point>();
  30.                 Path path = new Path(start);
  31.                 q.add(path);
  32.                
  33.                 while (!q.isEmpty()) {
  34.                         path = q.poll();
  35.                         Point curPoint = path.points.getLast();
  36.                         if (curPoint.equals(end)) return path;
  37.                         if (closed.contains(curPoint)) continue;
  38.                         closed.add(curPoint);
  39.                         for (Point point: getNeighbours(curPoint)) {
  40.                                 Path newPath = new Path(path);
  41.                                 newPath.points.addLast(point);
  42.                                 newPath.heuristicCost = heuristic(point, end);
  43.                                 q.add(newPath);
  44.                         }
  45.                 }
  46.                 return new Path();
  47.         }
  48.        
  49.         int heuristic(Point from, Point to) {
  50.                 return Math.abs(to.i - from.i) + Math.abs(to.j - from.j);
  51.         }
  52.        
  53.         public Set<Point> getNeighbours(Point p) {
  54.                 int i = p.i, j = p.j;
  55.                 Set<Point> neighbours = new HashSet<Point>();
  56.                 for (int m = Math.max(i - 1, 0); m <= Math.min(i + 1, grid.length - 1); m++)
  57.                         if (grid[m][j].c != 'W') neighbours.add(grid[m][j]);
  58.                 for (int n = Math.max(j - 1, 0); n <= Math.min(j + 1, grid[0].length - 1); n++)
  59.                         if (grid[i][n].c != 'W') neighbours.add(grid[i][n]);
  60.                 return neighbours;
  61.         }
  62. }
  63.  
  64. class Point {
  65.         int i, j;
  66.         char c;
  67.        
  68.         public Point (int i, int j, char c) {
  69.                 this.i = i;
  70.                 this.j = j;
  71.                 this.c = c;
  72.         }
  73. }
  74.  
  75. class Path implements Comparable<Path> {
  76.         Deque<Point> points = new ArrayDeque<Point>();
  77.         int heuristicCost = 0;
  78.        
  79.         public Path(Point point){
  80.                 points.addLast(point);
  81.         }
  82.        
  83.         /** Create a clone of the current path p */
  84.         public Path(Path p) {
  85.                 points = new ArrayDeque<Point>(p.points);
  86.         }
  87.        
  88.         public Path(){}
  89.        
  90.         @Override
  91.         public int compareTo(Path path2) {
  92.                 return Integer.compare(points.size() + heuristicCost,
  93.                                 path2.points.size() + path2.heuristicCost);
  94.         }
  95.        
  96.         @Override
  97.         public String toString() {
  98.                 if (points.size()==0) return "False";
  99.                 return "True, " + (points.size()-1);
  100.         }
  101.        
  102.         public String toStringAndDrawPath(Point[][] inputGrid) {
  103.                 if (points.size()==0) return "False";
  104.                 String result = toString() + "\n\n";
  105.                 char[][] map = new char[inputGrid.length][inputGrid.length];
  106.                 for (int i=0; i<map.length; i++)
  107.                         for (int j=0; j<map.length; j++)
  108.                                 map[i][j] = inputGrid[i][j].c;
  109.                 for (Point p: points)
  110.                         if (p.c != 'S' && p.c != 'E') map[p.i][p.j] = '-';
  111.                 for (char[] row: map) {
  112.                         result += new String(row) + "\n";
  113.                 }
  114.                 return result;
  115.         }
  116.        
  117. }
clone this paste RAW Paste Data