Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.66 KB | None | 0 0
  1.     public List<Point> computePath(Point start, Point end,
  2.                                    Predicate<Point> canPassThrough,
  3.                                    BiPredicate<Point, Point> withinReach,
  4.                                    Function<Point, Stream<Point>> potentialNeighbors) {
  5.  
  6.         List<Point> pth = new ArrayList<>();
  7.         HashMap<Point, Point> parent = new HashMap<>();
  8.         HashMap<Point, Integer> length = new HashMap<>();
  9.         PriorityQueue<Cmp> q = new PriorityQueue<>(100000);
  10.         q.add(new Cmp(manhattan(start, end), start));
  11.         parent.put(start, start);
  12.         length.put(start, 0);
  13.         Cmp cur = null;
  14.         List<Point> neighbors = potentialNeighbors.apply(cur.getP())
  15.                 .filter(canPassThrough)
  16.                 .filter(p -> !p.equals(start) && !p.equals(end))
  17.                 .collect(Collectors.toList());
  18.         while (q.peek() != null) {
  19.             cur = q.poll();
  20.             if (cur.getP() == end) {
  21.                 break;
  22.             }
  23.             for (Point p : neighbors) {
  24.                 if ((parent.get(p) == null || length.get(cur.getP()) < length.get(parent.get(p)))) {
  25.                     parent.put(p, cur.getP());
  26.                     length.put(p, length.get(cur.getP()) + 1);
  27.                     q.add(new Cmp(manhattan(p, end) + length.get(p), p));
  28.                 }
  29.             }
  30.         }
  31.             Point p = cur.getP();
  32.             if (p != end) {
  33.                 return pth;
  34.             }
  35.             pth.add(0, p);
  36.             while (parent.get(p) != p) {
  37.                 p = parent.get(p);
  38.                 pth.add(0, p);
  39.             }
  40.             return pth;
  41.         }
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement