夢見るエンジニアの肥溜めブログ

エンジニアである私の技術日記でございます。インターネッツという大海原にクソみたいな投稿を繰り返すのは申し訳なく思い、インターネットの片隅に肥溜めを配置しました。非常に環境に優しいブログです。

【JavaScript】重みを付けてランダムに出現させる。(重み付き乱択) 簡単説明

背景

JavaScriptにおいて、ある特定の要素群を重みを付けてランダムに出現させる方法について記載します。 既に記載されている方も多いのですが、私の理解力不足でイメージしづらかったため、少しずつ順を追って説明していきます。

重み付き乱択について

前提

ゲームなどで、アイテムごとに出現確率を変えてドロップさせたい場合の実装を例に説明していきます。
例えば、以下の3つのアイテムがある場合を考えます。

  • 金の剣
  • 青銅の剣
  • 木の棒

上記アイテムの能力を考慮し、以下の重みをそれぞれ設定します。

アイテム名 重み(個数)
金の剣 1
青銅の剣 2
木の棒 7

重みは出現のしやすさですから、ここではわかりやすさのため、重み=個数と捉えていただいて構いません。
金の剣 1個は、「青銅の剣 2個分」 および 「木の棒 7個分」の価値があると考えてください。
また、上記10個のアイテムはすべて宝物庫に入っているとします。

棒グラフで図示すると以下のようになります。
このように位置関係で考えることが理解に繋がります。

f:id:stuffed_cabbage:20190112025702p:plain
全体要素のグラフイメージ

説明

本例では、以下の順に処理していきます。

  1. 宝物庫内にアイテムを準備する。
  2. 宝物庫内のアイテムの合計個数を取得する。
  3. 宝物庫からアイテムを取り出す。(ランダムな値を取得)
  4. どのアイテムが取り出されたか確認する。

それでは、順に説明していきます。

1. 宝物庫内にアイテムを準備する。

まず、宝物庫内にアイテムを生成する必要があります。
以下のコードで、アイテムを生成します。

const itemList = [
  { name: '金の剣' , stock: 1 },
  { name: '青銅の剣' , stock: 2 },
  { name: '木の棒', stock: 7 }
]

上記コードにより、金の剣が1個、青銅の剣が2個、木の棒が7個生成されます。

2. 宝物庫のアイテムの合計個数を取得する。

次に、以下のコードで、宝物庫(アイテムリスト)内のアイテムの合計個数を求めます。

const totalWeight = itemList.reduce((previous, current) => {
  return { weight: previous.weight + current.weight }
});

ここでは、アロー関数(※1)と配列のreduceメソッド(※2)を利用しています。
上記処理により、宝物庫内のアイテム合計個数が 10個 であることがわかります。

3. 宝物庫からアイテムを取り出す。(ランダムな値を取得)

宝物庫からアイテムを取り出します。

let pickedItem = Math.random() * totalWeight;

Math.random()では、0.0~1.0未満の乱数が返ります。
また、totalWeightには、現在10.0が格納されています。

つまり、pickedItemには、0.0~10未満の値が格納されることがわかります。
これが、どうしてアイテムを取り出したことになるのかは、次の項目で説明します。

4. どのアイテムが取り出されたか確認する。

処理2で取り出した値(pickedItem)が、どのアイテムに該当するか、アイテム鑑定書と比較する必要があります。
ここで、アイテム鑑定書は下図をイメージをしてください。

f:id:stuffed_cabbage:20190112025801p:plain
アイテム鑑定書イメージ

0.0から10.0までの長さがあるグラフに、左から順番にアイテムを並べてあります。
金の剣は1個あるので、0.0~1.0の幅でアイテム1個分のスペースをとります。続けて1.0を起点として青銅の剣を2個並べます。青銅の剣は1.0~3.0までの幅で、アイテム2個分のスペースをとります。同様に、木の棒は3.0~10.0までの幅で、アイテム7個分のスペースをとります。

上記がアイテム鑑定書となります。取り出したアイテム(pickedItem)とアイテム鑑定書を比較することで、どのアイテムが取り出されたか判明します。アイテム鑑定書は、あくまでイメージのため、コードを書く必要はありません。

以下に、取り出したアイテムとアイテム鑑定書を比較するコードを示します。

const AppraiseItem = (pickedItem, itemList) => {
  let searchPosition = 0.0;
  for (const item of itemList) {
    searchPosition += item.weight
    if (pickedItem < searchPosition) { 
      return item.name }
  }
}

取り出したアイテム(pickedItem)が、2.6だったと仮定して解説していきます。

本コードでは、アイテム鑑定書の左から順番に比較していきます。
はじめの探索位置(searchPosition)は、0.0から始まります。

1回目のfor文で、1個目の要素幅(金の剣)分探索します。 イメージとしては、下図になります。

f:id:stuffed_cabbage:20190112025655p:plain
探索1回目

初期探索位置(0.0)から現在探索位置(1.0)までの範囲で、取り出したアイテム(pickedItem)が該当しないか確認します。
取り出したアイテム(pickedItem)の値は、2.6ですので、金の剣には該当しません。
金の剣に該当しませんでしたので、次の要素(青銅の剣)に進みます。

2回目のfor文で、2個目の要素幅(青銅の剣)分探索します。
イメージとしては、下図になります。

f:id:stuffed_cabbage:20190112025651p:plain
探索2回目

前回探索位置から(1.0)から現在探索位置(3.0)までの範囲で、取り出したアイテム(pickedItem)が該当しないか確認します。
取り出したアイテム(pickedItem)の値は、2.6ですので、この範囲に該当することがわかります。つまり、取り出したアイテムが「青銅の剣」であったことがわかります。

総括

このように、重み付け乱択は、グラフ(軸)で考えると非常にわかりやすいです。
全部で10の範囲のうち、0.0~1.0は金の剣、1.0~3.0は青銅の剣と、全体の領域を、 それぞれの要素が、自身の重み分の領域を占有するイメージになります。当然、占有する幅が大きいほど、出現する確率は高くなります。
このアルゴリズムは、順番が前後しても出現確率は同様です。重み(幅)が変わらない限りは変化がありません。

完成コード

完成コードを以下に示します。
処理3と4については、GetItem関数として1つにまとめています。

    const itemList = [
     { name: '金の剣' , weight: 1 },
     { name: '青銅の剣' , weight: 2 },
     { name: '木の棒', weight: 7 }
    ]
    
    const totalWeight = itemList.reduce((previous, current) => {
      return { weight: previous.weight + current.weight }
    });

    const GetItem = (itemList) => {
      const pickedItem = Math.random() * totalWeight.weight;
      let searchPosition = 0.0;
      for (const item of itemList) {
        searchPosition += item.weight
        if (pickedItem < searchPosition) { 
          return item.name }
      }
    }

参考

※1: JavaScript アロー関数を説明するよ
※2: 【javascript】reduce
参考1: 【JavaScript】重み付けされた値をランダムで取得する | Black Everyday Company
参考2: 2017-03-25
参考3: ガチャプログラムの実装(中級者向け) - Qiita
参考4: 重み付けの抽選を行うアルゴリズム – Lancarse Blog

初めてのJavaScript 第3版 ―ES2015以降の最新ウェブ開発

初めてのJavaScript 第3版 ―ES2015以降の最新ウェブ開発

  • 作者: Ethan Brown,武舎広幸,武舎るみ
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2017/01/20
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログを見る

入門JavaScript フロントエンドエンジニアになるための基本と実践スキル (Web Engineer's Books)

入門JavaScript フロントエンドエンジニアになるための基本と実践スキル (Web Engineer's Books)