(Refer to the entire repository in GitHub.)

Intro

This time, I present my take on Jump point search that I translated from Javascript (PathFinding.js/src/finders/JumpPointFinderBase.js and related files) to Java.

Code

io.github.coderodde.pathfinding.finders..java:

package io.github.coderodde.pathfinding.finders;

import static io.github.coderodde.pathfinding.finders.Finder.expandPath;
import static io.github.coderodde.pathfinding.finders.Finder.searchSleep;
import io.github.coderodde.pathfinding.finders.jps.jumpers.DiagonalNonCrossingJumper;
import io.github.coderodde.pathfinding.finders.jps.jumpers.NoDiagonalJumper;
import io.github.coderodde.pathfinding.finders.jps.neighbourfinders.DiagonalCrossingNeighbourFinder;
import io.github.coderodde.pathfinding.finders.jps.neighbourfinders.DiagonalNoCrossingNeighbourFinder;
import io.github.coderodde.pathfinding.finders.jps.neighbourfinders.NoDiagonalNeighbourFinder;
import io.github.coderodde.pathfinding.heuristics.HeuristicFunction;
import io.github.coderodde.pathfinding.logic.GridCellNeighbourIterable;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.logic.SearchState;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * This class implements the Jump Point Search.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 19, 2025)
 * @since 1.0.0 (Oct 19, 2025)
 */
public final class JumpPointSearchFinder implements Finder {

    /**
     * This interface defines the API for computing neighbour cells of a given 
     * cell.
     */
    public interface NeighbourFinder {
        
        /**
         * Finds the neighbour cells of the cell {@code current}.
         * 
         * @param current    the cell whose neighbours to find.
         * @param parentsMap the map which maps cells to their respective parent
         *                   cells.
         * @param model      the grid model.
         * @param ps         the pathfinding settings.
         * @return 
         */
        List<Cell> findNeighbours(Cell current,
                                  Map<Cell, Cell> parentsMap,
                                  GridModel model,
                                  PathfindingSettings ps);
    }
    
    /**
     * This interface defines the API for jumping algorithms.
     */
    public interface Jumper {
        
        /**
         * Jumps to the next jump point cell.
         * 
         * @param x                the {@code x} coordinate of the current cell.
         * @param y                the {@code y} coordinate of the current cell.
         * @param px               the {@code x} coordinate of the parent cell.
         * @param py               the {@code y} coordinate of the parent cell.
         * @param model            the grid model.
         * @param searchStatistics the search statistics object.
         * 
         * @return the next jump point cell or {@code null} if there is no such.
         */
        Cell jump(int x,
                  int y,
                  int px,
                  int py,
                  GridModel model,
                  SearchStatistics searchStatistics);
    }
    
    @Override
    public List<Cell> findPath(GridModel model, 
                               GridCellNeighbourIterable neighbourIterable, 
                               PathfindingSettings pathfindingSettings, 
                               SearchState searchState, 
                               SearchStatistics searchStatistics) {
        
        NeighbourFinder neighbourFinder = 
                getNeighbourFinder(pathfindingSettings);
        
        Jumper jumper = getJumper(pathfindingSettings);
        
        Cell source = model.getSourceGridCell();
        Cell target = model.getTargetGridCell();
        
        Queue<HeapNode> open          = new PriorityQueue<>();
        Set<Cell> openSet             = new HashSet<>();
        Set<Cell> closed              = new HashSet<>();
        Map<Cell, Double> distanceMap = new HashMap<>();
        Map<Cell, Cell> parentsMap    = new HashMap<>();
        
        open.add(new HeapNode(source, 0.0));
        openSet.add(source);
        parentsMap.put(source, null);
        distanceMap.put(source, 0.0);
        
        while (!open.isEmpty()) {
            if (searchState.haltRequested()) {
                return List.of();
            }
            
            if (searchState.pauseRequested()) {
                searchSleep(pathfindingSettings);
                continue;
            }
            
            Cell current = open.remove().cell;
            
            if (model.getCellType(current) != CellType.SOURCE &&
                model.getCellType(current) != CellType.TARGET) {
                model.setCellType(current, CellType.VISITED);
            }
            
            if (current.equals(target)) {
                List<Cell> compressedPath = tracebackPath(target,
                                                          parentsMap);
                return expandPath(compressedPath, 
                                  model);
            }
            
            searchStatistics.incrementVisited();
            closed.add(current);
            
            identifySuccessors(current,
                               open,
                               closed,
                               openSet,
                               distanceMap,
                               parentsMap,
                               model,
                               pathfindingSettings,
                               searchState,
                               searchStatistics,
                               neighbourFinder,
                               jumper);
        }
        
        return List.of();
    }
    
