(Refer to the entire repository in GitHub.)
How it looks like
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.
