迷路の作り方は構造に影響を与えるのか~特徴量を用いた傾向分析~

情報処理学会

説明

迷路は多方面で利用されているが，どのようなアルゴリズムで迷路を作ればユーザーが求める特徴を持つ迷路を取得しやすいのかといった情報がほとんど知られていない．本研究では，代表的な６種類の迷路生成アルゴリズムで，23 段階のサイズの迷路群を用意し，迷路群に対する１~３次的な特徴量の分布が迷路サイズの増大に伴いどのように変化するのかを解析した．また，特徴量の傾向から主成分分析を用いて迷路生成アルゴリズム間の相互関係を求めた．AldousBroder と GrowingTree は性質が似ており，曲がり角が多くなりやすい迷路を作る特徴があった．これとは逆に Sidewinderは，曲がり角が少なく，R 領域に構造を作り，分岐が深くなりやすい特徴の迷路を作る特徴があった．PrimsとKruskalは，迷路全体における曲がり角は少なくなるものの，正道の上の曲がり角は他のアルゴリズムよりもやや多く，L 領域にも経路構造もつ迷路を作る特徴があった．Division は，これらのアルゴリズムの中間的な性質を有していた．代表的な迷路生成アルゴリズムによって生成された迷路の特徴と，アルゴリズム間の類似性を明らかにできた．

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