迷路生成アルゴリズムのソース

迷路を生成のアルゴリズムのサンプルコードどこかにないですか？

迷路生成アルゴリズムといっても色々あるかもしれませんが
知らないのでなんでもいいです。
言語もなんでもいいです。とにかく見たいです。

NetHack、Angband、Omega、ローグクローンのソースなんかも
見てみましたがいまいちです。
一本道の迷路じゃなくて部屋で区切られているというのが邪魔しているのかも、、、
お願いします。

xmaze を忘れていないか?

昔、ファンダムに面白いのが載ってたなあ。

ソースが迷路なものはいっぱい有るぞ。

>2
ftp://ftp.scn.rain.com/pub/games/xmazewar.tar.Z
これですかーと思ったらコンパイルできない。
Xのバージョンが新しいのかな。

ややりました！！
http://ring.etl.go.jp/archives/X/opengroup/unsupported/programs/maze/
ここです。
xmkmfは成功するけどmakeで失敗します。(VineLinux 2.0CR)
独自にgetoptを作っているのが原因なのでImakefileの真ん中辺りを
#else
SRCS = maze.c
OBJS = maze.o
#endif
とすればmake出来ますやった！

今、globalでHTML化して読んでます。

initialize_mazeは外壁とか出入り口を作ります。
create_mazeで迷路本体を作ります。
choose_doorは壁を作る方向を決めるのかな????

壁や通路じゃなくてさ、三次元のグニャグニャのチューブみたいな
迷路の作成考えてよ。

>8
三次元の基礎さえ知りません。
あ、でも今月のC MAGAZINEになんか書いてるので見てみます。

人間が迷路を作るとしたらどうするか考えて
それをアルゴリズム化しましょう。

グレッグ・ブライトの「迷路の本」に載っているやつは難しかった、
とゆーより、よほどの運が無いと抜けられなかったなぁ…
なにしろ、「行きどまりが無い」迷路だったからなぁ…
そういうのを自動生成してほしいなぁ、って、わけわかんねーな、これだけじゃ。

ホントの迷路じゃないけど、それっぽいのと短いのであげてみた
#include <stdio.h>
#include <stdlib.h>
void prtc0(int n＠｀char *s)
{while(n--){ *s++=rand()%2; }
}

void prtc1(int n＠｀char *s)
{while(n--){if(*s++){printf("%s"＠｀"／　");}else{printf("%s"＠｀"　＼");};}
printf("\n");
}

void prtc2(int n＠｀char *s)
{while(n--){if(*s++){printf("%s"＠｀"　／");}else{printf("%s"＠｀"＼　");};}
printf("\n");
}

int main()
{ char buf[19];
　int i;
　for(i=0;i<100;i++)
　{
　　prtc0(sizeof buf＠｀buf);
　　prtc1(sizeof buf＠｀buf);
　　prtc2(sizeof buf＠｀buf);
　}
return 0;
}

実行結果はこんな感じ・・・上手く表示されるかな？
＼　　／　／＼　　／＼　＼　　／　／＼　　／　／　／　／＼　
／　／　／　／　／　／　　＼／　　＼　＼　＼／　／　／　／　
　／　／　／　／　／　／＼　　／＼　＼　＼　　／　／　／　／＼
／　　＼／　　＼／　／　　＼／　／　　＼／　／　／　／　　＼
　／＼　　／＼　　／　／＼　　／　／＼　　／　／　／　／＼　＼
　＼／　／　　＼／　／　　＼／　　＼／　／　／　　＼／　／　
＼　　／　／＼　　／　／＼　　／＼　　／　／　／＼　　／　／＼
　＼／　　＼／　　＼／　　＼／　／　／　／　／　　＼／　　＼
＼　　／＼　　／＼　　／＼　　／　／　／　／　／＼　　／＼　＼
　＼／　／　／　／　　＼　＼／　　＼　＼／　／　　＼／　　＼
＼　　／　／　／　／＼　＼　　／＼　＼　　／　／＼　　／＼　＼
／　　＼／　／　　＼／　／　　＼／　　＼　＼　＼／　／　／　／
　／＼　　／　／＼　　／　／＼　　／＼　＼　＼　　／　／　／
／　　＼　＼／　／　　＼　＼／　／　　＼／　　＼／　　＼　＼
　／＼　＼　　／　／＼　＼　　／　／＼　　／＼　　／＼　＼　＼

