Recursively get all combinations of tiles
For a game, I need to calculate all possible combinations of a set of a grid in a 5x5-grid and do some calculations on these.
Some combinations of tiles will match a certain algorithm, which is not important for this part of the code, and if it matches, the player will get some points.
To check if the game is over, a very expensive recursive function needs to run which will check all possible combinations. If it doesn't find one, the game is over.
To speed this up, I need to create a cache of all the possible combinations.
What I am asking for help about is how to create a nested list of all combinations, following the Rules for selection below.
This will be used to check if the game is over.
Rules for selection.
- Tile needs to be adjacent to the previous tile, e.g. directly above, below, to the left or to the right.
- Tile cannot be on the list of already selected tiles.
- User must select at least two tiles, up to a maxium of the whole board.
- If the user selects a different tile, the selection will be cleared, and the user can start over selecting a different tile.
Goal of selection
This is a numbers-based game, where the goal is to combine some tiles, that together will "add up" to the last selected tile.
I will not go into the details of the algorithm here, so I will use an example of a basic addition-algorithm.
For instance, let's say that the board is like the screenshot below. Here, the user could select tile 1, 2
, and then 3
, and since 1+2=3, the user would get some points. Another example would be selecting 3, 2, 7, 12
, since 3 + 2 + 7 = 12
Checking for game over.
Now, I would like to add a function which checks if there are any possible moves left, and this would basically need to check every combination of tiles. Since this is very exhaustive, I was thinking of creating a nested list of possible combinations ahead of time, and then while the user is playing it would check those combinations.
Example grid:
A valid selection above would be 0, 1, 6, 7
, but 0, 10
(rule 1), 0, 5, 0
(rule 2) is not valid.
What I've tried.
I've tried to create a recursive function, but keeping track of the current path while creating a nested path seems to be very difficult.
I've therefore extracted the relevant code of what I've tried. This is for a grid of 5x5.
EDIT: Code now returns a flat list of combinations, however it doesn't actually get them all.
A flat list would be huge, since it repeats the data quite often:
[
[
0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
22, 23, 18, 13, 8, 3, 4, 9, 14, 19, 24
],
[
0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
22, 23, 18, 13, 8, 3, 9, 4
],
[
0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
22, 23, 18, 13, 8, 3, 9, 4, 14, 19, 24
],
[
0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
22, 23, 18, 13, 8, 14, 9, 4, 3
],
[
0, 5, 10, 15, 20, 21, 16, 11, 6, 1, 2, 7, 12, 17,
22, 23, 18, 13, 8, 14, 9, 19, 24
],
...(3473 more objects)
]
It would be a lot better if I could nest these into an object.
Current code
// A list of all neighbours. I've just inlined it here, since my actual functions for creating it are inside an object.
const neighboursArray = [[5, 1], [6, 2], [7, 1, 3], [8, 2, 4], [9, 3], [10, 6], [1, 11, 5, 7], [2, 12, 6, 8], [3, 13, 7, 9], [4, 14, 8], [5, 15, 11], [6, 16, 10, 12], [7, 17, 11, 13], [8, 18, 12, 14], [9, 19, 13], [10, 20, 16], [11, 21, 15, 17], [12, 22, 16, 18], [13, 23, 17, 19], [14, 24, 18], [15, 21], [16, 20, 22], [17, 21, 23], [18, 22, 24], [19, 23], [20]]
const nested = (position) => {
const paths = []
const getAllNeighbours = (pos, path) => {
// console.log('checking', pos, path)
// Lookup neighbours for this pos
const neighbours = neighboursArray[pos]
// Make sure neighbours are not in list of already selected path.
.filter((tile) => path.indexOf(tile) < 0)
if (neighbours.length === 0) {
paths.push(path)
}
for (const neighbour of neighbours) {
path = [...path, neighbour]
getAllNeighbours(path[path.length -1 ], path)
}
}
getAllNeighbours(position, [position])
return [paths]
}
Example of output
I've created part of the tree-structure visually for position 0. As you can see, nodes can have 0-3 children (the first can have 4 children), up to 24 levels deep for a 5x5-grid. The deeper the level, it tends to have fewer children as there would be less possibilities available.