JavaScriptで迷路の自動生成

JavaScriptで迷路自動生成のコードを書きました。

実行ボタンで開始できます。
寂しいのでなんとなく設置してみた主人公っぽいキャラのほうは、W,A,S,Dキーで動かせます。

迷路の生成方法は棒倒し法で、巡回しているキャラは左手法を使っています。
（どっちもこの手のものを作るには一番簡単なアルゴリズムですね。）

この棒倒し法が迷路を作る手順は以下のような感じです。

1. まず、迷路を作りたい部分を壁で囲みます。
2. その壁内部を一つ飛ばしに壁を作って埋めていきます。
3. 2.で埋めた壁を中心にランダムで上下左右どれかに壁を作っていきます。

なんとこれだけで迷路になってしまうのです。
このアルゴリズム考えたひと賢すぎる。

実際に作っていくのを見たほうがわかりやすいと思うので、サンプルを作りました。

実行ボタンで開始します。

初期状態のマップから壁が作られていき、迷路になっていくのが確認できると思います。
うーん、これで入れない場所のない迷路ができるなんて不思議ですねぇ。

いつものごとく微妙なコードですが、以下においておきます。

var Maze = function(w,h) {

    this.maze = new Array(h);
    this.width = w;
    this.height = h;
    
    for(var i = 0; i < w; ++i){
        this.maze[i] = new Array(w);
    }
}

Maze.prototype.init = function() {
    for(var i = 0; i < this.height; ++i){
        for(var j = 0; j < this.width; ++j){
            this.maze[i][j] = 0;
        }
    }   
}

Maze.prototype.create = function() {
    this.init();
    // 棒倒し法の初期状態マップを作る
    for(var i = 0; i < this.height; ++i ){
        for(var j = 0; j < this.width; ++j ){
            if( i == 0 ||  i == this.height - 1 )
                this.maze[i][j] = 1;
            else if( i % 2 == 0 && j % 2 == 0 )
                this.maze[i][j] = 1;
                
            if( j == 0 ||  j == this.width - 1 )
                this.maze[i][j] = 1;
        }
    }
    
    // 上で作ったマップの壁の上下左右どちらかに壁を追加する
    for(var i = 0; i < this.height; ++i ){
        for(var j = 0; j < this.width; ++j ){
            // 端以外で壁を見つけたら
            if( ( i == 0 ||  i == this.height - 1 ) || ( j == 0 ||  j == this.width - 1 ) )
                ;
            else if( i % 2 == 0 && j % 2 == 0 ){
                var ok = false;
                while( !ok ){
                    switch( Math.floor(Math.random()*5) ){
                    // 上に倒す
                    case 0:
                        // 既に倒れていたらやり直し
                        if( this.maze[i - 1][j] == 1 )
                            continue;
                        else{
                            // 上に倒せるのは一行目のときだけ
                            if( i == 2 ){
                                this.maze[i - 1][j] = 1;
                                ok = true;
                            }else
                                continue;
                        }
                        break;
                    // 下に倒す
                    case 1:
                        if( this.maze[i + 1][j] == 1 )
                            continue;
                        else{
                            this.maze[i + 1][j] = 1;
                            ok = true;
                        }
                        break;
                    // 右に倒す
                    case 2:
                        if( this.maze[i][j + 1] == 1 )
                            continue;
                        else{
                            this.maze[i][j + 1] = 1;
                            ok = true;
                        }
                        break;
                    // 左に倒す
                    case 3:
                        if( this.maze[i][j - 1] == 1 )
                            continue;
                        else{
                            this.maze[i][j - 1] = 1;
                            ok = true;
                        }
                        break;
                    }
                }
            }
        }
    }
    return true;
}

Maze.prototype.printMaze = function(x,y) {
    var src = new Array( "image/floor.png", "image/wall.png" );
    for(var i = 0; i < this.height; ++i){
        for(var j = 0; j < this.width; ++j){
            var name = "map"+i+""+j;
            document.write('<img id="'+name+'" src="'+src[this.maze[i][j]]+'" STYLE="position:absolute;top:'+(y+i*16)+';left:'+(x+j*16)+'">');
        }
    }
}

