为Minecraft中的物品组合优化,使用约束满足。
Constraint satisfaction to optimize item selection for bundles in Minecraft

原始链接: https://www.robw.fyi/2025/10/12/using-constraint-satisfaction-to-optimize-item-selection-for-bundles-in-minecraft/

受一篇强调MiniZinc易用性的博文启发,作者启动了一个项目,利用约束满足来优化Minecraft的物品栏空间。Minecraft玩家面临有限的物品栏格子,而捆绑包提供了一种整合物品的解决方案,但选择*哪些*物品捆绑至关重要。 作者在MiniZinc中模拟了玩家的物品栏,最初专注于完整的堆叠,然后扩展到处理不同的堆叠大小(64、16和不可堆叠)。解决方案的核心在于定义一个代表物品栏格子的数组,并使用约束来最大化所选格子的数量,同时保持在捆绑包的容量范围内。 实施了一个缩放系统,将捆绑包成本表示为整数,避免小数。最终的模型成功地识别出最大化捆绑包利用率的最佳物品组合,展示了MiniZinc在解决实用、游戏相关的优化问题方面的强大功能。作者发现MiniZinc的声明式方法和Playground的易用性使其成为学习和应用约束满足的令人惊讶的有效工具。

黑客新闻 新的 | 过去的 | 评论 | 提问 | 展示 | 工作 | 提交 登录 约束满足用于优化 Minecraft 捆绑包中的物品选择 (robw.fyi) 5 分,someguy101010,1 小时前 | 隐藏 | 过去的 | 收藏 | 讨论 考虑申请 YC 2026 冬季批次!申请截止至 11 月 10 日 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请 YC | 联系 搜索:
相关文章

原文

I read a blog post on how Many Hard Leetcode Problems are Easy Constraint Problems and was pleasantly surprised at how approachable MiniZinc was compared to other solver software I have been exposed to, and the examples given helped me to understand how to apply it to a domain I was already familiar with. I have always wanted to be able to get more familiar with using constraint satisfaction as a way to solve problems, so I decided to create a solver to help optimize storage space for Minecraft using constraint satisfaction to help learn how to use this tool. I will outline my thought process and how I reached the solution I came up with.

Game Mechanics

In Minecraft, your player inventory is limited. You have 27 inventory slots, 9 hotbar slots, 4 armor slots, 4 temporary crafting slots, 1 offhand slot, and 1 temporary slot for the result of crafting.

Each slot can either contain a single item, a small stack of 16, or a full stack of 64 items, depending on the item.

Often when adventuring, you will come across many rare and powerful items and accumulate many items in your inventory slots, but they may be stacks of items that are not at maximum capacity for that inventory slot. Once your inventory is full, you cannot pick up new items. Using bundles, you can consolidate your inventory and pick up more items.

bundle is an item that can store up to a stack’s worth of mixed item types within itself in a single inventory slot. Items can be individually selected and taken out of the bundle via the inventory menu.

Item stack sizes (top row) and the number of bundle slots they take up (middle row). Sticks stack to 64, so they take up one bundle slot; ender pearls stack to 16, so they take up four; and swords do not stack, so they take up the whole bundle. So, for instance, a bundle may have 32 sticks and 8 ender pearls inside, which take up a total of (32×1)+(8×4)=64 bundle slots.

Creating an Optimizer

Using the MiniZinc Playground, we can model our player’s inventory and the constraints such that we free up the maximum number of inventory slots. That way, our player can pick up the most new items! items!

First, let’s create an inventory and let’s only focus on items that have full stacks. We can maximize our free inventory slots for this case, and then we will progressively make our way toward supporting all of the item types.

array[int] of int: inventory = [
  % fullstack of dirt 
  64,
  % half of a fullstack of wood
  32,
  % half stack of a fullstack of  wool
  32,
  % quarter of fullstack of sticks
  16,
  % quarter of a fulstack of carrots
  16
];

If our optimizer was working, it would select three slots of our inventory to go in the bundle to maximize our free inventory space. We can model inventory selection by creating another array of integers of either 0 or 1, with 1 representing a selected slot in our inventory and 0 representing an unselected slot.

int: n = length(inventory);
array[1..n] of var 0..1: selected;

Once we have this array representing our selected slots, we can maximize the sum of our array in order to select the most slots possible.

solve maximize sum(i in 1..n)(selected[i]);

The full code now will look like this

% Use this editor as a MiniZinc scratch book
array[int] of int: inventory = [
  % fullstack of dirt 
  64,
  % half of a fullstack of wood
  32,
  % half stack of a fullstack of  wool
  32,
  % quarter of fullstack of sticks
  16,
  % quarter of a fulstack of carrots
  16
];

int: n = length(inventory);
array[1..n] of var 0..1: selected;

