Racetrack pathfinding and path following

Question

Racetrack

The August community challenge is to implement a program that plays the Racetrack game. Each player starts with an integer position on a square grid. On each turn, the current player can accelerate by -1, 0, or 1 unit in each direction. The first player to reach the finish line wins.

Most of my Java implementation of the challenge is posted in the question Racetrack in Java. The pathfinding and path following logic is below. Any feedback on any aspect of the program would be appreciated.

I'm sorry about the long lines. I was following a margin line, but I just now realized how far out it was set (120 columns).

---

PathFinder.java

The goal was not just to implement a program that allows the user to play Racetrack, but to implement a program that plays the game. For this, the ability to find a path to the finish line, moving in the correct direction, is needed. That's what PathFinder is for.

It's pretty obvious that I've never dealt with pathfinding before, yes?

package com.erichamion.racetrack;

import java.util.*;

/**
 * Created by me on 8/17/15.
 */
public class PathFinder {
    // Give impassable nodes a cost too high for anything else to match,
    // but not so high as to create any possibility of overflow.
    private static final double COST_IMPASSABLE = Double.MAX_VALUE / 1e6;
    private static final double COST_OPEN = 1.0;
    private static final double COST_NEAR_WALL = 2.0;
    private static final double COST_DIRECTION_CONSTANT = 0.001;

    private Deque<GridPoint> mPath = new LinkedList<>();



    public PathFinder(final Track track, final int playerIndex) {
        PathNode pathEnd = findBestPath(track, track.getPlayerPos(playerIndex));
        if (pathEnd != null) {
            //noinspection StatementWithEmptyBody
            while (smoothPath(track, pathEnd)) {}

            PathNode currentNode = pathEnd;
            while (currentNode != null) {
                mPath.addFirst(currentNode.getPosition());
                currentNode = currentNode.getPrev();
            }
        }

    }

    /**
     * Returns the next point on the calculated path without altering the
     * path.
     * @return The next point on the path
     */
    public GridPoint peekNextPathPoint() {
        return (mPath.isEmpty()) ? null : mPath.peekFirst();
    }

    /**
     * Removes and returns the next point on the calculated path.
     * @return The next point on the path
     */
    public GridPoint getNextPathPoint() {
        return (mPath.isEmpty()) ? null : mPath.removeFirst();
    }


    private static PathNode findBestPath(final Track track, final GridPoint start) {
        // Since we don't know where our goals are, use Dijkstra's algorithm.
        PriorityQueue<PathNode> frontier = new PriorityQueue<>(PathNode.costComparator);
        frontier.add(new PathNode(start, null, 0.0));
        Set<PathNode> visited = new TreeSet<>(PathNode.gridPointComparator);

        PathNode endNode = null;
        while (!frontier.isEmpty()) {
            PathNode currentNode = frontier.remove();

            // Fail when we run out of passable locations, or succeed when
            // we reach a finish line.
            if (currentNode.getTotalCost() >= COST_IMPASSABLE) {
                break;
            }
            Track.SpaceType spaceType = track.getSpace(currentNode.getPosition());
            if (spaceType == Track.SpaceType.FINISH_UP || spaceType == Track.SpaceType.FINISH_DOWN ||
                    spaceType == Track.SpaceType.FINISH_LEFT || spaceType == Track.SpaceType.FINISH_RIGHT) {
                endNode = currentNode;
                break;
            }

            PathNode[] neighbors = getNeighbors(currentNode);
            for (PathNode neighbor : neighbors) {
                if (visited.contains(neighbor)) continue;

                PathNode realNeighborNode = Util.getObjectFromIterable(frontier, neighbor);
                boolean needsRemovedFromFrontier = true;
                if (realNeighborNode == null) {
                    realNeighborNode = neighbor;
                    needsRemovedFromFrontier = false;
                }
                double totalCostToNeighbor = getMoveCost(track, currentNode, realNeighborNode) + currentNode.getTotalCost();
                if (totalCostToNeighbor < realNeighborNode.getTotalCost()) {
                    if (needsRemovedFromFrontier) frontier.remove(realNeighborNode);

                    realNeighborNode.setPrev(currentNode);
                    realNeighborNode.setTotalCost(totalCostToNeighbor);
                    frontier.add(realNeighborNode);
                }
            }

            visited.add(currentNode);
        }

        return endNode;
    }

