トラック
/
Elm
Elm
/
演習
/
迷路メーカー
迷路メーカー

迷路メーカー

学習演習

はじめに

ランダム

Elmのような純粋関数型言語では、同じ引数で呼び出された関数は、常に同じ値を返さなければなりません。 そのため、型シグネチャがrand : Intである関数はrand = 4としか実装できません。これでは乱数を生成するには心もとない話です。

では、Elmでランダムな値はどうやって生成するのでしょうか? 問題を2つに分けます。まず、生成したい値をRandom.Generator aで記述し、次に値を生成します。

値を生成する1つ目の方法は、initialSeed : Int -> SeedでRandom.Seedを作り、次にstep : Generator a -> Seed -> ( a, Seed )を使うことです。これは値と新しいシードを返します。 どちらの関数も純粋なので、同じ引数で2回呼び出すと、同じ値が生成されることに注意してください。

値を生成する2つ目の方法は、generate : (a -> msg) -> Generator a -> Cmd msgを使うことですが、これはElmアプリケーションの中でしか行えません。 その場合、Elmランタイムはstepだけでなく、外部の純粋でないリソースも使ってシードを生成することがあります。

ここからは、ジェネレーターに焦点を当てます。

例を示すために、initialSeedとstepを使って、ジェネレーターからいくつかの値を生成する関数generate : Int -> Generator a -> List aを定義したとしましょう。

Randomモジュールには、特定の範囲の整数と小数を生成するための基本的なジェネレーターが2つ用意されています。

generate 5 (Random.int -5 5)
    --> [0, 3, -5, 5, 0]

generate 3 (Random.float 0 5)
    --> [1.61803, 3.14159, 2.71828]

これらの値は、タプルにまとめたり、値の配列にまとめたりできます。

generate 2 (Random.list 3 (Random.int 0 3))
    --> [[0, 3, 3], [1, 3, 2]]

generate 2 (Random.pair (Random.int 0 3) (Random.float 10 10.3))
    --> [(0, 10.23412), (2, 10.17094)]

elm-community/random-extraパッケージには、文字列、日付、辞書、配列、集合など、さまざまなデータ構造のためのジェネレーターがたくさん用意されています。

Random.constantを使うと、常に1つの値だけを返すジェネレーターを作れます。

generate 4 (Random.constant "hello")
    --> ["hello", "hello", "hello", "hello"]

Random.uniformを使うと、与えられた要素の中から等しい確率でランダムに選べます。

generate 5 (Random.uniform Red [Green, Blue])
    --> [Red, Blue, Blue, Green, Red]

Random.uniformが2つの引数(Redと[Green, Blue])を取るのは、選べる値が少なくとも1つあることを保証するためです。配列を1つだけ渡すと、空になっている可能性があるからです。

Random.weightedを使えば、確率を調整することもできます。

generate 5 (Random.weighted (80, Red) [(15, Green), (5, Blue)])
    --> [Red, Red, Green, Red, Red]

値の合計は100でなくてもかまいません。最終的には正規化されます。

Random.mapを使うと、ジェネレーターの中の値に手を加えられます。

generate 3 (Random.int 1 6 |> Random.map (\n -> n * 10))
    --> [30, 60, 10]

Random.map2からRandom.map5までを使えば、より多くのジェネレーターを組み合わせることもできます。

position =
    Random.map3
      (\x y z -> Position x y z)
      (Random.float -100 100)
      (Random.float -100 100)
      (Random.float -100 100)

generate 1 position
    --> [Position 33.788 -98.321 10.0845]

もっと複雑な用途には、Random.andThen : (a -> Generator b) -> Generator a -> Generator bがあります。これは、あるジェネレーターが生成した値を使って別のジェネレーターを作れます。

bool = Random.uniform True [False]

failHalfOfTheTime : Generator a -> Generator (Maybe a)
failHalfOfTheTime generator =
    bool
        |> Random.andThen
            (\boolResult ->
                if boolResult then
                    Random.map Just generator

                else
                    Random.constant Nothing
            )

generate 6 (Random.int 0 1 |> failHalfOfTheTime)
    --> [Nothing, Just 1, Just 0, Nothing, Just 1, Nothing]

ジェネレーターを自己再帰的に定義すると便利なことがあります。 そのような場合は、コンパイラーがジェネレーターを無限に展開しないように、Random.lazyを使う必要があるかもしれません。

type Peano
    = Zero
    | Next Peano


peano : Generator Peano
peano =
    Random.uniform (Random.constant Zero)
        [ Random.map Next (Random.lazy (\_ -> peano))
        ]
        |> Random.andThen identity

generate 12 peano
    --> [Zero, Next(Next(Zero)), Zero, Next(Zero), Zero, Zero, Next(Zero), Zero, Zero, Next(Zero), Next(Next(Next(Zero)))]