グレッグ・ブライトねぇ。

迷路を極めて、あっちの世界にいっちゃって。
天国で幸せに暮らしているかしら。

Windows の 画面がゆがんだりするスクリンセーバがあったりするけど、
アレのソースってでている？

あと、xlock の swarm(?) とか julian(?) とかのソースもみてみたい。

基本的な考え方は…
1)入口と出口を決めて、それを一直線に結ぶ。
2)1)で決めた道を「移動」「折り曲げ」する。※
3)2)と並行して「分岐」を作っていく。※

※すでに道が置かれて部分には適用できない。
まだ道が出来ていない部分に「移動」「折り曲げ」「分岐」が可能。

1)で入口から出口までつながっているのは保障されるので
2)3)の処理はテキトーに行えばＯＫ。

俺のしっているやりかた。
A線とB線をくっつけないように、再起的に延ばせば、出来上がり。

・迷路の作成
塊を掘り進む形で、塊の外部は既に掘ったところとみなした上で再帰的に、
１．開始点となる点を座標（２，２）とし、そこを掘った上で着目点とする。
２．着目点の四方を順に（或いは乱数で）チェックする。
　　ａ．そこを掘るとすでに掘った部分に貫通してしまう場合。
　　　　次の方向をチェックする。
　　ｂ．そこを掘ってもすでに掘った部分に貫通しない場合。
　　　　そこを掘り着目点をそことして、２．を再帰的に呼び出す。
　　ｃ．全部の方向を調べても貫通しない場所が無い場合。
　　　　再帰を戻る。

３．最上位レベルまで戻ったときは迷路は完成している。
　　外周の掘った部分と繋がる任意の２点に穴を開けそこを入り口と
　　出口として終了。

あ、このやり方で１００＊１００位の迷路を作ると再帰が深くなりすぎて
ＤＯＳ環境じゃスタックがオーバーフローするからWin32環境などで
やること。

って、17が荒っぽく書いてんじゃん。

再帰をつかわなくても、迷路のすべての部分について１８みたいな事を繰り返して、
どこも掘れなくなったら終りっていう方法もあるね。

要するに、ランダムな方向に塗りつぶしていく
ペイントルーチンを作ればいいのだ。……なんか違う気もするが。

かべは作らなくちゃだが、やってる事は似たようなもんだな。

swarmは結構簡単に見つかると思うよ。検索すれば。
たしかVectorの本にも収録されていたような気が…。

サンクス&haerts;

追加便乗。
Windows 98 で RPM ファイルを解凍したいんだけど、どうすればいい？

結構、いかすアルゴリズムだと思ったけどな、当時は。
今でも、おぼろげながら覚えてるよ。
説明は出来ないんだけどね。

import java.applet.*;
import java.awt.*;
import java.awt.event.*;

