轨道
/
Elm
Elm
/
练习
/
迷宫生成器
迷宫生成器

迷宫生成器

学习练习

简介

Random

在 Elm 这样的纯函数式语言中,用相同的实参调用同一个函数,必须始终返回相同的值。 因此,类型签名为rand : Int的函数只能实现为rand = 4,这对生成随机整数来说可不是个好兆头。

那么在 Elm 中,我们该如何生成随机的值呢? 把问题拆成两步:先用Random.Generator a描述想要生成的值,再生成一个值。

生成值的第一种方式,是用initialSeed : Int -> Seed创建一个Random.Seed,再使用step : Generator a -> Seed -> ( a, Seed ),它会返回一个值和一个新的种子。 注意,这两个函数都是纯函数,所以用相同的实参调用两次,会得到相同的值。

生成值的第二种方式是使用generate : (a -> msg) -> Generator a -> Cmd msg,但这只能在 Elm 应用内部进行。 这种情况下,Elm 运行时既可以使用step,也可以使用外部的、非纯的资源来生成种子。

接下来,我们只关注生成器。

为了演示示例,我们不妨假设:已经用initialSeed和step定义了一个函数generate : Int -> Generator a -> List a,它能从一个生成器生成若干个值。

Random模块提供了两个基础生成器,用于在特定范围内生成整数和浮点数:

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可以创建只返回单个值的生成器:

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接收两个实参(Red和[Green, Blue]),以保证至少有一个值可供挑选,因为单个数组有可能是空的。

还可以用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在零(概率 50%)和另一个Peano数加一(概率 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% 的时间会生成自身的又一次迭代加一。 也就是说,生成的数会是 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% 会再次分支,数量不到一个,所以你生成的迷宫很可能会最终结束。

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,全部免费。