Solver for Flow game
I have been playing this android game Flow. I also ran into a post in a game developer forum that someone asked for a solver to find the solution of a game. So I thought it would be an interesting problem to solve.
The game is really simple. The starting map is an N-by-M grid with a number of pairs of color dots on it. The goal is the game is to connect the pairs of dots with the same color, and fill up all the grids on the map.
The codes can be found here.
Defining a game map
First I define a graph class to store and generate a game map. The map is represented by a 2D N-by-M matrix. An element 0 means an empty spot. Each color is presented by an integer 1 or higher. The Graph class also has a method for getting the neighbors of a given position.
import numpy as np
class Graph():
''' class for storing and generating game maps '''
def __init__(self, numRow, numCol):
self.map = np.zeros([numRow,numCol], dtype='int32')
self.numRow = numRow
self.numCol = numCol
def generateRandom(self, numColors, dotsPerColor):
''' generate random positions of color dots '''
#np.random.seed(100)
dots = []
for c in range(1,numColors+1):
for d in range(0, dotsPerColor):
done = False
while not done:
row = np.random.randint(0, self.numRow)
col = np.random.randint(0, self.numCol)
if self.map[row, col] == 0:
self.map[row, col] = c
done = True
def neighbors(self, pos, include=[0]):
''' return neigbors of position pos marked with colors listed in include '''
pos = np.array(pos)
neig = []
for npos in [pos+[0,1], pos+[1,0], pos+[-1,0], pos+[0,-1]]:
if npos[0] in range(0, self.numRow) and npos[1] in range(0, self.numCol):
if any(np.array(include) == self.map[tuple(npos)]): # check with valid neigbor color
neig.append(tuple(npos))
return neig
Defining path structure
The first problem is to create a way to represent paths starting from a color dot. It may end on a dead end, or end by connecting a matching color dot. Below I defined a node class to represent a point of a path. If more than one of it’s neighbor is empty, the path can take any of them as the next step. So the node class can have a number of children, which are also nodes, as it’s next steps.
class node():
''' data structure for tree nodes '''
def __init__(self, value, children = None, parent = None):
self.value = value # coordinate tuple
if children is None:
self.children = list()
else:
self.children = list(children) # list of nodes
self.parent = parent # a node or None if head node
def addChild(self, child):
self.children.append(child)
##Getting paths
As my first shot, I consider a “brute force” approach that finds all possible paths starting from a color dot. It always considers the initial map with only color dots, i.e. without any spots ocuppied by any paths. Starting from a color dot, a path can either end on a dead end, or end by connecting another matching color dot. As you can imagine, almost always there are more than 1 paths that can connect two matching color dots, especially when you consider the fact that we are acting on the initial empty game map.
The walk function generates all possible paths from a color dot. It first create a head node designating the position of the starting color dot. It then populates the next possible moves as it’s child nodes. The process repeats recursively until all possible paths are found. It other words, it generates a tree for all possible paths.
The getPaths function generates a list of paths, in the form of series of coordinates, from the tree generated by the walk function.
If we do the walk and getPaths functions for all colors, we would find a set of all possible paths for each color. By comparing them, we will be able to a solution that connects all matching dots while filling up all the empty spots, if that solution ever exists.
def walk(current_node, graph, endColor):
''' recursively walk on the graph to create a tree at ends either at dead end or endColor'''
for next in graph.neighbors(current_node.value, include=[0, endColor]):
if not visited(next, current_node):
next_node = node(next, parent=current_node)
current_node.addChild(next_node)
if graph.map[next] != endColor:
walk(next_node, graph, endColor)
def visited(position, current_node):
''' trace back from current node to head. return True if position is visited '''
n = current_node
while n.parent is not None:
n = n.parent
if n.value == position:
return True
return False
def getPaths(node, endColor, graph, paths = None, path = None):
'''
Return all paths starting from node that ends at endColor.
Usage: paths = getPaths(head_node, endColor, graph)
'''
if paths is None: paths = list()
if path is None: path = list()
path.append(node.value)
if graph.map[node.value] == endColor and node.parent is not None:
paths.append(path) # record path ends at the right color
for child in node.children:
getPaths(child, endColor, graph, paths, list(path)) # list(path) to create new copy of path
return paths
def getPathsAllColor(graph):
'''
Get all possible paths from all color dots.
Return as dictionary of colors
'''
paths = {}
for color in np.unique(graph.map):
if color != 0:
pos = np.argwhere(graph.map==color)
start = tuple(pos[0])
head_node = node(start)
walk(head_node, graph, color)
paths[color] = getPaths(head_node,color, graph)
return paths
def checkPaths(paths, graph):
m = np.zeros(graph.map.shape, dtype='bool')
for p in paths:
for pos in p:
if m[pos] == False:
m[pos] = True
else:
return False
if m.all():
return True
else:
return False
def showPath(p, graph):
mm = np.array(graph.map)
for c in range(len(p)):
for pos in p[c]:
mm[pos] = c+1
print mm
import itertools
def solve_bruteForce(paths, graph):
for p in itertools.product( *(paths[key] for key in paths) ):
if checkPaths(p, graph):
yield p
##An example
Here’s an example I took out from the game. I first reproduce the 5-by-5 game map. There are 5 pairs of color dots, represented by number 1 to 5.
graph = Graph(5,5)
graph.map[2,0] = 1
graph.map[0,2] = 1
graph.map[4,0] = 2
graph.map[0,3] = 2
graph.map[0,4] = 3
graph.map[3,4] = 3
graph.map[3,3] = 4
graph.map[4,4] = 4
graph.map[4,1] = 5
graph.map[2,3] = 5
print graph.map
Output:
[[0 0 1 2 3]
[0 0 0 0 0]
[1 0 0 5 0]
[0 0 0 4 3]
[2 5 0 0 4]]
Then we use getPathsAllColor function to get all possible paths for all colors, and use solve_bruteForce generator function to find a soluton.
paths = getPathsAllColor(graph) # find all possible paths for all colors
p = solve_bruteForce(paths, graph) # solution generator
showPath(p.next(), graph)
Output:
[[1 1 1 2 3]
[1 2 2 2 3]
[1 2 5 5 3]
[2 2 5 4 3]
[2 5 5 4 4]]
Another example:
graph = Graph(6,6)
graph.map[0,0] = 1
graph.map[1,2] = 1
graph.map[1,0] = 2
graph.map[1,3] = 2
graph.map[0,2] = 3
graph.map[4,3] = 3
graph.map[3,1] = 4
graph.map[4,4] = 4
graph.map[3,2] = 5
graph.map[4,1] = 5
graph.map[0,5] = 6
graph.map[5,5] = 6
print graph.map
Output:
[[1 0 3 0 0 6]
[2 0 1 2 0 0]
[0 0 0 0 0 0]
[0 4 5 0 0 0]
[0 5 0 3 4 0]
[0 0 0 0 0 6]]
paths = getPathsAllColor(graph) # find all possible paths for all colors
p = solve_bruteForce(paths, graph) # solution generator
showPath(p.next(), graph)
Output:
[[1 1 3 3 3 6]
[2 1 1 2 3 6]
[2 2 2 2 3 6]
[4 4 5 3 3 6]
[4 5 5 3 4 6]
[4 4 4 4 4 6]]
Final thoughts
Although it works, the brute force search approach is pretty slow. It would be interesting to find other search methods to improve speed.
The code-based method to construct the game map is not user-friendly. Some kind of GUI would be a great improvement.
Another drawback is that this program does not work when there are more than 1 pair of color dots with the same color.