Bidirectional Search Playground

Two searches, one from each end. Change anything and see what it does to the meeting point.

0Expansions

Algorithm Moves Which side next Speed

Map

Width in cells

Random walls

Mud (cost 5)

Heuristic features

Forward open0

Backward open0

Heuristic weight w

Picks the node with lowest

Stops when

Output

∞Best path U

0Lower bound

∞Gap U − LB

0True shortest

Proof closing

Best path ULower bound

Frontier size

All algorithms on this map, nodes expanded

How to read it

Orange grows from the start and blue grows from the goal. Solid cells are the frontier, faded cells are finished. A dashed line appears when the frontiers first connect. It marks the best path found so far, which the search hasn't yet proved to be the shortest.

The search is finished when the best path U meets the lower bound in the Proof closing chart. Until then, a cheaper path could still exist.

Space play or pause, → step, ← step back, R reset. Draw on the grid to add walls, or drag the start and goal.

Try these

The algorithms

Algorithm	Picks lowest	Stops when	Good to know	Source

g is the cost so far, h the estimate of what remains, f = g + h, and ε = 1 is the cheapest edge on the grid. F and B mean forward and backward.