Breadth-first search algorithm applied to Swift mobile game development

[51CTO.com Quick Translation] Swift Algorithm Club (https://github.com/raywenderlich/swift-algorithm-club) is an open source project whose purpose is to implement some commonly used algorithms and data structures using the Swift language.

Every month, the SAC team will publish a cool data structure or algorithm in the form of a tutorial on the website www.raywenderlich.com. So if you want to learn more about algorithms and data structures implemented in Swift, you can always keep an eye on this website.

In this tutorial, you will learn a classic search and pathfinding algorithm, the breadth-first search algorithm.

The breadth-first search algorithm was originally implemented by Chris Pilcher (https://github.com/chris-pilcher). In this tutorial, we will refactor its implementation slightly as needed.

This tutorial assumes that you already know the adjacency list algorithm (https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list) and the queue algorithm (https://www.raywenderlich.com/148141/swift-algorithm-club-swift-queue-data-structure) in graph theory based on Swift language, or have similar basic knowledge.

Note, if you are interested in the Swift Algorithm Club and are new to it, you can visit this address https://www.raywenderlich.com/135533/join-swift-algorithm-club.

getting Started

In Swift Graph Adjacency List Algorithm (https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list), we proposed a method to describe objects in a graph and their relationships. In a graph, each object is represented as a vertex and each relationship is represented as an edge.

For example, a maze can be described as a graph. Each junction in the maze can be described by a vertex, and each passage between junctions can be described by an edge.

Breadth-first search was discovered by EF Moore in 1950. This algorithm is not just for finding a path through a maze, but for finding the shortest path through a maze. The idea behind this breadth-first search algorithm is quite simple:

• Search every position corresponding to a set of moves around a source point.
• Then, modify this number in incremental steps until you find your destination.

Next, let's analyze a specific example.

Example

Suppose you are at the entrance of a maze, please refer to the picture below.

The breadth-first search algorithm works as follows:

1. Search your current location. If this is your destination, stop searching.

2. Search for neighboring locations of your location. If any of them is the destination, stop searching.

3. Search all neighboring locations of these locations. If any of them is the destination, stop searching.

4. Finally, if there is a route to the destination, a path is found and the path is stored with the minimum number of steps from the origin. If you have run out of positions to search, there is no path to the destination.

[Note] For the breadth-first search algorithm, the shortest path refers to the minimum number of steps required to get from one location to the next.

In the maze example we provided, the breadth-first search algorithm assumes that all passages between rooms in the maze are of the same length, although this may not be true in practice. You can think of the shortest path through a maze as a list of the shortest directions, rather than the shortest distances.

In future tutorials we will explore shortest distance path finding algorithms.

Swift Breadth-First Search Algorithm

From now on, let’s analyze the breadth-first search algorithm implemented in Swift.

To do this, please first download the original source code of this tutorial (https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Start.playground.zip), which provides the data structures of adjacency list and queue implemented in Swift language.

[Note] If you want to understand how the adjacency list and queue data structures implemented in Swift work, you can use the command View\Navigators\Show Project Navigator to analyze the relevant code. You can also learn how to build these adjacency lists and queues in Swift.

First, we define a protocol called Graphable; all graph data structures must conform to this protocol. Then, we extend this protocol; this way, we can apply breadth-first search to all graph types.

Here is what the Graphable protocol looks like:

 public protocol Graphable {
  associated type Element: Hashable
  var description: CustomStringConvertible { get } 
  
  func createVertex(data: Element) -> Vertex<Element>
  func add (_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double ?)
  func weight( from source: Vertex<Element>, to destination: Vertex<Element>) -> Double ?
  func edges( from source: Vertex<Element>) -> [Edge<Element>]?
 }

Create our extension at the top of the initial sample project downloaded above (after the statement import XCPlayground):

 extension Graphable {
 public func breadthFirstSearch( from source: Vertex<Element>, to destination: Vertex<Element>)
 -> [Edge<Element>]? { 
  
 }
 }

Let's summarize this function signature:

• A function is declared that takes two vertex parameters: the first is the source vertex, which is our starting point; the second is the destination vertex, which is our destination. This function returns a route (starting from the source vertex to the destination position) in the form of edge objects.
• If a route exists, we also expect it to be stored in sorted order! The first edge in the route will start at a source vertex, and the last edge in the route will end at a destination vertex. For each pair of adjacent edges in the route, the destination of the first edge will be the same vertex as the source of the second edge.
• If the source and destination points are the same, the route is an empty array.
• If the route does not exist, the function should return nil.

Breadth-first search relies on visiting vertices in the correct order. The first vertex to be visited always corresponds to the source vertex. After that, we analyze the source's neighbors; then, and so on. As we visit a vertex, we add its node to the back of the queue.

Since we already know about queues, we can use it here!

So, we can update the above function to the following:

 public func breadthFirstSearch( from source: Vertex<Element>, to destination: Vertex<Element>)
 -> [Edge<Element>]? { 
  
 var queue = Queue<Vertex<Element>>()
 queue.enqueue(source) // 1 
  
  while let visitedVertex = queue.dequeue() { // 2
    if visitedVertex == destination { // 3
 return []
 }
 // TODO...
 }
 return nil // 4 
  
 }

Next, let's analyze the above code step by step:

1. First, create a vertex queue and add the source point to the queue.

2. Dequeue a vertex from the queue (as long as the queue is not empty) and call it a visited vertex.

3. In the first iteration, the visited vertex will be the source, and the queue will be empty immediately. However, if visiting the source vertex adds more nodes, the search will continue.

4. Check if the visited vertex is the target vertex. If so, end the search immediately. In the current case, you will return an empty list - which is the same as when the target node is found. Then, a more detailed path will be constructed.

5. If the queue is empty, nil is returned. This means that the target node is not found; there may not be a path to it.

Next, we need to add all neighbor nodes of the visited node to the queue. To do this, we can use the following code:

 let neighborEdges = edges( from : visitedVertex) ?? [] // 1
 for edge in neighbourEdges {
  queue.enqueue(edge.destination)
 } // 2

Let us do a detailed analysis:

1. Here we use the edges(from:) function of the Graphable protocol to get the edge array of the visited node. Remember, the edges(from:) function returns an optional edge array. This means that if this array is empty or nil, there is no edge starting from this node.

Since (for our search purposes) an empty list means the same thing as nil - no neighbors to enqueue; therefore, we use an empty list to nil-aggregate the optional array, thus removing the optional functionality.

2. Now you can safely iterate over the edge list with a for loop, enqueuing the target node of each edge.

At this point, our task is not completely completed. In fact, there is a subtle danger in this search algorithm! What problems will you encounter if you run the search algorithm in this example? At this point, we can ignore the fact that the treasure room is not connected to the graph.

We might as well manually figure out what will happen each time we visit a vertex.

What problem would you encounter if you ran the search algorithm on this example? Here is the answer:

1. The breadth-first search algorithm will create a queue and put the entrance room into the queue.

2. When we first enter the while loop, we dequeue the entrance room and visit it. There is no treasure in the entrance room, so we can search all the neighboring rooms of the entrance room. The entrance room has one neighbor room, the spider room. So, we queue it.

3. When we enter the while loop for the second time, we dequeue the spider room and visit it. Since there is no treasure in the spider room, we further search all the neighboring rooms of the spider room. The spider room has a neighbor room, which is the entrance room, so we queue it.

4. When entering the while loop for the third time, we dequeue the entrance room...

The problem is: we’ve been to this position before!

To fix this, we need to keep track of which vertices we have visited so that we can make sure we don't visit them a second time.

There are several ways to solve this problem. You can update your code like this:

 public func breadthFirstSearch( from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? {
  var queue = Queue<Vertex<Element>>()
 queue.enqueue(source)
  var enqueuedVertices = Set <Vertex<Element>>() // 1 
  
  while let visitedVertex = queue.dequeue() {
    if visitedVertex == destination {
 return []
 }
   let neighborEdges = edges( from : visitedVertex) ?? []
 for edge in neighbourEdges {
      if !enqueuedVertices. contains (edge.destination) { // 2
        enqueuedVertices. insert (visitedVertex) // 3
        queue.enqueue(edge.destination)
 }
 }
 }
 return nil
 }

Let's review what has changed:

1. The above code will create a vertex array that describes the list of vertices you have encountered so far. Remember that the Vertex type is Hashable, so we don't need to do any more work to build a vertex set.

2. Whenever checking an adjacent vertex, first check whether the node has been encountered before.

3. If you have not encountered the node before, add it to two queues: the list of vertices to be processed (queue structure) and the list of vertices encountered (enqueuedVertices).

This means that the search algorithm above is fairly safe. However, you cannot yet visit more vertices in the graph than the one you started with, so the search must eventually terminate.

Discovery loop

Our algorithm is almost there!

By now, you know that if you can't find your destination, you get a nil value back. However, if you do find your destination, you need to find your way back. Unfortunately, every room you visit is dequeued, leaving no record of how to find your destination!

To keep track of your searches, you need to replace the set of vertices you searched with a dictionary structure that contains all the vertices you searched for and how you got there. Think of this as exploring a maze, with a chalk marker with arrows pointing to all the rooms you've explored - this way you remember all the information you need to get to the entrance.

If we keep track of all the arrows - for any room we visit, we can just look for the edge we followed to get to it. This edge will lead back to the room we visited earlier. Of course, we can also look for the edge we followed to get to it, and so on... until we get to the edge at the beginning.

Let’s try this idea out by creating the following Visit enumeration type. Note that you must create this type outside of the Graphable extension because Swift 3 does not support nested generic types.

 enum Visit<Element: Hashable> {
 case source
 case edge(Edge<Element>)
 }

In our lookup table, every item in the first column is a vertex, but not every item in the second column is an edge; a vertex is always the source vertex; otherwise, something would go terribly wrong and we would never get out of the graph!

Next, modify your method as follows:

 public func breadthFirstSearch( from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? {
  var queue = Queue<Vertex<Element>>()
 queue.enqueue(source)
  var visits : [Vertex<Element> : Visit<Element>] = [source: .source] // 1 
  
  while let visitedVertex = queue.dequeue() {
 // TODO: Replace this...
    if visitedVertex == destination {
 return []
 }
    let neighborEdges = edges( from : visitedVertex) ?? []
 for edge in neighbourEdges {
      if visits[edge.destination] == nil { // 2
        queue.enqueue(edge.destination)
        visits[edge.destination] = .edge(edge) // 3
 }
 }
 }
 return nil
 }

Let's review what has changed in the above code:

1. This creates a dictionary with keys of Vertex and values ​​of Visit and initializes it with the source vertex as the visit from the “source point”.

2. If there is no entry corresponding to a vertex in the dictionary, it means that this vertex has not been added to the queue.

3. Every time you enqueue a vertex, you don't just put it into a set of vertices, you also record the edges that reach it.

***, you can backtrack from the target to the entry point! And update the if statement with the actual code in the TODO comment:

 if visitedVertex == destination {
  var vertex = destination // 1
  var route : [Edge<Element>] = [] // 2 
  
  while let visit = visits[vertex],
 case .edge(let edge) = visit { // 3 
  
 route = [edge] + route
 vertex = edge.source // 4 
  
 }
 return route // 5
 }

Let's analyze the above code:

1. First, create a new variable to store each vertex that is part of the route.

2.Also create a variable to store the route.

3. Create a while loop; this loop will continue as long as the access dictionary has a vertex entry and as long as this entry is an edge. If the entry is a source vertex, the while loop will end.

4. Add an edge to the beginning of your route and set the vertex as the source of the edge. Now you are one step closer to where you started.

5.The while loop ends; so, your route must now also be completed.

[[185897]]

So far, we have solved all the problems! You can add the following code at the end of the sample project file to test it:

 if let edges = dungeon.breadthFirstSearch( from : entranceRoom, to : treasureRoom) {
 for edge in edges {
    print( "\(edge.source) -> \(edge.destination)" )
 }
 }

Accordingly, you should observe the following output on the console:

 Entrance -> Rat 
 
 Rat -> Treasure

summary

I sincerely hope that you will enjoy this tutorial on breadth-first search in Swift!

In this tutorial, we've extended the behavior of all Graphable data types so that you can search for a route from any vertex to any other vertex. Even better, you get the route that has the fewest number of steps.

You can download the improved example project source code containing all the above code from https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Final.playground.zip. You can also find the original implementation code of the original breadth-first search algorithm in the Swift Algorithm Club repository and participate in further discussions.

In fact, this algorithm is just a small part of the Swift Algorithm Club repository. Interested readers can further consult these code libraries (https://github.com/raywenderlich/swift-algorithm-club).

[Translated by 51CTO. Please indicate the original translator and source as 51CTO.com when reprinting on partner sites]