스위프트에서 매우 느린 지뢰 찾기 재귀 알고리즘

Question

스위프트 3 및 Xcode에서 작업하고 있습니다.

기본적으로 지뢰 찾기 도구 인 iOS 게임을 만들지 만 사각형이 아니라 육각형이므로 각 육각형의 주변에는 최대 6 개의 지뢰가있을 수 있습니다.

플레이어가 육각형에 닿으면 폭탄이 아니라면 "계시"라는 재귀 함수가 호출됩니다. - 하나 이상의 광산이 주변에 있고 터치 된 경우 육각형은 여전히 ​​숨겨져 있습니다 (숨겨진 의미로는 광산인지 아닌지를 알 수 없음). 육각형을 나타냅니다. & 주변 광산 레이블의 수를 설정하고 기능을 중지하십시오. - 주변에 광산이 없으면 근처에 각각 숨겨진 육각형. 계시 기능을 호출하십시오.

그래서 여기 내 코드의 모습입니다 :

class Hexagon: SKShapeNode 
{ 
    var mine: Bool 
    var hide: Bool 
    var proximityMines: Int 

    init(mine: Bool = false, proximityMines: Int = 0, hide: Bool = true) 
    { 
     self.mine = mine // if it's a mine 
     self.proximityMines = proximityMines // number of surrounding mines (that I calculated using a function after I generated the level) 
     self.hide = hide // if the hexagon is still hidden 

     super.init() 
    } 
    required init?(coder aDecoder: NSCoder) { 
     fatalError("init(coder:) has not been implemented") 
    } 
} 

func reveal(hexagon: Hexagon) 
{ 
    if hexagon.proximityMines == 0 && hexagon.hide == true // if there are no mines in the surrounding 
    { 
     hexagon.hide = false // we update the value of this hexagon 
     setNumberLabel(hexagon: hexagon) // we set the .proximityMines number as a label (here 0) 

     for proxyHexagon in proximityHexagons(hexagon: hexagon) // for each surrounding hexagon ... 
     { 
      if proxyHexagon.hide == true // ... that is still hidden 
      { 
       reveal(hexagon: proxyHexagon) // we call this function again 
      } 
     } 
    } 
    else if hexagon.proximityMines != 0 && hexagon.hide == true // else if there are mines in the surrounding 
    { 
     hexagon.hide = false // update 
     setNumberLabel(hexagon: hexagon) // set label 
    } 
} 

proximityHexagons(hexagon: Hexagon) 함수는 주어진 육각형의 모든 주변 육각형을 포함하는 배열을 반환합니다.

그래서 알고리즘을 반복해서 확인했는데 실제로 좋은 알고리즘이라고 생각합니다.

사실 나는 0 또는 매우 적은 양의 광산으로 수준을 만들고 육각형을 클릭하면 재귀 함수가 모든 빈 육각형을 업데이트하는 데 2 ​​초 정도 걸립니다. 내지도에는 260 개의 육각형이 포함되어 있으며 reveal()의 전화 번호를 디버깅했으며 거의 ​​같은 금액입니다.

왜 그렇게 많은 시간이 소요됩니까? iPhone 6이이 정도의 작업을 처리 할 수 ​​없다고 생각합니다! 에뮬레이터가 아닌 내 iPhone에서 시험해 보았습니다. 의견이 있으십니까?

Answer 1

좋아, 나는 내 문제를 해결할 수 있었다.

문제는 많은 시간이 걸리는 proximityHexagons 기능이었습니다. 사실이 함수를 호출 할 때마다 그는 6 개의 복잡한 계산을하고 주변의 육각형을 배열에 추가 했으므로 많은 시간이 걸렸습니다. 내 수준이 항상 일정한지도가 있기 때문에 nodes(at: Point) 기능으로 주변의 육각형을 확인 선호

func proximityHexagons(hexagon: Hexagon) -> Array<Hexagon> 
{ 
    var array = [Hexagon]() 

    var nodeArray = [[Hexagon]]() 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x, y: hexagon.position.y + hexagon.height)).filter({$0 is Hexagon}) as! [Hexagon]) 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x + hexagon.width * 3/4, y: hexagon.position.y + hexagon.height/2)).filter({$0 is Hexagon}) as! [Hexagon]) 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x + hexagon.width * 3/4, y: hexagon.position.y - hexagon.height/2)).filter({$0 is Hexagon}) as! [Hexagon]) 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x, y: hexagon.position.y - hexagon.height)).filter({$0 is Hexagon}) as! [Hexagon]) 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x - hexagon.width * 3/4, y: hexagon.position.y - hexagon.height/2)).filter({$0 is Hexagon}) as! [Hexagon]) 
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x - hexagon.width * 3/4, y: hexagon.position.y + hexagon.height/2)).filter({$0 is Hexagon}) as! [Hexagon]) 

// first, for each 6 directions, I'm adding in an array every nodes that are Hexagon, and then adding all of theses arrays in another bigger one 

    for node in nodeArray // for each hexagon array in the big array 
    { 
     if node.count != 0 // if there is an hexagon 
     { 
      array.append(node.first!) // we set the hexagon in the final array 
     } 
    } 

    return array // we return the array containing all surrounding hexagons 
} 

, 그들이 이상한 위치를 가질 수 있고 twiz_의 func indices(surrounding index: Int) 기능이 작동하지 수 : 여기

는 어떻게 생겼는지입니다 . 그래서 난 내 기능을 유지하지만 각 육각형의 모든 주변 육각형 내 육각 클래스에 새로운 변수의 수준과 상점의 시작 부분에 한 번 전화 : 다음

class Hexagon: SKShapeNode 
{ 
    var mine: Bool 
    var hide: Bool 
    var proximityMines: Int 
    var proxyHexagons: [Hexagon] // here 

