良い迷路とは何か?

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

良い迷路とは何か?

投稿記事 by usao » 6年前

迷路の自動生成について考える.
とは言え,いわゆる「生成アルゴリズム」の側ではなく,

何かしらプログラムがデータを自動的に生成した場合,そのデータの「良さ」というのはどうやって評価するのだろう?
「迷路としての良さ」って何だろう?
という側についてである.


例えば,迷路のデータの形式として,
「N*Mのマス目があって,各マスの値が{壁,通路}のどちらかを取る」
という簡素なものを考えることにする.

CODE:

bool Maze[M*N]
みたいなデータだ.trueとfalseのどちらかが「壁」を,もう一方が「通路」を表す的な.
自動生成アルゴリズムは何らかの処理の結果,配列の各要素の値を決定するわけだ.

さて,
「生成されたデータの評価を行う(迷路としての良さを計算する)関数」:

CODE:

//「良い」ほど大きい値を返す
double GoodnessAsMaze( bool Data[], size_t M, size_t N )
{
  //計算内容不明
}
を用意することを考えれば,この関数の中身を適切に定義することができさえすれば,
「自動生成するアルゴリズム」の側はぶっちゃけどうでもいいわけだ.
極端な話(?),全マスの値を乱数で決めるような処理であろうが,
とにかくぶっ通しで動かしてさえいれば(時間が経過するほど相対的に)「良い」データが得られることになる(よね?).
この評価関数の中身を入れ替えれば,「生成される迷路の具合」を変化させられる可能性もあるわけだ.なんと便利な話だろうか!

しかし,肝心の「評価関数の中身」をうまく書ける気がしないんですよね.うーむ.

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

Re: 良い迷路とは何か?

投稿記事 by usao » 6年前

補足:
評価関数は,データを迷路として見た場合の「形」を評価する.

「スタートとゴールの位置」みたいな要素は評価対象の生データには含まれない.

が,そういう事柄を評価内容に含めたい場合
(例えば「スタートからゴールまでの経路が繋がっていること」みたいなのを評価したい場合)
には,
評価関数自身が,その内側で
「このデータの形だと……スタートとゴールをこことここに置いたら,めっちゃ良い迷路やん!」
とかなんとか勝手に考えて評価すればいい.

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

Re: 良い迷路とは何か?

投稿記事 by usao » 6年前

例えば下記のようなプログラムがあったときに
EvalGoodnessAsMaze()関数のできばえを競う遊び!
(勝敗を決めるための最終的な評価は人間が行うのだなぁ)

…みたいなの,入社試験とかにいかがでしょうか?

CODE:

//迷路データ.W*Hのbool
template< size_t W, size_t H >
struct MazeData
{
	bool P[ W*H ];

	//デフォルトコンストラクタ
	MazeData(){	/* P[]の内容がランダムで決定される*/	}

	//データサイズ系
	static size_t Width(){	return W;	}
	static size_t Height(){	return H;	}
	static size_t Size(){	return W*H;	}

	//(x,y)位置へのアクセスヘルパ
	bool &At( int x, int y ){	return P[ y*W + x ];	}
	bool At( int x, int y ) const {	return P[ y*W + x ];	}
};

//Srcを元に,何か別のデータを生成してDstに格納する.
//(SrcとDstが全く同じ内容にならないことは保障する)
template< size_t W, size_t H >
void TransformProcess( const MazeData<W,H> &Src, MazeData<W,H> &Dst )
{
	Dst = Src;
	/* ランダムに,Dst.P[]の何箇所かの値を反転させるとかそんな */
}

//引数データの「迷路としての良さ」を評価する.
//「良い」ほど大きい値を返す
template< size_t W, size_t H >
double EvalGoodnessAsMaze( const MazeData<W,H> &Data )
{
	//★TODO : 評価計算の実装★
	return 0;
}

//main
int main(void)
{
	/*このあたりで乱数生成手段に特定のSeed値を与える*/

	//迷路の生成と評価
	MazeData<32,24> Buff[2];
	MazeData<32,24> *pCurrBest = &(Buff[0]);
	MazeData<32,24> *pCandidate = &(Buff[1]);

	double BestScore = EvalGoodnessAsMaze( *pCurrBest );
	for( int i=0; i<10000; ++i )	//※適当な回数試行(ループ条件は「一定時間」とかの方が良いかも?)
	{
		TransformProcess( *pCurrBest, *pCandidate );
		double Score = EvalGoodnessAsMaze( *pCandidate );
		if( Score > BestScore )
		{
			BestScore = Score;
			std::swap( pCurrBest, pCandidate );
		}
	}

	//結果表示
	/* pCurrBestが指すデータを表示なりする */

	return 0;
}

アバター
いわん
記事: 32
登録日時: 9年前

Re: 良い迷路とは何か?

投稿記事 by いわん » 6年前

やっぱり、ゴールに到達するまでにより時間がかかる(迷う)のがよい迷路ではないだろうか。
迷路を探索歩行する標準のモデルを考えて、迷路を探索させてどれだけ迷ったかを計測するとか。
でも探索歩行のモデルを考えるほうが大変そう。「壁伝いの方法」とか脱出方法のセオリーの
存在も無視できませんね。
私としては迷路全体の見た目の美しさもよい迷路の条件に加えたいところです(^^)

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

Re: 良い迷路とは何か?

投稿記事 by usao » 6年前

評価関数は,「迷路として良いか」以前に,まず「迷路」が生成されるように仕向ける必要があるので,
「ただの雑音的なパターン」と「迷路っぽい(?)パターン」があった際に,後者に高得点を出せないとダメですね.
ここが既にわりと難しそう.

「全マスが通路!」みたいなパターンに低い点数を与えるために,例えば
【壁と通路の個数は半々くらいになるほど良いぞ】とかいう評価を与えることを考えると…
 ↓
「じゃあ砂嵐パターンで良くね!?」とかなりそうなので,
【空間の個数が多いほど低評価だぞ】とかいう要素を加えることを考える.すると…
 ↓
「じゃあ,左半分が全部壁で,右半分が全部通路な!」とかいうのが高い評価を得ることになる.
うーん.そうすると,{通路の細さ?,壁の連結具合?}みたいな事柄に関する評価を入れないと…??


まず上記をクリアして,どうにか「迷路っぽいもの」を選び出せるようになったとして,
そこからさらに「良い迷路」を評価する方法:例えば
> ゴールに到達するまでにより時間がかかる(迷う)
みたいなのを考えると,
・【一本道はダメ:分岐が欲しい】
・【分岐から行き止まりまでの距離が1とかじゃ話にならんので長い経路がいくつか(?)欲しい】
とか何とか…? そういうルールを明文化(:実装)するのがさらに難しい予感.

加えて
> 見た目の美しさ
とか考えると,「美しさ…って何だろう?」っていう.
対象性? 直線性? 模様が猫に見える? 放射状に見えたらどこぞから怒られたりして…(冗談)