HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to evaluate all possible groups of adjacent tiles in 2D array?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
adjacentgroupshowallarraytilespossibleevaluate

Problem

I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain goal number, for example 5 or 7 or 9.

However, I'm stuck on the algorithm to detect these sum groups. I know how to do a flood fill algorithm using recursion to detect a group of adjacent tiles, like in the same game. But I don't know how to iterate through all the possible permutations of possible groups, and what is the best way to approach this?

Because the problem is that adjacent tiles form a group, but within that group of tiles there are many possibilities for sub groups. See tiles example below

Tile letters     Contains numbers    Represented as graph
+---+---+---+    +---+---+---+
| A | B | C |    | 1 | 5 | 2 |       1---5---2
+---+---+---+    +---+---+---+       |   |
| D | E | . |    | 2 | 1 | . |       2---1
+---+---+---+    +---+---+---+       |
| F | . | . |    | 4 | . | . |       4
+---+---+---+    +---+---+---+


So the group is all the tiles A though F, and a subgroup could be A, B and E (1+5+1) but also A, D and F (1+2+4). But A, C and F is not a possible group because those tiles are not adjacent. I suspect it could maybe be approached like it's a graph problem. But then I still don't know how to handle the many possible circular nodes.

So my question is; How to systematically go through and evaluate all possible permutations? Is there an algorithm for something like this? Or can someone explain how to approach this problem?

EDIT:
I've put my code in the jsfiddle in the link below. It uses flood fill from a starting tile, in the example tile with nr 2. Then for each cell it counts to 15 and uses the bits of that counter to flood-fill to the 4 adjacent tiles (up,down,left,right). However it doesn't work properly because it doesn't consider branching paths. For example, in the jsfiddle example the combination 3-2-4 is never evaluated.
https

Solution

I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$. The initial state has the empty set $\emptyset$, and it can transition to any state containing a single tile.

Then, use a search algorithm, such a depth-first search or breadth-first search, to explore all states reachable from the initial state. You can store the reachable states in a hashtable. Whenever you discover a new reachable state, check if the numbers on its tiles sum to 7. If they do, you have found a valid solution.

As an optimization, you can use flood-fill to find all of the groups (connected components), then apply the above algorithm separately to each group.

Context

StackExchange Computer Science Q#115405, answer score: 3

Revisions (0)

No revisions yet.