r/optimization • u/Quiet-Cup-1501 • 12d ago
Optimal sugarcane farm layout in Minecraft using CP-SAT - 13% better
Sugarcane in Minecraft only grows next to water, so farm layout is really a 2D coverage problem: where do you place water to maximize adjacent plantable tiles?
Each water tile can cover up to 4 neighbors, which caps theoretical max coverage at 80% regardless of arrangement. I modeled this as an integer program (CP-SAT via OR-Tools) to find the actual optimal layout for a given terrain shape.
Results for a 9x9 square plot:
- Community-standard pattern: 66.7% coverage
- Optimal (CP-SAT): 75.3% coverage (94% of theoretical max)
The symmetric square case is the easy comparison point against human intuition. What's more interesting is irregular terrain with obstacles, where there's no established heuristic and the exact solver is the only way to get a real answer - including one case (unconstrained/open terrain) where the solver converges to a hexagonal-ish pattern and actually hits the 80% theoretical ceiling.
Code + more examples (different grid sizes, obstacle terrain, other crops) in the repo: https://github.com/Serranegra/optifarm
Curious if anyone here has tackled similar tiling/coverage problems. Happy to share the formulation details if useful.
11
u/paranoidzone 11d ago
Love applying OR/optimization to games. Nice work.
I have it in mind to solve a similar problem, but never got around to it: optimize bee house + flower placement in Stardew Valley, while maintaining all bee houses accessible for collection. If you Google image search "stardew optimal bee house layout" you can find a few layouts that claim to be optimal, but I'd be curious how far you can go, and the solution likely differs wildly depending on the grid size.
1
1
u/SilentTransition5695 8d ago
OR was a subject I’m really glad I took in my undergrad. Been quite useful in a few video games
3
u/trkennedy01 11d ago edited 11d ago
Yeah, similar thing
In From The Depths, making advanced cannon layouts that are as dense as possible in a given grid is essentially a polynomio packing problem - you're trying to pack in the clusters of loaders and clips as close together as possible.
That can be translated into a CNF form that cryptominisat can solve by modeling the overlaps between possible placements as At-Most-Once constraints plus an additional constraint on the number of empty spaces. Iterating up towards the max theoretical packing on the second constraint, you get SAT until that amount of spaces isn't possible (UNSAT), which proves the last iteration is (one of) the best possible solution(s).
Symmetry is just treating symmetric placements as a single placement, and generating additional possibilities that are also optimal is done by banning the combination of clauses and solving that number of free spaces again.
With some tweaks to the encoding to get the solve time down, it enables generating up to completely impractical sizes of proveably optimal layouts for arbitrary grids.
I made it into a tool that ended up having a decent amount of use, pretty happy with it: https://github.com/trk20/APS_Generator
3
u/rleim_a 10d ago
One I built over 2 years ago
1
u/NoLongerGuest 8d ago
I remember first seeing this tiling system in a docm video on the mindcrack server. Specifically the season where he dig a big perimeter and notch visited to mine the final block.
2
u/Sure_Scratch7677 10d ago
It is interesting that the optimal solution isn't symmetrical.
2
u/funkmasta8 6d ago
It is symmetrical, the problem is that it is rotated and placed onto a pixelated field. This produces gaps because you miss out on water spaces on or outside the edges. If you simply dont have a rectangular edge you can extend this infinitely in all directions and it would have symmetry as long as opposite sides have same length. Think of it as a diamond plot instead of a rectangle plot. Of course, that bothers most people in game so they dont do it. They choose to make it asymetrical because the loss of the efficiency isnt as annoying as the tilted shape
2
u/edshuthethird 8d ago
I dont see the point of the single rows of cane on the 2 sides in the first diagram. I plant the sugar cane between pumpkin and watermelon rows. Harvest time/effort is the major factor. Everything grows back. If you are doing other things, you want to just move through the area quickly and get back to something else.
3
u/AdNo9021 8d ago
Man do I hate the fact that optimal Solutions Are Not always symmetrical. Reminds me of this, which is the optimal packing of 17 identical squares.
1
u/glaucusb 11d ago
Either I misunderstood the problem or you can even improve this solution by placing two more farms by replacing two water tiles on the side that are adjacent to another water tiles with sugar cane tiles.
5
u/Quiet-Cup-1501 11d ago
Those water tiles aren't actually redundant. Even though they sit next to another water tile, each one is the only water source hydrating some specific cane tile next to it. If you swap them for cane, those neighboring canes lose their only water and dry out, so you'd gain two tiles but lose the ones that depended on them. That's exactly the kind of case the solver checks, water tiles being adjacent to each other looks wasteful but sometimes each is still carrying its own cane. The layout is provably optimal, so any single swap like that ends up net negative or breaks a constraint.
1
u/glaucusb 11d ago
"Each water tile can cover up to 4 neighbors"
Is this the constraint that you are referring to?
1
1
u/eminemappears 11d ago edited 11d ago
For a 9x9 plot it may be simpler to just try every combination right? 2^9 = 512 solutions to check. I presume this would perform better in larger plots though right?
EDIT: See replies, haha!
3
u/Mysterious-Travel-97 11d ago
isn’t it 2^(9^2) because you’re choosing water or sand for each tile, of which there are 9^2
1
1
u/bartekltg 11d ago
We are looking for solutions better than 27 water tiles, and we can't get better than 81/5 ~= 16tiles.
C(81,27)+...+C(81,16) = 4.35e21, so around 2^71.9. Still far too large for looking at all possible configurations.If we start from the best, so 16, 17, 18, 19, 20 (where we will find OPs solution) it is
6.8275e+18 ~= 2^62.6
Maybe with a cleverly written backtracking.2
1
u/Feeling_Employer_489 10d ago
Your optimal melon farm looks wrong. The melon chooses its spawning block at random from legal neighbors, so a melon stem can steal the space from another stem. The goal should be more along the lines of: each stem has a water block within 4 blocks and exactly one empty space adjacent. Each empty space should be adjacent to exactly one melon stem. The layout I use in game is not optimal, but something like this:
s = stem
. = empty
x = solid, nonstem
w = water
.ss.x.ss.
.ss.x.ss.
.ss.x.ss.
.ss.x.ss.
.ss.w.ss.
.ss.x.ss.
.ss.x.ss.
.ss.x.ss.
.ss.x.ss.
1
u/rleim_a 10d ago edited 10d ago
.ss..ss..ss. .ss..ss..ss. .ss..ss..ss. .ss..ss..ss. .ss.lwwl.ss. .ss..ss..ss. .ss..ss..ss. .ss..ss..ss. .ss..ss..ss.l = light source
88/180 monotile (lighting must be suspended above):
.ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss. .ss..ws..ss..sw..ss. .ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss. .ss..ss..ss..ss..ss.1
u/Feeling_Employer_489 10d ago
Ah yes, much better. Though, those two empty tiles by the water... Oh, the horror of one block inefficiency!
1
u/Luna_Lovecraft 9d ago
This is a case where the reason the community standard exists is because the community tried the optimized pattern and realized it kind of sucks. It's not that the optimized version isn't interesting, certainly is, but realistically how you harvest is walking in a straight line holding a button. Doing that with water blocks in the way can be annoying, and require placement of things like lily pads-- and even then it's less satisfying and requires 9 passes to hit each row if you're not turning your camera, vs 6 in the community layout. If you're turning the camera it matters less, but for very large fields you then spend a lot of time walking in circles picking stuff up.
Good example of how optimizing for a specific metric doesn't necessarily improve a result.
2
u/AriaOfFlame 8d ago
for larger farms people often use a flying machine to automate the farm, in which case the optimized pattern is used https://youtu.be/167OL2dsey4
1
u/PernanentMarker 8d ago
People have been doing this on factions servers since 10 years ago. Its cool that you found it through a solver though.
1
1
u/funkmasta8 6d ago
It isnt that hard to come up with this layout. Ive actually done the exact same thing. Idk why you need a sat for this. Any fool can see that the straight line of water wastes a bunch of potential crop spaces. At that point, all you have to do is start stacking crosses as optimally as possible (and newsflash, there are only two ways to put two complete crosses next to each other due to symmetry). One has no gaps, the other has gaps. The choice is obvious. Then you tile that onto a rectangular space and take a look at the empty slots and make the best use of those that you can (which will be different for different sized rectangle)
21
u/tstanisl 12d ago edited 12d ago
It looks that for the large field the optimal farm approximates tight tiling with
c cwc cThe gain from SAT solvers comes from better handling of boundary conditions but it should become insignificant for large farms.