solve maximize sum(i in 1..n)(selected[i]);

if we ran this on the playground, the ouptut is

Running Playground.mzn
selected = [0, 0, 0, 0, 0];
----------
selected = [1, 0, 0, 0, 0];
----------
selected = [1, 1, 0, 0, 0];
----------
selected = [1, 1, 1, 0, 0];
----------
selected = [1, 1, 1, 1, 0];
----------
selected = [1, 1, 1, 1, 1];
----------
==========
Finished in 215msec.

Our solver found the solution selected = [1, 1, 1, 1, 1]; to maximize our selected slots in our inventory, which means it selected every slot. This makes sense because we did not constrain it in any way. Let’s add some constraints so we can now make better-informed selections.

The constraint we are exceeding is our bundle capacity. If we include our bundle capacity in our model and constrain our selections to include only inventory items that do not exceed the bundle capacity, we can find a valid solution.

int: capacity = 64;
constraint sum(i in 1..n)(selected[i] * inventory[i]) <= capacity;

If we add this constraint to our model and run it again, we can see that it now only selects three inventory slots, and it selects slots that do not exceed the capacity of our bundle.

Running Playground.mzn
selected = [0, 0, 0, 0, 0];
----------
selected = [1, 0, 0, 0, 0];
----------
selected = [0, 1, 1, 0, 0];
----------
selected = [0, 1, 0, 1, 1];
----------
==========
Finished in 207msec.

Great! Our initial model works for items that all stack to 64, but Minecraft has items with different maximum stack sizes. As mentioned earlier:

  • Items that stack to 64 (like dirt, sticks) take up 1 bundle slot per item
  • Items that stack to 16 (like ender pearls, snowballs) take up 4 bundle slots per item
  • Unstackable items (like tools, armor) take up 64 bundle slots (the entire bundle)

To handle this in our model, we need to represent each item’s bundle cost accurately. We’ll use a scaled representation to avoid decimal arithmetic:

int: units = 16 * 64;  % Total bundle capacity (1024 units)
int: fullstack = 1 * 16;  % Cost per fullstack item (16 units per item)
int: smallstack = 1 * 64;  % Cost per smallstack item (64 units per item)
int: unstackable = 16 * 64 + 1;  % Cost exceeds capacity (1025 units)

Why scale by 16? This gives us clean integer values:

  • 1 dirt item = 16 units (1 bundle slot × 16)
  • 1 ender pearl = 64 units (4 bundle slots × 16)
  • Total capacity = 1024 units (64 bundle slots × 16)

Now we can model a more realistic inventory:

array[int] of int: inventory = [
  % full stack of 64 dirt (takes entire bundle)
  64 * fullstack,  % 64 × 16 = 1024 units
  
  % full stack of 16 ender pearls (takes entire bundle)
  16 * smallstack,  % 16 × 64 = 1024 units
  
  % 1 pickaxe (can't fit with anything else)
  unstackable,  % 1025 units
  
  % half stack of 32 dirt (half a bundle)
  32 * fullstack,  % 32 × 16 = 512 units
  
  % half stack of 8 ender pearls (half a bundle)
  8 * smallstack,  % 8 × 64 = 512 units
];

and the rest of the model remains the same

int: n = length(inventory);
array[1..n] of var 0..1: selected;

constraint sum(i in 1..n)(selected[i] * inventory[i]) <= units;
solve maximize sum(i in 1..n)(selected[i]);

the full example:

int: units = 16 * 64;
int: fullstack = 1 * 16;
int: smallstack = 1 * 64;
int: unstackable = 16 * 64 + 1;

array[int] of int: inventory = [
  % stack of dirt 
  64 * fullstack,
  % stack of ender pearls 
  16 * smallstack,
  % pickaxe
  unstackable,
  % half stacks, should select these to maximize inventory space
  32 * fullstack,
  8 * smallstack,
];

int: n = length(inventory);
array[1..n] of var 0..1: selected;

constraint sum(i in 1..n)(selected[i] * inventory[i]) <= units;
solve maximize sum(i in 1..n)(selected[i]);

When we run this on the playground, we can see that it selects the last two slots, which correctly selects the maximum number of mixed items to store in a bundle.

Running Playground.mzn
selected = [0, 0, 0, 0, 0];
----------
selected = [1, 0, 0, 0, 0];
----------
selected = [0, 0, 0, 1, 1];
----------
==========
Finished in 169msec.

Using MiniZinc, we can represent our problem declaratively, making it easy to extend and modify as needed. If game mechanics change or we want to support other storage systems like shulker boxes, we can simply update our constraints. This project was an enjoyable introduction to constraint satisfaction problems, and the MiniZinc Playground made it accessible without requiring any local setup.

联系我们 contact @ memedata.com