この例は少し重いので、分解してみましょう。

Peanoは正の整数を表す型です。Zeroが0、Next(Zero)が1、Next(Next(Zero))が2、というようになります。 peanoは、ランダムなPeanoの数値を得るために定義します。

まず、Random.lazyはロジックに何も付け加えず、コンパイラーがpeanoをpeanoの中に無限に書き込むのを防ぐだけであることに注意してください。

Random.uniformを使って、0(50%の確率)か、別のPeanoの数値に1を足したもの(50%の確率)のどちらかを選びます。 ただし、前の例とは違い、Random.uniformは値(Zeroなど)から選ぶのではなく、ジェネレーター(Random.constant Zeroなど)から選びます。peano自身を使いたいからです。 これはつまり、Random.uniformがGenerator (Generator Peano)型の値を返すということで、必要なものではありません。

ジェネレーターを「平坦化」するには、それをRandom.andThen : (a -> Generator b) -> Generator a -> Generator bにパイプします。ここではbがPeanoであってほしいところです。 Generator aはGenerator (Generator Peano)なので、aはGenerator Peanoでなければならず、関数(a -> Generator b)は(Generator Peano -> Generator Peano)型でなければなりません。 何も変更したくないので、identityが適切な選択です。

最後に、peanoはどんな数値を生成するのでしょうか? 50%の確率で0を、50%の確率で自分自身をもう1回繰り返して1を足したものを生成することがわかります。 つまり、数値は0(50%の確率)、1(25%の確率)、2(12%の確率)、3(6%の確率)…となります。 peanoはいくらでも大きな数値を生成できますが、その確率は指数的に小さくなります。

説明

迷宮の研究者として、新世代のダンジョンと冒険の舞台を設計する仕事に取り組んでいます。

理論家なので、迷宮の物理的な配置には関心がありません(それは迷宮エンジニアの仕事です)。むしろ、分岐数や最大深さといった数学的な複雑さに関心があります。

次のプロジェクトには、ランダム生成のアプローチで取り組むことにします。

1. 最後から始めましょう

よい迷宮は、そのほとんどが行き止まりです。

deadendジェネレーターを、常にDeadEndバリアントを生成するように定義しましょう。

2. 酢ではハエは捕まえられません

冒険者が迷宮に入ってみたくなる理由を作りましょう。

treasureジェネレーターを、Gold、Diamond、Friendshipのいずれかを同じ確率で生成するように定義しましょう。

次に、roomジェネレーターを、treasureが生成した値をRoomバリアントで包むように定義しましょう。

3. 枝分かれさせましょう

さて、迷宮の心臓部ともいえるのが、分岐です。

branchジェネレーターはGenerator Mazeの引数を受け取ります。これは、任意の迷宮を生成できるジェネレーターです。

branchジェネレーターを、その引数が生成する迷宮へとつながる複数の分岐を含むBranchバリアントを生成するように定義しましょう。

分岐の数は2から4の間にします(それより多いと迷宮エンジニアが怒り出します)。同じ確率でランダムに決めます。

4. 驚きの迷宮

いよいよ本番です。

mazeジェネレーターを、60%の確率で行き止まりを、15%の確率で宝物の部屋を、25%の確率で分岐を生成するように定義しましょう。 分岐は、mazeを再帰的に使って新しい迷宮を生成します。 ジェネレーターの中では、deadend、room、branchを必ず使いましょう。

それぞれの分岐には平均3つの迷宮が含まれますが、そのうちさらに分岐するのは25%だけです。その数は1未満なので、生成される迷宮はいずれ終わりを迎えるでしょう。

5. もっと深くへ

mazeはよくできていますが、いくつか問題があります。

  1. 生成される値の75%は分岐をまったく持たず、とても本物の迷宮とはいえません
  2. 冒険者が迷宮の早い段階で宝物の部屋を見つけ、探索をやめてしまうかもしれません
  3. 深い迷宮も生成できますが、その確率はあまり高くありません。深さ3の迷宮が生成される確率はおよそ3%、深さ10の迷宮は0.2%です(迷宮の深さはMazeMakerSupport.mazeDepthで計算します)

mazeOfDepth nジェネレーターを、深さnの迷宮を生成するように定義しましょう。 最も深いレベル0だけが、行き止まりまたは宝物の部屋を含みます(同じ確率です)。それ以外のレベルはすべて、mazeOfDepthで再帰的に生成された深さn-1の迷宮を含む分岐にします。 ジェネレーターの中では、deadend、room、branchを必ず使いましょう。

GitHubで編集する リンクは新しいウィンドウまたはタブで開きます
Elm Exercism

迷路メーカーを始める準備はできましたか?

Exercismに登録すれば、28個のコンセプト110個の演習、そして本物の人間によるメンタリングとともに、Elmを学んでマスターできます。すべて無料です。