[WP]no.002 素朴な迷路生成

第2回「迷路生成」
製作時間1h あえてjava使用
壁のデータ構造を考えるのを忘れてそこそこ時間がかかってしまった様子
再帰使っちゃったのでメモリ使用量はお察し、やや実行速度重視?

こんな感じ

□□□□□□□■□□□
□■■■■■■■□■□
□□□■□□□□□■□
□■□■□■■■■■□
□■□□□■□□□■□
□■■■■■□■□■□
□■□□□■□■□■□
□■□■□■■■□■□
□□□■□■□□□■□
■■■■□■□■□■□
□□□□□□□■□■□
データ構造と再帰を見直したい。


import java.util.*;

public class Maze {

private int width;
private int height;
private boolean[][] wall;
private Random rnd;

public int getWidth() {
return width;
}

public int getHeight() {
return height;
}

public Maze(int w,int h){
int x,y;
width = w;
height = h;
wall = new boolean[width*2-1][height*2-1];
for (x=0;x<w*2-1;x++)
for (y=0;y<h*2-1;y++)
wall[x][y] = !(x%2==0 && y%2==0);
rnd = new Random();
}

public void randomCreate(){

recCreate(rnd.nextInt(width)*2,rnd.nextInt(height)*2);
}

private boolean recCreate(int x,int y){
Stack<Integer> dl;
int dirc;

if (wall[x][y]) return true;
wall[x][y] = true;

dl = createRandomDirection();
for (int i=0;i<4;i++){
dirc = dl.pop().intValue();
if (2<=x && dirc == 0) wall[x-1][y]=recCreate(x-2,y);
if (2<=y && dirc == 1) wall[x][y-1]=recCreate(x,y-2);
if (x<width*2-2 && dirc == 2) wall[x+1][y]=recCreate(x+2,y);
if (y<height*2-2 && dirc == 3) wall[x][y+1]=recCreate(x,y+2);
}
return false;
}

private Stack<Integer> createRandomDirection(){
Stack<Integer> r = new Stack<Integer>();
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(0);l.add(1);l.add(2);l.add(3);
r.push(l.remove(rnd.nextInt(4)));
r.push(l.remove(rnd.nextInt(3)));
r.push(l.remove(rnd.nextInt(2)));
r.push(l.get(0));
return r;
}

public String WriteString(){
int x,y;
String result = "";
for (x=0;x<width*2-1;x++){
for (y=0;y<height*2-1;y++){
if (x%2==0 && y%2==0){result+="□";continue;}
if (x%2==1 && y%2==1){result+="■";continue;}
if (wall[x][y]){result+="■";}
else result+="□";
}
result +="\n";
}
return result;
}
}



テストクラス


public class TestMaze {
public static void main(String arg[]){
Maze maze = new Maze(6,6);
System.out.println(maze.WriteString());
maze.randomCreate();
System.out.println(maze.WriteString());
}
}



2015/06/13 追記解説
時間重視なので、投稿時にはコメントを入れませんが、気が向いたら後日解説やコメントを入れるかもしれません

保持するwidth,heightは、その軸の道の数。

wall配列は迷路全体のマスの要素を保持。つまり、インデックスx偶数y偶数は必ず道、x奇数y奇数は必ず壁、ランダムに生成すべきはx偶数y奇数,x奇数y偶数の要素である。

穴掘り法では、現在地を選択し、まだ通行したことがない、隣接した道を選んで、その道と現在地との間の壁を破壊する。
この道は既に通行した、していないフラグを保持する変数が必要だが、それをwallのインデックスx偶数y偶数に割り当てている。

再帰部分については解説放棄。グラフの深さ優先探索と一緒です。

createRandomDirection()は、0,1,2,3の集合のスタックが返ってきます。popすると、ランダムに出てきます。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : Java アルゴリズムとデータ構造

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>