    init(mine: Bool = false, proximityMines: Int = 0, hide: Bool = true, proxyHexagons: [Hexagon] = 
     [Hexagon]()) 
    { 
     self.mine = mine 
     self.proximityMines = proximityMines 
     self.hide = hide 
     self.proxyHexagons = proxyHexagons 

     super.init() 
    } 
    required init?(coder aDecoder: NSCoder) { 
     fatalError("init(coder:) has not been implemented") 
    } 
} 

그리고, 공개 함수

func reveal(hexagon: Hexagon) 
{   
    if hexagon.proximityMines == 0 && hexagon.hide == true 
    { 
     hexagon.hide = false 
     setNumberLabel(hexagon: hexagon) 
     for proxyHexagon in hexagon.proxyHexagons // here 
     { 
      if proxyHexagon.hide == true 
      { 
       reveal(hexagon: proxyHexagon) 
      } 
     } 
    } 
    else if hexagon.proximityMines != 0 && hexagon.hide == true 
    { 
     hexagon.hide = false 
     setNumberLabel(hexagon: hexagon) 
    } 
} 

그리고 지금 내 기능은 빠른 방법은, 내가 대신 기존의 0.001 초에있는 모든 260 개 육각형을 나타 내기 위해 관리된다, 대신 proximityHexagons 함수를 호출, 나는 다음과 같이 육각형의 .proxyHexagons 배열을 사용 2.81 초.

Answer 2

좋아 재미있는 문제로 들리기 때문에 나는 이것을 생각 해왔다. 나는 지뢰 찾기 해결사를 찾지 않았으므로 왼쪽 필드에서 탈출 할 수 있었지만, 여기 당신의 문제에 어떻게 접근 할 것인가.

먼저 모든 광산에 지수를 부여해야하며 모든 광산의 주변 지표를 얻기 위해 약간의 계산을 할 수 있도록 해당 지표의 패턴을 알아야합니다. 행이 동일한 번호를 가지고 있고, 번호 행에 걸쳐 순차적 경우, 주변의 인덱스는 다음과 같습니다

[index - 1, index + 1, 
index - rowCount, index - rowCount - 1, 
index + rowCount, index + rowCount + 1] 

그럼 난 당신이 가지고지도에있는 모든 안전 점의 집합을 보유하고 클래스를 만들 것이다 때 당신은 퍼즐을 만들었습니다. 나는 그것을 SafetyManager라고 부를 것이다.

class SafetyManager { 

var safeSpots: Set<Int> = all your safe spots 

func indices(surrounding index: Int) -> Set<Int> { 
    return [index - 1, index + 1, 
      index - rowCount, index - rowCount - 1, 
      index + rowCount, index + rowCount + 1] 
} 

func safePlaces(around hexagon: Int) -> Set<Int> { 

    let allIndices = indices(surrounding: hexagon) 
    let safe = allIndices.intersection(safeSpots) 

    safeSpots.subtract(safe) 

    return safe 
} 
} 

그것은 하나는 주변 인덱스, 두 번째 필터 안전한 지점을 계산, 두 가지 중요한 기능을 가지고있다. 저는 안전 지대와 주변 지형 간의 교차점을 신속하게 결정할 수 있도록 세트를 사용하고 있습니다.

다음으로 우리는 재귀를 할 수 있도록 이동이 이루어질 때 인스턴스화 될 클래스가 필요합니다. CheckManager를 호출 할 수 있습니다.

class CheckManager { 

var checked : [Int] 
var unchecked : Set<Int> 

init(firstHex: Hexagon, surroundingSafeSpots: Set<Int>) { 
    checked = [firstHex.index] 
    unchecked = surroundingSafeSpots 
} 


func nextUnchecked() -> Int? { 
    guard !unchecked.isEmpty else { return nil } 

    let next = unchecked.removeFirst() 
    checked += [next] 
    return next 
} 

func pleaseTake(these indices: Set<Int>) { 
    unchecked.formUnion(indices) 
} 
} 

당신은 첫 번째 육각형, 또는 16 진수 지수를 초기화하고 SafetyManager에서 안전한 장소를 얻을 수없는 경우 주변 safespots은 안전 관리자가, 당신을 줄 것, 필요 인스턴스화 없습니다. 체크 된 스팟과 체크되지 않은 스팟을 유지합니다.중요한 두 가지 기능은 안전 관리자가 새롭게 획득 한 안전 지대를 제공하여 점검되지 않은 목록에 추가하는 두 번째 기능입니다. 다른 하나는 선택적 Int를 반환합니다. 다음의 안전한 장소에서 주변을 확인하십시오.

그런 다음, 이런 식으로 뭔가를 재귀를 수행하는 ..

func check(spot: Hexagon) { 

let safe = safetyMan.safePlaces(around: spot.index) 
guard safe.count > 0 else { .. } 

let checkMan = CheckManager(firstHex: spot, surroundingSafeSpots: safe) 

while let i = checkMan.nextUnchecked() { 
    let safeSpots = safetyMan.safePlaces(around: i) 
    checkMan.pleaseTake(these: safeSpots) 
} // goes until unchecked is empty 

for spot in checkMan.checked { 
    // get the hex and reveal 
} 

} 

당신은 [Int 인 : 육각]의 사전을 유지할 수 신속하게 지정된 인덱스의 진수를 잡아. 나는 이것을 테스트하지 않았기 때문에 잘 작동하는지 또는 전혀 작동하지 않거나 부적절한 구문이 있는지 확실하지 않습니다. 멀티 스레딩을 사용하는 것이 더 빠를 수도 있습니다. 재미있는 문제. 행운을 빕니다.