snippetMinor
How to evaluate all possible groups of adjacent tiles in 2D array?
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
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
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.
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.