1

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

1 Answer 1

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.