    private boolean smoothPath(final Track track, final PathNode pathEnd) {
        boolean madeChanges = false;
        PathNode middleNode = pathEnd.getPrev();
        if (middleNode == null) {
            // pathEnd is also the path start, can't change anything
            return madeChanges;
        }
        PathNode anchorNode = middleNode.getPrev();
        if (anchorNode == null) {
            // middleNode is the path start, can't remove it
            return madeChanges;
        }

        boolean hasLineOfSight = true;
        for (GridPoint point : track.getPath(pathEnd.getPosition(), anchorNode.getPosition())) {
            if (track.getSpace(point) == Track.SpaceType.WALL) {
                hasLineOfSight = false;
                break;
            }
        }

        if (hasLineOfSight) {
            pathEnd.setPrev(anchorNode);
            madeChanges = true;
        }

        return madeChanges || smoothPath(track, pathEnd.getPrev());
    }



    /**
     * Retrieves all 8 neighbors of a node. Does not check the neighboring
     * nodes for validity in any way.
     * @param centerNode The central node for which to get neighbors
     * @return A List containing 8 PathNodes, each representing a
     * neighbor (horizontal, vertical, or diagonal) of the original node.
     * The GridPoints may represent locations that are outside of the
     * track or otherwise invalid.
     */
    private static PathNode[] getNeighbors(final PathNode centerNode) {
        PathNode[] result = new PathNode[8];

        int arrayIndex = 0;
        GridPoint displacement = new GridPoint(-1, -1);
        for (; displacement.getRow() <= 1; displacement.setRow(displacement.getRow() + 1)) {
            for (displacement.setCol(-1); displacement.getCol() <= 1; displacement.setCol(displacement.getCol() + 1)) {
                if (displacement.getRow() == 0 && displacement.getCol() == 0) continue;

                GridPoint point = GridPoint.add(centerNode.getPosition(), displacement);
                result[arrayIndex++] = new PathNode(point, centerNode, Double.MAX_VALUE);
            }
        }

        return result;
    }

    private static double getMoveCost(final Track track, final PathNode fromNode, final PathNode toNode) {
        switch (track.getSpace(toNode.getPosition())) {
            case WALL:
                return COST_IMPASSABLE;
            case TRACK:
                return getOpenSpaceMoveCost(track, fromNode, toNode);
            case FINISH_UP:
                return (GridPoint.subtract(toNode.getPosition(), fromNode.getPosition()).getRow() == -1) ?
                        getOpenSpaceMoveCost(track, fromNode, toNode) : COST_IMPASSABLE;
            case FINISH_DOWN:
                return (GridPoint.subtract(toNode.getPosition(), fromNode.getPosition()).getRow() == 1) ?
                        getOpenSpaceMoveCost(track, fromNode, toNode) : COST_IMPASSABLE;
            case FINISH_LEFT:
                return (GridPoint.subtract(toNode.getPosition(), fromNode.getPosition()).getCol() == -1) ?
                        getOpenSpaceMoveCost(track, fromNode, toNode) : COST_IMPASSABLE;
            case FINISH_RIGHT:
                return (GridPoint.subtract(toNode.getPosition(), fromNode.getPosition()).getCol() == 1) ?
                        getOpenSpaceMoveCost(track, fromNode, toNode) : COST_IMPASSABLE;
            default:
                // Should never happen
                return COST_IMPASSABLE;
        }
    }

    private static double getOpenSpaceMoveCost(final Track track, final PathNode fromNode, final PathNode toNode) {
        // Prefer straight paths that don't hug the walls
        double baseCost = isNearWall(track, toNode) ? COST_NEAR_WALL : COST_OPEN;
        double directionPenalty = 0.0;
        if (fromNode.getPrev() != null) {
            GridPoint oldDirection =
                    GridPoint.subtract(fromNode.getPosition(), fromNode.getPrev().getPosition());
            GridPoint newDirection = GridPoint.subtract(toNode.getPosition(), fromNode.getPosition());
            directionPenalty = COST_DIRECTION_CONSTANT * (1 - GridPoint.unitDotProduct(oldDirection, newDirection));
        }
        return baseCost + directionPenalty;
    }

