Automatic sticky block clustering.

[magnus-ISU]

I am aware that this problem is NP-complete but at this size it can hopefully be either bruteforced or at least solved with some dynamic programming. Algorithmic geniuses and their PRs are welcome.

It can certainly be solved; if a human can manually do it by looking at it for 10 minutes or so, there should be some sort of greedy algorithm that should work with near-100% efficiency; I can start thinking about it now.

It is ProjectGeode() which should be modified to place slime, honey, and mob heads right? I guess seems to be the way to reuse the existing functionality as much as possible?

[magnus-ISU]

Or I suppose, ProjectGeode should be left untouched but somehow modified so the information about each slice can be passed to a new function. As #4 notes ProjectGeode could be modified in the future to be more intelligent.

[qgustavor]

I'm trying to work the logic of it. I made a simplified GUI in JavaScript since it's what I know and because it's possible to work in browser without requiring Minecraft or something similar. Using the test framework below seems better.

[spencer3035]

I'm also working through this. I made a simple java test repo here https://github.com/spencer3035/slime_honey_placer

[MLFlexer]

Could not stop myself from giving a cluster algorithm a try on "paper".

I think this should work, altough i would probably need some preprocessing to get rid of edge cases + it does not force having space for the flying machines (L-shapes)

The idea is clustering the nodes based on progressivly larger Images kernels: https://setosa.io/ev/image-kernels/ And using a shortest path algorithm to connect nodes within the kernels, with some restrictions that a cluster cannot become bigger than 12 with the addition of the new node + path to the node.

I have only tried it on the problem below, and havent given it much more though than this, but it might be a starting point / inspiration for you guys :D (very small image, attached)

[palani-johnson]

I was bored so i worked on the problem a little. Not sure if this will help anyone but i managed an ok clustering algorithm that works to generate sensible clusters. https://github.com/palani-johnson/clusters/blob/main/clusters.py.

Edit: Some more content while I have a little time. Ill test and refine this tomorrow but currently the algorithm is pretty good at finding clusters, but no checks are performed for valid configurations. In its current form the algorithm always generates the same clusters but with some noise i can have it generate a new configuration every time. Tomorrow I want to add in the validation functionality and the ability to retry if a configuration is invalid. I can assist in translating this over to Java if needed. Python is just easier for me to script in.

[kosma]

Python is absolutely fine, we can translate to Java once the algorithm has been polished out.

[MLFlexer]

I have made a solution that is by no means perfect as it can cluster somewhat well (Clusters attached), but does not take into account that 2 honey or slime clusters cannot be placed side by side, or that the L-shapes are needed for the flying machines. Feel free to copy/continue the work on this: https://github.com/MLFlexer/MatrixClustering/blob/main/Cluster.java

[Dragon-Hatcher]

I have made a test framework to evalute everyone's solutions so we can see empiracly which perform best. It generates random amethyst clusters in a way quite similar to how the game does it and then test each algorithm on 100 of those random clusters.

So far I have implemented palani-johnson and MLFlexer's algorithms.

Feel free to fork/make pull requests to evaluate any algorithms you come up with. I may work on my own algorithm soon.

https://github.com/Dragon-Hatcher/amethyst-clustering

Currently MLFlexer's algorithm performs best. Harvesting an average of ~6.8 amethyst per group.

[kosma]

I've created a Discord server to make discussion easier, feel free to join:

https://discord.gg/Kg9NkbdjQB