Very slow minesweeper recursive algorithm in Swift

Question

I'm working with Swift 3 and Xcode.

I'm creating an iOS game that is basically a Minesweeper, but there are no squares but hexagons, so each hexagon can have up to 6 mines in their surrounding.

I created a recursive algorithm, so that when the player touches an hexagon, if it's not a bomb, then it call a recursive function called "reveal" which : - if one ore more mine in the surrounding and the touched hexagon is still hidden (by hidden I mean we don't know if it's a mine or not), reveal the hexagon & set the number of surrounding mine's label, and stop the function - if no mine in the surrounding, for each nearby hexagon that is hidden, call the reveal function.

So here's what my code looks like :

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

the proximityHexagons(hexagon: Hexagon) function returns an array containing all surrounding hexagons of a given hexagon.

So I really checked my algorithm again and again, and I really think it's the good one.

But the fact is that when I create a level with 0 or a really low amount of mine, and I click on an hexagon, it takes something like 2 seconds for the recursive function to update all the empty hexagons. My map contains more or less 260 hexagons, and I debugged the number of calls of reveal() and it's about the same amount.

So why is it taking so much time ? I don't think the iPhone 6 can't handle this amount of operations ! I tried it on my iPhone, not an emulator. Do you have any idea ?

Answer 1

Okay, I managed to solve my problem.

The problem was the proximityHexagons function that was taking a lot of time. In fact, each time I called this function, he made 6 complex calculations and added the surrounding hexagons in an array, so it was taking a lot of time.

Here's what it looked like :

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
}

I prefer checking the surrounding hexagons with the nodes(at: Point) function because my levels aren't always regular maps, they can have a weird positioning and twiz_'s func indices(surrounding index: Int) function could not work. So I kept my function, but I call it once at the beginning of the level and store in a new variable in my hexagon class all the surrounding hexagons of each hexagon:

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

And then, in the reveal function, instead of calling the proximityHexagons function, I use the .proxyHexagons array of the hexagon, like this :

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

And now my function is way faster, I manage to reveal all 260 hexagons in 0.001 secs instead of the old 2.81 secs.

Answer 2

Ok I've been thinking about this because it sounds like a fun problem. I didn't look up any minesweeper solvers, so I might be way out in left field, but here is how I would approach your problem.

First you have to give every mine an index, and you need to know the pattern of that index such that you can do a little math to get the surrounding indices of every mine. If the rows have identical numbers, and the numbering is sequential across rows, then the surrounding indices are:

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

Then I would make a class that holds a set of all the safe spots on the map that you had when you built the puzzle. I'll call it 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
}
}

It's got two important functions, one calculates the surrounding indices, the second filters the safe spots. I'm using sets so we can quickly determine the intersection between the safe spots and the surrounding spots.

Next we need a class that would be instantiated when a move is made so we can do the recursion. Lets call it 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)
}
}

You initialize it with your first hexagon, or hex index, and the surrounding safespots that the safety manager would give you, if you get no safe spots from the SafetyManager, no need to instantiate. It keeps a set of checked spots and unchecked spots. Two important functions, the second you use to give it newly acquired safe spots from the safety manager to be added to the unchecked list. The other returns an optional Int? of the next safe spot to check the surroundings of.

Then to do the recursion, something like this..

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 
}

}

You could keep a dictionary of [Int: Hexagon] to quickly grab the hex for a given index. I haven't tested this so I'm not sure if it works well, or at all or has some improper syntax. It would also probably be a lot faster to use multithreading. Fun problem. Good luck.