Simple way to remove duplicated tiles to improve performance

[loic-brtd]

Hi :smiley: We can write a function to get only the unique tiles in an array :

function removeDuplicatedTiles(tiles) {
  const uniqueTilesMap = {};
  for (const tile of tiles) {
    const key = tile.edges.join(","); // ex: "ABB,BCB,BBA,AAA"
    uniqueTilesMap[key] = tile;
  }
  return Object.values(uniqueTilesMap);
}

So we can apply rotations to all the tiles and then keep only the unique ones :

const initialTileCount = tiles.length;
for (let i = 0; i < initialTileCount; i++) {
  for (let j = 1; j < 4; j++) {
    tiles.push(tiles[i].rotate(j));
  }
}
tiles = removeDuplicatedTiles(tiles);

In our case, we have 13 images. By rotating all of them, we get 52. And by removing the duplicates, we get down to 33.

On my PC, the generation time goes from 23s to 14s :rocket:

[shiffman]

Oh, this is fantastic!!! I usually like the keep the code identical to the video (but maybe I can add something about this to the video!). Regardless, I think this is worth putting in there with comments explaining it's an optimization added after the fact. Would you like to pull request it or shall I add it myself?

[loic-brtd]

I made a pull request, you can modify the code I added as you wish :) If you prefer to write/copy-paste this code yourself during a stream, you can too, I don't mind at all 😄

Choo choo 🚂

[MrAmericanMike]

Wouldn't this fail when 2 tiles have the exact same edges by overwriting the already existing key?

For example, tiles 6 and 12 share the same edges.

[loic-brtd]

@MrAmericanMike Oh you're absolutely right!

For this deduplication technique to be correct, we would have to store the image number (or filename) in each Tile, and then concatenate it to the key in the removeDuplicatedTiles function.

But then it's not a trivial change anymore to make to the existing code ^^

[shiffman]

Couldn't we just check for duplicates amongst the 4 rotations of each tile? So make a little array of 4, remove duplicates, and then add what is remaining to the final tiles array?

[loic-brtd]

@shiffman Great idea! I implemented this solution in PR #25 (but you can implement it yourself if you want).

I noticed that this also fixes an error in the original code :

  tiles[11] = new Tile(tileImages[11], ["BCB", "BCB", "BBB", "BBB"]);
  tiles[12] = new Tile(tileImages[12], ["BBB", "BCB", "BBB", "BCB"]);

  for (let i = 2; i < 14; i++) {
    for (let j = 1; j < 4; j++) {
      tiles.push(tiles[i].rotate(j));
    }
  }

The initial tiles are indexed from 0 to 12, but the loop was going up to index 13.