public class MazeApplet extends Applet implements Runnable{
final int XMAX = 80;
final int YMAX = 24;
final int MAXSITE = XMAX*YMAX/4;
int map[][] = new int[XMAX+1][YMAX+1];
int nsite = 0;
int xx[] = new int[MAXSITE];
int yy[] = new int[MAXSITE];
int dx[] = { 2＠｀ 0＠｀-2＠｀ 0};
int dy[] = { 0＠｀ 2＠｀ 0＠｀-2};
int dirtable[][] = {
{ 0＠｀1＠｀2＠｀3 }＠｀ { 0＠｀1＠｀3＠｀2 }＠｀ { 0＠｀2＠｀1＠｀3 }＠｀ { 0＠｀2＠｀3＠｀1 }＠｀ { 0＠｀3＠｀1＠｀2 }＠｀ { 0＠｀3＠｀2＠｀1 }＠｀
{ 1＠｀0＠｀2＠｀3 }＠｀ { 1＠｀0＠｀3＠｀2 }＠｀ { 1＠｀2＠｀0＠｀3 }＠｀ { 1＠｀2＠｀3＠｀0 }＠｀ { 1＠｀3＠｀0＠｀2 }＠｀ { 1＠｀3＠｀2＠｀0 }＠｀
{ 2＠｀0＠｀1＠｀3 }＠｀ { 2＠｀0＠｀3＠｀1 }＠｀ { 2＠｀1＠｀0＠｀3 }＠｀ { 2＠｀1＠｀3＠｀0 }＠｀ { 2＠｀3＠｀0＠｀1 }＠｀ { 2＠｀3＠｀1＠｀0 }＠｀
{ 3＠｀0＠｀1＠｀2 }＠｀ { 3＠｀0＠｀2＠｀1 }＠｀ { 3＠｀1＠｀0＠｀2 }＠｀ { 3＠｀1＠｀2＠｀0 }＠｀ { 3＠｀2＠｀0＠｀1 }＠｀ { 3＠｀2＠｀1＠｀0 }};
int tmpi＠｀tmpj;
int Si=3＠｀Sj=3＠｀Ei=XMAX-3＠｀Ej=YMAX-3＠｀success=0;
int sp=0＠｀ri[]=new int[200]＠｀rj[]=new int[200];
Color col[] = {Color.magenta＠｀Color.black＠｀Color.orange};
Image offs;
Graphics grf;
Thread th = null;

public void init(){
offs = createImage(820＠｀260);
grf = offs.getGraphics();
}

public void add(int i＠｀int j){
xx[nsite] = i; yy[nsite] = j; nsite++;
}

public int select(int i＠｀int j){
int r;
if(nsite == 0) return 0;
nsite--; r = (int)(Math.random()*nsite+1);
tmpi = xx[r]; xx[r] = xx[nsite];
tmpj = yy[r]; yy[r] = yy[nsite];
return 1;
}

public void meiro(){
int i＠｀j＠｀i1=0＠｀j1=0＠｀d＠｀t＠｀tt;

for(i=0;i<=XMAX;i++)
for(j=0;j<=YMAX;j++)
map[i][j] = 2;
for(i=3;i<=XMAX-3;i++)
for(j=3;j<=YMAX-3;j++)
map[i][j] = 0;
map[2][3] = 0; map[XMAX-2][YMAX-3] = 0;
for(i=4;i<=XMAX-4;i+=2){
add(i＠｀2); add(i＠｀YMAX-2);
}
for(j=4;j<=YMAX-4;j+=2){
add(2＠｀j); add(XMAX-2＠｀j);
}
tmpi=i;tmpj=j;
while(select(tmpi＠｀tmpj)==1){
for(;;){
tt=(int)(Math.random()*24);
for(d=3;d>=0;d--){
t=dirtable[tt][d]; i1=tmpi+dx[t]; j1=tmpj+dy[t];
if(map[i1][j1]==0) break;
}
if(d<0) break;
map[(tmpi+i1)/2][(tmpj+j1)/2]=2;
tmpi=i1; tmpj=j1; map[tmpi][tmpj]=2; add(tmpi＠｀tmpj);
try{
th.sleep(100);
}catch(InterruptedException e){}
repaint();
}
}
}

public int visit(int i＠｀int j){
map[i][j]=1;
ri[sp]=i;rj[sp]=j;sp++;
repaint();
try{
th.sleep(110);
}catch(InterruptedException e){}
if(i==Ei&&j==Ej) success=1;

if(success!=1&&map[i][j+1]==0) visit(i＠｀j+1);
if(success!=1&&map[i+1][j]==0) visit(i+1＠｀j);
if(success!=1&&map[i][j-1]==0) visit(i＠｀j-1);
if(success!=1&&map[i-1][j]==0) visit(i-1＠｀j);

sp--;
return success;
}

public void update(Graphics g){
paint(g);
}

public void paint(Graphics g){
grf.setColor(Color.magenta);
grf.fillRect(0＠｀0＠｀820＠｀260);
for(int j=2;j<=YMAX-2;j++){
for(int i=2;i<=XMAX-2;i++){
grf.setColor(col[map[i][j]]);
grf.fillOval(i*10＠｀j*10＠｀10＠｀10);
}
}
g.drawImage(offs＠｀0＠｀0＠｀this);
}

public void start(){
th = new Thread(this);
th.start();
}

public void stop(){
th = null;
}

public void run(){
meiro();
map[2][3]=2; map[XMAX-2][YMAX-3]=2;
int k=visit(Si＠｀Sj);
}

}

正方形に対してひし形のマップが多い理由が少しだけ判ったよ
２つのしかも鏡パターンで描けるんだねえ