    /**
     * Returns the required neighbour finder.
     * 
     * @param pathfindingSettings the pathfinding settings object.
     * 
     * @return an instance of the suitable 
     *         {@link io.github.coderodde.pathfinding.finders.JumpPointSearchFinder.NeighbourFinder}.
     */
    private static NeighbourFinder 
        getNeighbourFinder(PathfindingSettings pathfindingSettings) {
        
        if (pathfindingSettings.allowDiagonals()) {
            if (pathfindingSettings.dontCrossCorners()) {
                return new DiagonalNoCrossingNeighbourFinder();
            } else {
                return new DiagonalCrossingNeighbourFinder();
            }
        } else {
            return new NoDiagonalNeighbourFinder();
        }
    }
    
    /**
     * Returns the required jumper.
     * 
     * @param pathfindingSettings the pathfinding settings object.
     * 
     * @return an instance of the suitable 
     *         {@link io.github.coderodde.pathfinding.finders.JumpPointSearchFinder.Jumper}.
     */
    private static Jumper getJumper(PathfindingSettings pathfindingSettings) {
        
        if (pathfindingSettings.allowDiagonals()) {
            return new DiagonalNonCrossingJumper();
        } else {
            return new NoDiagonalJumper();
        }
    }
           
    private static void identifySuccessors(Cell current,
                                           Queue<HeapNode> open,
                                           Set<Cell> closed,
                                           Set<Cell> openSet,
                                           Map<Cell, Double> distanceMap,
                                           Map<Cell, Cell> parentsMap,
                                           GridModel model,
                                           PathfindingSettings ps,
                                           SearchState searchState,
                                           SearchStatistics searchStatistics,
                                           NeighbourFinder neighbourFinder,
                                           Jumper jumper) {
        
        List<Cell> neighbors = 
                neighbourFinder.findNeighbours(current,
                                               parentsMap,
                                               model,
                                               ps);
        
        int x = current.getx();
        int y = current.gety();
        HeuristicFunction hf = ps.getHeuristicFunction();
        
        for (Cell child : neighbors) {
            if (searchState.haltRequested()) {
                throw new HaltRequestedException();
            }
            
            while (searchState.pauseRequested()) {
                searchSleep(ps);
                
                if (searchState.haltRequested()) {
                    throw new HaltRequestedException();
                }
            }
            
            Cell jumpCell = jumper.jump(child.getx(),
                                        child.gety(),
                                        x,
                                        y,
                                        model,
                                        searchStatistics);
            
            if (jumpCell == null) {
                continue;
            }
            
            int jx = jumpCell.getx();
            int jy = jumpCell.gety();
            jumpCell = model.getCell(jx, jy);
            
            if (closed.contains(jumpCell)) {
                continue;
            }
            
            double distance = hf.estimate(jx - x,
                                          jy - y);
            
            double nextg = distanceMap.get(current) + distance;
            
            if (!openSet.contains(jumpCell) ||
                nextg < distanceMap.get(jumpCell)) {
                
                distanceMap.put(jumpCell, nextg);
                
                double f = 
                        nextg + 
                        hf.estimate(jx - model.getTargetGridCell().getx(),
                                    jy - model.getTargetGridCell().gety());
                
                parentsMap.put(jumpCell, current);
                
                if (!openSet.contains(jumpCell)) {
                     openSet.add(jumpCell);
                }
                
                open.add(new HeapNode(jumpCell, f));
                
                searchStatistics.incrementOpened();
                searchSleep(ps);
            }
        }
    }
}

