Sehr langsamer Minesweeper rekursiver Algorithmus in Swift

Question

Ich arbeite mit Swift 3 und Xcode.

Ich erstelle ein iOS-Spiel, das im Grunde ein Minesweeper ist, aber es gibt keine Quadrate, sondern Sechsecke, also kann jedes Sechseck bis zu 6 Minen in seiner Umgebung haben.

Ich habe einen rekursiven Algorithmus erstellt, so dass, wenn der Spieler ein Sechseck berührt, wenn es keine Bombe ist, dann eine rekursive Funktion genannt "offenbaren", die: - wenn eine oder mehrere meins in der Umgebung und die berührt Sechseck ist immer noch versteckt (durch versteckte ich meine wir wissen nicht, ob es eine Mine ist oder nicht), enthüllen Sie das Sechseck & legen Sie die Nummer der umliegenden Mine Label, und stoppen Sie die Funktion - wenn keine Mine in der Umgebung, für jede in der Nähe Hexagon, das ausgeblendet ist, rufen Sie die Funktion "Offenlegung" auf.

Also hier ist, was mein Code wie folgt aussieht:

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

die proximityHexagons(hexagon: Hexagon) Funktion gibt ein Array alle umgebenden Hexagons eines gegebenen Sechseck enthält.

Also habe ich meinen Algorithmus immer wieder überprüft, und ich denke wirklich, dass es der Gute ist.

Aber Tatsache ist, dass, wenn ich eine Ebene mit 0 oder eine wirklich geringe Menge von mir zu erstellen, und ich auf ein Sechseck klicken, dauert es etwa 2 Sekunden für die rekursive Funktion, alle leeren Sechsecke zu aktualisieren. Meine Karte enthält mehr oder weniger 260 Sechsecke, und ich debugged die Anzahl der Aufrufe von reveal() und es ist ungefähr die gleiche Menge.

Warum dauert es so viel Zeit? Ich glaube nicht, dass das iPhone 6 mit dieser Menge an Operationen nicht fertig wird! Ich habe es auf meinem iPhone versucht, kein Emulator. Haben Sie eine Idee?

Answer 1

Okay, ich habe mein Problem gelöst.

Das Problem war die proximityHexagons Funktion, die viel Zeit in Anspruch nahm. Jedes Mal, wenn ich diese Funktion aufgerufen habe, hat er 6 komplexe Berechnungen durchgeführt und die umgebenden Sechsecke in einem Array hinzugefügt, so dass es viel Zeit in Anspruch nahm.

Hier ist, wie es aussah:

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 
} 

Ich ziehe die umliegenden Hexagone mit der nodes(at: Point) Funktion überprüft, weil meine Ebenen nicht immer regelmäßig Karten sind, sie eine seltsame Positionierung und twiz_ die haben könnte func indices(surrounding index: Int)-Funktion nicht . Also hielt ich meine Funktion, aber ich nenne es einmal am Anfang des Levels und speichern Sie in einer neuen Variablen in meiner Sechseck Klasse alle umliegenden Hexagone jedes Sechsecks:

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

Und dann, in der offenbaren Funktion statt die proximityHexagons Funktion aufzurufen, verwende ich die .proxyHexagons Anordnung des Sechsecks, wie folgt aus:

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

Und nun meine Funktion schneller Art und Weise, ich schaffe in 0,001 Sekunden anstelle der alten alle 260 Hexagone offenbaren 2,81 Sekunden

Answer 2

Ok Ich habe darüber nachgedacht, weil es wie ein lustiges Problem klingt. Ich habe keine Minensucher-Löser nachgeschlagen, also bin ich vielleicht im linken Feld, aber hier würde ich Ihrem Problem näher kommen.

Zuerst müssen Sie jeder Mine einen Index geben, und Sie müssen das Muster dieses Indexes kennen, so dass Sie ein bisschen rechnen können, um die Umgebungsindizes jeder Mine zu erhalten. Wenn die Zeilen identische Zahlen haben, und die Nummerierung ist über die Reihen sequentiell, dann die umliegenden Indizes:

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

Dann würde ich eine Klasse machen, das einen Satz von allen sicheren Flecken auf der Karte hält, die Sie haben, wenn Du hast das Puzzle gebaut. Ich werde es SafetyManager nennen.

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

Es ist zwei wichtige Funktionen erhalten, berechnet man die umliegenden Indizes, die zweiten Filter die sicheren Flecken. Ich benutze Sets, so dass wir schnell den Schnittpunkt zwischen den sicheren Punkten und den umliegenden Spots bestimmen können.

Als nächstes brauchen wir eine Klasse, die instanziiert werden würde, wenn eine Bewegung gemacht wird, damit wir die Rekursion durchführen können. Lass es CheckManager nennen.

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

Sie initialisieren es mit Ihrem ersten Sechseck oder Hex-Index und die umgebenden safespots, dass die Sicherheitsmanager würden Sie, wenn Sie keine sicheren Flecke vom SafetyManager bekommen, keine Notwendigkeit, instanziiert. Es enthält eine Reihe von überprüften und nicht markierten Punkten.Zwei wichtige Funktionen, die zweite, die Sie verwenden, um neu erworbene sichere Stellen aus dem Sicherheitsmanager in die ungeprüfte Liste aufzunehmen. Der andere gibt eine optionale Int? der nächste sichere Ort, um die Umgebung von zu überprüfen.

dann die Rekursion, so etwas zu tun ..

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 
} 

} 

Sie ein Wörterbuch von [Int: Hexagon] halten konnte für einen bestimmten Index, der die Hex schnell zu greifen. Ich habe das nicht getestet, also bin ich mir nicht sicher, ob es gut oder überhaupt funktioniert oder eine falsche Syntax hat. Es wäre wahrscheinlich auch viel schneller Multithreading zu verwenden. Spaßproblem. Viel Glück.