迷路で遊びたくなったので作りました。Goで書いています。
Homebrewをお使いの方は、次のコマンドでインストールしてください。
brew install itchyny/tap/maze
そうでない方は、次のコマンドでビルドしてインストールするか、
go get github.com/itchyny/maze/cmd/maze
あるいは https://github.com/itchyny/maze/releases よりバイナリーを落としてご利用ください。
mazeコマンドは、ランダムな迷路を出力します。
maze
--interactive引数を渡すと、カーソルを動かして迷路を遊ぶことができます。
maze --interactive
--format colorを渡すと迷路が綺麗に表示されます。--widthや--heightなどで迷路のサイズを制御することができます。
maze --width 20 --height 10 --format color
sキーを押すと、解答 (solution) の表示をトグルすることができます。
端末の文字サイズを小さくすると、複雑な迷路を楽しむことができます。
ぜひお楽しみください！
これからは少し実装の話をしようと思います。
迷路の表現
迷路の構造体の定義は次のように書きました。
const ( Up = 1 << iota Down Left Right ) type Maze struct { Directions [][]int Height int Width int Start *Point Goal *Point } type Point struct { X, Y int }
Maze構造体のDirectionsフィールドには、迷路の道の情報が入っています。それぞれのセルには、道が空いている方向の情報がバイナリー表現で格納されています。例えば Down は2進数で 10 で、Right は 1000 なので、下と右が空いているセルは2進数で 1010、つまり int で 10 と表現されます。バイナリー表現だとフラグを立てるのは|= (bitwise or)、道があるかチェックするのは& (bitwise and)、道をトグルするのは^ (bitwise xor)で書くことができます。それにしてもGoのiotaは便利ですね。
Directionsには、迷路の道に加えて、正解の道順も格納されています。下から1ビット目から4ビット目が迷路の道に利用され、5ビット目から8ビット目が正解の道に利用されています。さらに、9ビット目から12ビット目が、ユーザーのカーソルが辿った道に利用されています。
迷路の生成と解答
迷路の生成には、深さ優先探索を使いました。
- 隣の点をランダムに選び、道を作り点を進めてスタックに積む。前に進めるまでこれを繰り返す。
- 前に進めなくなったら、スタックからランダムに点を選び、スタックから落して1を繰り返す。
実際のコードは次のようになっています。
func (maze *Maze) Next(point *Point) *Point { neighbors := maze.Neighbors(point) if len(neighbors) == 0 { return nil } direction := neighbors[rand.Int()%len(neighbors)] maze.Directions[point.X][point.Y] |= direction next := point.Advance(direction) maze.Directions[next.X][next.Y] |= Opposite[direction] return next } func (maze *Maze) Generate() { point := maze.Start stack := []*Point{point} for len(stack) > 0 { for { point = maze.Next(point) if point == nil { break } stack = append(stack, point) } i := rand.Int() % ((len(stack) + 1) / 2) point = stack[i] stack = append(stack[:i], stack[i+1:]...) } }
単純ですね。スタックと書きましたが、端から取り出す必要はありません。経験的に前の方から取ると迷路がいい感じになるような気がするので、上のようなコードになっています。
迷路を解くときは二本のスタックを使いました。
- スタート地点から開始する。スタックと解答スタックにスタート地点を入れておく。
- 迷路の道があり移動できる隣接点をすべてスタックに積む。
- スタックをpopして次の点とする。
- その点が解答スタックの最後と繋がっていなければ、その点まで解答スタックをpopする。
- 解答スタックに次の点をpushして2に戻る。ゴールに着いたら修了。
具体的なコードはリポジトリを参照してください。最初は再帰で書いていましたが、なんとなく再帰よりもスタックを使って書いたほうが、手続きが分かって良いなぁと思ったのでそういう実装になっています。
ターミナルUI
最初は標準出力にprintfするだけで、遊ぶときは迷路を目で追うしかありませんでした。しかしそれでは面白くないので、キー入力を受け付けて遊べるようにしたい。Go言語でターミナル上のUIを作ろうと思ったのは初めてでしたが、termbox-goを使ってみると簡単でした。
mazeコマンドは引数がないと標準出力に表示してすぐに終了し、--interactiveをつけると矢印キーで遊べるようになっています。これはtermbox.Close()にdeferをつけるかつけないかという違いがあります。以下は実際のソースコードの一部を簡略化したものです。
func action(ctx *cli.Context) { termbox.Init() config := makeConfig(ctx) maze := createMaze(config) if config.Interactive { defer termbox.Close() interactive(maze, config.Format) } else { termbox.Close() maze.Print(config.Output, config.Format) } }
インタラクティブモードではないときは、termbox.Close()を直接呼び、迷路を出力して終わりです。
出力先が二種類あると、ライブラリー側がどういう関数を提供すればいいか、少し頭を捻る必要があります。termboxを用いて端末に表示する場合、termbox.SetCellという関数を用いて一文字ずつ場所と色を指定しなければなりません。迷路の出力は (解答の描画も含め)、わりと複雑なタスクなので、迷路ライブラリーが提供するべき機能です。ユーザー (これもわたしなんですが) は迷路を標準出力にもtermboxにも表示したいと考えています。コマンドを実装する場所ではtermboxを利用しますが、迷路ライブラリー (maze.go) ではtermboxに依存したくありません。
今回わたしは、出力channelをもらってそこに流しこむことにしました。迷路を書き込む関数はchan stringをもらってそこに迷路を出力します。
func (maze *Maze) Write(writer chan string, format *Format) { // fmt.Print(str) するかわりに writer <- str // 例えば壁なら writer <- "##" // 例えば道なら writer <- " " // 最後を知らせる writer <- "\u0000" }
この関数を使って、標準出力、あるいはファイル出力に流すのはとても簡単です。
func (maze *Maze) Print(writer io.Writer, format *Format) { // 出力を待ち受けるchannelを作る strwriter := make(chan string) go maze.Write(strwriter, format) for { str := <-strwriter switch str { // この文字が来たら修了 case "\u0000": return // 流れてくる文字列を単純にFprintするだけ default: fmt.Fprint(writer, str) } } }
上記の関数は迷路ライブラリー (maze.go) が提供してくれます。
さて、迷路ライブラリーはchannelに出力を流すWrite関数を提供してくれています。termboxに迷路を表示したいと思ったライブラリー利用者 (これもわたし) は、このWrite関数をtermboxをうまく繋いでやる必要があります。mazeコマンドの実装は、だいたい次のようなコードになっています。
func interactive(maze *maze.Maze, format *maze.Format) { // 略 strwriter := make(chan string) go printTermbox(maze, strwriter) maze.Write(strwriter, format) // 略 } func printTermbox(maze *maze.Maze, strwriter chan string) { // 表示位置 x, y := 1, 0 for { str := <-strwriter switch str { // 終了したらFlushする・位置をリセット case "\u0000": termbox.Flush() x, y = 1, 0 // そうでなければ、一文字ずつSetCellする default: for _, c := range str { if c == '\n' { x, y = x+1, 0 } else { termbox.SetCell(y, x, c, termbox.ColorDefault, termbox.ColorDefault) y = y + 1 } } } } }
改行の時の処理とかがミソですね。色付けとかに対応するため、実際の実装はもっと複雑になっています。
言われてみればそりゃそれで動くでしょうねと思われるかもしれませんが、実際にこの方法で、それまでずっと標準出力に出力して終わっていたコマンドが、termboxを使って表示できるようになった瞬間は、とても嬉しく思いました。ライブラリーとしての責務は守り (例えば迷路ライブラリーをtermboxに依存させるなんてことはせず)、やっていることは単純 (chan stringに流すだけ) で過度な抽象化にも走っていない、バランスのよい解決法だと思います。
テスト
迷路を出力するだけのコマンドですので、単体テストみたいな大げさなテストコードは書いていません。そのかわりに、mazeコマンドにいくつか引数を渡したものが書いたshell scriptと、それを実行した時に期待される出力を用意し、scriptの実行結果と比較するテストをしています。テストの一例は次のようになっています。以下のようなテストが20程度あります。TravisCIでテストしています。
~/.go/src/github.com/itchyny/maze cat test/default.sh test/default.txt maze --seed 0 --width 10 --height 10 ########################################## S ## ## ## ###### ## ## ## ## ############## ## ## ## ## ## ## ## ## ## ## ###### ########## ## ## ###### ## ## ## ## ## ## ## ## ## ###### ########## ## ###### ## ## ## ## ## ## ########## ###### ############## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ########## ## ## ## ## ## ## ## ## ## ########## ########## ###### ###### ## ## ## ## ## ###### ## ## ###################### ## ## ## ## ## ## ## ############## ## ## ## ########## ## ## ## ## ## ## ###### ## ## ###################### ## ## ## ## G ##########################################
デフォルトではランダムな迷路が生成されてしまい、テストしようがありません。テストでは上記のように、--seed 0のようにしてrandom seedを固定しています。この引数の値が同じであれば、mazeコマンドは常に同じ迷路を生成して出力します。--seed引数が与えられなければ、時刻から適当に初期化します。
裏話
実を言うと、迷路コマンドを書くのはこれが初めてではありません。かつてC言語で実装してブログを書いたことがありました。
このとき書いたコマンドは迷路を解く事ができず、またカーソルを動かして遊ぶこともできないものでした。なぜか「迷路の圧縮」という謎の課題に夢中になり、二次元の迷路を一次元文字列で圧縮・解凍するコードを一所懸命書いていました。autotoolsの勉強にはなりましたが、使いみちのない謎機能にのめり込んでしまったがためにコードもめちゃくちゃになってしまい、手がつけられなくなっていました。
Go言語はcliツールを簡単に書くことができ、またターミナル上で動くゲームもいくつか実装されていることから、インタラクティブに遊べる迷路コマンドが欲しいと思うようになりました。3月の半ばくらいに迷路の生成・解答コードを書き、標準出力に吐き出せた時点で一時期興味が薄れてしまっていました。しかし、前の土曜日でtermboxを触り始めて、上記のchan string使う方法を思いついて実装し、日曜日にテストを用意しコマンドのフラグを整え、昨日READMEやスクリーンショット、TravisCIとの連携とこの記事を用意し、本日リリースしました。
まとめ
Go言語で迷路コマンドを作りました。迷路の実装やchannelを用いた出力の切り替え、random seedを外から注入できるようにしておいてテストする方法などを説明しました。
息抜きに迷路で遊びたくなったらお使いください。
はてなでは、自分が興味を持った課題には全力でコードを書く、意欲あるエンジニアを募集しています。
