地図を生成しよう（難解な地図を求めて）

Question

地図（というか迷路）を生成するプログラムを書いています。
ここでの問題意識としては以下のようなものが挙げられるはずです。
・地図生成にあたって、人間が解くときの難解さを意識した迷路にするためにはどのようにプログラムするべきか？

しかし、この問いに答えるためには次の問題に答えることが大切です。
・そもそも地図の難解さをどのような指標で定義づけするべきか？

２つ目の問いに答えるために、僕はまず、次のような概念を定義しました。
20×20の升目上の領域において、与えられたA地点から測ったB地点の「深さ」とは、
「A地点から連結に移動してB地点に辿り着く事ができる最短の経路のマスの移動距離」

とりあえず、この「深さ」を測るプログラムを、僕は前回の質問文中で求め、解決しました。
これが結果です。
地図中を連結に移動する

この地図において、最深部となるのが、赤色のマスで、最もスタート地点から遠い点です。
まず、任意の地図中の最深部を測ることに成功したわけです。
「難解さ」を定義する上で、A地点からB地点への深度、というのは有用なはず。

では、次にどのような方向に進んだらいいでしょう？
僕としては地図を調べるにあたって、もっと様々な指標を、まずは発見したい。
ここでご意見を募っている理由がそれにあたります。
ご意見持っている方がおられましたら、お願いします。

Comments

[justmeet0924]

回答してくださった皆様、ありがとうございます。
低評価がたくさんついた時には、「俺の質問力が災いしたか・・・」と愕然としましたが、きちんと汲み取ってくださった方もたくさんおられたようで、これからのプログラミングdaysがより楽しみになりました。ありがとうございます。

[justmeet0924]

低評価多いので、とりあえず閉めます。この問題については継続的に考えます。

[ozwk]

回答はしましたけどそれはそれで低評価もしてます

Answer 1

難しい迷路の条件に関する研究

---

といったように、
自分で考えることが目的でもない限りは先行研究が無いかを調べるところから始めると良いでしょう。

Comments

[justmeet0924]

特に研究がしたいわけではなく、プログラミングの動的なプロセスを味わいたいだけなんですがね……。

[ozwk]

よその研究の過程や成果を利用する話です

Answer 2

正解の経路長だけを評価するならば，既存回答で述べられているとおり，「全箇所を通る一本道」という自明解に陥ります．
また，「分岐数を増やすこと」を重視させると，「１マスの袋小路」みたいな，人間には一瞬で枝刈りできる（つまり難しさに全く寄与しない）分岐だけが大量に生まれる結果となります．

プログラムに解かせる話ではなくて，人間から見ての難しさということであれば「経路の複雑さ」を考えるべきと思います．
言い換えれば，「ぱっと見で把握できないこと」．

---

このような話を過去に検討した個人的な経験に基づいて言えば，
「複雑さ」は正解経路だけでなく不正解の経路についても評価する必要があります．

＃なお，経路長と「複雑さ」の間に正の相関がある形での評価を行うならば，経路長を陽に評価基準とする必要はなくなります．

Answer 3

teratailの推奨する質問ではないとは思いますが、個人的興味から回答します。

「深さ」を最大化することは、一本道となります。

重要な指標は、分岐数と逆方向度です。
0. 分岐数：
移動できる方向が3以上のマスの数
移動できる方向が4のマス(つまり十字路)は二倍でカウントするというのもあり

1. 逆方向度：

それぞれのマスからゴールのマスへの方向ベクトルと正解方向への方向ベクトルの角度を0°から180°としたときの角度の90°以上のマスの数
逆方向度がゼロに近いほど解かれやすい迷路になる。