この記事では、Minecraftでエンチャントに必要な経験値コストを最小にする、合成方法を探るJavascriptコードを書いていきたいと思います。
完成品のコードは#完成にあります。コピペして使ってください。
はじめに
バニラのMinecraftであれば、従来のコスト計算のサイトが沢山あります。ぜひググって見てください。
一方、エンチャントに関するmod/datapackを導入している環境下では、エンチャントのコスト/レベル上限がなくなっていたり、また競合するはずのエンチャントが競合しなかったり、さらにはバニラに存在しない新しいエンチャントが追加されていたりするため、これらのサイトはまるっきり機能しない場合があります。
バニラの場合でさえ、エンチャントを合成する順番によってはコストが何倍にもなってしまいます。ましてやエンチャントが大量に追加された環境ではなおさら合成の順番に気をつける必要があります。だから、こんなコードを書く必要があったんですね。
参考文献
今回の内容に関連する、Minecraft Wiki の記事です。(いつもお世話になっております。)
余談
Apotheosisというmod(のエンチャントモジュール)が入っている場合は、追加されるEnchantment Libraryを使えば、経験値0でエンチャント本を合成・分解し放題なので、こんな風に最安値を追い求める貧民ムーブをしなくて済みます。エンチャントもりもりのmod環境で遊んでいるのであれば、ぜひ導入してみてはいかがでしょうか。え？エンチャ本管理のためだけにバランス崩壊mod入れるんですか？
仕組み
Minecraft Wikiの方を読んでいただいても構いません。その場合、#コーディングまで飛ばしてください。
筆者はMinecraft1.21.1JEでこの記事を書いています。JEであれば大体のバージョンで通用するはずです。BEはMinecraft wikiを参照してください。
Minecraftには様々なエンチャントがあり、それぞれにレベル及び固有の倍率といったパラメータが存在します。金床でエンチャント(またはアイテム)を合成するときは、ある一定の式や規則に従って合成コストが算出されます。
以下、Minecraft Wiki「金床の仕組み」からの引用も交えて解説していきます。というか引用がほとんどです。
今回の記事と関係ないところは簡潔に済ませます。
必要経験値量
金床で作業する際に使用する経験値レベルの量を求めるためには、そのアイテムが持つ「累計作業値」から算出される「累積作業費用」と、そのアイテムに対して行う作業から算出される「基礎作業費用」の2つを足すことで求めることができる。この値を「作業コスト」と呼ぶ。
累計作業値 & 累計作業費用
ここで、
-
累計作業値: そのアイテムを金床で作業した回数
なお、名前変更は作業には含まれません。作業したことのないアイテムは0として計算し、鉄床で合成したときに、累計作業値の大きい方の値に1加えます。
(ex)
ダイヤモンドの剣 (累計作業値: 3) と、
エンチャントの本 (累計作業値: 4)
を合成したとき、出来上がった
エンチャントされたダイヤモンドの剣
の累計作業値は 4 + 1 = 5 となる。
そして累積作業費用は$2^{累計作業値}-1$で求められるコストのことです。
この指数関数で増えていく累計作業費用が、この後解説する基礎作業費用に上乗せされ、最終的な作業コスト(つまり必要分の経験値)が算出されます。
——と思っていた時期が私にもありました。
実際には、累計作業値などというものは存在せず、Minecraftではこの累計作業費用はminecraft:repair_costというアイテムコンポーネントで管理されているようです。累計作業費用は、作業したことのないアイテムは0として計算し、鉄床で合成したときに、より大きい方の値を2倍し1を加えて算出します。
累積作業費用 = 2\ max(\ 累計作業費用_{item1}\ ,\ 累計作業費用_{item1}\ ) + 1
金床のみを使いアイテムを合成する通常のプレイでは、上記の式にしたがってコストが1, 3, 7, 15...と増えていくため、wikiで述べられていた法則でも問題なく通用しますが、コマンドなどの非正規手段ではアイテムコンポーネントであるrepair_costを好きに変更することができるため、$2^n-1$とならなければいけないwikiの法則が全く通用しないのは目に見えることでしょう。
基礎作業費用
基礎作業費用は鉄床で行う作業によって算出方法が変化します。
名称変更
アイテムの名前を変更するとき、基礎作業費用は1なので作業コストは $(2^{累計作業値}-1)+1=2^{累計作業値}$と求められます。
他の作業と同時に行われるときは、基礎作業費用にさらに1足します。
原材料での修理
大半の耐久力が存在するアイテムは、その原材料を使用して耐久力を回復させることができ、その際基礎作業費用は使用した原材料の数です。
また、1回の修理につき累計作業値が1加算されます。
アイテムの合成、及びエンチャントの合成
金床は、同じ2つのアイテムや、アイテムとエンチャントの本を合成することができる。これは武器や防具などの耐久力を持つアイテムと、エンチャントの本にのみ適用される。アイテムを合成すると、エンチャントの移動と、耐久値の回復の処理がそれぞれ行われる。それぞれ経験値が必要となるが、2つ同時に行う場合はコストの一部が共有される。
一つずつ見ていきましょう。
左のアイテムの耐久値が減っていた場合
右のアイテムの耐久値にそのアイテムの最大耐久力の12%を加えた値が左のアイテムの耐久値に加算されます。このとき基礎作業費用は2です。
右のアイテムにエンチャントがついている場合
左右のアイテムにあるエンチャントの種類数にかかわらず、それぞれのエンチャントのレベルに対して以下の処理が行われます。
-
2つのアイテムが同じエンチャントを持っている場合
エンチャントのレベルについて、合成されたアイテムのエンチャントのレベルは、- 右 > 左のとき: 右のレベルに従う。
- 右 = 左のとき: レベルが最大でなければレベルが1つ上がる。
- 右 < 左のとき: なにも起こらない。
-
右のみが持つエンチャントがある場合
左のアイテムに適用できる、かつ左の持つ何らかのエンチャントと競合しなければ、そのまま合成される。無効なエンチャントである場合(ex: 剣にダメージ軽減など)、競合する場合は無視される。 -
左のみが持つエンチャントがある場合
そのまま引き継がれる。
またこのとき、右のアイテムが持つエンチャントに応じて、作業コストが増加します。
右のアイテムのエンチャントが、左のアイテムについたエンチャントと、
- 競合するならば、作業コストに1が加算
- 競合しなければ、作業コストにエンチャントのレベルと倍率を掛けた値が加算
されます。
倍率とはなんぞや、ということですが、倍率はそれぞれのエンチャントに固有の値です。
ここで、エンチャントを定義しているjsonファイルを見てみましょう。
例として、ここでは耐久力のjsonファイルを見ていきます。
データパックで追加されたエンチャントのjsonファイルは[DataPack Name]/data/[namespace]/enchantmentで見つけられます。
unbreaking.json
{
"anvil_cost": 2,
"description": {
"translate": "enchantment.minecraft.unbreaking"
},
"effects": {
"minecraft:item_damage": [
{
"effect": {
"type": "minecraft:remove_binomial",
"chance": {
"type": "minecraft:fraction",
"denominator": {
"type": "minecraft:linear",
"base": 10.0,
"per_level_above_first": 5.0
},
"numerator": {
"type": "minecraft:linear",
"base": 2.0,
"per_level_above_first": 2.0
}
}
},
"requirements": {
"condition": "minecraft:match_tool",
"predicate": {
"items": "#minecraft:enchantable/armor"
}
}
},
{
"effect": {
"type": "minecraft:remove_binomial",
"chance": {
"type": "minecraft:fraction",
"denominator": {
"type": "minecraft:linear",
"base": 2.0,
"per_level_above_first": 1.0
},
"numerator": {
"type": "minecraft:linear",
"base": 1.0,
"per_level_above_first": 1.0
}
}
},
"requirements": {
"condition": "minecraft:inverted",
"term": {
"condition": "minecraft:match_tool",
"predicate": {
"items": "#minecraft:enchantable/armor"
}
}
}
}
]
},
"max_cost": {
"base": 55,
"per_level_above_first": 8
},
"max_level": 3,
"min_cost": {
"base": 5,
"per_level_above_first": 8
},
"slots": [
"any"
],
"supported_items": "#minecraft:enchantable/durability",
"weight": 5
}
最初のanvil_costがエンチャントに固有の倍率です。
アイテムにエンチャントがついている場合、倍率はそのままですが、本についている場合、倍率は元の値の半分になります(最小1)。
なお、すべてのバニラのエンチャントの倍率は$2^n(nは0以上の整数)$となっているようですが、データパックを作る際は好きに設定できます。やったことはないですが負に設定できるんですかね...
アイテムの合成、及びエンチャントの合成例はMinecraft Wikiの例を参照してください。
仕組みはこれで以上です。次はいよいよコードを書いていきましょう。
コーディング
今回はNode.jsを使用してJavascriptを実行しています。
最初はデバッグなども含め全部書いていましたが全カットしました。
デバッグの過程なんてとても見せられるものではないのでね...
欲しい機能をすべて羅列しておきます。
- 最安コスト探索
- カスタムエンチャント対応
- レベル上限無視(というか無視しないときつい)
- 競合エンチャント切り替え可能
ぱっと思いつくのは全ての組み合わせ方法にかかるコストを逐一計算して、その中で一番安い方法を返すというやり方ですね。
金床での合成
2つのアイテムを合成するコストを計算する関数を作っていきます。
アイテムの型
まずはアイテムの型です。
(jsでは識別子として有効なときは、キーを""で括っていなくてもstringと黙認するようです。今回は統一していませんが、やはりした方がわかりやすいのでしょうか？)
const items = [
{
id: "diamond_sword",
enchantment: {
"sharpness": 3,
"unbreaking": 1,
},
repair_cost: 0
},
{
id: "book",
enchantment: {
"knockback": 2
},
repair_cost: 1
}
];
(penaltyは累計作業値のことです。)
ここではitemsにすべて格納していますが、実際使うときはそれぞれの要素を取り出して使います。
エンチャントの情報など
また、ここでエンチャントの基本情報も整理しておきましょう。(こっちを先にやるべきだったかも？)
// すべてのエンチャント
const enchantment = {
"aqua_affinity": {
max_level: 1,
anvil_cost: 4
},
"bane_of_arthropods": {
max_level: 5,
anvil_cost: 2,
exclusive_set: "damage"
},
// ...
"vanishing_curse": {
max_level: 1,
anvil_cost: 8
},
"wind_burst": {
max_level: 3,
anvil_cost: 4
}
};
// すべての競合エンチャントのセット
const exclusive_set = {
"armor": [
protection,
blast_protection,
fire_protection,
projectile_protection
],
"boots": [
frost_walker,
depth_strider
],
// ...
"mining": [
fortune,
silk_touch
],
"riptide": [
loyalty,
channeling
]
};
(anvil_costは倍率のことです。)
このような感じで整理しておき、いつでもアクセスできるようにします。
これで、自分で好きにカスタムエンチャントに対応させたり、競合エンチャントを決めたりできますね！
アイテムを合成する
// item1が左、item2が右のアイテム
function Combine(item1, item2) {
if (item1 == undefined || item2 == undefined) throw new Error("Undefined Item!");
// 合成できない場合(違うid同士で、item2が本じゃない場合)は即終了
const isDefferentItem = item1.id != item2.id;
const isBook = item2.id == "book";
if (isDefferentItem && !isBook) return;
// 累計作業値の大きい方
const repairCost = 2 * Math.max(item1.repair_cost, item2.repair_cost) + 1;
// 累計作業費用
const penalty = item1.repair_cost + item2.repair_cost;
// 累計作業値に1加える
let result = { id: item1.id, enchantment: { ...item1.enchantment }, repair_cost: repairCost };
// 基礎作業費用、競合カウンター
let cost = 0, exclusiveCount = 0;
const item1Ench = Object.keys(item1.enchantment);
const item2Ench = Object.keys(item2.enchantment);
// item2の各エンチャントについて
for (const enchName of item2Ench) {
// このエンチャントに競合するエンチャントが存在するとき、item1に競合するエンチャントがないことを確認
// 競合する場合は1上がる
if (IsExclusiveWith(enchName, item1Ench)) { cost++; exclusiveCount++; continue; }
// itemのエンチャントのレベル、エンチャントの倍率を取得
const item2EnchLv = item2.enchantment[enchName];
const item1EnchLv = result.enchantment[enchName];
const anvilCost = enchantment[enchName].anvil_cost;
const multiplier = isBook ? max(anvilCost / 2, 1) : anvilCost;
if (item1EnchLv != undefined) {
const level = MergeLevels(item1EnchLv, item2EnchLv, enchName);
result.enchantment[enchName] = level;
cost += level * multiplier;
} else {
// item1にこのエンチャントが含まれないので、そのまま合成
result.enchantment[enchName] = item2EnchLv;
cost += item2EnchLv * multiplier;
}
};
// item2が本、かつ持っている全てのエンチャントが競合するならば合成できない
if (item2Ench.length == exclusiveCount && isBook) return;
const totalCost = penalty + cost;
return { result, totalCost };
}
function IsExclusiveWith(enchantmentName, item1Enchants) {
const exclusiveSetId = enchantment[enchantmentName].exclusive_set;
if (!exclusiveSetId) return false
// すべての競合エンチャントを取得
const exclusiveList = exclusive_set[exclusiveSetId];
// some() は条件がtrueになった時点でループを抜けられるらしい
return exclusiveList.some(e =>
e != enchantmentName && item1Enchants.includes(e)
);
}
function MergeLevels(level1, level2, enchantmentName) {
// エンチャントレベル同じかつ最大でなければレベルが1つ上がる
if (level1 == level2 ) {
return level1 < enchantment[enchantmentName].max_level ? level1 + 1 : level1;
} else {
// 大きい方になる
return Math.max(level1, level2);
}
}
まあまあ細かくコメントで説明してあるので、大体の構造だけ説明します。
最初に戻り値用のオブジェクトresultをitem1から一部コピペして作ったら、item2のすべてエンチャントに対してfor文で
- 競合エンチャントを確認
- 最初にitem2が本か、元の倍率が1以上かで倍率を半分にするか判断
- item1にこのエンチャントがあるか確認
- 合成後のレベルに倍率をかけ合わせて、costに加算
します。その後、エンチャ可能かどうかもこの時点でチェックしておき累計作業費用と基礎作業費用を足し合わせてフィニッシュです。
ちなみに、このツールにこのエンチャントをつけられるかどうかのチェックをしていませんが、アイテムにつけられないエンチャントというのは、ユーザーがデータを入力する段階で十分気づくことができる上、かつ結局作業コストには影響しないので、エンチャントをつけられるかのチェックはユーザーに任せたいと思います。
これでコストまで得られましたね。
早速Minecraft Wikiの例で実験してみます。
{
id: "golden_sword",
enchantment: {
"sharpness": 3,
"knockback": 2,
"looting": 3
},
anvilUses: 0
},
{
id: "golden_sword",
enchantment: {
"sharpness": 3,
"looting": 3
},
anvilUses: 0
}
この2つを合成してみます。
node enchantment_cost_calculator.js
{
result: {
id: 'golden_sword',
enchantment: { sharpness: 4, knockback: 2, looting: 3 },
anvilUses: 1
},
totalCost: 16
}
大丈夫そうですね！ではアイテムの合成については以上です。
合成の順番
最終的には与えられたアイテムを全て最も少ない合計コストで合成する方法を探したいのですが、合成するたびにほぼ予測不可能な新しい合成コストを持つ新しいアイテムができるので、おそらく全通りの合成方法を総当りで探すのが一番手っ取り早いのではないのでしょうか。
すべてのエンチャントの組み合わせ方を総当りで計算するならば、まずは全ての組み合わせ方について固有のIDの付け方から考えていく必要があります。
idの付け方
合計$n$個のエンチャントについて、1回の合成でアイテムが一つ減るので、$k$回目の合成において、次の合成する2つアイテムの選び方は${}_{n-k+1} \mathrm{P}_2$通りとなります。ここで、$p$個目と$q$個目のアイテムの合成を繰り返したことを、$(p_1,q_1),(p_2,q_2),\dots(p _{n-1},q _{n-1})$のような一連の数字をIDとして使用すれば、すべての組み合わせに固有の表し方が存在することになります。
ここで"1_1"のような文字列をキーに設定したネストを作れば、それぞれの組み合わせ方に1対1で対応することができる上に、その時点までの合計コストなどを置いておけば、キャッシュして再利用できたりもします。
{
"1_1": {
cost: 100,
next: {
"1_1": {
cost: 200,
next: {
...
}
},
"1_2": {
cost: 250,
next: {
...
}
},
...
}
},
"1_2": {
cost: 100,
next: {
...
}
},
...
}
全組み合わせを列挙
早速このidを使っていきましょう。とりあえずメインのネストを作るところは再帰関数にしようと思います。ネストのキーでpqペアを全てカウントする必要があるので、pqをiから直接求める関数が必要になります。p≠qであり、p_qとq_pどちらも計算する必要がある(金床で合成する左右のアイテムを入れ替えるとコストが変わる。前節参照)ため、大小関係の制限はないことに気をつけましょう。
わざわざ自分で書く理由もないのでこういう簡単なやつはChatGPTに書かせます。
function getPair(n, i) {
// i番目のpqペア
let p = 0;
while (i >= n - p - 1) {
i -= (n - p - 1);
p++;
}
let q = p + i + 1;
return { p, q };
}
この関数では、入力されたnとiに応じて、
(0,1),\ (0,2),\ ... (0,n-1),\ (1,0),\ (1,2),\ ...\ (2,0),\ (2,1),\ (2,3),\ ...\ (n-1,n-2)
という数列の$i$番目の要素を返します。
そして、この数列に含まれる全ての組み合わせに対して、コストを計算する下のListAllPairs()では、for分でiを回してこの関数で取得したi番目のpqペアに対してアイテム合成処理を行っていくことになります。再帰を使い全組み合わせを探すので計算量オーダーO(n!)と圧倒的に非効率です。もっといい方法が思いつけば切り替えますが、ない気がします。気休め程度にその時点で見つかった最安値minCostを上回ったら止めるという軽量化を挟んでいます。
可読性？そんなものは知らん
function ListAllPairs(items, cost) {
if (cost > minCost) return;
let CombiningOrder = null;
// 全てのアイテムを合成し終えた時の処理
if (items.length <= 1) {
minCost = Math.min(minCost, cost);
// もし最安値なら
if (cost == minCost) {
// path = "";
CombiningOrder = "";
}
}
let temp = {};
for (let i = 0; i < items.length * (items.length - 1); i++) {
const pair = getPair(items.length, i);
// アイテムを合成し、キーを作る
const key = pair.p + "_" + pair.q;
const combinedItem = Combine(items[pair.p], items[pair.q]);
// 合成できないので、この組み合わせは飛ばす
if (combinedItem == null) continue;
temp[key] = {};
const totalCost = combinedItem.totalCost + cost
temp[key].cost = totalCost;
// itemsから合成済みのアイテムを削除し、合成結果を加える
// p < qの場合、qのときの削除するべきインデックスがズレることを考慮する
let newItems = [...items];
newItems.splice(pair.p, 1);
newItems.splice(pair.q - (pair.p < pair.q ? 1 : 0), 1);
newItems.push(combinedItem.result);
// 残ったアイテムで合成処理をする
data = ListAllPairs(newItems, totalCost);
if (data == null) continue;
temp[key].next = data.temp;
temp[key].combiningOrder = data.combiningOrder;
temp[key].currentItems = newItems;
if (data.combiningOrder != null) {
CombiningOrder = "Item1: " + genText(items[pair.p]) + ", Item2: " + genText(items[pair.q]) + (data.combiningOrder == "" ? " Finish!" : ("\n" + data.combiningOrder));
}
}
return { temp, combiningOrder: CombiningOrder };
}
function genText(item) {
let temp = item.id + "(enchantment(s): ";
for (const [key, value] of Object.entries(item.enchantment)) { temp += `${key}:${value},`; }
temp += ")"
return temp;
}
試しに以下のアイテムを合成してみましょう。
const items = [
{
id: "book",
enchantment: {
sharpness: 2
},
repair_cost: 0
},
{
id: "book",
enchantment: {
smite: 5,
looting: 3
},
repair_cost: 0
},
{
id: "book",
enchantment: {
knockback: 2
},
repair_cost: 0
}
];
node enchantment_cost_calculator.js
{
'0_1': {
cost: 7,
next: { '0_1': [Object], '1_0': [Object] },
combiningOrder: 'Item1: book(enchantment(s): sharpness:2,looting:3,), Item2: book(enchantment(s): knockback:2,) Finish!',
currentItems: [ [Object], [Object] ]
},
'0_2': {
cost: 2,
next: { '0_1': [Object], '1_0': [Object] },
combiningOrder: 'Item1: book(enchantment(s): smite:5,looting:3,), Item2: book(enchantment(s): sharpness:2,knockback:2,) Finish!',
currentItems: [ [Object], [Object] ]
},
'1_2': {
cost: 2,
next: { '0_1': [Object] },
combiningOrder: null,
currentItems: [ [Object], [Object] ]
},
'2_0': {
cost: 2,
next: { '0_1': [Object], '1_0': [Object] },
combiningOrder: 'Item1: book(enchantment(s): smite:5,looting:3,), Item2: book(enchantment(s): knockback:2,sharpness:2,) Finish!',
currentItems: [ [Object], [Object] ]
},
'2_1': { cost: 11 }
}
Item1: book(enchantment(s): knockback:2,), Item2: book(enchantment(s): sharpness:2,)
Item1: book(enchantment(s): smite:5,looting:3,), Item2: book(enchantment(s): knockback:2,sharpness:2,) Finish!
minCost: 6
という感じできちんと出力できています。
完成
以下がこちらのコードの全容になります。
enchantment_cost_calculator.js
// Enchantment Cost Calculator
//
const enchantment = {
"aqua_affinity": {
max_level: 1,
anvil_cost: 4
},
"bane_of_arthropods": {
max_level: 5,
anvil_cost: 2,
exclusive_set: "damage"
},
"binding_curse": {
max_level: 1,
anvil_cost: 8
},
"blast_protection": {
max_level: 4,
anvil_cost: 4,
exclusive_set: "armor"
},
"breach": {
max_level: 4,
anvil_cost: 4,
exclusive_set: "damage"
},
"channeling": {
max_level: 1,
anvil_cost: 8
},
"density": {
max_level: 5,
anvil_cost: 2,
exclusive_set: "damage"
},
"depth_strider": {
max_level: 3,
anvil_cost: 4,
exclusive_set: "boots"
},
"efficiency": {
max_level: 5,
anvil_cost: 1
},
"feather_falling": {
max_level: 4,
anvil_cost: 2
},
"fire_aspect": {
max_level: 2,
anvil_cost: 4
},
"fire_protection": {
max_level: 4,
anvil_cost: 2,
exclusive_set: "armor"
},
"flame": {
max_level: 1,
anvil_cost: 4
},
"fortune": {
max_level: 3,
anvil_cost: 4,
exclusive_set: "mining"
},
"frost_walker": {
max_level: 2,
anvil_cost: 4,
exclusive_set: "boots"
},
"impaling": {
max_level: 5,
anvil_cost: 4,
exclusive_set: "damage"
},
"infinity": {
max_level: 1,
anvil_cost: 8,
exclusive_set: "bow"
},
"knockback": {
max_level: 2,
anvil_cost: 2
},
"looting": {
max_level: 3,
anvil_cost: 4
},
"loyalty": {
max_level: 3,
anvil_cost: 2
},
"luck_of_the_sea": {
max_level: 3,
anvil_cost: 4
},
"lure": {
max_level: 3,
anvil_cost: 4
},
"mending": {
max_level: 1,
anvil_cost: 4
},
"multishot": {
max_level: 1,
anvil_cost: 4,
exclusive_set: "crossbow"
},
"piercing": {
max_level: 4,
anvil_cost: 1,
exclusive_set: "crossbow"
},
"power": {
max_level: 5,
anvil_cost: 1
},
"projectile_protection": {
max_level: 4,
anvil_cost: 2,
exclusive_set: "armor"
},
"protection": {
max_level: 4,
anvil_cost: 1,
exclusive_set: "armor"
},
"punch": {
max_level: 2,
anvil_cost: 4
},
"quick_charge": {
max_level: 3,
anvil_cost: 2
},
"respiration": {
max_level: 3,
anvil_cost: 4
},
"riptide": {
max_level: 3,
anvil_cost: 4,
exclusive_set: "riptide"
},
"sharpness": {
max_level: 5,
anvil_cost: 1,
exclusive_set: "damage"
},
"silk_touch": {
max_level: 1,
anvil_cost: 8,
exclusive_set: "mining"
},
"smite": {
max_level: 5,
anvil_cost: 2,
exclusive_set: "damage"
},
"soul_speed": {
max_level: 3,
anvil_cost: 8
},
"sweeping_edge": {
max_level: 3,
anvil_cost: 4
},
"swift_sneak": {
max_level: 3,
anvil_cost: 8
},
"thorns": {
max_level: 3,
anvil_cost: 8
},
"unbreaking": {
max_level: 3,
anvil_cost: 2
},
"vanishing_curse": {
max_level: 1,
anvil_cost: 8
},
"wind_burst": {
max_level: 3,
anvil_cost: 4
}
};
const exclusive_set = {
"armor": [
"protection",
"blast_protection",
"fire_protection",
"projectile_protection",
],
"boots": [
"frost_walker",
"depth_strider",
],
"bow": [
"infinity",
"mending",
],
"crossbow": [
"multishot",
"piercing",
],
"damage": [
"sharpness",
"smite",
"bane_of_arthropods",
"impaling",
"density",
"breach",
],
"mining": [
"fortune",
"silk_touch",
],
"riptide": [
"loyalty",
"channeling",
]
};
const items = [
{
id: "diamond_sword",
enchantment: {
sharpness: 3,
unbreaking: 1,
},
repair_cost: 0
},
{
id: "book",
enchantment: {
knockback: 2
},
repair_cost: 0
},
{
id: "book",
enchantment: {
smite: 5
},
repair_cost: 0
},
{
id: "book",
enchantment: {
sharpness: 3
},
repair_cost: 1
},
{
id: "book",
enchantment: {
sharpness: 3,
looting: 2,
unbreaking: 2
},
repair_cost: 0
}
];
const items2 = [
{
id: "book",
enchantment: {
knockback: 2
},
repair_cost: 0
},
{
id: "book",
enchantment: {
fire_aspect: 1,
sharpness: 1
},
repair_cost: 1
},
{
id: "book",
enchantment: {
fire_aspect: 2,
sharpness: 2
},
repair_cost: 3
},
{
id: "book",
enchantment: {
smite: 5
},
repair_cost: 0
},
{
id: "book",
enchantment: {
sharpness: 3
},
repair_cost: 0
},
{
id: "book",
enchantment: {
sharpness: 3,
looting: 2
},
repair_cost: 1
},
{
id: "book",
enchantment: {
looting: 2
},
repair_cost: 1
},
];
const items3 = [
{
id: "book",
enchantment: {
sharpness: 2
},
repair_cost: 0
},
{
id: "book",
enchantment: {
smite: 5,
looting: 3
},
repair_cost: 0
},
{
id: "book",
enchantment: {
knockback: 2
},
repair_cost: 0
}
];
let minCost = Infinity;
main();
function main() {
console.log("Start");
const result = ListAllPairs(items, 0)
console.log(result.temp);
console.log(result.combiningOrder);
console.log(minCost);
}
function ListAllPairs(items, cost) {
if (cost > minCost) return;
let CombiningOrder = null;
// 全てのアイテムを合成し終えた時の処理
if (items.length <= 1) {
minCost = Math.min(minCost, cost);
// もし最安値なら
if (cost == minCost) {
// path = "";
CombiningOrder = "";
}
}
let temp = {};
for (let i = 0; i < items.length * (items.length - 1); i++) {
const pair = getPair(items.length, i);
// アイテムを合成し、キーを作る
const key = pair.p + "_" + pair.q;
const combinedItem = Combine(items[pair.p], items[pair.q]);
// 合成できないので、この組み合わせは飛ばす
if (combinedItem == null) continue;
temp[key] = {};
const totalCost = combinedItem.totalCost + cost
temp[key].cost = totalCost;
// itemsから合成済みのアイテムを削除し、合成結果を加える
// p < qの場合、qのときの削除するべきインデックスがズレることを考慮する
let newItems = [...items];
newItems.splice(pair.p, 1);
newItems.splice(pair.q - (pair.p < pair.q ? 1 : 0), 1);
newItems.push(combinedItem.result);
// 残ったアイテムで合成処理をする
data = ListAllPairs(newItems, totalCost);
if (data == null) continue;
temp[key].next = data.temp;
temp[key].combiningOrder = data.combiningOrder;
temp[key].currentItems = newItems;
if (data.combiningOrder != null) {
CombiningOrder = "Item1: " + genText(items[pair.p]) + ", Item2: " + genText(items[pair.q]) + (data.combiningOrder == "" ? " Finish!" : ("\n" + data.combiningOrder));
}
}
return { temp, combiningOrder: CombiningOrder };
}
function genText(item) {
let temp = item.id + "(enchantment(s): ";
for (const [key, value] of Object.entries(item.enchantment)) { temp += `${key}:${value},`; }
temp += ")"
return temp;
}
function getPair(n, i) {
// i番目のpqペア
p = Math.floor(i / (n - 1));
q = i % (n - 1);
if (p <= q) q++;
return { p, q };
}
// item1が左、item2が右のアイテム
function Combine(item1, item2) {
if (item1 == undefined || item2 == undefined) throw new Error("Undefined Item!");
// 合成できない場合(違うid同士で、item2が本じゃない場合)は即終了
const isDefferentItem = item1.id != item2.id;
const isBook = item2.id == "book";
if (isDefferentItem && !isBook) return;
// 累計作業値の大きい方
const repairCost = 2 * Math.max(item1.repair_cost, item2.repair_cost) + 1;
// 累計作業費用
const penalty = item1.repair_cost + item2.repair_cost;
// 累計作業値に1加える
let result = { id: item1.id, enchantment: { ...item1.enchantment }, repair_cost: repairCost };
// 基礎作業費用、競合カウンター
let cost = 0, exclusiveCount = 0;
const item1Ench = Object.keys(item1.enchantment);
const item2Ench = Object.keys(item2.enchantment);
// item2の各エンチャントについて
for (const enchName of item2Ench) {
// このエンチャントに競合するエンチャントが存在するとき、item1に競合するエンチャントがないことを確認
// 競合する場合は1上がる
if (IsExclusiveWith(enchName, item1Ench)) { cost++; exclusiveCount++; continue; }
// itemのエンチャントのレベル、エンチャントの倍率を取得
const item2EnchLv = item2.enchantment[enchName];
const item1EnchLv = result.enchantment[enchName];
const anvilCost = enchantment[enchName].anvil_cost;
const multiplier = isBook ? Math.max(anvilCost / 2, 1) : anvilCost;
if (item1EnchLv != undefined) {
const level = MergeLevels(item1EnchLv, item2EnchLv, enchName);
result.enchantment[enchName] = level;
cost += level * multiplier;
} else {
// item1にこのエンチャントが含まれないので、そのまま合成
result.enchantment[enchName] = item2EnchLv;
cost += item2EnchLv * multiplier;
}
};
// item2が本、かつ持っている全てのエンチャントが競合するならば合成できない
if (item2Ench.length == exclusiveCount && isBook) return;
const totalCost = penalty + cost;
return { result, totalCost };
}
function IsExclusiveWith(enchantmentName, item1Enchants) {
const exclusiveSetId = enchantment[enchantmentName].exclusive_set;
if (!exclusiveSetId) return false
// すべての競合エンチャントを取得
const exclusiveList = exclusive_set[exclusiveSetId];
// some() は条件がtrueになった時点でループを抜けられるらしい
return exclusiveList.some(e =>
e != enchantmentName && item1Enchants.includes(e)
);
}
function MergeLevels(level1, level2, enchantmentName) {
// エンチャントレベル同じかつ最大でなければレベルが1つ上がる
if (level1 == level2 ) {
return level1 < enchantment[enchantmentName].max_level ? level1 + 1 : level1;
} else {
// 大きい方になる
return Math.max(level1, level2);
}
}
終わりに
だいぶ駆け足になってしまいましたが、いかがでしたでしょうか。
しばらくデバッグしてみても特にバグは見つからなかったので、多分取りきったと信じたいです。本当に信じてますよ！！！
記事のほうは結構サクサク進めていますが、執筆時間があまり取れなかったとは言え、バグ取り含めコードが完成するのに1ヶ月以上余裕で掛かっているので、正直最初の方はもう自分でも覚えていないです(笑)。
なお、
- 最終的に残すエンチャント(競合がある際片方は消えてしまうため)やレベルの範囲を指定できない
- 非効率的なコードでありパフォーマンス的な問題も生じる
などといった問題もあるので、まだまだ完璧なものには程遠いです。
前者はListAllPairs()内の全てのアイテムを合成し終えた時の処理で指定された条件とアイテムのエンチャを一つずつ比べれば簡単に終わるでしょうが、後者は如何ともし難いでしょう。いつかやる気が出たら続きを出すかもしれませんが、期待はしないでください。
最後までご覧いただきありがとうございました。お楽しみいただけたら幸いです。