To find a route through a maze, start at one location and examine reachable locations one move away before moving farther out. Breadth-first search (BFS) explores the closest states first. In a small graph, this often makes it sufficient for finding a shortest path. section 2.2 section 2.4
public class Queue<T> {
private var container: [T] = [T]()
public var isEmpty: Bool { return container.isEmpty }
public func push(thing: T) { container.append(thing) }
public func pop() -> T { return container.removeFirst() }
}
The queue is the key change from depth-first search: new nodes go to the back, and the next node comes from the front. section 2.2
A generic Swift search needs an initial state, a goal test, and a function that returns successors:
- Put the initial state in the queue as a node with no parent, and add its state to an explored set. section 2.2
- Remove the front node. If it passes the goal test, return it. Otherwise, enqueue each unexplored successor, recording the current node as its parent and marking the successor explored. section 2.2
- Follow parent links backward from a returned goal node to recover the path. section 2.2
A four-way maze
Represent the maze as a grid of open and blocked cells. From each location, generate unblocked neighbors above, below, left, and right—never diagonally. A search from (0, 0) toward (9, 9) can then produce a path to mark and print on the grid. section 2.2
Depth-first search uses a stack instead and may follow one route deep before trying another. For a larger graph with a useful heuristic, A* is an alternative to BFS. section 2.2 section 2.4