    private static boolean isNearWall(final Track track, final PathNode node) {
        PathNode[] neighbors = getNeighbors(node);
        for (PathNode neighbor : neighbors) {
            if (track.getSpace(neighbor.getPosition()) == Track.SpaceType.WALL) {
                return true;
            }
        }
        return false;
    }


    private static class PathNode {
        private GridPoint mPosition;
        private PathNode mPrev;
        private Double mTotalCost;

        /**
         * Compares nodes based on the total cost from the starting point
         * to each node. Note that this Comparator is NOT consistent with
         * PathNode#equals.
         */
        public static final Comparator<PathNode> costComparator = new Comparator<PathNode>() {
            @Override
            public int compare(PathNode o1, PathNode o2) {
                return o1.getTotalCost().compareTo(o2.getTotalCost());
            }
        };

        /**
         * Compares nodes based on their location on the grid.
         */
        public static final Comparator<PathNode> gridPointComparator = new Comparator<PathNode>() {
            @Override
            public int compare(PathNode o1, PathNode o2) {
                // I don't care too much about what the actual order is,
                // as long as it is well defined.
                // Directly access the mPosition members to avoid creating
                // new copies.
                int result = o1.mPosition.getRow() - o2.mPosition.getRow();
                if (result == 0) {
                    result = o1.mPosition.getCol() - o2.mPosition.getCol();
                }
                return result;
            }
        };

        public PathNode() { }

        public PathNode(final GridPoint pos, final PathNode prev, final double totalCost) {
            mPosition = new GridPoint(pos);
            mPrev = prev;
            mTotalCost = totalCost;
        }

        public Double getTotalCost() {
            return mTotalCost;
        }

        public void setTotalCost(final double totalCost) {
            mTotalCost = totalCost;
        }

        public GridPoint getPosition() {
            return mPosition;
        }

        public PathNode getPrev() {
            return mPrev;
        }

        public void setPrev(final PathNode prev) {
            mPrev = prev;
        }

        @Override
        public boolean equals(final Object obj) {
            if (obj instanceof PathNode) {
                PathNode secondNode = (PathNode) obj;
                return gridPointComparator.compare(this, secondNode) == 0;
            } else if (obj instanceof GridPoint) {
                GridPoint point = (GridPoint) obj;
                return this.mPosition.equals(point);
            } else {
                throw new ClassCastException();
            }
        }

        @Override
        public String toString() {
            return "Location: " + mPosition.toString() + "; Cost: " + mTotalCost.toString();
        }
    }
}

---

PathFollower.java

It's nice to have a path, but the path doesn't accomplish anything without some way to follow it. PathFollower follows the path given by a PathFinder, while doing its best to avoid obstacles and other players.

This isn't a great strategy for a racecar driver. It drives like an old lady going 50 mph on the highway, stopping and looking both ways at every corner. It's also not hard to design a track that will confuse the PathFinder and send it crashing into a wall. Still, it works, and it can navigate some surprisingly complex tracks.

package com.erichamion.racetrack;

import java.util.*;

/**
 * Created by me on 8/19/15.
 */
public class PathFollower {
    private final PathFinder mPathFinder;
    private final Track mTrack;
    private final int mPlayerIndex;
    private GridPoint mGoal;
    // private GridPoint mNextGoal;
    // private GridPoint mNextGoalDiff;

    private static final GridPoint[] ALL_DIRECTIONS = new GridPoint[9];
    static {
        int i = 0;
        for (int row = -1; row <= 1; row++) {
            for (int col = -1; col <= 1; col++) {
                ALL_DIRECTIONS[i++] = new GridPoint(row, col);
            }
        }
    }

    public PathFollower(final Track track, final PathFinder pathFinder, final int playerIndex) {
        mTrack = track;
        mPathFinder = pathFinder;
        mPlayerIndex = playerIndex;
        updateGoal();
    }

