CODEWITHSUNDEEP
javaalgorithm
nick voorham
nick voorham

Reputation: 9

How can I create an algorithm that optimizes/combines tiles in a tileset

My problem is that I can't entirely figure out how to make an algorithm that combines tiles to create one tile. Maybe these pictures that I made in ms paint will help you to get an idea for what I mean.

The idea that I have is that there is a loop that goes over every single tile and creates a correlation when there is another tile like it. Illustrated below.

https://i.sstatic.net/ID0KL.png

And the expected result from this unknown algorithm should be:

https://i.sstatic.net/hcsLP.png

For clarification, every tile has an x, y, w, h, and sprite which is currently a string directory which is bound to change.

Though I would like to hear the theory behind this. The code is not important for me. Thanks in advance.

class Tile {

  float x, y, w, h;
  String sprite;

  Tile(float x, float y, float w, float h, String sprite) {
    // here be the initiating.
  }

}

The result should combine tiles which are the same to increase performance loading the tiles. It is also fun to think of this and try to solve this problem. Thank you for this in advance.

Good luck and have a nice day!

Added information:

Lets say there is a 3 x 3 grid. How could you couple as many colors of the same type together so that there are the least amount of couples in there.

https://i.sstatic.net/mdIwE.png

That would be:

https://i.sstatic.net/y12UP.png

Now what if it were a 13 x 5 grid?

https://i.sstatic.net/3neac.png

I would like an algorithm to solve this for me, though I can not figure one out.

Summary: Create the least amount of couples in a grid with different tiles. And have the most amount of tiles residing in the objects.

Upvotes: 0

Views: 171

Answers (1)

Ovidiu Nicolae Tuca
Ovidiu Nicolae Tuca

Reputation: 11

I am pretty new here as well, so please do not judge my answer too harshly…

Here is my solution in a descriptive manner:

Step 1:

We detect each individual blob (where blob is a connected mass of tiles that share the same color). This can be done efficiently with a dictionary/hashtable.

Step 2 (greedy algorithm):

We then run the following process over each blob. We split it into lines once horizontally and once vertically.

If two consecutive lines are “aligned” and have the same length, they are joined to make a bigger tile and the process then repeats.

If the next line does not match this criteria, then then we return the lines gathered so far as a tile.

At the end we will have two possible results for the tile distribution.

Step 3:

We compare the output of the horizontal scan with the output of the vertical scan. Whichever one yielded the least amount of tiles is treated as the final result.

I believe obtaining the best result with dynamic programming is also an option, however it would take too long and defeat the whole purpose (unless I am missing something).

Upvotes: 1

Related Questions