By David Kopec This article is all about finding a path through mazes, which is an analogous to many common search problems in computer science. Examples are in Swift. 
Save 37% off Classic Computer Science Problems in Swift with code fcckopec at manning.com.
Maze Solving
Finding a path through a maze is analogous to many common search problems in computer science. Why not literally find a path through a maze then, to illustrate the breadthfirst search, depthfirst search, and A* algorithms? Our maze is a twodimensional array of Cell
. A Cell
is an enum with raw Character
values where O
represents an empty space, but an X
represents a blocked space. Various other cases are for illustrative purposes when we print a maze.
// A Cell represents the status of a grid location in the maze enum Cell: Character { case Empty = "O" case Blocked = "X" case Start = "S" case Goal = "G" case Path = "P" } typealias Maze = [[Cell]]
Generating a Random Maze
The generated maze should be fairly sparse to ensure a path from a given starting node to a given ending node (this is for testing out our algorithms after all). We will let the caller of generateMaze()
decide on the exact sparseness
. When a random number beats the threshold of the sparseness parameter in question, we will replace an empty space with a wall. If we do this for every possible place in the maze, statistically the sparseness of the maze as a whole approximates the sparseness parameter that we supply.
srand48(time(nil)) // seed random number generator // sparseness is the approximate percentage of walls represented // as a number between 0 and 1 func generateMaze(rows: Int, columns: Int, sparseness: Double) > Maze { // initialize maze full of empty spaces var maze: Maze = Maze(repeating: [Cell](repeating: .Empty, count: columns), count: rows) // put walls in for row in 0..<rows { for col in 0..<columns { if drand48() < sparseness { //chance of wall maze[row][col] = .Blocked } } } return maze }
Now that we have a maze, we will also want a way to print it succinctly to the console. We want its characters to be close together to look like a real maze.
func printMaze(_ maze: Maze) { for i in 0..<maze.count { print(String(maze[i].map{ $0.rawValue })) } }
Go ahead and try testing out our maze functions.
var maze = generateMaze(rows: 10, columns: 10, sparseness: 0.2) printMaze(maze)
Miscellaneous Maze Minutiae
We will need a way to refer to an individual location in the maze. This could be a tuple of row and column, but later we will want to store a maze location in data structures that require their keys to be Hashable
. Instead, therefore, we will define a custom struct for maze locations (tuples don’t conform and can’t be made to conform to Hashable
). All Hashable
conforming types must also implement the ==
operator.
struct MazeLocation: Hashable { let row: Int let col: Int var hashValue: Int { return row.hashValue ^ col.hashValue } } func == (lhs: MazeLocation, rhs: MazeLocation) > Bool { return lhs.row == rhs.row && lhs.col == rhs.col }
It will come in handy later to have a function that checks whether we have reached our goal during the search. We want to check whether a particular MazeLocation
is the goal of our search. Arbitrarily, we will define the goal as always being at location 9, 9 for now.
let goal = MazeLocation(row: 9, col: 9) func goalTest(ml: MazeLocation) > Bool { return ml == goal }
How can one move within our mazes? Let’s say that one can move horizontally and vertically one space over atatime from a given space in the maze. Using this critieria, a successors()
function can find the possible next locations from a given MazeLocation
. The successors()
function differs for every Maze because every Maze has a different size and set of walls. Therefore, we will define a function successorsForMaze()
that returns an appropriate successors()
function for a Maze
in question.
func successorsForMaze(_ maze: Maze) > (MazeLocation) > [MazeLocation] { func successors(ml: MazeLocation) > [MazeLocation] { //no diagonals var newMLs: [MazeLocation] = [MazeLocation]() if (ml.row + 1 < maze.count) && (maze[ml.row + 1][ml.col] != .Blocked) { newMLs.append(MazeLocation(row: ml.row + 1, col: ml.col)) } if (ml.row  1 >= 0) && (maze[ml.row  1][ml.col] != .Blocked) { newMLs.append(MazeLocation(row: ml.row  1, col: ml.col)) } if (ml.col + 1 < maze[0].count) && (maze[ml.row][ml.col + 1] != .Blocked) { newMLs.append(MazeLocation(row: ml.row, col: ml.col + 1)) } if (ml.col  1 >= 0) && (maze[ml.row][ml.col  1] != .Blocked) { newMLs.append(MazeLocation(row: ml.row, col: ml.col  1)) } return newMLs } return successors }
successors()
checks above, below, to the right, and to the left of a MazeLocation
in a Maze
to see if it can find empty spaces that can be moved to from the current location. It does not check locations beyond the edges of the Maze
. Every possible MazeLocation
that it finds is put into an array which is ultimately returned to the caller.
DepthFirst Search
A depthfirst search is (DFS) what its name suggests — a search that goes as deeply as it can before backtracking to its last decision point if it reaches a deadend. We’ll implement a generic depthfirst search that can solve our maze problem. It will be reusable for other problems.
Figure 1: In depthfirstsearch, the search proceeds along a continuously deeper path until it hits a barrier and must backtrack to the last decision point.
Stacks
The depthfirst search algorithm relies on a data structure known as a stack. A stack is a data structure that operates under the acronym LIFO — last in, first out. Imagine a stack of papers. The last paper placed on top of the stack is the first paper pulled off of the stack. It is common for a stack to be implemented ontop of a more primitive data structure like a linkedlist. We will implement our stack on top of Swift’s Array
type.
Stacks generally have at least two operations:

push()
– places an item on top of the stack 
pop()
– removes the item on the top of the stack and returns it
We will implement both of them, in addition to a property to check, if the stack has any more items in it, isEmpty
(The examples in this chapter are based on prior code the author wrote for the open source project SwiftGraph).
public class Stack<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.removeLast() } }
Note that implementing a stack using a Swift Array
is as simple as always appending items onto its right end and always removing items from its extreme right end. The removeLast()
method on Array
fails if there are no longer any items in the array, and pop()
fails on a Stack
if it is empty.
The DFS Algorithm
We will need one more tidbit before we can get to implementing DFS. We need a class Node
which is used to keep track of how we got from one state to another state (or one place to another place) as we search. You can think about a Node
as a wrapper around a state. In the case of our maze solving problem, those states are of type MazeLocation
. We will call the Node
that a state came from its parent. We will also define our Node
class as having properties cost
and heuristic
and being Comparable
and Hashable
.
class Node<T>: Comparable, Hashable { let state: T let parent: Node? let cost: Float let heuristic: Float init(state: T, parent: Node?, cost: Float = 0.0, heuristic: Float = 0.0) { self.state = state self.parent = parent self.cost = cost self.heuristic = heuristic } var hashValue: Int { return (Int) (cost + heuristic) } } func < <T>(lhs: Node<T>, rhs: Node<T>) > Bool { return (lhs.cost + lhs.heuristic) < (rhs.cost + rhs.heuristic) } func == <T>(lhs: Node<T>, rhs: Node<T>) > Bool { return lhs === rhs }
An inprogress depthfirst search needs to keep track of two data structures: the stack of states (or “places”) that we consider searching, which we call “the frontier,” and the set of states that have already been searched, which we call “visited.” As long as there are more states to visit in the frontier, DFS keeps checking if they are the goal (if a state is the goal it stops and returns it) and adding their successors onto the frontier. It also marks each state that has already been searched as visited to prevent going in circles if it reaches states with prior visited states as successors. If the frontier is empty, it means there is nowhere left to search.
func dfs<StateType: Hashable>(initialState: StateType, goalTestFn: (StateType) > Bool, successorFn: (StateType) > [StateType]) > Node<StateType>? { // frontier is where we've yet to go let frontier: Stack<Node<StateType>> = Stack<Node<StateType>>() frontier.push(Node(state: initialState, parent: nil)) // explored is where we've been var explored: Set<StateType> = Set<StateType>() explored.insert(initialState) // keep going while there is more to explore while !frontier.isEmpty { let currentNode = frontier.pop() let currentState = currentNode.state // if we found the goal, we're done if goalTestFn(currentState) { return currentNode } // check where we can go next and haven't explored for child in successorFn(currentState) where !explored.contains(child) { explored.insert(child) frontier.push(Node(state: child, parent: currentNode)) } } return nil // never found the goal }
If dfs()
is successful, it returns the Node
encapsulating the goal state. The path from the start to the goal can be reconstructed by working backwards from this Node
and its priors using the parent property.
func nodeToPath<StateType>(_ node: Node<StateType>) > [StateType] { var path: [StateType] = [node.state] var currentNode = node.parent // work backwards from end to front while currentNode != nil { path.insert(currentNode!.state, atIndex: 0) currentNode = node.parent } return path }
For display purposes, it is useful to mark up our maze with the successful path, the start state, and the goal state.
func markMaze(_ maze: inout Maze, path: [MazeLocation], start: MazeLocation, goal: MazeLocation) { for ml in path { maze[ml.row][ml.col] = .Path } maze[start.row][start.col] = .Start maze[goal.row][goal.col] = .Goal }
It has been a long journey, but we are finally ready to solve our maze.
let start = MazeLocation(row: 0, col: 0) if let solution = dfs(initialState: start, goalTestFn: goalTest, successorFn: successorsForMaze(maze)) { let path = nodeToPath(solution) markMaze(&maze, path: path, start: start, goal: goal) printMaze(maze) }
A successful solution looks something like this:
SPXOOOOXOO OPPPPPPPPO XOOOOOOOPO OOOOXPPPPX OXXOXPXOXO OXPPPPOOOO PPPXXXOOOX POOOXOOOOX PPPPPPPPPP OOOXOOOOOG
Remember, because each maze is randomly generated, not every maze has a solution.
BreadthFirst Search
You may notice that the solution paths to our mazes found by depthfirst traversal seem unnatural. They are usually not the shortest paths. Breadfirst search (BFS) always finds the shortest path by systematically looking one layer of nodes further away from the start state each iteration of the search. Particular problems can be solved more quickly with a depthfirst search rather than a breadfirst search, and vice versa. Therefore, choosing between the two is a tradeoff between the possibility of finding a solution quickly and the certainty of finding the shortest path to the goal (if one exists).
Figure 2: In a breadthfirstsearch, the closest elements to the starting location are searched first.
To understand why a depthfirst search sometimes returns a result faster than a breadthfirst search, imagine looking for a marking on a particular layer of an onion. A searcher using a depthfirst strategy may plunge a knife into the center of the onion and haphazardly examine the chunks he cuts out. If the marked layer happens to be near the chunk cut out, there is a chance he will find it more quickly than another searcher using a breadthfirst strategy, who painstakingly peels back the onion, one layer at a time.
To get a better picture of why breadthfirst search always finds the shortest solution path where one exists, consider trying to find the path with the fewest number of stops between Boston and New York by train. If you keep going in the same direction and backtracking when you hit a deadend (as in depthfirst search) you may first find a route all the way to Seattle before it connects back to New York. In a breadthfirst search, you will first check each station one stop away from Boston. Then you will check each station two stops away from Boston. Then you will check each station three stops away from Boston. This keeps going until you find New York. Therefore, when you find New York, you will know you have found the route through the fewest stops, because you already checked all of the stations that are fewer stops away from Boston and none of them were New York.
Queues
To implement BFS a data structure known as a queue
is required. Although a stack is LIFO, a queue is FIFO — firstin, firstout. A queue is like a line to use a restroom. The first person who got on line goes to the restroom first. At a minimum, a queue has the same push()
and pop()
methods as a stack. In fact, our implementation for Queue
(backed by a Swift Array
) is almost identical to our implementation of Stack
, with the only change being removal of elements from the left end of the Array
instead of the right end. The elements on the left end are the oldest elements (in terms of arrival time) still in the Array
, therefore they are the first elements.
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 BFS Algorithm
Amazingly, the algorithm for breadthfirst search is identical to the algorithm for depthfirst search with the frontier changed from a stack to a queue. Changing the frontier from a stack to a queue changes the order in which states are searched and ensures the states closest to the start state are searched first.
func bfs<StateType: Hashable>(initialState: StateType, goalTestFn: (StateType) > Bool, successorFn: (StateType) > [StateType]) > Node<StateType>? { // frontier is where we've yet to go let frontier: Queue<Node<StateType>> = Queue<Node<StateType>>() frontier.push(Node(state: initialState, parent: nil)) // explored is where we've been var explored: Set<StateType> = Set<StateType>() explored.insert(initialState) // keep going while there is more to explore while !frontier.isEmpty { let currentNode = frontier.pop() let currentState = currentNode.state // if we found the goal, we're done if goalTestFn(currentState) { return currentNode } // check where we can go next and haven't explored for child in successorFn(currentState) where !explored.contains(child) { explored.insert(child) frontier.push(Node(state: child, parent: currentNode)) } } return nil // never found the goal }
If you try running bfs()
you’ll find it always finds the shortest solution to the maze in question.
var maze2 = generateMaze(rows: 10, columns: 10, sparseness: 0.2) if let solution = bfs(initialState: start, goalTestFn: goalTest, successorFn: successorsForMaze(maze2)) { let path = nodeToPath(solution) markMaze(&maze2, path: path, start: start, goal: goal) printMaze(maze2) }
If you’re interested in using Swift with the A* algorithm, see this presentation on Slideshare.net.
For now though, that’s all for maze solving techniques using Swift. For more on using Swift to solve some of the classic problems in computer science, download the free second chapter of Classic Computer Science Problems in Swift.