迷路を作って遊んでみる

JavaScript

迷路の探索がやりたくなったので、迷路を作ってみました。

セルの種類

まず迷路を表現するためにセルを作ります。このときセルの種類として以下のものを想定します。

  • 壁
  • 通路
  • スタート
  • ゴール

これをオブジェクトで表現すると以下のようになります。

var MAZETYPE = {
    BLOCK : "block",
    WAY : "way",
    START : "start",
    GOAL : "goal"
};

セルを格納

次に迷路を表現するMazeオブジェクト(コンストラクタ)を作ります。このMazeオブジェクトは、先ほど作ったセルを格納するために、内部に二次元配列を持たせます。この二次元配列には、初期値として壁を表すオブジェクトMAZETYPE.BLOCKが入れられます。また、この二次元配列のためのセッターとゲッターも実装します。

var Maze = function(w,h) {
    this.w = w;
    this.h = h;
    this.array = new Array(w);
    for(var i = 0; i < w; i++) {
        this.array[i] = new Array(h);        
            for (var j = 0; j < h; j++) {
                this.array[i][j] = MAZETYPE.BLOCK; //初期値
            }
    }

    /**
     * 
     * @param {Object} x
     * @param {Object} y
     */
    Maze.prototype.getCell = function(x, y) {
        if( !(0<= x && x < w && 0 <= y && y < h)) return MAZETYPE.BLOCK;
        else return this.array[x][y];
    };
    
    /**
     * 
     * @param {Object} x
     * @param {Object} y
     * @param {Object} type
     */
    Maze.prototype.setCell = function(x, y, type) {
        if( !(0<= x && x < w && 0 <= y && y < h)) return false;
        else {
            this.array[x][y] = type;
            return true;
        }
    };

Mazeオブジェクトの利用例は以下のようになります。

maze = new Maze(11,10); // 11*10の迷路

maze.setCell(2,1,MAZETYPE.WAY);
maze.setCell(3,1,MAZETYPE.WAY);
maze.setCell(4,1,MAZETYPE.WAY);
maze.setCell(5,1,MAZETYPE.WAY);

…

maze.setCell(1,1,MAZETYPE.START);
maze.setCell(9,8,MAZETYPE.GOAL);

表示する

上で作った迷路を画面に表示するdisplayメソッドを追加します。ここではdom操作を楽にするため、Ajaxライブラリのprototype.jsを利用してます。たいした処理ではないので、prototype.jsが無くても書けないことはありません。

Maze.prototype.cellsize = 40;
Maze.prototype.domplace = "maze";

Maze.prototype.display = function() {
    var place = $(this.domplace);
    if(place == null){
       throw new Error("place is not dom element");
       return; 
    }
    place.innerHTML = "";
    place.setStyle("position:relative;overflow:hidden;width:"+this.cellsize*maze.w+"px;height:"+this.cellsize*maze.h+"px");
    for(var i = 0; i < maze.w; i++){
        for (var j = 0; j < maze.h; j++) {
            var cell = new Element("div",{style:"position:absolute;width:"+this.cellsize+"px;height:"+this.cellsize+"px;left:"+ this.cellsize*i +"px;top:" +this.cellsize*j+ "px;" });
            switch(maze.array[i][j]){
                case MAZETYPE.BLOCK :
                    cell.setStyle("background-color:#2e2e2e");
                break;
                case MAZETYPE.WAY :
                    cell.setStyle("background-color:#e0e0e0");
                break;
                case MAZETYPE.START :
                    cell.setStyle("background-color:blue");
                break;
                case MAZETYPE.GOAL :
                   cell.setStyle("background-color:red");
                break;
            }
            place.insert(cell);
        }
    }
};

これを使うには、事前にhtmlファイルのほうで、prototype.jsを読み込み、さらに

<div id ="maze"></div>

という空の要素を作っておく必要があります。またこれの利用例は以下のとおりです。

    maze = new Maze(11,10);
    
    maze.setCell(2,1,MAZETYPE.WAY);
    maze.setCell(3,1,MAZETYPE.WAY);
    maze.setCell(4,1,MAZETYPE.WAY);
    maze.setCell(5,1,MAZETYPE.WAY);
    maze.setCell(7,1,MAZETYPE.WAY);
    maze.setCell(8,1,MAZETYPE.WAY);
    maze.setCell(9,1,MAZETYPE.WAY);
    
    maze.setCell(1,2,MAZETYPE.WAY);
    maze.setCell(3,2,MAZETYPE.WAY);
    maze.setCell(5,2,MAZETYPE.WAY);
    maze.setCell(7,2,MAZETYPE.WAY);
    maze.setCell(9,2,MAZETYPE.WAY);

    maze.setCell(1,3,MAZETYPE.WAY);
    maze.setCell(2,3,MAZETYPE.WAY);
    maze.setCell(3,3,MAZETYPE.WAY);
    maze.setCell(5,3,MAZETYPE.WAY);
    maze.setCell(6,3,MAZETYPE.WAY);
    maze.setCell(7,3,MAZETYPE.WAY);
    maze.setCell(9,3,MAZETYPE.WAY);

    maze.setCell(5,4,MAZETYPE.WAY);
    maze.setCell(9,4,MAZETYPE.WAY);

    maze.setCell(1,5,MAZETYPE.WAY);
    maze.setCell(2,5,MAZETYPE.WAY);
    maze.setCell(3,5,MAZETYPE.WAY);
    maze.setCell(4,5,MAZETYPE.WAY);
    maze.setCell(5,5,MAZETYPE.WAY);
    maze.setCell(7,5,MAZETYPE.WAY);
    maze.setCell(8,5,MAZETYPE.WAY);
    maze.setCell(9,5,MAZETYPE.WAY);

    maze.setCell(3,6,MAZETYPE.WAY);
    maze.setCell(5,6,MAZETYPE.WAY);
    maze.setCell(6,6,MAZETYPE.WAY);
    maze.setCell(7,6,MAZETYPE.WAY);

    maze.setCell(3,7,MAZETYPE.WAY);
    maze.setCell(5,7,MAZETYPE.WAY);
    maze.setCell(7,7,MAZETYPE.WAY);
    maze.setCell(8,7,MAZETYPE.WAY); 
    maze.setCell(9,7,MAZETYPE.WAY);

    maze.setCell(1,8,MAZETYPE.WAY);
    maze.setCell(2,8,MAZETYPE.WAY);
    maze.setCell(3,8,MAZETYPE.WAY);
    maze.setCell(5,8,MAZETYPE.WAY);

    maze.setCell(1,1,MAZETYPE.START); //スタート
    maze.setCell(9,8,MAZETYPE.GOAL); //ゴール
    
    maze.display(); //表示

これを実行すると以下のような迷路が表示されます。


プレイヤーを表示

次に迷路を進むプレイヤーを表現します。Mazeオブジェクトの中で以下のようにplayerオブジェクトを定義します。このオブジェクトにはプレイヤーの今いる座標を格納します。

this.player = { x : null, y : null };

今はまだ使いませんが、プレイヤーと同様に迷路のスタートとゴールの位置も保存しておいたほうが楽でしょう。

this.start = { x : null, y : null };
this.goal = { x : null, y : null };

プレイヤーの一番最初の位置は、スタートの位置と同じです。セッターで、迷路のスタートやゴールが設定されたとき、上で作ったプレイヤー、スタート、ゴールの位置情報を変更します。これを踏まえてセッターを以下のように変更します。

/**
 * 
 * @param {Object} x
 * @param {Object} y
 * @param {Object} type
 */
Maze.prototype.setCell = function(x, y, type) {
    if( !(0<= x && x < w && 0 <= y && y < h)) return false;
    else {
        this.array[x][y] = type;
        if(type == MAZETYPE.START) {
            this.player.x = x;
            this.player.y = y;
            this.start.x = x;
            this.start.y = y;
        }else if(type == MAZETYPE.GOAL){
            this.goal.x = x;
            this.goal.y = y;
        }
        return true;
    }
};

displayメソッドの一番最後に変更を加え、プレイヤーを表示するようにします。

Maze.prototype.display = function() {

	……

    var player = new Element("div",{style:"position:absolute;width:" + this.cellsize + "px;height:" + this.cellsize + "px;left:" + this.cellsize * this.player.x + "px;top:" + this.cellsize * this.player.y + "px;color:green;font-size:" + (this.cellsize - 5) + "px;" });
    player.insert("●");
    place.insert(player);
};

表示すると以下のようになります。


プレイヤーを移動させる

プレイヤーを移動させるためのメソッドを作ります。このメソッドを使うと、壁でない場所なら、好きな場所にプレイヤーを移動できます。移動したあとは、displayを呼び、迷路を再描写します。また、ゴールと同じ座標に来ると、alertで「goal」というメッセージが出ます。移動が成功するとtrueが返り、失敗するとfalseが返ってきます。

/**
 * 
 * @param {Object} x
 * @param {Object} y
 */
Maze.prototype.move = function (x,y){
    if (!(0 <= x && x < w && 0 <= y && y < h)) return false;
    else {
        var cell = this.array[x][y];
        if(cell == MAZETYPE.BLOCK) return false;
        this.player.x = x;
        this.player.y = y;
        this.display();
        if( this.goal.x == this.player.x && this.goal.y == this.player.y ) alert("goal");
        return true;
    }
};
１セル移動

実際に迷路を進む場合は、1セルずつしか移動することができません。プレイヤーの現在位置から、上、下、左、右の四方向に対して1セル進むためのメソッドを作ります。

Maze.prototype.moveUp = function() {
    if( this.move(this.player.x, this.player.y - 1) ) return true;
    else return false;
};

Maze.prototype.moveDown = function() {
    if( this.move(this.player.x, this.player.y + 1) ) return true;
    else return false;
};

Maze.prototype.moveRight = function() {
    if( this.move(this.player.x + 1, this.player.y) ) return true;
    else return false;
};

Maze.prototype.moveLeft = function() {
    if( this.move(this.player.x - 1, this.player.y) ) return true;
    else return false;
};

これの利用例は以下のようになります。

maze.moveRight();
maze.moveRight();
maze.moveDown();

表示はこうなります。

ゴールまで行くには以下のような順番になります。

maze.moveRight();
maze.moveRight();
maze.moveRight();
maze.moveRight();
maze.moveDown();
maze.moveDown();
maze.moveDown();
maze.moveDown();
maze.moveDown();
maze.moveRight();
maze.moveRight();
maze.moveDown();
maze.moveRight();
maze.moveRight();
maze.moveDown();

表示結果

ここでひと段落です。

プレイヤーの進行方向

先ほどは迷路全体の位置からみて、上、下、左、右の方向に１セル進んでいました。今度はプレイヤーの向いてる方向を設けて、そちらに向かって1セル進みます。例えば、プレイヤーが迷路の右側を向いてるとき、プレイヤーは直進すると、迷路の右の方向へと進んでいきます。また、プレイヤーが迷路の下側を向いてる場合、直進すると迷路の下方向に進みます。

進行方向の表現

mazeのplayerプロパティの指すオブジェクトに変更を加えて、dx、dyというプロパティを設けます。プレイヤーは、最初は迷路の右側を向いています。

this.player = { x : null, y : null, dx : 1, dy : 0};

( x + dx )が次のx座標、( y + dy )が次のy座標になります。四方向のdx、dyをまとめると以下のようになります。

迷路の方向 dx dy
右 1 0
左 -1 0
上 0 -1
下 0 1
進行方向に対して1セル進む
Maze.prototype.moveStraight = function() {
    if( this.move(this.player.x + this.player.dx, this.player.y + this.player.dy) ) return true;
    else return false;
};
進行方向を変える

現在のプレイヤーの向いている方向を90度回転させます。これによって、直進した場合、進む位置が変化します。まず右回転から作ります。デフォルトでは、プレイヤーは迷路の右側を見ているので、右回転すると、迷路の方向は…

1.迷路の右側
2.迷路の下側
3.迷路の左側
4.迷路の上側
(5.迷路の右側)
(6.迷路の下側)

という風に変化していきます。これを実装すると、以下のようになります。

Maze.prototype.turnRight = function() {
    if(this.player.dy != 0){
        this.player.dx = this.player.dy * -1;
        this.player.dy = 0;
    }else{
        this.player.dy = this.player.dx;
        this.player.dx = 0;            
    }        
};

この表の数字を当てはめてみると、ちゃんと右回転しているのが分かると思います。

迷路の方向 dx dy
上 0 -1
右 1 0
下 0 1
左 -1 0

同様に左回転は次のようになります。

Maze.prototype.turnLeft = function() {
    if(this.player.dy != 0){
        this.player.dx = this.player.dy;
        this.player.dy = 0;
    }else{
        this.player.dy = this.player.dx * -1;
        this.player.dx = 0;            
    }        
};

利用例は以下のとおり。

maze.turnRight(); //右回転するので、下側を向く
maze.moveStraight();
maze.moveStraight();
maze.moveStraight(); //壁にぶつかってすすめない
maze.turnLeft();
maze.moveStraight();
maze.moveStraight();
maze.turnLeft();
maze.moveStraight();


ソース

まだ未完成ですが、今回はここまでにしておきます。最後にソースを貼っておきます。ダウンロードもできるようにしておきます。このプログラムは、index.html、maze.js、mazetest.jsの3つのファイルから構成されています。また、外部ライブラリとしてprototype.jsも必要です。

HelloMaze.zip 直

index.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Maze</title>
<script src="prototype.js"></script>
<script src="maze.js"></script>
<script src="mazetest.js"></script>

</head>
<body onload="init()">
<div id ="maze"></div>
</body>
</html>

maze.js

var MAZETYPE = {
    BLOCK : "block",
    WAY : "way",
    START : "start",
    GOAL : "goal"
};

var Maze = function(w,h) {
    Maze.prototype.cellsize = 40;
    Maze.prototype.domplace = "maze";
    this.w = w;
    this.h = h;
    this.player = { x : null, y : null, dx : 1, dy : 0};
    this.goal = { x : null, y : null };
    this.start = { x : null, y : null };
    this.array = new Array(w);
    for(var i = 0; i < w; i++) {
        this.array[i] = new Array(h);        
            for (var j = 0; j < h; j++) {
                this.array[i][j] = MAZETYPE.BLOCK;
            }
    }

    /*
     * 迷路に対するメソッド
     */
    
    /**
     * 
     * @param {Object} x
     * @param {Object} y
     */
    Maze.prototype.getCell = function(x, y) {
        if( !(0<= x && x < w && 0 <= y && y < h)) return MAZETYPE.BLOCK;
        else return this.array[x][y];
    };
    
    /**
     * 
     * @param {Object} x
     * @param {Object} y
     * @param {Object} type
     */
    Maze.prototype.setCell = function(x, y, type) {
        if( !(0<= x && x < w && 0 <= y && y < h)) return false;
        else {
            this.array[x][y] = type;
            if(type == MAZETYPE.START) {
                this.player.x = x;
                this.player.y = y;
                this.start.x = x;
                this.start.y = y;
            }else if(type == MAZETYPE.GOAL){
                this.goal.x = x;
                this.goal.y = y;
            }
            return true;
        }
    };
    
    /**
     * 
     */
    Maze.prototype.display = function() {
        var place = $(this.domplace);
        if(place == null){
           throw new Error("place is not dom element");
           return; 
        }
        place.innerHTML = "";
        place.setStyle("position:relative;overflow:hidden;width:"+this.cellsize*maze.w+"px;height:"+this.cellsize*maze.h+"px");
        for(var i = 0; i < maze.w; i++){
            for (var j = 0; j < maze.h; j++) {
                var cell = new Element("div",{style:"position:absolute;width:"+this.cellsize+"px;height:"+this.cellsize+"px;left:"+ this.cellsize*i +"px;top:" +this.cellsize*j+ "px;" });
                switch(maze.array[i][j]){
                    case MAZETYPE.BLOCK :
                        cell.setStyle("background-color:#2e2e2e");
                    break;
                    case MAZETYPE.WAY :
                        cell.setStyle("background-color:#e0e0e0");
                    break;
                    case MAZETYPE.START :
                        cell.setStyle("background-color:blue");
                    break;
                    case MAZETYPE.GOAL :
                       cell.setStyle("background-color:red");
                    break;
                }
                place.insert(cell);
            }
        }
        var player = new Element("div",{style:"position:absolute;width:" + this.cellsize + "px;height:" + this.cellsize + "px;left:" + this.cellsize * this.player.x + "px;top:" + this.cellsize * this.player.y + "px;color:green;font-size:" + (this.cellsize - 5) + "px;" });
        player.insert("●");
        place.insert(player);
    };

    /*
     * プレイヤーに対するメソッド
     */
    
    /**
     * 
     * @param {Object} x
     * @param {Object} y
     */
    Maze.prototype.move = function (x,y){
        if (!(0 <= x && x < w && 0 <= y && y < h)) return false;
        else {
            var cell = this.array[x][y];
            if(cell == MAZETYPE.BLOCK) return false;
            this.player.x = x;
            this.player.y = y;
            this.display();
            if( this.goal.x == this.player.x && this.goal.y == this.player.y ) alert("goal");
            return true;
        }
    };
    
    /**
     * 
     */
    Maze.prototype.moveUp = function() {
        if( this.move(this.player.x, this.player.y - 1) ) return true;
        else return false;
    };

    /**
     * 
     */
    Maze.prototype.moveDown = function() {
        if( this.move(this.player.x, this.player.y + 1) ) return true;
        else return false;
    };

    /**
     * 
     */
    Maze.prototype.moveRight = function() {
        if( this.move(this.player.x + 1, this.player.y) ) return true;
        else return false;
    };

    /**
     * 
     */
    Maze.prototype.moveLeft = function() {
        if( this.move(this.player.x - 1, this.player.y) ) return true;
        else return false;
    };

    /**
     * 進行方法に対して1セル進む
     */
    Maze.prototype.moveStraight = function() {
        if( this.move(this.player.x + this.player.dx, this.player.y + this.player.dy) ) return true;
        else return false;
    };

    /**
     * 進行方向を現在の進行方向からみて右側にする
     */
    Maze.prototype.turnRight = function() {
        if(this.player.dy != 0){
            this.player.dx = this.player.dy * -1;
            this.player.dy = 0;
        }else{
            this.player.dy = this.player.dx;
            this.player.dx = 0;            
        }        
    };

    /**
     * 進行方向を現在の進行方向からみて左側にする
     */
    Maze.prototype.turnLeft = function() {
        if(this.player.dy != 0){
            this.player.dx = this.player.dy;
            this.player.dy = 0;
        }else{
            this.player.dy = this.player.dx * -1;
            this.player.dx = 0;            
        }        
    };
};

mazetest.js

var maze;

var init = function() {
    mazeinit();
/**
    //ゴールまでの経路
    maze.moveRight();
    maze.moveRight();
    maze.moveRight();
    maze.moveRight();
    maze.moveDown();
    maze.moveDown();
    maze.moveDown();
    maze.moveDown();
    maze.moveDown();
    maze.moveRight();
    maze.moveRight();
    maze.moveDown();
    maze.moveRight();
    maze.moveRight();
    maze.moveDown();
**/

    //プレイヤーの進行方向の利用
    maze.turnRight();
    maze.moveStraight();
    maze.moveStraight();
    maze.moveStraight(); //壁にぶつかってすすめない
    maze.turnLeft();
    maze.moveStraight();
    maze.moveStraight();
    maze.turnLeft();
    maze.moveStraight();

};

var mazeinit = function (){
    maze = new Maze(11,10);
    
    maze.setCell(2,1,MAZETYPE.WAY);
    maze.setCell(3,1,MAZETYPE.WAY);
    maze.setCell(4,1,MAZETYPE.WAY);
    maze.setCell(5,1,MAZETYPE.WAY);
    maze.setCell(7,1,MAZETYPE.WAY);
    maze.setCell(8,1,MAZETYPE.WAY);
    maze.setCell(9,1,MAZETYPE.WAY);
    
    maze.setCell(1,2,MAZETYPE.WAY);
    maze.setCell(3,2,MAZETYPE.WAY);
    maze.setCell(5,2,MAZETYPE.WAY);
    maze.setCell(7,2,MAZETYPE.WAY);
    maze.setCell(9,2,MAZETYPE.WAY);

    maze.setCell(1,3,MAZETYPE.WAY);
    maze.setCell(2,3,MAZETYPE.WAY);
    maze.setCell(3,3,MAZETYPE.WAY);
    maze.setCell(5,3,MAZETYPE.WAY);
    maze.setCell(6,3,MAZETYPE.WAY);
    maze.setCell(7,3,MAZETYPE.WAY);
    maze.setCell(9,3,MAZETYPE.WAY);

    maze.setCell(5,4,MAZETYPE.WAY);
    maze.setCell(9,4,MAZETYPE.WAY);

    maze.setCell(1,5,MAZETYPE.WAY);
    maze.setCell(2,5,MAZETYPE.WAY);
    maze.setCell(3,5,MAZETYPE.WAY);
    maze.setCell(4,5,MAZETYPE.WAY);
    maze.setCell(5,5,MAZETYPE.WAY);
    maze.setCell(7,5,MAZETYPE.WAY);
    maze.setCell(8,5,MAZETYPE.WAY);
    maze.setCell(9,5,MAZETYPE.WAY);

    maze.setCell(3,6,MAZETYPE.WAY);
    maze.setCell(5,6,MAZETYPE.WAY);
    maze.setCell(6,6,MAZETYPE.WAY);
    maze.setCell(7,6,MAZETYPE.WAY);

    maze.setCell(3,7,MAZETYPE.WAY);
    maze.setCell(5,7,MAZETYPE.WAY);
    maze.setCell(7,7,MAZETYPE.WAY);
    maze.setCell(8,7,MAZETYPE.WAY); 
    maze.setCell(9,7,MAZETYPE.WAY);

    maze.setCell(1,8,MAZETYPE.WAY);
    maze.setCell(2,8,MAZETYPE.WAY);
    maze.setCell(3,8,MAZETYPE.WAY);
    maze.setCell(5,8,MAZETYPE.WAY);

    maze.setCell(1,1,MAZETYPE.START); //スタート
    maze.setCell(9,8,MAZETYPE.GOAL); //ゴール
    
    maze.display(); //表示
};

リンク

迷路を作って遊んでみる2
迷路を作って遊んでみる3
迷路を作って遊んでみる4