0
\$\begingroup\$

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.

  1. Tile needs to be adjacent to the previous tile, e.g. directly above, below, to the left or to the right.
  2. Tile cannot be on the list of already selected tiles.
  3. User must select at least two tiles, up to a maxium of the whole board.
  4. 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:

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.

First five levels of position 5

\$\endgroup\$
  • \$\begingroup\$ Hi ! I have some clue about what you could do but i'm not sure I understand everything. Does the game goes like this : 1. Player chose a tile 2. Player now can only chose a tile adjacent to the previous tile (except if the adjacent tile has already been picked) 3. And so on.. So there is only ONE path the whole game right ? \$\endgroup\$ – Sebastien Servouze Jan 11 '18 at 16:44
  • \$\begingroup\$ Is the path itself important? Your selection rules seem like they only care about the current state of the board. Would it not be sufficient to maintain the 5x5 board with selection state, and maintain the most recent selection? (i.e., each step, check neighbors of previous move. If any are open, there are moves remaining.) \$\endgroup\$ – Chris Mills-Price Jan 11 '18 at 18:54
  • \$\begingroup\$ @SebastienServouze You are correct in that the player first select a tile, then another adjacent tile. The player can select as many tiles as he/she wants, but a minimum of two, and not a previously selected tile. The player can also deselect all tiles and start over. There can however be multiple paths. It is a numbers-based-game, so for each selection, it will do a calculation based on those tiles, and if the tiles selected matches that algorithm, the player gets some points. \$\endgroup\$ – Runar Jan 12 '18 at 14:53
  • \$\begingroup\$ @ChrisMills-Price , since this is a feature to automatically check if there are any possible moves/calculations on the board, it would need to check every combination of possible tiles. \$\endgroup\$ – Runar Jan 12 '18 at 14:55
1
\$\begingroup\$

So my best attempt would be something like this :

  1. Initialize a x per y array, let's call it map.
  2. Let the player chose an authorized path following your neighbour rules.
  3. Keep the choosen tiles in memory in another array, let's call this one path.
  4. Once the path is valided, remove all the path tiles from map so you don't have to care about them anymore.
  5. Clear path array.
  6. Check if at least two tiles can be chose by running a simple loop on map array which breaks if a pair is found. This way you don't have to iterate through all possibilities, only one is enough for the game to go on.
  7. If a pair exists, go back to step 2, if not, it's game over.

This induces the following behavior : The more tiles in map array, the more possible combinations exists, the quicker it is for the algorithm to find at least one possible combinations. The less tiles in map array, the less possible combinations exists, maybe even none ! But if less tiles exists, less imaginable combinations are possible.

I let you think about the mathematical function that can compute if two tiles are neighboured or not, i guess you already have it ;)

Hope it helps

\$\endgroup\$
  • \$\begingroup\$ I may not have been clear enough. The game itself is working, the player can already select a path, and get points if the path is correct. The point number 6 here is what I need. However, since on game over it will have to check all combinations. To speed this up, since there are lots of combinations to check, I need to add a cache of all combinations. \$\endgroup\$ – Runar Jan 12 '18 at 15:18
  • \$\begingroup\$ Hmmm... You don't have to compute all combinations. Every time a path is valided, number of tiles in map array is reduced, also reducing the number of possible combinations. If a big amount of tiles are in map array, more possible combinations exists, but you just need to find one, so it's pretty quick. If a little amount of tiles are in map array, not a lot of possible combinations exists, maybe even none. But since there is a little number of tiles, you don't have to check a lot of combinations. What i'm saying is that you might not need to cache of all combinations ! \$\endgroup\$ – Sebastien Servouze Jan 12 '18 at 15:27
  • \$\begingroup\$ yup, I understand what you are saying. The function will not even run unless the board is filled up with tiles everywhere, and most times, it will not calculate all combinations, since it can exit early on many paths. However, in cases where the board is layed up in a way that very few paths can be exited early, and therefore it will have to check a lot of them, it is important to keep that function as fast as possible. It will be a lot faster to check if there is a cache than not. If no cache is used, it will have to generate all combinations on the fly AND verify them. \$\endgroup\$ – Runar Jan 12 '18 at 15:39
  • 1
    \$\begingroup\$ Yeah i get it, the thing is, you don't need to compute all imaginable combinations, you just need to compute imaginable tile's pair, not all imaginable full paths. A x > 2 tiles path exists only if at least a 2 tiles path exists. Therefore you only need to compute 2 tiles possible paths. If you want to cache theses combinations, nothing stop you from computing every 2 tiles path at the beggining of the game and delete those minimal possible paths each time a path containing one of the two tiles is valided. \$\endgroup\$ – Sebastien Servouze Jan 12 '18 at 15:54
1
\$\begingroup\$

I figured out a way to do this. There might be more effective ways, but it works. It now generates first an array of all possible combinations, and then creates a nested object from that.

From this I generated two files, to compare sizes. The array is now huge, at 80 MB (7.8 MB compressed), while the nested object is 8.4 MB (424 KB), a reduction of almost 90%.

// 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 getCombinationsForPosition = (position) => {
  const getAllNeighbours = (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)
      paths.push(path)
      for (const neighbour of neighbours) {
        const p = [...path, neighbour]
        getAllNeighbours(p[p.length -1 ], p)
      }
      }

  getAllNeighbours(position, [position])
}

function assign(obj, prop) {
    if (prop.length > 1) {
        var e = prop.shift();
        assign(obj[e] = Object.prototype.toString.call(obj[e]) === "[object Object]" ? obj[e] : {},
               prop);
    } else
        obj[prop[0]] = -1;
}

const length = neighboursArray.length
const paths = []
const nesty = {}

for (var i = 0; i < length; i++) {
  getCombinationsForPosition(i)
}
paths.map(path => assign(nesty, [...path]))

const sorted = paths.sort((a,b) => a.length - b.length)
while (sorted[0].length < 2) {
  sorted.shift()
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.