Swift 中非常慢的扫雷递归算法

Question

我正在与 Swift 3 和 Xcode 合作。

我正在创建一个 iOS 游戏，它基本上是一个扫雷游戏，但是没有正方形而是六边形，所以每个六边形周围最多可以有 6 个地雷。

我创建了一个递归算法，这样当玩家触摸一个六边形时，如果它不是炸弹，它就会调用一个名为 "reveal" 的递归函数，其中： - 如果周围多了一个矿并且触摸的六边形仍然隐藏（隐藏我的意思是我们不知道它是否是地雷），揭示六边形并设置周围矿山标签的数量，并停止该功能 - 如果周围没有地雷，对于附近隐藏的每个六边形，调用显示功能。

我的代码如下所示：

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)函数returns包含给定六边形的所有周围六边形的数组。

所以我真的一遍又一遍地检查我的算法，我真的认为它是好的。

但事实是，当我创建一个 0 或非常低的关卡时，我单击一个六边形，递归函数需要大约 2 秒的时间来更新所有空六边形。我的地图大概有260个六边形，我调试了reveal()的调用次数也差不多。

那为什么要花这么多时间呢？我认为 iPhone 6 无法处理如此多的操作！我在 iPhone 上试过，不是模拟器。你有什么想法吗？

Answer 1

好的，我一直在考虑这个问题，因为它听起来很有趣。我没有查找任何扫雷求解器，所以我可能在左场出路，但这是我解决你的问题的方法。

首先你必须给每个地雷一个索引，你需要知道那个索引的模式，这样你就可以做一点数学来得到每个地雷周围的索引。如果行具有相同的编号，并且编号在各行之间是连续的，那么周围的索引是：

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

然后我会制作一个 class，其中包含一组您在构建拼图时所拥有的地图上的所有安全点。我将其称为 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
}
}

它有两个重要的功能，一是计算周围指数，二是过滤安全点。我正在使用集合，因此我们可以快速确定安全点和周围点之间的交集。

接下来我们需要一个 class ，它会在移动时被实例化，这样我们就可以进行递归。让我们称之为 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)
}
}

你用你的第一个六边形或十六进制索引，以及安全管理器会给你的周围安全点初始化它，如果你没有从安全管理器得到安全点，就不需要实例化。它保留一组检查点和未检查点。两个重要的功能，第二个是你用来给它从安全管理器中新获得的安全点，将其添加到未检查列表中。另一个returns一个可选的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: Hexagon] 的字典以快速获取给定索引的十六进制。我还没有对此进行测试，所以我不确定它是否运行良好，或者根本无法运行，或者有一些不正确的语法。使用多线程也可能要快得多。有趣的问题。祝你好运。

Answer 2

好的，我设法解决了我的问题。

问题是 proximityHexagons 函数花费了很多时间。其实我每次调用这个函数，他都要进行6次复杂的计算，把周围的六边形加到一个数组里，所以很费时间。

这是它的样子：

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({[=10=] 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({[=10=] 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({[=10=] is Hexagon}) as! [Hexagon])
    nodeArray.append(nodes(at: CGPoint(x: hexagon.position.x, y: hexagon.position.y - hexagon.height)).filter({[=10=] 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({[=10=] 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({[=10=] 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
}

我更喜欢用 nodes(at: Point) 函数检查周围的六边形，因为我的关卡并不总是规则的地图，它们的位置可能很奇怪，而 twiz_ 的 func indices(surrounding index: Int) 函数无法工作。所以我保留了我的函数，但我在关卡开始时调用它一次，并在我的六边形 class 中的一个新变量中存储每个六边形的所有周围六边形：

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

然后，在显示函数中，我没有调用 proximityHexagons 函数，而是使用六边形的 .proxyHexagons 数组，如下所示：

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 个六边形，而不是旧的 2.81 秒。

Swift 中非常慢的扫雷递归算法

Very slow minesweeper recursive algorithm in Swift

algorithm

recursion

minesweeper

sprite-kit

swift