Lummox Labs

Mobile app maker since 2015

Updating noodles puzzles

Haven't noodled yet? Download noodles here!


This is the first of (what will likely be) three posts on some algorithms used in building Noodles.

I'll start off with this link. That is pretty much amazing, and I wish I had known about it when I started building the hex games. The trickiest things with hexagons (ignoring design challenges) is the math in placing them because columns are offset, and the hexes don't have equal height and width. Read up there on how to do that math. Or do high school trig again.

Okay, so what is a Noodles puzzle, as a data structure? Well, if you think of the pieces as nodes and the connections between them as edges, it's a graph. Let's say an edge exists between two nodes (x, y) and (a, b) only if they both connect to each other. Like this:

Connected

Connected

Pieces that are connected to the Source, the dark ones in the game, I refer to as "powered" in code. So to find out which pieces are powered, you just go through the edges of the graph, starting at the source, and any node you reach has power. A simple breadth-first search will do the trick. I use a BFS for a bunch of stuff in the game, so I created a BFS function. 

The thing is, the two types of puzzles, squares and hexes, have very different rules: Different piece types, and even different pairs of indices that could be connected. So the BFS function allows the caller to pass in these "rules". That way you can use it for any game type, any graph. The rules are: 

  1. What node(s) to start with
  2. Which nodes are adjacent
  3. What makes two nodes equal?
/**
Perform a Breadth-first-search on ... well, anything!
:param: startNodes A list of nodes that comprise level 0.
:param: levels How deep to search the tree. Will stop after levels has been reached. Pass 0 for no limit.
:param: equalNodes A closure to determine when two nodes are equal.
:param: adjacentTo A closure to determine what nodes are adjacent to a given node.
:param: visited A closure called once for each visited node.
*/
func breadthFirstSearch<T: Hashable>(startNodes: [T],
  levels: Int = 0,
  equalNodes: (lhs: T, rhs: T) -> Bool,
  adjacentTo: (node: T) -> [T],
  visited: (node: T, level: Int) -> Void) {
    
    // Hashcodes
    var seenNodes = [T: Bool]()
    var nextNodes = [T](startNodes)
    
    for startNode in startNodes {
      seenNodes[startNode] = true
    }
    
    var actualLevels = (levels > 0) ? levels : 1000
    for level in 0 ..< actualLevels {
      var tempNextNodes = [T]()
      
      for nextNode in nextNodes {
        
        visited(node: nextNode, level: level)
        
        let adjacentNodes = adjacentTo(node: nextNode)
        for adjacentNode in adjacentNodes {
          if (seenNodes[adjacentNode] == nil) {
            tempNextNodes.append(adjacentNode)
            seenNodes[adjacentNode] = true
          }
        }
      }
      
      nextNodes = tempNextNodes
      
      if (nextNodes.count == 0) {
        // We're done! We've been through the whole thing.
        break
      }
    }
}

And with that, finding the powered nodes is straightforward:

  func updatePowered() {
    // Flag everything as unpowered to start
    for piece in self.pieces {
      piece.powered = false
    }
    
    // Set up the BFS
    let equalBlock: (GamePiece, GamePiece) -> Bool = { lhs, rhs in
      return lhs.index == rhs.index
    }
    
    let adjacentBlock: (GamePiece) -> [GamePiece] = { node in
      return self.connectingPiecesToPoint(node.index)
    }
    
    let visitedBlock: (GamePiece, Int) -> () = { node, level in
      node.powered = true
    }
    
    let sourceNodes = self.pieces.filter{ $0.source }
    
    breadthFirstSearch(sourceNodes,
      levels: 0,
      equalBlock,
      adjacentBlock,
      visitedBlock)
  }

And that's it! every time the user rotates a piece I run updatePowered() and update the visual state of the game. Easy peasy.

And bonus: I use the same BFS function to generate the "disappear" animation when you finish a puzzle.

Footnote for the interested: The adjacentBlock in the code above is a simplified version of the one I actually use. It was getting slow to recalculate which pieces are connected so many times, and they don't change for the duration of the method, so I cache the list of adjacent nodes for every piece.