Maze.prototype.getWidth = function() {
    return this.width * 16;
}

Maze.prototype.getHeight = function() {
    return this.height * 16;
}

Maze.prototype.isHit = function(x,y) {
    return this.maze[y][x] == 1;
}


var Chara = function(name,path,map) {

    this.px = 0;
    this.py = 0;
    this.map = map;
    this.x = 0;
    this.y = 0;
    this.dir = 2;
    this.step = 0;
    this.name = name;
    this.animationCount = 0;
    this.SPEED = 2;
    this.CS = 16;
    this.movingLength = 0;
    this.isMoving = false;
    
    for(var i = 0; i < 12; ++i){
        document.write('<img id="'+(name+i)+'" src="'+(path+"/"+i)+'.png" STYLE="position:absolute;top:-64;left:-64;visibility:hidden">');
    }
}

Chara.prototype._set = function(element,x,y) {
    element.style.left = x - 4;
    element.style.top  = y - 16;    
}

Chara.prototype.put = function(x,y) {
    this.x = x;
    this.y = y;
    this.px = (x * this.CS);
    this.py = (y * this.CS);
    var element = document.getElementById(this.name + (this.dir * 3 + this.step));
    this._set(element,this.px,this.py);
    element.style.visibility = "visible";   
}

Chara.prototype.animation = function() {
    if(++this.animationCount > 10){
        this.setVisibleCurrentStep("hidden");
        this.step = this.step ? 0 : 2;
        var name = this.setVisibleCurrentStep("visible");
        this._set(document.getElementById(name),this.px,this.py);
        this.animationCount = 0;
    }
}

Chara.prototype.setVisibleCurrentStep = function(str) {
    var name = this.name + (this.dir * 3 + this.step);
    document.getElementById(name).style.visibility = str;
    return name;
}

Chara.prototype.move = function(input) {
    this.animation();
    
    if( this.isMoving ){
        this.setVisibleCurrentStep("hidden");
        var ret = false;
        switch (this.dir) {
            case 1: ret = this.moveRight(); break;
            case 3: ret = this.moveLeft();  break;
            case 0: ret = this.moveUp();    break;
            case 2: ret = this.moveDown();  break;
        }
        var name = this.setVisibleCurrentStep("visible");
        this._set(document.getElementById(name),this.px,this.py);
        return ret;
    }else{
        if((this.isMoving = (input.up || input.down || input.left || input.right)) ){
            this.setVisibleCurrentStep("hidden");
            
            if(input.up && !input.down){
                this.dir = 0;                   
            }else if(input.down && !input.up){
                this.dir = 2;
            }
            if(input.left && !input.right){
                this.dir = 3;                   
            }else if(input.right && !input.left){
                this.dir = 1;
            }
            var name = this.setVisibleCurrentStep("visible");
            this._set(document.getElementById(name),this.px,this.py);
        }
    }
    return false;
}

Chara.prototype.autoMove = function(courseSearch) {
    this.animation();
    
    if( this.isMoving ){
        this.setVisibleCurrentStep("hidden");
        var ret = false;
        switch (this.dir) {
            case 1: ret = this.moveRight(); break;
            case 3: ret = this.moveLeft();  break;
            case 0: ret = this.moveUp();    break;
            case 2: ret = this.moveDown();  break;
        }
        var name = this.setVisibleCurrentStep("visible");
        this._set(document.getElementById(name),this.px,this.py);
        return ret;
    }else{
        this.setVisibleCurrentStep("hidden");
        this.dir = courseSearch.getGoNextLeftHandMethod();
        var name = this.setVisibleCurrentStep("visible");
        this._set(document.getElementById(name),this.px,this.py);
        this.isMoving = true;
    }
    return false;
}

