PathFinding.java: Beam search in Java

Question

Intro

I am currently working on this project (PathFinding.java). This time, I need to get the following class reviewed:

Code

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

package io.github.coderodde.pathfinding.finders;
import static io.github.coderodde.pathfinding.finders.Finder.searchSleep;
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.model.GridModel;
import io.github.coderodde.pathfinding.utils.Cell;
import io.github.coderodde.pathfinding.utils.CellType;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
 *
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 5, 2025)
 * @since 1.0.0 (Sep 5, 2025)
 */
public final class BeamSearchFinder implements Finder {
 @Override
 public List<Cell> findPath(GridModel model,
 GridCellNeighbourIterable neighbourIterable, 
 PathfindingSettings pathfindingSettings, 
 SearchState searchState) {
 Map<Cell, Cell> parents = new HashMap<>();
 Deque<Cell> queue = new ArrayDeque<>();
 
 Cell source = model.getSourceGridCell();
 Cell target = model.getTargetGridCell();
 
 parents.put(source, null);
 queue.addLast(source);
 
 while (!queue.isEmpty()) {
 if (searchState.haltRequested()) {
 return List.of();
 }
 
 if (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 continue;
 }
 
 if (queue.size() > pathfindingSettings.getBeamWidth()) {
 List<Cell> layer = new ArrayList<>(queue);
 HeuristicFunction hf = 
 pathfindingSettings.getHeuristicFunction();
 
 layer.sort((a, b) -> {
 return Double.compare(hf.estimate(a, target),
 hf.estimate(b, target));
 });
 
 for (Cell cell : queue) {
 model.setCellType(cell, CellType.FREE);
 }
 
 queue.clear();
 queue.addAll(
 layer.subList(
 0,
 Math.min(layer.size(),
 pathfindingSettings.getBeamWidth())));
 
 for (Cell cell : layer) {
 model.setCellType(cell, CellType.OPENED);
 }
 }
 
 Cell current = queue.removeFirst();
 
 if (current.equals(target)) {
 return tracebackPath(target, parents);
 }
 
 if (!current.equals(source)) {
 model.setCellType(current, CellType.VISITED);
 }
 
 neighbourIterable.setStartingCell(current);
 
 for (Cell neighbour : neighbourIterable) {
 if (searchState.haltRequested()) {
 return List.of();
 }
 
 while (searchState.pauseRequested()) {
 searchSleep(pathfindingSettings);
 }
 
 searchSleep(pathfindingSettings);
 
 if (parents.containsKey(neighbour)) {
 continue;
 }
 
 if (!neighbour.equals(target)) {
 model.setCellType(neighbour, CellType.OPENED);
 }
 
 parents.put(neighbour, current);
 queue.addLast(neighbour);
 }
 }
 
 return List.of();
 }
}

Possible output

Beam search found an optimal path

Warning

If you decide to clone or fork the above repository, note that it will require some tweaking with Maven: in order to run the app, go to the root directory of the repository and run mvn clean javafx:run. Also, after the first search run, the UI may fail.

Critique request

I am eager to hear any constructive commentary. However, my first concern is whether I got the algorithm right. Especially, I am wondering whether the following part

if (queue.size() > pathfindingSettings.getBeamWidth()) {
 List<Cell> layer = new ArrayList<>(queue);
 HeuristicFunction hf = 
 pathfindingSettings.getHeuristicFunction();
 
 layer.sort((a, b) -> {
 return Double.compare(hf.estimate(a, target),
 hf.estimate(b, target));
 });
 
 for (Cell cell : queue) {
 model.setCellType(cell, CellType.FREE);
 }
 
 queue.clear();
 queue.addAll(
 layer.subList(0,
 Math.min(layer.size(),
 pathfindingSettings.getBeamWidth())));
 
 for (Cell cell : layer) {
 model.setCellType(cell, CellType.OPENED);
 }
}
 

can be optimized efficiency-wise.

• greybeard: (I'd appreciate an example where the path found by beam search is not the shortest one.)

Answer 1

Naming:
Map<Cell, Cell> parents fine
Deque<Cell> queue 2nd rate: reminds me of what I can do with it, instead of why what's in it is there - toDo? open? opened?

Seeing FIFO does not get used with queue/open, make it a List<Cell> and avoid moving to layer and fro.

Regarding the snippet, one obviously small improvement would be to set all of layer.subList(beamWidth, layer.size()) to FREE, and all of the newly populated queue to OPENED.
(Is it even intended to set all of layer to OPENED? Wouldn't that undo all the setting to FREE?)

To add to user293216's idea to use an ordered Set to avoid ordering over&again:
Implement a size-limited MultiPriorityQueue.
This should keep the number of comparisons low and highlight the relation to Dijkstra's Shortest Path: size limit vs. none, evaluating all neighbours vs. always the highest priority node.

I don't see CellType used (assuming use in visualisation).