Skip to content
Algorithm Atlas
Back to Benchmarks

Benchmark Family

Pathfinding

Deterministic 4-neighbor grid benchmarks across obstacles, weighted terrain, no-path cases, and start/goal patterns.

Generated

Apr 28, 2026, 12:07 PM

Measured

108

Skipped

12

Failures

0

Algorithms

5

Grid profiles

8

How to Read These Results

Benchmarks measure specific local JavaScript implementations on deterministic inputs. Results depend on runtime, hardware, implementation details, and input shape. They are not universal algorithm rankings.

BFS-style methods skip weighted grids; greedy best-first search is validated for path validity but is not treated as optimal.

Contextual results

Algorithms Tested

Readable implementations included in this run

BFS Grid

Unweighted

Breadth-first search on unweighted 4-neighbor grids.

Dijkstra Grid

Nonnegative Weights

Dijkstra shortest path on nonnegative 4-neighbor grid costs.

A* Grid

Admissible Heuristic

A* grid search with Manhattan distance scaled by minimum traversal cost.

Greedy Best-First Grid

Heuristic Nonoptimal

Greedy best-first grid search using Manhattan distance; not guaranteed optimal.

Bidirectional BFS Grid

Unweighted

Bidirectional breadth-first search on unweighted 4-neighbor grids.

Grid profiles

Fixture coverage in this family

Empty GridRandom ObstaclesMaze CorridorsNarrow PassageWeighted TerrainWeighted ObstaclesBlocked No PathStart Near Goal

Start/goal patterns

Fixture coverage in this family

Corner To CornerEdge To EdgeCenter To CornerNear

Summary Findings

Careful takeaways from the generated benchmark data

  • BFS and bidirectional BFS skip weighted grids because unweighted traversal is not cost-optimal there.
  • Dijkstra and A* are checked for optimality where nonnegative weights and admissible heuristics apply.
  • Greedy Best-First Search is validated for path validity but is not required to return an optimal path.

Chart Previews

Static previews from the existing chart-ready benchmark exports. These charts are read-only summaries, not live benchmark execution or universal rankings.

Runtime on Random Obstacles

Median runtime by grid size for compatible algorithms on deterministic unweighted obstacle grids.

median ms
0 ms0.54 ms1.08 ms2050100BFS: 0.01 ms at 20BFS: 0.061 ms at 50BFS: 0.279 ms at 100Bidirectional BFS: 0.009 ms at 20Bidirectional BFS: 0.065 ms at 50Bidirectional BFS: 0.297 ms at 100Dijkstra: 0.017 ms at 20Dijkstra: 0.137 ms at 50Dijkstra: 0.762 ms at 100A*: 0.009 ms at 20A*: 0.042 ms at 50A*: 0.299 ms at 100Greedy Best-First: 0.01 ms at 20Greedy Best-First: 0.03 ms at 50Greedy Best-First: 0.038 ms at 100grid widthmedian ms
BFS
Bidirectional BFS
Dijkstra
A*
Greedy Best-First

5 series, 15 plotted points. Unit: median ms.

BFS-style methods are included here because this fixture is unweighted.

Nodes Expanded on Random Obstacles

Search effort by grid size for the same deterministic obstacle fixture.

nodes expanded
04,0538,1062050100BFS: 306 at 20BFS: 1,909 at 50BFS: 7,505 at 100Bidirectional BFS: 245 at 20Bidirectional BFS: 1,705 at 50Bidirectional BFS: 6,778 at 100Dijkstra: 306 at 20Dijkstra: 1,909 at 50Dijkstra: 7,506 at 100A*: 106 at 20A*: 476 at 50A*: 2,407 at 100Greedy Best-First: 39 at 20Greedy Best-First: 99 at 50Greedy Best-First: 199 at 100grid widthnodes expanded
BFS
Bidirectional BFS
Dijkstra
A*
Greedy Best-First

5 series, 15 plotted points. Unit: nodes expanded.

Greedy Best-First may expand fewer nodes but is not guaranteed to return optimal paths.

Optimality Ratio on Weighted Terrain

Path cost divided by optimal cost on weighted terrain. A ratio of 1.0 matches the validated optimum.

optimality ratio
00.9771.9552050100Dijkstra: 1 at 20Dijkstra: 1 at 50Dijkstra: 1 at 100A*: 1 at 20A*: 1 at 50A*: 1 at 100Greedy Best-First: 1.541 at 20Greedy Best-First: 1.681 at 50Greedy Best-First: 1.81 at 100grid widthcost / optimal
Dijkstra
A*
Greedy Best-First

3 series, 9 plotted points. Unit: optimality ratio.

A* and Dijkstra are checked against optimal cost; Greedy Best-First is only a heuristic baseline.

No-Path Effort

Nodes expanded when the blocked fixture has no valid route from start to goal.

nodes expanded
03,3086,6152050100BFS: 200 at 20BFS: 1,250 at 50BFS: 5,000 at 100Bidirectional BFS: 225 at 20Bidirectional BFS: 1,500 at 50Bidirectional BFS: 6,125 at 100Dijkstra: 200 at 20Dijkstra: 1,250 at 50Dijkstra: 5,000 at 100A*: 200 at 20A*: 1,250 at 50A*: 5,000 at 100Greedy Best-First: 200 at 20Greedy Best-First: 1,250 at 50Greedy Best-First: 5,000 at 100grid widthnodes expanded
BFS
Bidirectional BFS
Dijkstra
A*
Greedy Best-First

5 series, 15 plotted points. Unit: nodes expanded.

No-path cases require proving disconnection or exhausting reachable search space.

Path Overlay Previews

Small 20x20 fixtures show how different pathfinding implementations move through the same grid. These are precomputed benchmark artifacts, not live browser execution.