Chara.prototype.moveLeft = function() {
    var nextX = this.x - 1;
    var nextY = this.y;
    if (nextX < 0) {
        nextX = 0;
    }
    if (!this.map.isHit(nextX, nextY)) {
        this.px -= this.SPEED;
        if (this.px < 0) {
            this.px = 0;
        }
        this.movingLength += this.SPEED;
        if (this.movingLength >= this.CS) {
            this.x--;
            this.px = this.x * this.CS;
            this.isMoving = false;
            this.movingLength = 0;
            return true;
        }
    } else {
        this.isMoving = false;
        this.px = this.x * this.CS;
        this.py = this.y * this.CS;
    }
    
    return false;
}

Chara.prototype.moveRight = function() {
    var nextX = this.x + 1;
    var nextY = this.y;
    if (!this.map.isHit(nextX, nextY)) {
        this.px += this.SPEED;
        if (this.px > this.map.getWidth() - this.CS) {
            this.px = this.map.getWidth() - this.CS;
        }
        this.movingLength += this.SPEED;
        if (this.movingLength >= this.CS) {
            this.x++;
            this.px = this.x *this. CS;
            this.isMoving = false;
            this.movingLength = 0;
            return true;
        }
    } else {
        this.isMoving = false;
        this.px = this.x * this.CS;
        this.py = this.y * this.CS;
    }
    
    return false;
}

Chara.prototype.moveUp = function() {
    var nextX = this.x;
    var nextY = this.y - 1;
    if (nextY < 0) {
        nextY = 0;
    }
    if (!this.map.isHit(nextX, nextY)) {
        this.py -= this.SPEED;
        if (this.py < 0) this.py = 0;
        this.movingLength += this.SPEED;
        if (this.movingLength >= this.CS) {
            this.y--;
            this.py = this.y * this.CS;
            this.isMoving = false;
            this.movingLength = 0;
            return true;
        }
    } else {
        this.isMoving = false;
        this.px = this.x * this.CS;
        this.py = this.y * this.CS;
    }
    
    return false;
}

Chara.prototype.moveDown = function() {
    var nextX = this.x;
    var nextY = this.y + 1;
    if (!this.map.isHit(nextX, nextY)) {
        this.py += this.SPEED;
        if (this.py > this.map.getHeight() - this.CS) {
            this.py = this.map.getHeight() - this.CS;
        }
        this.movingLength += this.SPEED;
        if (this.movingLength >= this.CS) {
            this.y++;
            this.py = this.y * this.CS;
            this.isMoving = false;
            this.movingLength = 0;
            return true;
        }
    } else {
        this.isMoving = false;
        this.px = this.x * this.CS;
        this.py = this.y * this.CS;
    }
    
    return false;
}

var CourseSearch = function(map,chara) {
    this.map = map;
    this.searcher = chara;

    this.UP = 0;    
    this.DOWN = 2;
    this.LEFT = 3;
    this.RIGHT = 1;
    
    this.goFront = false;
}

CourseSearch.prototype.getGoNextLeftHandMethod = function () {
    if( this.goFront ){
        this.goFront = false;
        return this.getSearcherDir( this.UP );
    }
        
    // ゴールに着いているなら-1を返す
    //if( this.searcher.x == this.goalX && this.searcher.y == this.goalY )
    //  return -1;
    
    // 左に進めるか？
    if( this.checkGoLeft( this.searcher.x, this.searcher.y ) ){
        this.searcher.dir = ( this.getSearcherDir( this.LEFT ) );
        this.goFront = true;
        return this.getSearcherDir( this.UP );
    }

    // 前に進めるか？
    if( this.checkGoFront( this.searcher.x, this.searcher.y ) ){
        this.goFront = true;
        return this.getSearcherDir( this.UP );
    }

    // 右に進めるか？
    if( this.checkGoRight( this.searcher.x, this.searcher.y ) ){
        this.searcher.dir = ( this.getSearcherDir( this.RIGHT ) );
        this.goFront = true;
        return this.getSearcherDir( this.UP );
    }
    
    this.searcher.dir = ( this.getSearcherDir( this.DOWN ) );
    this.goFront = true;
    return this.getSearcherDir( this.UP );  
}