io.github.coderodde.pathfinding.finders.jps.jumpers.DiagonalNonCrossingJumper.java:

package io.github.coderodde.pathfinding.finders.jps.jumpers;

import io.github.coderodde.pathfinding.finders.JumpPointSearchFinder;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;

/**
 * This class implements the algorithm for doing jumps also diagonally but only 
 * if there is no obstacle wall crossing on the way.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 21, 2025)
 * @since 1.0.0 (Oct 21, 2025)
 */
public final class DiagonalNonCrossingJumper 
        implements JumpPointSearchFinder.Jumper {
    
    /**
     * This method implements jumping when diagonal moves crossing obstacle wall 
     * corners are not allowed.
     * 
     * @param x                the {@code X}-coordinate of the current cell.
     * @param y                the {@code Y}-coordinate of the current cell.
     * @param px               the {@code X}-coordinate of the parent cell.
     * @param py               the {@code Y}-coordinate of the parent cell.
     * @param model            the grid model.
     * @param searchStatistics the search statistics object.
     * 
     * @return the next cell.
     */
    @Override
    public Cell jump(int x,
                     int y,
                     int px, 
                     int py,
                     GridModel model,
                     SearchStatistics searchStatistics) {
        
        int dx = x - px;
        int dy = y - py;
        
        if (!model.isWalkable(x, y)) {
            return null;
        }
        
        if (!model.getCellType(x, y).equals(CellType.SOURCE) &&
            !model.getCellType(x, y).equals(CellType.TARGET)) {
            model.setCellType(x, y, CellType.TRACED);
            searchStatistics.incrementTraced();
        }
        
        if (model.getCell(x, y).equals(model.getTargetGridCell())) {
            return model.getTargetGridCell();
        }
        
        if (dx != 0 && dy != 0) {
            if (jump(x + dx,
                     y,
                     x,
                     y,
                     model,
                     searchStatistics) != null ||
                jump(x,
                     y + dy,
                     x,
                     y,
                     model,
                     searchStatistics) != null) {
                
                return model.getCell(x, y);
            }
        } else {
            if (dx != 0) {
                if ((model.isWalkable(x, y - 1) &&
                    !model.isWalkable(x - dx, y - 1)) ||
                    (model.isWalkable(x, y + 1) &&
                    !model.isWalkable(x - dx, y + 1))) {
                    
                    return model.getCell(x, y);
                }
            } else if (dy != 0) {
                if ((model.isWalkable(x - 1, y) &&
                    !model.isWalkable(x - 1, y - dy)) ||
                    (model.isWalkable(x + 1, y) &&
                    !model.isWalkable(x + 1, y - dy))) {
                    
                    return model.getCell(x, y);
                }
            }
        }
        
        if (model.isWalkable(x + dx, y) && model.isWalkable(x, y + dy)) {
            return jump(x + dx, 
                        y + dy, 
                        x, 
                        y, 
                        model,
                        searchStatistics);
        }
        
        return null;
    }
}

io.github.coderodde.pathfinding.finders.jps.jumpers.NoDiagonalJumper.java:

package io.github.coderodde.pathfinding.finders.jps.jumpers;

import io.github.coderodde.pathfinding.finders.JumpPointSearchFinder;
import io.github.coderodde.pathfinding.logic.SearchStatistics;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;

/**
 * This class implements the algorithm for doing jumps only vertically and
 * horizontally regardless the crossing obstacle walls.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 21, 2025)
 * @since 1.0.0 (Oct 21, 2025)
 */
public final class NoDiagonalJumper implements JumpPointSearchFinder.Jumper {

