Swift Recursive Back Tracking Algorithm Not Working

Question

Hi I have written a class in swift that should create a maze through a recursive backtracking algorithm. I seem to have a problem around the assignment of walls to my maze. But I can not crack it.

It would be great if I could get some help here, thank you!

Please find a description of the code below

2D Array Class - Pretty self explanatory. Give it a number of columns and rows and a default value, from there it generate the 2d array. The subscript methods allow you to set and get values.

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 A enum which allows us to abstract ourselves from bits by assigning them names.

enum DIR : UInt8 {
 case N = 1
 case S = 2
 case E = 4
 case W = 8
 case O = 0
}

Direction Class This class holds all the information about the Directions. It may be slightly an overkill. It allows you to get directions (N,S,E,W) in relation to a current location. You can also get the opposite direction.

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 Class This is where the magic happens. This class auto generates a maze given a width(x) and a height(y). The generateMaze() function does most of the work with the other functions in support. Everything here seems to work but I am still not getting the appropriate result. Potentially the problem may also by in the display() function.

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("+")
 }
}

Additional Information: This algorithm is based off of http://rosettacode.org/wiki/Maze#Java

Martin R Martin R · Accepted Answer · 2014-12-10T12:01:06

The error is here:

var nx : Int = cx + dir.dx
var ny : Int = cx + dir.dy

The second cx should be cy.

Remark: There is some room for improvement in your code. As an example, the bitwise or | is already defined for UInt8, so there is no need to define that as a function. If you have fixed your code to work correctly, you might consider to post it at http://codereview.stackexchange.com to get a review.

Swift Recursive Back Tracking Algorithm Not Working

1 Answers