    /**
     * Calculate the acceleration needed for the next move. Will attempt
     * to follow the path that was supplied as a PathFinder argument to
     * this object's constructor.
     * @return A GridPoint containing the row and column acceleration to
     * apply. The acceleration in each dimension will be in the range
     * [-1, 1].
     */
    public GridPoint getMove() {
        GridPoint currentPosition = mTrack.getPlayerPos(mPlayerIndex);
        GridPoint currentVelocity = mTrack.getPlayerVelocity(mPlayerIndex);

        if (currentPosition.equals(mGoal)) {
            updateGoal();
        }

        MoveMap moveMap = new MoveMap(currentPosition, mGoal, currentVelocity, ALL_DIRECTIONS);
        Comparator<GridPoint> comparator;

        // If we're moving the wrong direction or the goal is farther than
        // the distance needed to stop, rush headlong toward the goal.
        if (isWrongDirection(currentPosition, currentVelocity, mGoal) ||
                isPastStoppingDistance(GridPoint.add(currentPosition, currentVelocity), currentVelocity, mGoal)) {
            comparator = new LongDistanceComparator(moveMap);

        } else if (Math.abs(currentVelocity.getRow()) > 1 || Math.abs(currentVelocity.getCol()) > 1) {
            // Once we're down to the stopping distance, decelerate to -1, 0,
            // or 1 in each direction.
            comparator = new DecelerateComparator(moveMap);

        } else {
            // Once velocity is within +/- 1 in each direction, head toward
            // the goal while keeping velocity low.
            comparator = new LimpComparator(moveMap);

        }

        Queue<GridPoint> candidates = new PriorityQueue<>(ALL_DIRECTIONS.length, comparator);
        for (GridPoint direction : ALL_DIRECTIONS) {
            candidates.add(direction);
        }

        // Get the best move that doesn't crash immediately into a wall or
        // another player.
        GridPoint result = null;
        do {
            GridPoint candidate = candidates.remove();
            if (!mTrack.willPlayerCrash(mPlayerIndex, moveMap.getPosition(candidate))) {
                result = candidate;
            }
        } while (result == null && !candidates.isEmpty());

        return (result == null) ? new GridPoint(0, 0) : result;
    }



    private void updateGoal() {
        mGoal = mPathFinder.getNextPathPoint();
//        mNextGoal = mPathFinder.peekNextPathPoint();
//        if (mNextGoal != null) {
//            mNextGoalDiff = GridPoint.subtract(mNextGoal, mGoal);
//        } else {
//            mNextGoalDiff = null;
//        }
    }

    /**
     * Calculates the number of spaces on each axis needed to stop, given
     * an initial velocity.
     * @param startVelocity A starting velocity
     * @return A GridPoint containing the number of spaces needed to stop
     * from the initial velocity. Both the row and column values will be
     * non-negative, representing distance, not displacement.
     */
    private GridPoint getStoppingDistance(GridPoint startVelocity) {
        // For each axis with an initial speed S, stopping requires a
        // number of spaces equal to:
        // S + (S - 1) + (S - 2) + ... + 2 + 1
        // This sum is equal to S * (S + 1) / 2

        GridPoint result = new GridPoint();
        for (GridPoint.Axis axis : GridPoint.Axis.values()) {
            int velocity = startVelocity.getValueOnAxis(axis);
            int speed = Math.abs(velocity);
            int distanceNeeded = speed * (speed + 1) / 2;
            result.setValueOnAxis(axis, distanceNeeded);
        }

        return result;
    }