    /**
     * This method implements jumping when diagonal moves are not allowed.
     * 
     * @param x                the {@code X}-coordinate of the current cell.
     * @param y                the {@code Y}-coordinate of the current cell.
     * @param px               the {@code X}-coordinate of the parent cell.
     * @param py               the {@code Y}-coordinate of the parent cell.
     * @param model            the grid model.
     * @param searchStatistics the search statistics object.
     * 
     * @return the next cell.
     */
    @Override
    public Cell jump(int x, 
                     int y, 
                     int px, 
                     int py, 
                     GridModel model,
                     SearchStatistics searchStatistics) {
        
        int dx = x - px;
        int dy = y - py;
        
        if (!model.isWalkable(x, y)) {
            return null;
        }
        
        if (!model.getCellType(x, y).equals(CellType.SOURCE) &&
            !model.getCellType(x, y).equals(CellType.TARGET)) {
            model.setCellType(x, y, CellType.TRACED);
        }
        
        if (model.getCell(x, y).equals(model.getTargetGridCell())) {
            return model.getTargetGridCell();
        }
        
        if (dx != 0) {
            if ((model.isWalkable(x, y - 1) &&
                !model.isWalkable(x - dx, y - 1)) ||
                (model.isWalkable(x, y + 1) &&
                !model.isWalkable(x - dx, y + 1))) {
                
                return model.getCell(x, y);
            }
        } else if (dy != 0) {
            if ((model.isWalkable(x - 1, y) &&
                !model.isWalkable(x - 1, y - dy)) ||
                (model.isWalkable(x + 1, y) &&
                !model.isWalkable(x + 1, y - dy))) {
                
                return model.getCell(x, y);
            }
            
            if (jump(x + 1, y, x, y, model, searchStatistics) != null ||
                jump(x - 1, y, x, y, model, searchStatistics) != null) {
                
                return model.getCell(x, y);
            }
        } else {
            throw new IllegalStateException("Should not get here");
        }
        
        return jump(x + dx, 
                    y + dy,
                    x,
                    y, 
                    model, 
                    searchStatistics);
    }
}

io.github.coderodde.pathfinding.finders.jps.neighbourfinders.DiagonalNoCrossingNeighbourFinder.java:

package io.github.coderodde.pathfinding.finders.jps.neighbourfinders;

import io.github.coderodde.pathfinding.finders.JumpPointSearchFinder;
import io.github.coderodde.pathfinding.logic.GridNodeExpander;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * This class implements the 
 * {@link io.github.coderodde.pathfinding.finders.JumpPointSearchFinder.NeighbourFinder} 
 * interface for computing neighbours with diagonal movement that does not 
 * involve crossing an obstacle wall.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 21, 2025)
 * @since 1.0.0 (Oct 21, 2025)
 */
public final class DiagonalNoCrossingNeighbourFinder 
        implements JumpPointSearchFinder.NeighbourFinder {

    @Override
    public List<Cell> findNeighbours(Cell current, 
                                     Map<Cell, Cell> parentsMap, 
                                     GridModel model, 
                                     PathfindingSettings ps) {
        
        List<Cell> neighbours = new ArrayList<>();
        Cell parent = parentsMap.get(current);
        
        int x = current.getx();
        int y = current.gety();
        int px;
        int py;
        int dx;
        int dy;
        
        if (parent != null) {
            px = parent.getx();
            py = parent.gety();
            dx = (x - px) / Math.max(Math.abs(x - px), 1);
            dy = (y - py) / Math.max(Math.abs(y - py), 1);
            
            // Diagonal search:
            if (dx != 0 && dy != 0) {
                if (model.isWalkable(x, y + dy)) {
                    neighbours.add(model.getCell(x, y + dy));
                }
                
                if (model.isWalkable(x + dx, y)) {
                    neighbours.add(model.getCell(x + dx, y));
                }
                
                if (model.isWalkable(x, y + dy) &&
                    model.isWalkable(x + dx, y)) {
                    neighbours.add(model.getCell(x + dx, y + dy));
                }
            } else {
                // Once here, search horizontally or vertically:
                boolean isNextWalkable;
                
                if (dx != 0) {
                    isNextWalkable = model.isWalkable(x + dx, y);
                    boolean isTopWalkable = model.isWalkable(x, y + 1);
                    boolean isBottomWalkable = model.isWalkable(x, y - 1);
                    
                    if (isNextWalkable) {
                        neighbours.add(model.getCell(x + dx, y));
                        
                        if (isTopWalkable) {
                            neighbours.add(model.getCell(x + dx, y + 1));
                        }
                        
                        if (isBottomWalkable) {
                            neighbours.add(model.getCell(x + dx, y - 1));
                        }
                    }
                    
                    if (isTopWalkable) {
                        neighbours.add(model.getCell(x, y + 1));
                    }
                    
                    if (isBottomWalkable) {
                        neighbours.add(model.getCell(x, y - 1));
                    }
                } else if (dy != 0) {
                    isNextWalkable = model.isWalkable(x, y + dy);
                    boolean isRightWalkable = model.isWalkable(x + 1, y);
                    boolean isLeftWalkable  = model.isWalkable(x - 1, y);
                    
                    if (isNextWalkable) {
                        neighbours.add(model.getCell(x, y + dy));
                        
                        if (isRightWalkable) {
                            neighbours.add(model.getCell(x + 1, y + dy));
                        }
                        
                        if (isLeftWalkable) {
                            neighbours.add(model.getCell(x - 1, y + dy));
                        }
                    }
                    
                    if (isRightWalkable) {
                        neighbours.add(model.getCell(x + 1, y));
                    }
                    
                    if (isLeftWalkable) {
                        neighbours.add(model.getCell(x - 1, y));
                    }
                }
            }
        } else {
            // Once here, return all neighbours:
            neighbours.addAll(
                    new GridNodeExpander(model, 
                                         ps).expand(current));
        }
            
        return neighbours;
    }
}

