Kuroda Software Service
アルゴリズムを考えよう
  [サイトマップ]

コンテンツ内メニュー

表示モード 全項表示  部分表示



マークの色と認証の関係

一般公開

無料認証

購入認証


認証についての説明

無料アカウント作成フォーム

有料ページ購入フォーム


ほかのコンテンツトップページ

アルゴリズムを考えよう

迷路の作り方を単純にして考えてみます。

*        プログラムは、単純さが重要です。

 紙と鉛筆を渡されて、迷路を書きなさいと言われれば100人100様な書き方があると思いますし、それが人間の個性です。ただし機械にそれを行わせようとする場合、できるだけ単純な手順を選択する必要があります。なぜなら、複雑な手順をいきなりプログラミングしようとしても書く側の人間の方が混乱してしまうからです。ここでは最も単純な迷路の作成方法を考えます。

1.     
◆◆◆◆◆◆◆◆◆◆◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆◆◆◆◆◆◆◆◆◆◆

 図では◆を迷路の外壁、□を空き地、■を壁と呼ぶことにします。

2.     
◆◆◆◆◆◆◆◆◆◆◆
◆A■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆◆◆◆◆◆◆◆◆◆◆

 今、左上のA地点から迷路の作成を開始します。Aの地点から上下左右に、壁を挟んだ空き地が存在するかを調べます。存在した場合、いずれかの空き地との間にある壁を取り払い、道とします。たとえば、右への移動を選択した場合、下図のようになります。

3.     
◆◆◆◆◆◆◆◆◆◆◆
◆A B■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆◆◆◆◆◆◆◆◆◆◆

 次に、B地点で同じ事を繰り返します。このように、つねに道の先頭で新たな空き地を探すと、袋小路になって、周りに空き地が無くなるなる場合があります。その場合、元の地点に戻って空き地を探すことが必要になります。下図に例を示します。

4.     
◆◆◆◆◆◆◆◆◆◆◆
◆A B■□■□■□◆
◆■■ ■■■■■■◆
◆F■C■□■□■□◆
◆ ■ ■■■■■■◆
◆E D■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆■■■■■■■■■◆
◆□■□■□■□■□◆
◆◆◆◆◆◆◆◆◆◆◆

 道はF地点まで進みましたが、Fには道を作るべき空き地がまわりにありません。この場合、AからEまでの地点を基準に、上下左右の空き地を探して候補があった場合、新たな道を作ります。もし、すべての地点で上下左右に空き地が無いという場合、迷路は完成しています。

 この方法で作成された迷路の道は、すべてつながっていることに注目してください。外壁のどこか2箇所を取り払って、外に出られるようにすれば入り口と出口のある迷路になりますよね。

 

お問い合わせ
©クロダ ソフトウェア サービス programmed by hidebou