 |
From Classic Computer Science Problems in Swift 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% on Classic Computer Science Problems in Swift. Just enter code fcckopec into the discount code box at checkout 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 breadth-first search, depth-first search, and A* algorithms? Our maze is a two-dimensional 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 at-a-time 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.
Depth-First Search
A depth-first 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 dead-end. We’ll implement a generic depth-first search that can solve our maze problem. It will be reusable for other problems.
Figure 1: In depth-first-search, the search proceeds along a continuously deeper path until it hits a barrier and must backtrack to the last decision point.
Stacks
The depth-first 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 on-top of a more primitive data structure like a linked-list. 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 in-progress depth-first 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.
Breadth-First Search
You may notice that the solution paths to our mazes found by depth-first traversal seem unnatural. They are usually not the shortest paths. Bread-first 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 depth-first search rather than a bread-first search, and vice versa. Therefore, choosing between the two is a trade-off 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 breadth-first-search, the closest elements to the starting location are searched first.
To understand why a depth-first search sometimes returns a result faster than a breadth-first search, imagine looking for a marking on a particular layer of an onion. A searcher using a depth-first 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 breadth-first strategy, who painstakingly peels back the onion, one layer at a time.
To get a better picture of why breadth-first 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 dead-end (as in depth-first search) you may first find a route all the way to Seattle before it connects back to New York. In a breadth-first 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 — first-in, first-out. 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 breadth-first search is identical to the algorithm for depth-first 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.