// 探索者の方向から見て画面に対する方向を返す
CourseSearch.prototype.getSearcherDir = function(dir) {
    switch( dir ){
        case this.LEFT: 
            switch( this.searcher.dir ){
                case this.LEFT : return this.DOWN;
                case this.RIGHT: return this.UP;
                case this.UP:    return this.LEFT;
                case this.DOWN:  return this.RIGHT;
            }
            break;
        case this.RIGHT:
            switch( this.searcher.dir ){
                case this.LEFT : return this.UP;
                case this.RIGHT: return this.DOWN;
                case this.UP:    return this.RIGHT;
                case this.DOWN:  return this.LEFT;
            }
            break;
        case this.UP:
            return this.searcher.dir;
        case this.DOWN:
            switch( this.searcher.dir ){
                case this.LEFT : return this.RIGHT;
                case this.RIGHT: return this.LEFT;
                case this.UP:    return this.DOWN;
                case this.DOWN:  return this.UP;
            }
            break;
    }
    return -1;
}

// 探索者から見て、そちらの方向に進めるのかを返す
CourseSearch.prototype.checkGoLeft = function(x,y) {
    
    var nextX = x - 1;
    var nextY = y;
    
    switch( this.searcher.dir ){
        case this.LEFT:
            nextX = x;
            nextY = y + 1;
            break;
        case this.RIGHT:
            nextX = x;
            nextY = y - 1;
            break;
        case this.UP:
            nextX = x - 1;
            nextY = y;
            break;
        case this.DOWN:
            nextX = x + 1;
            nextY = y;
            break;
    }

    return !this.map.isHit(nextX, nextY);
}

CourseSearch.prototype.checkGoRight = function(x,y) {
    var nextX = x + 1;
    var nextY = y;

    switch( this.searcher.dir ){
        case this.LEFT:
            nextX = x;
            nextY = y - 1;
            break;
        case this.RIGHT:
            nextX = x;
            nextY = y + 1;
            break;
        case this.UP:
            nextX = x + 1;
            nextY = y;
            break;
        case this.DOWN:
            nextX = x - 1;
            nextY = y;
            break;
    }

    return !this.map.isHit(nextX, nextY);
}

CourseSearch.prototype.checkGoFront = function(x,y) {
    var nextX = x;
    var nextY = y - 1;

    switch( this.searcher.dir ){
        case this.LEFT:
            nextX = x - 1;
            nextY = y;
            break;
        case this.RIGHT:
            nextX = x + 1;
            nextY = y;
            break;
        case this.UP:
            nextX = x;
            nextY = y - 1;
            break;
        case this.DOWN:
            nextX = x;
            nextY = y + 1;
            break;
    }

    return !this.map.isHit(nextX, nextY);
}

// 入力
var Input = function() {
    this.up = false;
    this.down = false;
    this.left = false;
    this.right = false;
}

Input.prototype.keyDown = function (event) {
    switch(event.keyCode) {
        case 87: input.up = true; break;
        case 83: input.down = true; break;
        case 65: input.left = true; break;
        case 68: input.right = true; break;
    }
}

Input.prototype.keyUp = function (event) {
    switch(event.keyCode) {
        case 87: input.up = false; break;
        case 83: input.down = false; break;
        case 65: input.left = false; break;
        case 68: input.right = false; break;
    }       
}

// 入力
var input = new Input();

// マップの大きさ
// 奇数である必要あり
var MAZE_X = 25;
var MAZE_Y = 25;
        
// 迷路作成・描画
var maze = new Maze(MAZE_X,MAZE_Y);
maze.create()
maze.printMaze(0, 0);

// キャラ作成・設定
var chara = new Chara("player","image/player",maze);
chara.put(1,1);

var enemy = new Chara("enemy","image/enemy",maze);
var courseSearch = new CourseSearch(maze,enemy);
enemy.put(MAZE_X-2,MAZE_Y-2);
        
// 指定時間で更新
var timerID = setInterval("update()",16*2);
function update(){
    chara.move(input);
    enemy.autoMove(courseSearch);
}