PathFinder/MazeBuilder.swift
/* |
Copyright (C) 2016 Apple Inc. All Rights Reserved. |
See LICENSE.txt for this sample’s licensing information |
Abstract: |
Handles random generation for a Maze object. |
*/ |
import GameplayKit |
class MazeBuilder { |
// MARK: Types |
/** |
An enum for the cardinal directions. This enables you to randomly |
generate a direction with a random number generator. |
*/ |
enum Direction: Int { |
case left = 0, down, right, up |
/// Generates a random direction. |
static func random() -> Direction { |
/* |
Generate a random number from 0-3, and return a corresponing |
Direction enum. |
*/ |
let randomInt = GKRandomSource.sharedRandom().nextInt(upperBound: 4) |
return Direction(rawValue: randomInt)! |
} |
// The offset value for the x-axis associated with a direction. |
var dx: Int { |
switch self { |
case .up, .down: return 0 |
case .left: return -2 |
case .right: return 2 |
} |
} |
// The offset value for the y-axis associated with a direction. |
var dy: Int { |
switch self { |
case .left, .right: return 0 |
case .up: return 2 |
case .down: return -2 |
} |
} |
} |
// MARK: Properties |
/// A reference to the maze that the maze builder is building for. |
let maze: Maze |
/// Holds graph nodes designated as walls. |
var wallNodes = [GKGridGraphNode]() |
/// Used as a stack to search the maze during during maze generation. |
var searchStack = [GKGridGraphNode]() |
/// Used to keep track of visited nodes during maze generation. |
var visitedNodes = [GKGridGraphNode]() |
/** |
Returns every potential wall in the maze graph to the walls array. Due |
to the way the maze is constructed, a node is a potential wall if it has |
an odd x or y coordinate. |
*/ |
var potentialWalls: [GKGridGraphNode] { |
// Grab the graph nodes from the maze graph. |
let graphNodes = maze.graph.nodes as! [GKGridGraphNode] |
// Filter in the nodes that could potentially be walls. |
let potentialWalls = graphNodes.filter { node in |
// Grab the coordinates of the maze node. |
let x = Int(node.gridPosition.x) |
let y = Int(node.gridPosition.y) |
// If the maze node has an odd coordinate, filter it into the array. |
return x % 2 == 1 || y % 2 == 1 |
} |
return potentialWalls |
} |
// MARK: Initialization |
init(maze: Maze) { |
self.maze = maze |
} |
// MARK: Methods |
/** |
Returns an array of maze graph nodes representing walls in the maze. |
These nodes are to be removed from the pathfinding graph, since walls |
are impassible. |
This maze generation algorithm uses a depth-first search (DFS). |
It uses a stack to track its progress through the maze, and an array |
to check how much of the maze it has visited. It works like this: |
the starting node is added to the stack and array. The algorithm |
selects a node neighboring the top node of the stack (the starting |
node, in this case). It then removes the wall separating those two |
nodes, and adds the neighboring node to the stack and array. This |
process continues until the top node of the stack has no unvisited |
neighbors. When what happens, the algorithm removes nodes from the |
stack until the top node has an unvisited neighbor, and the process |
continues. Eventually the entire maze will have been visited, the |
stack will be empty, and the maze is created. |
Instead of removing walls directly, this method keeps track of |
which walls need to be removed, and returns those nodes. |
*/ |
func mazeWallsForRemoval() -> [GKGridGraphNode] { |
// First, add all of the potential walls to the array of walls. |
wallNodes += potentialWalls |
// Initialize both the stack and array with the starting maze graph node. |
searchStack.append(maze.startNode) |
visitedNodes.append(maze.startNode) |
// Until the stack is empty, process the maze graph. |
while let topNode = searchStack.last { |
/* |
First, check if the top node of the stack has any unvisited |
neighbors. If so, select a random unvisited neighbor to visit. |
Otherwise, remove the top node. |
*/ |
guard hasUnvisitedNeighborNode(topNode) else { |
// Remove the top node. |
searchStack.removeLast() |
// Skip to the next iteration of the while loop. |
continue |
} |
/* |
Check random neighboring directions until a neighboring node |
is found. Then visit that node. |
*/ |
exploreUnvisitedNodes: while true { |
// Generate a random direction. |
let randomDirection = Direction.random() |
/* |
If a direction should be explored by the algorithm, explore |
the node in that direction and exit the while loop. |
*/ |
if shouldExploreInDirectionFromNode(topNode, inDirection: randomDirection) { |
exploreNodeInDirectionFromNode(topNode, inDirection: randomDirection) |
break exploreUnvisitedNodes |
} |
} |
} |
// Return a set of walls that can be removed to form a maze. |
return wallNodes |
} |
/** |
Tests whether a node in a direction from a given node is unvisited. If |
so, it is explorable by the maze generation algorithm. |
*/ |
func shouldExploreInDirectionFromNode(_ node: GKGridGraphNode, inDirection direction: Direction) -> Bool { |
// Get the direction of the offset. |
let dx = direction.dx |
let dy = direction.dy |
// Get the location of the current node. |
let x = node.gridPosition.x |
let y = node.gridPosition.y |
// Return whether the node is unvisited or not. |
return nodeIsUnvisitedAtCoordinates(x: x + dx, y: y + dy) |
} |
/** |
Explores a direction in the maze generation algorithm, removing the wall |
between the given node and a node in the given direction. |
*/ |
func exploreNodeInDirectionFromNode(_ node: GKGridGraphNode, inDirection direction: Direction) { |
// Get the direction of the offset. |
let dx = direction.dx |
let dy = direction.dy |
// Get the location of the current node. |
let x = node.gridPosition.x |
let y = node.gridPosition.y |
// Get the location of node in the given direction. |
let nodeInDirectionPosition = int2(x + dx, y + dy) |
let nodeInDirection = maze.graph.node(atGridPosition: nodeInDirectionPosition)! |
// Add the node in the direction to the stack, and mark it as visited. |
searchStack.append(nodeInDirection) |
visitedNodes.append(nodeInDirection) |
// Remove the wall between this node and the current node. |
let wallNodePosition = int2(x + dx / 2, y + dy / 2) |
let wallNode = maze.graph.node(atGridPosition: wallNodePosition)! |
let wallNodeIndex = wallNodes.index(of: wallNode)! |
wallNodes.remove(at: wallNodeIndex) |
} |
/// Checks if the given maze graph node has any unvisited neighbor nodes. |
func hasUnvisitedNeighborNode(_ currentNode: GKGridGraphNode) -> Bool { |
// Grab the position of the given maze graph node. |
let x = currentNode.gridPosition.x |
let y = currentNode.gridPosition.y |
// Check whether the left, right, top, or bottom nodes are unvisited. |
let leftNodeIsUnvisited = nodeIsUnvisitedAtCoordinates(x: x - 2, y: y) |
let rightNodeIsUnvisited = nodeIsUnvisitedAtCoordinates(x: x + 2, y: y) |
let topNodeIsUnvisited = nodeIsUnvisitedAtCoordinates(x: x, y: y + 2) |
let bottomNodeIsUnvisited = nodeIsUnvisitedAtCoordinates(x: x, y: y - 2) |
/* |
If any of the neighboring nodes are unvisited, return that the node |
has at least one unvisited neighbor node. Otherwise, return that it |
doesn't. |
*/ |
let hasUnvisitedNeighborNode = leftNodeIsUnvisited || rightNodeIsUnvisited || topNodeIsUnvisited || bottomNodeIsUnvisited |
return hasUnvisitedNeighborNode |
} |
/// This method checks if a node is unvisited. |
func nodeIsUnvisitedAtCoordinates(x: Int32, y: Int32) -> Bool { |
// Check if a node with the given position exists. |
let nodePosition = int2(x, y) |
guard let node = maze.graph.node(atGridPosition: nodePosition) else { |
return false |
} |
// Return if the node is unvisited. |
let nodeIsUnvisited = !visitedNodes.contains(node) |
return nodeIsUnvisited |
} |
} |
Copyright © 2016 Apple Inc. All Rights Reserved. Terms of Use | Privacy Policy | Updated: 2016-09-28