1
안녕하세요 저는 재귀 적 백 트랙킹 알고리즘을 통해 미로를 만들어야하는 신속한 클래스를 작성했습니다. 내 미로에 벽을 배치하는 데 문제가있는 것 같습니다. 그러나 나는 그것을 깰 수 없다.스위프트 재귀 백 트래킹 알고리즘이 작동하지 않습니다.
내가 도움을 얻을 수 있다면 좋을 것입니다. 감사합니다! 꽤 자기 설명 -
것은2 차원 배열 클래스 아래의 코드에 대한 설명을 찾아주세요. 여러 개의 열과 행과 기본값을 지정하면 거기에서 2 차원 배열이 생성됩니다. 아래 첨자 메서드를 사용하면 값을 설정하고 가져올 수 있습니다.
class Array2D<T> {
let columns: Int
let rows: Int
var array : Array<Array<T?>>
init(columns: Int, rows: Int, repeatedValue: T?) {
self.columns = columns
self.rows = rows
var tmp = Array<T?>(count: rows, repeatedValue: repeatedValue)
array = Array<Array<T?>>(count: columns, repeatedValue: tmp)
}
subscript(column: Int, row: Int) -> T? {
get {
return array[column][row]
}
set(newValue) {
array[column][row] = newValue
}
}
}
DIR 열거 그들에게 이름을 할당하여 비트에서 추상적 인 스스로 우리를 허용하는 열거.
enum DIR : UInt8 {
case N = 1
case S = 2
case E = 4
case W = 8
case O = 0
}
방향 클래스이 클래스는 방향에 대한 모든 정보를 보유하고 있습니다. 그것은 약간 과잉일지도 모른다. 현재 위치와 관련하여 방향 (N, S, E, W)을 얻을 수 있습니다. 반대 방향으로 갈 수도 있습니다. 마법이 일어나는 곳
class Direction {
var bit : DIR
var dx : Int
var dy : Int
init(bit: DIR, dx: Int, dy: Int) {
self.bit = bit
self.dx = dx
self.dy = dy
}
class func NORTH() -> Direction {
return Direction(bit: DIR.N, dx: 0, dy: -1)
}
class func SOUTH() -> Direction {
return Direction(bit: DIR.S, dx: 0, dy: 1)
}
class func EAST() -> Direction {
return Direction(bit: DIR.E, dx: 1, dy: 0)
}
class func WEST() -> Direction {
return Direction(bit: DIR.W, dx: -1, dy: 0)
}
func opposite() -> Direction {
switch(bit){
case DIR.N:
return Direction.SOUTH()
case DIR.S:
return Direction.NORTH()
case DIR.E:
return Direction.WEST()
case DIR.W:
return Direction.EAST()
default:
println("An error occured while returning the opposite of the direction with bit: \(bit)")
return Direction(bit: DIR.O, dx: 0, dy: 0)
}
}
}
RecursiveBackTracking 클래스이입니다. 이 클래스는 폭 (x)과 높이 (y)가 주어진 미로를 자동으로 생성합니다. generateMaze() 함수는 지원되는 다른 함수와 대부분의 작업을 수행합니다. 여기있는 모든 것은 효과가있는 것처럼 보이지만 나는 여전히 적절한 결과를 얻지 못하고 있습니다. 잠재적으로 문제는 display() 함수에서도 발생할 수 있습니다.
class RecursiveBacktracking {
var x : Int
var y : Int
var maze : Array2D<UInt8>
init(x: Int, y: Int) {
self.x = x
self.y = y
maze = Array2D<UInt8>(columns: x, rows: y, repeatedValue: 0)
generateMaze(0, cy: 0)
display()
}
func generateMaze(cx: Int, cy: Int) {
var directions : [Direction] = [Direction.NORTH(),Direction.SOUTH(),Direction.EAST(),Direction.WEST()]
directions = shuffle(directions)
for dir in directions {
var nx : Int = cx + dir.dx
var ny : Int = cx + dir.dy
if between(nx, upper: x) && between(ny, upper: y) && getMazeObject(nx, y: ny) == 0 {
maze[cx,cy] = bitwiseOr(getMazeObject(cx, y: cy), b: dir.bit.rawValue)
maze[nx,ny] = bitwiseOr(getMazeObject(nx, y: ny), b: dir.opposite().bit.rawValue)
generateMaze(nx, cy: ny)
}
}
}
func bitwiseOr(a: UInt8, b: UInt8) -> UInt8 {
return a | b
}
func getMazeObject(x: Int, y: Int) -> UInt8 {
if var object = maze[x,y] {
return object
}else{
println("No object could be found at location: (\(x),\(y)).")
return 0
}
}
func between(v: Int, upper: Int) -> Bool {
return (v>=0) && (v<upper)
}
func shuffle<C: MutableCollectionType where C.Index == Int>(var list: C) -> C {
let count : Int = Int(countElements(list))
for i in 0..<(count - 1) {
let j = Int(arc4random_uniform(UInt32(count - i))) + i
swap(&list[i], &list[j])
}
return list
}
func display() {
for i in 0..<y {
// Draw North Edge
for j in 0..<x {
var bit : UInt8 = getMazeObject(j, y: i)
bit = bit & 1
if bit == 0 {
print("+---")
}else{
print("+ ")
}
}
println("+")
// Draw West Edge
for j in 0..<x {
var bit : UInt8 = getMazeObject(j, y: i)
bit = bit & 8
if bit == 0 {
print("| ")
}else{
print(" ")
}
}
println("|")
}
// Draw the bottom line
for j in 0..<x {
print("+---")
}
println("+")
}
}
추가 정보는이 알고리즘은 http://rosettacode.org/wiki/Maze#Java