diff(A*)

Rogue Likeか Tower Defense か何かで使おうとしてA*をつくっていたけど これってdiffだよね〜と思ってたらやっぱりdiffだったので diffにも使えるように改造していた。

ランダムに問題を生成してedit graph をA*でたどったもの f:id:hrt1ro:20180919130111p:plain

A*のパラメータとしては

  • S: スタートは左上隅
  • G: ゴールは右下隅
  • ノード展開は、3方向(→↘↓) か 2方向(→↓)
  • h(n) は d←n-G で |dx| と |dy| の大きい方
  • f値が同じときのタイブレークは Gまでのユークリッド距離で小さい方を選ぶ
  • COST(n,m)は1

で、だいたいこんなかんじ

A*

ここのところA*をSwiftで実装していた。

アルゴリズムwikipediaのとおり

https://ja.wikipedia.org/wiki/A*

案の定なかなか動かないのだけど、いちど動いてしまえばああそうか、みたいな簡単なものである。 なかなかうまくいかないのは日本語の解釈の問題なので、 それはつまり読み取り側の能力が足りないからだけど、 アルゴリズム自然言語じゃなく架空でいいのでプログラミング言語っぽい言語で書いて欲しいものである。

ノード配列から最小値を持つノードを見つける、なんてのはSwiftっぽい書き方ができてちょっとうれしい。

    while let n = openList.min(by: { (a, b) -> Bool in a.value < b.value }) {〜}

ただ「取り出す」などと書いてあるとそれはリストからremoveすることも意味していたりするので 削除するとなるとindexが必要で…などとなってちょっとAh...という気持ちになる

別件で UIGraphicsImageRenderer も調べていたので問題と解を画像化してみたりしてみた。 f:id:hrt1ro:20180914144317p:plain

迷路

迷路生成アルゴリズムを実装した。 (壁伸ばし法)

1が壁で0が通路

1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 0 1
1 1 1 0 1 1 1 0 1
1 0 0 0 1 0 0 0 1
1 1 1 0 1 0 1 0 1
1 0 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1

Flood-fillアルゴリズムで通路(0)を2で塗りつぶす。

1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 1 2 1
1 1 1 2 1 1 1 2 1
1 2 2 2 1 2 2 2 1
1 1 1 2 1 2 1 2 1
1 2 2 2 2 2 1 2 1
1 1 1 1 1 1 1 1 1

通路(0)がなくなっていれば、通路は連結している(壁に塞がれた通路は無い)と診断できる。

同様に壁(1)を3で塗りつぶす。

3 3 3 3 3 3 3 3 3
3 2 2 2 2 2 3 2 3
3 3 3 2 3 3 3 2 3
3 2 2 2 3 2 2 2 3
3 3 3 2 3 2 3 2 3
3 2 2 2 2 2 3 2 3
3 3 3 3 3 3 3 3 3

壁(1)がなくなっていれば、壁は連結している(通路に回廊は無い)と診断できる

Rogue Likeななにか

ダンジョンの自動生成を作っているけどなかなかぐっとくる感じにならない

        -------------------------       -------
        |.......................|       |.....|
        |.......................+#######|.....|
        |.......................|      #+.....|
        |.......................|       |.....|
        |.......................|       |.....|
        ---+-+-------------------       --+----
           # #                            #
     ####### ##############################
     #                     ##
  ---+-----        --------++-----
  |.......|   #####+.............|
  |.......|   #    |.............|
  |.......|   #    |.............|
  |.......|   #    |.............|
  |.......|   #    |.............|
  |.......|   #    ------------+--
  |.......|   #                #
  |.......|   #                #
  |.......|   #        #########
  |.......|   #        #           -------------
  |.......|   #        #           |...........|
  |.......|   #        #        ###+...........|
  |.......|   #        #        #  |...........|
  |.......+####        #        #  |...........|
  |.......|            #        #  |...........|
  ---------     -------+-----   #  -+-----------
                |...........+####   #
                |...........|       #
                |...........|       ##
                |...........|    ----+----
                |...........|    |.......|
                -------------    |.......|
                                 |.......|
                                 |.......|
                                 |.......|
                                 ---------

Swift LANGUAGE GUIDE を読んで書いたブログエントリの一覧