Separate frontier, discovered cells and parents

“Visited” is often used for several different moments. In this course we name them precisely. Discovered means a cell has entered the search and received its first parent. Frontier means discovered work waiting to be expanded. Expanded means we removed the cell and inspected its outgoing moves.

The visualizer uses D for discovered, F for frontier and E for expanded, plus text descriptions. Frontier cells are discovered but not yet expanded. The reconstructed path is a separate result.

Initialize only the start. It enters the frontier, discovered set and parent map, with parent None. Expanded is empty. The goal is a target, not proof of a route. Both endpoints must be in bounds and walkable.

Using tuples for normalized coordinates makes them suitable dict keys and set members. Keep the caller’s list inputs unchanged.

start, goal = (0,0), (1,1)
state = {"frontier":[start], "discovered":{start}, "expanded":[], "parents":{start:None}, "goal":goal}
print("scheduled", state["frontier"])
print("root", state["parents"][start])
print("expanded", state["expanded"])

Mark on discovery, when adding to the frontier. Waiting until removal allows two different predecessors to schedule the same neighbor before either copy is expanded. That creates duplicate work and can overwrite the useful first-parent relationship.

The discovered set and parent-map keys represent the same membership in our algorithm, but their responsibilities differ: the set is a scheduling guard and the map carries an edge. Tests keep them consistent. The trace uses parent insertion order to report discoveries deterministically; it never relies on set iteration order.

Each initial_state call must return fresh mutable containers. Otherwise replaying one search could inherit work or parents from another.

def ready(start):
    return {"frontier":[start], "parents":{start:None}}
a, b = ready((0,0)), ready((0,0))
a["frontier"].clear()
print(a["frontier"], b["frontier"])
print(a["parents"] == b["parents"])

Implement the ready state, then mutate one returned container in a test and prove a second search remains intact. Start equal to goal is still a valid initial state: the algorithm will expand it once and return a one-cell path.

Next we choose which frontier item to remove. A queue gives breadth-first search; a stack gives depth-first search.