Grid Algorithms· 25 min

A* Search

Dijkstra + heuristic — fastest pathfinding

Setup

0 walls · 15×30 grid
Long straight corridors with single gaps. Clean, structured, easy to follow.
Step 1 / 88

Current step

1 / 88

Initialize A* Search. Start=7,4, End=7,25.

Step log

Tip: pick a tool, then click or drag on the grid. Walls block the path; start and end are draggable. Hit Generate maze for a structured layout.

Start
End
Wall
Visited
Frontier
Current
Path
astar.java
1List<Cell> astar(Cell[][] grid, Cell start, Cell end) {
2    Map<Cell, Integer> g = new HashMap<>(Map.of(start, 0));
3    Map<Cell, Integer> f = new HashMap<>(Map.of(start, h(start, end)));
4    PriorityQueue<Cell> pq = new PriorityQueue<>(Comparator.comparingInt(f::get));
5    pq.add(start);
6    Map<Cell, Cell> parent = new HashMap<>();
7    while (!pq.isEmpty()) {
8        Cell cur = pq.poll();
9        if (cur.equals(end)) return reconstruct(parent, end);
10        for (Cell n : neighbors(cur)) {
11            int ng = g.get(cur) + 1;
12            if (ng < g.getOrDefault(n, Integer.MAX_VALUE)) {
13                parent.put(n, cur); g.put(n, ng);
14                f.put(n, ng + h(n, end)); pq.add(n);
15            }
16        }
17    }
18    return null;
19}
● Java

A* Search

Combines Dijkstra's actual distance with a heuristic (Manhattan distance to end) to guide the search toward the target. Optimal and typically faster than Dijkstra.

Time
O(E log V)
Visited
0
Frontier
1
Path length
0
31 / 46