io.github.coderodde.pathfinding.finders.jps.neighbourfinders.NoDiagonalNeighbourFinder.java:

package io.github.coderodde.pathfinding.finders.jps.neighbourfinders;

import io.github.coderodde.pathfinding.finders.JumpPointSearchFinder;
import io.github.coderodde.pathfinding.logic.GridNodeExpander;
import io.github.coderodde.pathfinding.logic.PathfindingSettings;
import io.github.coderodde.pathfinding.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * This class implements the 
 * {@link io.github.coderodde.pathfinding.finders.JumpPointSearchFinder.NeighbourFinder} 
 * interface for computing neighbours with no diagonal movement.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Oct 21, 2025)
 * @since 1.0.0 (Oct 21, 2025)
 */
public final class NoDiagonalNeighbourFinder 
        implements JumpPointSearchFinder.NeighbourFinder {

    @Override
    public List<Cell> findNeighbours(Cell current,
                                     Map<Cell, Cell> parentsMap, 
                                     GridModel model, 
                                     PathfindingSettings ps) {
        
        List<Cell> neighbours = new ArrayList<>();
        Cell parent = parentsMap.get(current);
        
        int x = current.getx();
        int y = current.gety();
        int px;
        int py;
        int dx;
        int dy;
        
        if (parent != null) {
            px = parent.getx();
            py = parent.gety();
            dx = (x - px) / Math.max(Math.abs(x - px), 1);
            dy = (y - py) / Math.max(Math.abs(y - py), 1);
            
            if (dx != 0) {
                if (model.isWalkable(x, y - 1)) {
                    neighbours.add(model.getCell(x, y - 1));
                }
                
                if (model.isWalkable(x, y + 1)) {
                    neighbours.add(model.getCell(x, y + 1));
                }
                
                if (model.isWalkable(x + dx, y)) {
                    neighbours.add(model.getCell(x + dx, y));
                }
            } else if (dy != 0) {
                if (model.isWalkable(x - 1, y)) {
                    neighbours.add(model.getCell(x - 1, y));
                }
                
                if (model.isWalkable(x + 1, y)) {
                    neighbours.add(model.getCell(x + 1, y));
                }
                
                if (model.isWalkable(x, y + dy)) {
                    neighbours.add(model.getCell(x, y + dy));
                }
            }
        } else {
            // Once here, return all neighbours:
            neighbours.addAll(
                    new GridNodeExpander(model, 
                                         ps).expand(current));
        }
        
        return neighbours;
    }
}

Critique request

As always, I am eager to receive constructive commentary on my work. Especially, I would like some directions on how to code up a jumper and its neighbour finder for dealing with diagonal moves with crossing walls.