    /**
     * Determines whether at least one of the velocity components (row or
     * column component) points away from the goal.
     * @param position The current position
     * @param velocity The velocity
     * @param goal The target position
     * @return Returns true if one or both velocity components point away
     * from the goal, false otherwise.
     */
    private boolean isWrongDirection(final GridPoint position, final GridPoint velocity, final GridPoint goal) {
        for (GridPoint.Axis axis : GridPoint.Axis.values()) {
            int goalDistance = goal.getValueOnAxis(axis) - position.getValueOnAxis(axis);
            int velocityComponent = velocity.getValueOnAxis(axis);

            // If either the velocity or the distance to the goal on this
            // axis is 0, it isn't wrong.
            if (goalDistance == 0 || velocityComponent == 0) continue;

            if (!Util.isSignSame(goalDistance, velocityComponent)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Returns true if the goal is outside the required stopping
     * distance with the current velocity, in at least one component (row
     * or column).
     * @param position The current position
     * @param velocity The current velocity
     * @param goal The target position
     * @return Returns false if both components of the distance to the
     * goal are equal to or less than the required stopping distance, true
     * otherwise.
     */
    private boolean isPastStoppingDistance(final GridPoint position, final GridPoint velocity, final GridPoint goal) {
        GridPoint stoppingVector = getStoppingDistance(velocity);
        for (GridPoint.Axis axis : GridPoint.Axis.values()) {
            int goalDistance = Math.abs(goal.getValueOnAxis(axis) - position.getValueOnAxis(axis));
            int stoppingDistance = stoppingVector.getValueOnAxis(axis);

            if (goalDistance > stoppingDistance) {
                return true;
            }
        }

        return false;
    }



    /**
     * Prioritizes the closest direction to the goal, with near matches
     * being broken by the highest velocity.
     */
    private static class LongDistanceComparator implements Comparator<GridPoint> {
        private static final double DOT_PRODUCT_CUTOFF = 0.01;

        private final MoveMap mMap;
        private final GridPoint mFromStartToGoal;

        public LongDistanceComparator(MoveMap moveMap) {
            mMap = moveMap;
            mFromStartToGoal = GridPoint.subtract(mMap.getGoalPoint(), mMap.getStartPoint());
        }


        @Override
        public int compare(GridPoint o1, GridPoint o2) {
            GridPoint velocity1 = mMap.getVelocity(o1);
            GridPoint velocity2 = mMap.getVelocity(o2);

            // (0, 0) doesn't have a unit vector, so it needs special
            // handling. There's no reason to sit stationary, so give
            // (0, 0) the lowest priority.
            if (velocity1.getRow() == 0 && velocity1.getCol() == 0) {
                if (velocity2.getRow() == 0 && velocity2.getCol() == 0) {
                    return 0;
                } else {
                    return 1;
                }
            } else if (velocity2.getRow() == 0 && velocity2.getCol() == 0) {
                return -1;
            }

            double dotResult = GridPoint.unitDotProduct(mFromStartToGoal, velocity2) -
                    GridPoint.unitDotProduct(mFromStartToGoal, velocity1);

            // Velocities of (2, 0) and (2,1) will have a unit dot product
            // of (2 / Math.sqrt(5)), which is about 0.89.
            if (Math.abs(dotResult) < DOT_PRODUCT_CUTOFF) {
                // The directions are close. Prioritize high velocity.
                return (velocity2.getRow() * velocity2.getRow() + velocity2.getCol() * velocity2.getCol()) -
                        (velocity1.getRow() * velocity1.getRow() + velocity1.getCol() * velocity1.getCol());
            } else if (dotResult < 0) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    /**
     * Prioritizes deceleration. If two directions have equally low
     * resulting speeds, then the one that points closest to the goal
     * wins.
     */
    private static class DecelerateComparator implements Comparator<GridPoint> {
        private final MoveMap mMap;
        private final GridPoint mFromStartToGoal;

        public DecelerateComparator(MoveMap moveMap) {
            mMap = moveMap;
            mFromStartToGoal = GridPoint.subtract(mMap.getGoalPoint(), mMap.getStartPoint());
        }

        @Override
        public int compare(GridPoint o1, GridPoint o2) {
            // First-order comparison: minimize the total resulting
            // velocity (measured as the sum of the velocity coordinates).
            GridPoint velocity1 = mMap.getVelocity(o1);
            GridPoint velocity2 = mMap.getVelocity(o2);
            int comparison = (Math.abs(velocity1.getRow()) + Math.abs(velocity1.getCol())) -
                    (Math.abs(velocity2.getRow()) + Math.abs(velocity2.getCol()));

            // Break ties by pointing toward the goal (use unit dot
            // product, not just dot product, because we want to reward
            // only direction, not speed.
            if (comparison == 0) {
                double secondComparison = GridPoint.unitDotProduct(mFromStartToGoal, velocity2) -
                        GridPoint.unitDotProduct(mFromStartToGoal, velocity1);
                if (secondComparison < 0.0) {
                    comparison = -1;
                } else if (secondComparison >= 0.0) {
                    comparison = 1;
                }
            }

            return comparison;
        }
    }

    /**
     * Limps along toward the goal. The first order comparison breaks
     * directions into two groups: directions which result in velocities
     * that have both components in the range [-1, 1], and directions
     * which don't result in such velocities. The first group is
     * preferred. Within each group, the direction that results in
     * movement closest to the direction of the goal is preferred.
     */
    private static class LimpComparator implements Comparator<GridPoint> {
        private final MoveMap mMap;
        private final GridPoint mFromStartToGoal;

        public LimpComparator(MoveMap moveMap) {
            mMap = moveMap;
            mFromStartToGoal = GridPoint.subtract(mMap.getGoalPoint(), mMap.getStartPoint());
        }

        @Override
        public int compare(GridPoint o1, GridPoint o2) {
            GridPoint velocity1 = mMap.getVelocity(o1);
            GridPoint velocity2 = mMap.getVelocity(o2);

            boolean isSlow1 = Math.abs(velocity1.getRow()) <= 1 && Math.abs(velocity1.getCol()) <= 1;
            boolean isSlow2 = Math.abs(velocity2.getRow()) <= 1 && Math.abs(velocity2.getCol()) <= 1;

            if (isSlow1 != isSlow2) {
                // Exactly one of the resulting velocities has a component
                // greater than 1 (or less than -1). Prioritize the other
                // one.
                return isSlow1 ? -1 : 1;
            }

            // Either both velocities are either acceptably slow, or
            // neither is. Prioritize the highest unit dot product between
            // the velocity vector and the vector to the goal.
            double comparison = GridPoint.unitDotProduct(mFromStartToGoal, velocity2) -
                    GridPoint.unitDotProduct(mFromStartToGoal, velocity1);
            if (comparison < 0.0) {
                return -1;
            } else if (comparison >= 0.0) {
                return 1;
            }
            return 0;
        }
    }


    private static class MoveMap {
        private static final int VEL = 0;
        private static final int POS = 1;

        private final GridPoint mStart;
        private final GridPoint mGoal;
        private final Map<GridPoint, GridPoint[]> mMap = new HashMap<>();


        public MoveMap(final GridPoint start, final GridPoint goal, final GridPoint baseVelocity,
                       final GridPoint[] directions) {
            mStart = start;
            mGoal = goal;
            for (GridPoint direction : directions) {
                GridPoint[] newEntry = new GridPoint[2];
                newEntry[VEL] = GridPoint.add(baseVelocity, direction);
                newEntry[POS] = GridPoint.add(mStart, newEntry[VEL]);
                mMap.put(direction, newEntry);
            }
        }

        public GridPoint getStartPoint() {
            return mStart;
        }

        public GridPoint getGoalPoint() {
            return mGoal;
        }

        public GridPoint getPosition(final GridPoint direction) {
            GridPoint[] entry = mMap.get(direction);
            return (entry == null) ? null : entry[POS];
        }

        public GridPoint getVelocity(final GridPoint direction) {
            GridPoint[] entry = mMap.get(direction);
            return (entry == null) ? null : entry[VEL];
        }
    }
}

---

track1.txt

A track is a text file with a simple format. The first character that appears is considered to be a wall. ^, v, <, and > are finish lines that must be crossed in the direction that they point. Any other characters are player starting positions. Here is an example track.

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwww                                     wwwwwwwww
wwwwwwwwwwwwwww                                       wwwwwwwww
wwwwwwwwwwwwwww                                       wwwwwwwww
wwwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwww           wwwwwwwww
wwwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwww           wwwwwwwww
wwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwwww           wwwwwwwww
wwwwwwwwwwww        wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwww
wwwwwwwww       wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwww
wwwwwwwww      wwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwwwww
wwwwwwwww        wwwwwwwwwwwwwwwww           wwwwwwwwwwwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwww           wwwwwwwwwwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwww           wwwwwwwwwwwwwww
wwwwwwwwwww         wwwwwwwwwwwwwwwwwwww          wwwwwwwwwwwww
wwwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwww          wwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwww           wwwwwwww
wwwwww        wwwwwwwwwwwwwwwwwwwwwwwwwwwwww          wwwwwwwww
wwwwww                > 1                           wwwwwwwwwww
wwwwww                >                          wwwwwwwwwwwwww
wwwwwwww              > 2                     wwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

If Player 2 is computer controlled and Player 1 doesn't get in the way, here is the path it will follow:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwww                                     wwwwwwwww
wwwwwwwwwwwwwww          XXXX  X X                    wwwwwwwww
wwwwwwwwwwwwwww        X             X  X X           wwwwwwwww
wwwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwwwX          wwwwwwwww
wwwwwwwwwwwwwww     X  wwwwwwwwwwwwwwwwwwww X         wwwwwwwww
wwwwwwwwwwwwww   XX   wwwwwwwwwwwwwwwwwwwww X         wwwwwwwww
wwwwwwwwwwww   X    wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwwwwwwwww    X      wwwwwwwwwwww
wwwwwwwww     X wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwww
wwwwwwwww      wwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwwwww
wwwwwwwww        wwwwwwwwwwwwwwwww          Xwwwwwwwwwwwwwwwwww
wwwwwwwww    X    wwwwwwwwwwwwwwww           wwwwwwwwwwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwww       X   wwwwwwwwwwwwwww
wwwwwwwwwww  X      wwwwwwwwwwwwwwwwwwww     X    wwwwwwwwwwwww
wwwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwww   X      wwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwww X       wwwwwwwww
wwwwwwwww   X     wwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwww X       wwwwwwww
wwwwwww     X   wwwwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwww      X  wwwwwwwwwwwwwwwwwwwwwwwwwwwww   X       wwwwwwww
wwwwww       Xwwwwwwwwwwwwwwwwwwwwwwwwwwwwww XX       wwwwwwwww
wwwwww        X X     > 1                 XX        wwwwwwwwwww
wwwwww             X XX           X  X XX        wwwwwwwwwwwwww
wwwwwwww              > 2X X  X               wwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

If either (but not both) of the players is computer controlled, it can successfully navigate the track below.

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwww            w                        wwwwwwwww
wwwwwwwwwwwwwww              w            wwwwwwwwww  wwwwwwwww
wwwwwwwwwwwwwww                           w           wwwwwwwww
wwwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwww wwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwww           wwwwwwwww
wwwwwwwwwwwwww        wwwwwwwwwwwwwwwwwwwwwwwwwwwwww  wwwwwwwww
wwwwwwwwwwww        wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwww
wwwwwwwww       wwwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwww
wwwwwwwww      wwwwwwwwwwwwwwwwwwwww           wwwwwwwwwwwwwwww
wwwwwwwww        wwwwwwwwwwwwwwwww           wwwwwwwwwwwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwww           wwwwwwwwwwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwww           wwwwwwwwwwwwwww
wwwwwwwwwww         wwwwwwwwwwwwwwwwwwww          wwwwwwwwwwwww
wwwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwww          wwwwwwwwww
wwwwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwww     w   wwwwwwwww
wwwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwww    w    wwwwwwww
wwwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww  wwwwwwww
wwwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwwww         wwwwwwww
wwwwww         wwwwwwwwwwwwwwwwwwwwwwwwwwwww           wwwwwwww
wwwwww        wwwwwwwwwwwwwwwwwwwwwwwwwwwwww          wwwwwwwww
wwwwww                > 1                 wwwww     wwwwwwwwwww
wwwwww                >                          wwwwwwwwwwwwww
wwwwwwww              > 2                     wwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

Answer 1

public PathFinder(final Track track, final int playerIndex) {
    PathNode pathEnd = findBestPath(track, track.getPlayerPos(playerIndex));
    if (pathEnd != null) {
        //noinspection StatementWithEmptyBody
        while (smoothPath(track, pathEnd)) {}

        PathNode currentNode = pathEnd;
        while (currentNode != null) {
            mPath.addFirst(currentNode.getPosition());
            currentNode = currentNode.getPrev();
        }
    }

}

So, first point is the obviously empty while loop. Seems you have even put a comment there... or an automated tool did so? It looks like something related to automated tools. Anyway, if that's a disable flag for an automated tool, you might want to explain why this is not a problem. Maybe something like "Smooth the path until no more improvements are made".

You have a loop afterwards, with a condition that currentNode != null. currentNode starts off at pathEnd, which has a value guaranteed to ... not be null. So you could have a do while loop instead, skipping that initial null check.