I have set out on a quest to conquer the super addictive Android game Jewels Star. The goal is to get 3 stars in all levels of the game. I have decided to take the help of a few Computer Science disciplines.
- Install Jewels Star apk on an Android emulator
- Use java.awt.robot to capture screenshots and move jewels around
- Store each cell's rgb value. Currently I'm only storing the rgb value of the center point but if this isn't accurate enough, I can use rgb values from more regions of the cell (more on that later).
- Use k-means clustering to figure out which class each cell belongs to.
- Figure out which cells to move based on the classes. I think DFS will work but I haven't figured out the exact mechanism yet. Btw, this would be a cool Google Code Jam problem.
- Once the above is done, I will have a rudimentary algorithm to solve simple puzzles. This method will eventually fail as specialized cells start to appear in later levels (such as "frozen" cells, empty cells, "destroyer" jewels, lightning jewels, etc).
- Finding "k". This is the classic problem when using k-means clustering. How do you know what k is? I can always try different values of k and evaluate the clusters to see which produces the best result. Although I'm not sure how accurate this strategy will be if, for example, there is only 1 cell with a specific jewel on the board. I have a feeling there is another algorithm that's better suited for this.