AStarPathingStrategy.java

import java.util.*;
import java.util.function.BiPredicate;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.stream.Stream;

public class AStarPathingStrategy implements PathingStrategy {

    @Override
    public List<Point> computePath(Point start, Point end, Predicate<Point> canPassThrough, BiPredicate<Point, Point> withinReach, Function<Point, Stream<Point>> potentialNeighbors) {

        //initialize variables (need openList, closedList, and list of previous)
        Map<Point, Integer> gValue = new HashMap<>();  //acts as closed list
        Map<Point, Integer> fValue = new HashMap<>();  //keeps track of total (g+h)
        Map<Point, Point> previous = new HashMap<>();  //keeps track of where each node came from
        PriorityQueue<Point> openList = new PriorityQueue<>(Comparator.comparingInt(fValue::get)); //keeps track of the nodes being searched by their fValue

        //add the start node to the openList (gValue is 0)
        openList.add(start);
        gValue.put(start, 0);
        fValue.put(start, calculateHeuristic(start, end));

        //continue while there are still nodes being searched
        while (!openList.isEmpty()) {
            Point current = openList.poll();  //.poll() is part of PriorityQueue: returns and removes the head from list (lowest fValue = highest priority)

            //BiPredicate uses .test
            if (withinReach.test(current, end)) {  //checks if the current point is adjacent (one away) to the goal
                return reconstructPath(previous, current);
            }

            //Function uses .apply
            for (Point neighbor : potentialNeighbors.apply(current).toArray(Point[]::new)) { //get stream of current's neighbors and turn to array
                if (!canPassThrough.test(neighbor)) { //if you cant pass through (obstacle or out of bounds) skip to next iteration until a valid point is found
                    continue;
                }

                //valid point found that can be passed through
                //set up variables
                int tentativeG = gValue.getOrDefault(current, Integer.MAX_VALUE) + 1;  //default max if it doesn't have a gValue since it wouldn't be part of the path
                int heuristic = calculateHeuristic(neighbor, end); //calculate euclidean distance
                int tentativeF = tentativeG + heuristic; //calculate g + h

                if (tentativeF < fValue.getOrDefault(neighbor, Integer.MAX_VALUE)) { //tentative < current ?
                    // update lists for potentially better path
                    previous.put(neighbor, current);
                    gValue.put(neighbor, tentativeG);
                    fValue.put(neighbor, tentativeF);

                    if (!openList.contains(neighbor)) { //add to the list of points being searched
                        openList.add(neighbor);
                    }
                }
            }
        }
        return Collections.emptyList();  //return empty list if there is no path
    }

        //creates the final best path to get to the goal
        private List<Point> reconstructPath(Map<Point, Point> previous, Point current) {
            List<Point> path = new ArrayList<>();
            while (previous.containsKey(current)) { //add path from end to each previous point
                path.add(current);
                current = previous.get(current);
            }
            Collections.reverse(path); //reverse since starts from end
            return path;
        }

        //euclidean distance formula
        public int calculateHeuristic(Point start, Point end) {
            int x = end.getX() - start.getX();
            int y = end.getY() - start.getY();
            return (int) Math.sqrt(x * x + y * y);
        }
}