Precomputed overlays

Compare Overlays

Each card uses the same selected implementation when overlay data is available.

Start
Goal
Path
Blocked
Heavier terrain

Profiles shown

8

Selected

A*

Compatible

8

No-path fixtures

1

BFS and Bidirectional BFS skip weighted grid overlays.

Dijkstra and A* are optimal under the tested nonnegative-weight conditions.

Greedy Best-First may return valid but non-optimal paths.

Blocked No Path

20x20 fixture

UnweightedNo path expected

Status

No path

Path cost

n/a

Optimal cost

n/a

Optimality

n/a

Nodes expanded

200

Edges relaxed

740

Frontier max

67

Empty Grid

20x20 fixture

UnweightedPath expected

Status

Path found

Path cost

38

Optimal cost

38

Optimality

1

Nodes expanded

76

Edges relaxed

258

Frontier max

36

Maze Corridors

20x20 fixture

UnweightedPath expected

Status

Path found

Path cost

38

Optimal cost

38

Optimality

1

Nodes expanded

39

Edges relaxed

84

Frontier max

10

Narrow Passage

20x20 fixture

UnweightedPath expected

Status

Path found

Path cost

19

Optimal cost

19

Optimality

1

Nodes expanded

20

Edges relaxed

39

Frontier max

3

Random Obstacles

20x20 fixture

UnweightedPath expected

Status

Path found

Path cost

38

Optimal cost

38

Optimality

1

Nodes expanded

106

Edges relaxed

335

Frontier max

38

Start Near Goal

20x20 fixture

UnweightedPath expected

Status

Path found

Path cost

2

Optimal cost

2

Optimality

1

Nodes expanded

3

Edges relaxed

8

Frontier max

6

Weighted Obstacles

20x20 fixture

WeightedPath expected

Status

Path found

Path cost

162

Optimal cost

162

Optimality

1

Nodes expanded

322

Edges relaxed

990

Frontier max

23

Weighted Terrain

20x20 fixture

WeightedPath expected

Status

Path found

Path cost

61

Optimal cost

61

Optimality

1

Nodes expanded

261

Edges relaxed

1,011

Frontier max

58

These overlays are compact previews from 20x20 fixtures. They are meant to explain benchmark behavior, not replace the full benchmark report.

Best by Scenario

Scenario labels are local benchmark summaries, not universal recommendations.

ScenarioAlgorithmDetail
Fastest optimal unweightedBFS GridLowest average rank among compatible optimal unweighted cases.
Fastest optimal weightedDijkstra GridLowest average rank among compatible weighted optimal cases.
Fastest heuristicGreedy Best-First GridLowest average rank in the heuristic pathfinding group; not an optimality claim.
Fewest median nodes expandedGreedy Best-First GridMedian nodes expanded: 99.
Best path qualityDijkstra Grid0 non-optimal paths; worst ratio 1.
No Path fastestBFS Gridblocked-no-path 20x20.
Safest general optimal baselineDijkstra GridRuns on unweighted and nonnegative weighted grids in this suite, with optimality validation.

Path Quality Summary

Optimality is checked where an optimal cost is available; greedy behavior is called out separately.

AlgorithmPath casesOptimalNon-optimalWorst ratio
BFS Grid151501
Dijkstra Grid212101
A* Grid212101
Greedy Best-First Grid211561.81
Bidirectional BFS Grid151501

Search Effort Summary

Search effort metrics are local implementation measurements for the generated fixtures.

AlgorithmMedian nodesMedian edgesFrontier maxNode ratio
BFS Grid3531,104.517.50.389
Dijkstra Grid535.51,513.529.50.626
A* Grid199.5709540.19
Greedy Best-First Grid99209340.04
Bidirectional BFS Grid298774.525.50.364

Greedy Non-Optimal Callouts

These cases show valid paths where the heuristic baseline did not match the optimal cost.

ProfileSizePath costOptimalRatio
Weighted Terrain100x1005342951.81
Weighted Terrain50x502371411.681
Weighted Terrain20x2094611.541
Weighted Obstacles100x1001,0138701.164
Weighted Obstacles20x201851621.142
Weighted Obstacles50x504844391.103

Profile notes

Context for interpreting this family

  • Empty Grid: Manhattan distance is strongly aligned with the goal direction on open 4-neighbor grids, so heuristic-guided searches often reduce exploration.
  • Random Obstacles: Deterministic obstacles can either reduce reachable branching or force detours; these fixtures include a carved valid route.
  • Maze Corridors: Corridor-like layouts reduce branching but can make direct Manhattan guidance less informative when the route bends through passages.
  • Narrow Passage: Very low branching makes broad unweighted traversal competitive because there are few alternatives to explore.
  • Weighted Terrain: Dijkstra and A* optimize traversal cost; Greedy Best-First can choose visually direct paths that are more expensive.
  • Weighted Obstacles: Obstacle constraints and cell weights interact, so fewer expanded nodes do not necessarily imply an optimal-cost path.
  • Blocked No Path: Correct algorithms must prove disconnection by exhausting the relevant reachable region rather than returning an invalid path.
  • Start Near Goal: The path is so short that setup and data-structure overhead can dominate measured runtime differences.

Outputs

Generated benchmark artifacts used by this public page

pathfinding-baseline.jsonpathfinding-baseline-summary.jsonpathfinding-baseline.mdpathfinding-baseline.csvpathfinding-chart-data.jsonpathfinding-path-overlays.json

Limitations

Scope boundaries for this benchmark family

  • Synthetic square grid fixtures only.
  • Four-neighbor movement only.
  • Destination-cell traversal cost is used for weighted grids.
  • Greedy Best-First Search is not required to be optimal.
  • Memory usage and browser-runtime behavior are not measured.