Anonymous user
Maze solving: Difference between revisions
implements a solution for solving the mazes in swift
No edit summary |
(implements a solution for solving the mazes in swift) |
||
Line 5,226:
| * * | * * | * * * | * * * |
+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</pre>
=={{header|Swift}}==
{{works with|Swift|3}}
// The following requires the use of the implementation for [[Maze generation#Swift|generation task]]. Assumes there will be no // circular paths through the maze as the problem suggests.
enum errors: Error {
/// Occurs when a start or end position is given that is outside of bounds
case IndexOutsideMazeBoundary
}
/// Used to solve any maze generated by the swift implementation of maze generator at:
/// https://www.rosettacode.org/wiki/Maze_generation#Swift
class MazeSolver {
/// your starting index position in the maze
var startPos: (Int, Int)
/// the end index position you are trying to reach within the maze
var endPos: (Int, Int)
/// a maze of [[INT]] where each value is between 1 and 14.
/// each number representing a
var maze: [[Int]]
var visitedSpaces: [(Int, Int)]
init(maze: [[Int]]) {
self.startPos = (0, 0)
self.endPos = (0, 0)
/// a maze that consists of a array of ints from 1-14 organized to
/// create a maze like structure.
/// Each number represents where the walls and paths will be
/// ex. 2 only has a path south and 12 has paths E or W
self.maze = maze
/// spaces each branch has visited to stop from searching previously explored
/// areas of the maze
self.visitedSpaces = []
}
/// determine if the user has previously visited the given location within the maze
func visited(position: (Int, Int)) -> Bool {
return visitedSpaces.contains(where: {$0 == position})
}
/// used to translate the mazes number scheme to a list of directions available
/// for each number. DirectionDiff for N would be (0, -1) for example
func getDirections(positionValue: Int) -> [(Int, Int)] {
switch positionValue {
case 1:
return [Direction.north.diff]
case 2:
return [Direction.south.diff]
case 3:
return [Direction.north.diff, Direction.south.diff]
case 4:
return [Direction.east.diff]
case 5:
return [Direction.north.diff, Direction.east.diff]
case 6:
return [Direction.south.diff, Direction.east.diff]
case 7:
return [Direction.north.diff, Direction.east.diff, Direction.south.diff]
case 8:
return [Direction.west.diff]
case 9:
return [Direction.north.diff, Direction.west.diff]
case 10:
return [Direction.west.diff, Direction.south.diff]
case 11:
return [Direction.north.diff, Direction.south.diff, Direction.west.diff]
case 12:
return [Direction.west.diff, Direction.east.diff]
case 13:
return [Direction.north.diff, Direction.east.diff, Direction.west.diff]
case 14:
return [Direction.east.diff, Direction.south.diff, Direction.west.diff]
default:
return []
}
}
/// calculate and return all paths branching from the current position that haven't been explored yet
func availablePaths(currentPosition: (Int, Int), lastPos: (Int, Int)) -> [(Int, Int)] {
/// all available paths to be returned
var paths: [(Int, Int)] = []
/// the maze contents at the given position (ie the maze number)
let positionValue = maze[currentPosition.0][ currentPosition.1]
/// used to build the new path positions and check them before they
/// are added to paths
var workingPos: (Int, Int)
// is the maze at a dead end and not our first position
if ([1, 2, 4, 8].contains(positionValue) && currentPosition != lastPos) {
return []
}
/// the directions available based on the maze contents of our
/// current position
let directions: [(Int, Int)] = getDirections(positionValue: positionValue)
/// build the paths
for pos in directions {
workingPos = (currentPosition.0 + pos.0, currentPosition.1 + pos.1)
if (currentPosition == lastPos || (workingPos != lastPos && !visited(position: workingPos))) {
paths.append(workingPos)
}
}
return paths
}
/// prints a model of the maze with
/// O representing the start point
/// X representing the end point
/// * representing traveled space
/// NOTE: starting pos and end pos represent indexes and thus start at 0
func solveAndDisplay(startPos: (Int, Int), endPos: (Int, Int)) throws {
if (startPos.0 >= maze.count || startPos.1 >= maze[0].count) {
throw errors.IndexOutsideMazeBoundary
}
/// the posiiton you are beginning at in the maze
self.startPos = startPos
/// the position you wish to get to within the maze
self.endPos = endPos
/// spaces each branch has visited to stop from searching previously explored
/// areas of the maze
self.visitedSpaces = []
self.displaySolvedMaze(finalPath: solveMaze(startpos: startPos, pathSoFar: [])!)
}
/// recursivly solves our maze
private func solveMaze(startpos: (Int, Int), pathSoFar: [(Int, Int)]) -> [(Int, Int)]? {
/// marks our current position in the maze
var currentPos: (Int, Int) = startpos
/// saves the spaces visited on this current branch
var currVisitedSpaces : [(Int, Int)] = [startpos]
/// the final path (or the path so far if the end pos has not been reached)
/// from the start position to the end position
var finalPath: [(Int, Int)] = pathSoFar
/// all possible paths from our current position that have not been explored
var possiblePaths: [(Int, Int)] = availablePaths(currentPosition: startpos, lastPos: pathSoFar.last ?? startpos)
// move through the maze until you come to a position that has been explored, the end position, or a dead end (the
// possible paths array is empty)
while (!possiblePaths.isEmpty) {
// found the final path
guard (currentPos != self.endPos) else {
finalPath.append(contentsOf: currVisitedSpaces)
return finalPath
}
// multiple valid paths from current position found
// recursively call new branches for each valid path
if (possiblePaths.count > 1) {
visitedSpaces.append(contentsOf: currVisitedSpaces)
finalPath.append(contentsOf: currVisitedSpaces)
// for each valid path recursively call each path
// and if it contains the final path
// ie it found the endpoint, return that path
for pos in possiblePaths {
let path = solveMaze(startpos: pos, pathSoFar: finalPath)
if (path != nil) {
return path
}
}
// otherwise this branch and it's sub-branches
// are dead-ends so kill this branch
return nil
}
// continue moving along the only path available
else {
// update current path to our only available next
// position
currentPos = possiblePaths[0]
// calculate the available paths from our new
// current position
possiblePaths = availablePaths(currentPosition: currentPos, lastPos: currVisitedSpaces.last ?? currentPos)
// update the visited spaces for this branch
currVisitedSpaces.append(currentPos)
}
}
// if our new current position is the endpos return our final path
if (currentPos == self.endPos) {
finalPath.append(contentsOf: currVisitedSpaces)
return finalPath
}
else {
return nil
}
}
// Reference: https://www.rosettacode.org/wiki/Maze_generation#Swift
// adapts the display method used in the swift implementation of the maze generator we used for this app to display the maze solved
func displaySolvedMaze(finalPath: [(Int, Int)]) {
/// all cells are 3 wide in the x axis
let cellWidth = 3
for j in 0..<y {
// Draw top edge
// if mark corner with +, add either (cell width) spaces or - to the topedge var dependin on if it is a wall or not
var topEdge = ""
for i in 0..<x {
topEdge += "+"
topEdge += String(repeating: (maze[i][j] & Direction.north.rawValue) == 0 ? "-" : " ", count: cellWidth)
}
topEdge += "+"
print(topEdge)
// Draw left edge
//through the center of the cell if is a wall add | if not a space
// then if it is travelled add " * " otherwise just 3 spaces then
//cap it with a | at the end for the right most wall
var leftEdge = ""
for i in 0..<x {
leftEdge += (maze[i][j] & Direction.west.rawValue) == 0 ? "|" : " "
if (finalPath.first! == (i, j)) {
leftEdge += " O "
}
else if (finalPath.last! == (i, j)) {
leftEdge += " X "
}
else {
if (finalPath.contains(where: {$0 == (i, j)})) {
leftEdge += " * "
}
else {
leftEdge += String(repeating: " ", count: cellWidth)
}
}
}
leftEdge += "|"
print(leftEdge)
}
// Draw bottom edge
// adds + on corners and _ everywhere else
var bottomEdge = ""
for _ in 0..<x {
bottomEdge += "+"
bottomEdge += String(repeating: "-", count: cellWidth)
}
bottomEdge += "+"
print(bottomEdge)
}
}
// example implementation using the aforementioned maze generator code for the swift implementation on rosettaCode
// let x = 20
// let y = 10
// let maze = MazeGenerator(x, y)
// var solver: MazeSolver = MazeSolver(maze: maze.maze)
// for i in 0...5 {
// do {
// // making sure the start and end pos are within the maze boundary
// try solver.solveAndDisplay(startPos: (0, i), endPos: (5+i, 5))
// }
// catch errors.IndexOutsideMazeBoundary {
// print("[ERROR] given start or end point outside of bounds")
// }
// }
=={{header|Tcl}}==
| |||