Androidで迷路

名大の渡辺先生のクラスターを利用した迷路作成方法に感激してAndroid上にて実装してみました。*1

http://www.phys.cs.is.nagoya-u.ac.jp/~watanabe/tips/maze.html

迷路作成のアルゴリズムはいくつもありますが、この方法の素敵な所は事前に絵を書いておくとそれが保存されることです。
本当は一筆書きでお絵描きをするActivityも実装してみたかったのですが本業が忙しすぎてまた休みまで更新できそうにないので一旦公開します。

クラスターのデータ構造

最初はTreeMapだけで実装可能だと思いました。
しかし良く見てみたらfloorKeyやceilingKeyはsince JDK1.6でAndroidでは使えないのでした。
このためしょうがなしにLinkedListも使っています。
これはMapはkeyでなくindexでvalueを指定できないためです。
JDK1.6のTreeMapであればNavigableMapを利用することによりある値の最も近いKeyのValueを得ることができるのでindexの変わりにすることができます。
firstとlastは取れますのでその間で乱数を取れば良いでしょう。
ただ等分に離れていない状態では偏りがでるかもしれません。
しかしJDKは地道に良くなってますね。
Androidでもぜひ最新のJDKに対応していってほしいです。
携帯でもプログラムはでかくなる一方です。
これからは携帯でも生産性を重視しなくちゃ駄目ですよね。

迷路の床一つをセル(Cell)と私が勝手に呼んでいます。
セルには右側の壁と下側の壁だけあります。
周りのセルと壁を共有しないための苦肉の策です。
セルの大きさは計算しますので、MAZE_WIDTHとMAZE_HEIGHTを自由に変更することが可能です。

迷路の実装は解説があっても結構大変でした。
クラスターのデータ構造をどうするかや、特にどうすれば無駄のない実装ができるかばかり考えていました。
ループに無駄を作りたくなかったのでできるだけ乱数は使いたくなかったのです。
最初の実装は迷路のセルを左上から順に舐めていくタイプでした。
これだとどうしても迷路が右下へ右下へと流れていくものしかできずあえなく書き直しました。
色々考えて結局ランダムに選択するタイプに実装しました。
それでもセルをランダムに選択するのでなく、クラスターをランダムに選択するようにしています。
これだとセルはクラスターの先頭しか選ばないので微妙に影響が出ているかもしれませんが(クラスターの先頭は耐えず左上に収束するから)見た目にはそれほどでもないので良しとしました。

クラスターを毎回ランダムに選択していましたが、それだとどうしても距離1の行き止まりが多く作成されてしまうため、ある点を起点に全く移動できなくなるまでランダムウォークをさせ、その後クラスターを選び直しにするように変更しました。
これでやっと人の目から見て自然な迷路ができるようになりました。

SurfaceViewの謎

darty regionをRectで指定することに初めて挑戦したら挙動が全然わからなくて苦労しました。

一番最初は前回と同じく画面全体をフレーム毎に全部書き直していました。
しかしさすがにループの数と状態分岐が多すぎでとても遅いものでした。

次にdary Rectの指定をせずに1度だけ全体を書いて次からセルの部分だけを更新しました。
すると見事にポケモンフラッシュ状態となってしまったのです。
何が悪いのかわからなかったのですが、すごいチラツキでした。
マニュアルを見ると取得したcanvasは全てのドットを書く必要があることになっています。

次にdarty regionをRectにて指定しました。
しかし最初に書いた全体領域が今度は全部消えてしまう症状に悩みました。

上記の2つの挙動から想像するにどうやらプラットフォーム内部でダブルバッファを行っているもののうち、1回の書き込みでは片方しか更新できないのではないかということを想像しました。
ここらへんはマニュアルを良く読めば書いてあるのかもしれませんが、読むのが面倒なのでほってあります(笑
そこでダメモトで全体の描画を最初にただ2回繰り返しました。
すると見事にうまくいったのでこの推測でたぶん正しいのだろうと思います。
ただこれが仕様なのかどうかわかりませんのでこのプログラムは将来のSDKでは動かないかもしれません。

画面全体を書くプログラムと、セル1個を更新するプログラムで位置がズレてしまいました。
しかし、結果的にそのおかげで画面が立体的に見えるようになりました。
上のスクリーンショットではわかりませんが、迷路作成中画面更新が全てアニメ状に表示されます。
ぜひ手元のSDKにて遊んでみてください。

今回もまたソースの直接公開でいきます。
packageをminghai.practice5、その他をmemezoでプロジェクトを作成し、ソースを置き換えれば動きます。
今回迷路を書くだけで終ってしまいます。
いずれまた遊べる要素を追加するつもりです。

ソース

package minghai.practice5;

import java.util.LinkedList;
import java.util.Random;
import java.util.TreeMap;

import android.app.Activity;
import android.content.Context;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.graphics.Rect;
import android.graphics.drawable.ShapeDrawable;
import android.graphics.drawable.shapes.RectShape;
import android.os.Bundle;
import android.util.Log;
import android.view.Gravity;
import android.view.SurfaceHolder;
import android.view.SurfaceView;
import android.view.View;
import android.view.ViewGroup;
import android.widget.FrameLayout;
import android.widget.RelativeLayout;
import android.widget.TextView;

public class Memezo extends Activity {
    
    LinkedList<Integer> clusterList = new LinkedList<Integer>();
    TreeMap<Integer, int[]> clusterMap = new TreeMap<Integer, int[]>();
    static final private int MAZE_WIDTH  = 35;
    static final private int MAZE_HEIGHT = 50;
    private Cell[] cells = new Cell[MAZE_WIDTH * MAZE_HEIGHT];
    
    private SurfaceHolder mSurfaceHolder;
    private MyThread mThread;
    private final Random mRand = new Random(System.currentTimeMillis());
    private FieldView mFieldView;
    private TextView mStatusText;
    
    private class Cell {
        public boolean right_side = true;
        public boolean below_side = true;
        public int cluster_number;
        public boolean isSameCluster(int num) {
            return cluster_number == num;
        }
    }
    
    enum Direction {
        ABOVE, BELOW, RIGHT, LEFT;
    }
    
    class MyThread extends Thread {
        private boolean mRun = true;
        
        @Override
        public void run() {
            int screenWidth  = mFieldView.getWidth();
            int screenHeight = mFieldView.getHeight();
            
            while (mRun) {
                Canvas c = null;

                //long currentTime = System.currentTimeMillis();
                c = mSurfaceHolder.lockCanvas(new Rect(0, 0, screenWidth, screenHeight));
                synchronized (mSurfaceHolder) {
                    doDraw(c);
                }
                mSurfaceHolder.unlockCanvasAndPost(c);
                
                // 2nd
                c = mSurfaceHolder.lockCanvas(new Rect(0, 0, screenWidth, screenHeight));
                synchronized (mSurfaceHolder) {
                    doDraw(c);
                }
                mSurfaceHolder.unlockCanvasAndPost(c);
                
                for (int size = clusterList.size(); size > 1; size = clusterList.size()) {
                    int i = clusterList.get(mRand.nextInt(size - 1) + 1);  // This is cell address
                    while (true) {                
                        int next = make_maze(i);

                        if (next == -1) break;
                        i = next;
                    }
                }
                mRun = false;
            }
        }
        

        /*
         * ランダムにセルをclusterLlstから選ぶ
         * セルの上下左右と繋ぐ
         * クラスターを連結する。結果的にclisterList、clusterMapのsizeが縮む
         * クラスターサイズが1になるまで繰り返す
         */
        public int make_maze(int i) {

            //Log.d("TEST", "i = " + i);
            Cell cell = cells[i];
            boolean canAbove;
            boolean canBelow;
            boolean canRight;
            boolean canLeft;

            int ridx = i + 1;
            int lidx = i - 1;
            int aidx = i - MAZE_WIDTH;
            int bidx = i + MAZE_WIDTH;

            // WATCH OUT: if you forget to check isWall before, cells[idx] might throw IndexOutOfBounds
            int ccn = cell.cluster_number; // Current Cluster Number
            canRight = !rightIsWall(i) && !cells[ridx].isSameCluster(ccn);
            canLeft  = !leftIsWall(i)  && !cells[lidx].isSameCluster(ccn);
            canAbove = !aboveIsWall(i) && !cells[aidx].isSameCluster(ccn);
            canBelow = !belowIsWall(i) && !cells[bidx].isSameCluster(ccn);

            LinkedList<Direction> directionsToGo = new LinkedList<Direction>();
            //directionsToGo.clear();
            if (canRight)  directionsToGo.add(Direction.RIGHT);
            if (canLeft)   directionsToGo.add(Direction.LEFT);
            if (canAbove)  directionsToGo.add(Direction.ABOVE);
            if (canBelow)  directionsToGo.add(Direction.BELOW);

            int s = directionsToGo.size();
            if (s == 0) {
                //Log.d("TEST", "SIZE IS ZERO!!!");
                return -1;
            }
            Direction d = directionsToGo.get(mRand.nextInt(s));
            switch (d) {
            case RIGHT:
                cell.right_side = false;
                concat(ccn, cells[ridx].cluster_number);
                drawOneCell(i);
                drawOneCell(ridx);
                i = ridx;
                break;
            case LEFT:
                Cell leftCell = cells[lidx];
                leftCell.right_side = false;
                concat(ccn, leftCell.cluster_number);
                drawOneCell(i);
                drawOneCell(lidx);
                i = lidx;
                break;
            case ABOVE:
                Cell aboveCell = cells[aidx];
                aboveCell.below_side = false;
                concat(ccn, aboveCell.cluster_number);
                drawOneCell(i);
                drawOneCell(aidx);
                i = aidx;
                break;
            case BELOW:
                cell.below_side = false;
                concat(ccn, cells[bidx].cluster_number);
                drawOneCell(i);
                drawOneCell(bidx);
                i = bidx;
                break;
            }

            return i;
        }
        
        private int FRAME_SIZE = 5;
        
        private void drawOneCell(int i) {
            Canvas c = null;
            int screenWidth  = mFieldView.getWidth();
            int screenHeight = mFieldView.getHeight();
            	
            try {
                int cellWidth = screenWidth / MAZE_WIDTH;
                int cellHeight = screenHeight / MAZE_HEIGHT;

                if (cellWidth > cellHeight) {
                    cellWidth = cellHeight;
                } else {
                    cellHeight = cellWidth;
                }

                final int field_width = MAZE_WIDTH * cellWidth;
                final int field_height = MAZE_HEIGHT * cellHeight;
                
                int fx = (screenWidth - field_width)   / 2;
                int fy = (screenHeight - field_height) / 2;
                //c.translate(fx, fy);

                int x = (i % MAZE_WIDTH) * cellWidth;
                int y = (i / MAZE_WIDTH) * cellHeight;
                
                Rect dirty = new Rect(fx + x, fy + y, fx + x + cellWidth, fy + y + cellHeight);
                c = mSurfaceHolder.lockCanvas(dirty);
                //Log.d("TEST", "width  = " + c.getWidth());
                //Log.d("TEST", "Height = " + c.getHeight());
                c.translate(fx + x, fy + y);

                synchronized (mSurfaceHolder) {

                    //c.drawColor(0xFFFFFFFF);
                    
                    ShapeDrawable rect = new ShapeDrawable(new RectShape());
                    Paint p = rect.getPaint();
                    p.setAntiAlias(false);
                    
                    rect.setBounds(0, 0, cellWidth, cellHeight);
                    p.setColor(0xFFFFFFFF);
                    rect.draw(c);
                    
                    p = new Paint();
                    p.setAntiAlias(false);

                    if (cells[i].right_side) {
                        c.drawLine(cellWidth - 1, 0, cellWidth - 1, cellHeight, p);
                    }

                    if (cells[i].below_side) {
                        c.drawLine(0, cellHeight - 1, cellWidth, cellHeight - 1, p);
                    }
                }
            } finally {
                // do this in a finally so that if an exception is thrown
                // during the above, we don't leave the Surface in an
                // inconsistent state
                if (c != null) {
                    mSurfaceHolder.unlockCanvasAndPost(c);
                }
            }
        }
        
        private void doDraw(Canvas c) {
            c.drawColor(0xFFFFFFFF);
            int screenWidth = c.getWidth();
            int screenHeight = c.getHeight();
            //Log.d("TEST", "screenWidth = " + screenWidth);
            //Log.d("TEST", "screenHeight = " + screenHeight);
            
            int cellWidth = screenWidth / MAZE_WIDTH;
            int cellHeight = screenHeight / MAZE_HEIGHT;
            //Log.d("TEST", "cellWidth = " + cellWidth);
            //Log.d("TEST", "cellHeight = " + cellHeight);
            
            if (cellWidth > cellHeight) {
                cellWidth = cellHeight;
            } else {
                cellHeight = cellWidth;
            }
            
            ShapeDrawable rect = new ShapeDrawable(new RectShape());
            Paint p = rect.getPaint();
            p.setAntiAlias(false);
            final int field_width = MAZE_WIDTH * cellWidth;
            final int field_height = MAZE_HEIGHT * cellHeight;
            //Log.d("TEST", "fieldWidth = " + field_width);
            //Log.d("TEST", "fieldHeight = " + field_height);
            
            int fx = (screenWidth - field_width) / 2 - FRAME_SIZE;
            int fy = (screenHeight - field_height) / 2 - FRAME_SIZE;
            c.translate(fx, fy);
            
            rect.setBounds(0, 0, field_width + FRAME_SIZE * 2, field_height + FRAME_SIZE * 2);
            p.setColor(0xFF000000);
            rect.draw(c);
            c.translate(FRAME_SIZE, FRAME_SIZE);
            rect.setBounds(0, 0, field_width, field_height);
            p.setColor(0xFFFFFFFF);
            rect.draw(c);
     
            p.setColor(0xFF000000);
            //Log.d("TEST", "flags = " + p.getFlags());
            for (int i = 0; i < cells.length; i++) {
                int x = (i % MAZE_WIDTH) * cellWidth;
                int y = (i / MAZE_WIDTH) * cellHeight;
                
                //rect.setBounds(x, y, x + cellWidth, x + cellHeight);
                
                if (cells[i].right_side) {
                    c.drawLine(x + cellWidth, y, x + cellWidth, y + cellHeight, p);
                }
                
                if (cells[i].below_side) {
                    c.drawLine(x, y + cellHeight, x + cellWidth, y + cellHeight, p);
                }
            }
        }

        public void quit() {
            mRun = false;
        }
    }
    
    private class FieldView extends SurfaceView  implements SurfaceHolder.Callback {
        public FieldView(Context context) {
            super(context);
            
            mSurfaceHolder = getHolder();
            mSurfaceHolder.addCallback(this);
            mSurfaceHolder.setSizeFromLayout();
            
            setFocusable(true);
            setFocusableInTouchMode(true);
            requestFocus();
        }
        
        public void surfaceChanged(SurfaceHolder surfaceholder, int i, int j, int k) {
            surfaceholder.setFixedSize(j,k);
        }

        public void surfaceCreated(SurfaceHolder surfaceholder) {
            // start the thread here so that we don't busy-wait in run()
            // waiting for the surface to be created
            mThread.start();
        }

        public void surfaceDestroyed(SurfaceHolder surfaceholder) {
            // we have to tell thread to shut down & wait for it to finish, or else
            // it might touch the Surface after we return and explode
            boolean retry = true;
            mThread.quit();
            while (retry) {
                try {
                    mThread.join();
                    retry = false;
                } catch (InterruptedException e) {
                }
            }
        }
    }
    
    /** Called when the activity is first created. */
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        FrameLayout fl = new FrameLayout(this);
        mFieldView = new FieldView(this);
        fl.addView(mFieldView);
        RelativeLayout rl = new RelativeLayout(this);

        mStatusText = new TextView(this);
        mStatusText.setId(1);
        RelativeLayout.LayoutParams lp = new RelativeLayout.LayoutParams(
                ViewGroup.LayoutParams.WRAP_CONTENT, 
                ViewGroup.LayoutParams.WRAP_CONTENT);
        lp.addRule(RelativeLayout.CENTER_IN_PARENT, 1);
        
        mStatusText.setGravity(Gravity.CENTER_HORIZONTAL);
        mStatusText.setTextSize(40);
        mStatusText.setText("GAME OVER");
        mStatusText.setTextColor(Color.BLACK);
        mStatusText.setVisibility(View.INVISIBLE);
        rl.addView(mStatusText, lp);
        fl.addView(rl);
        setContentView(fl);
    }
    
    @Override
    protected void onResume() {
        super.onResume();
        
        mThread = new MyThread();
        
        for (int i = 0; i < cells.length; i++) {
            cells[i] = new Cell();
            cells[i].cluster_number = i;
            int[] tmp = {i};
            clusterList.add(i);
            clusterMap.put(i, tmp);
        }
        
        //make_maze();
        
        // Text Maze
/*        for (int i = 0; i < MAZE_HEIGHT; i++ ) {
            StringBuilder line1 = new StringBuilder();
            StringBuilder line2 = new StringBuilder();
            for (int j = 0; j < MAZE_WIDTH; j++) {
                Cell c = cells[i * MAZE_WIDTH + j];
                if (c.cluster_number < 100) line1.append(0);
                if (c.cluster_number < 10) line1.append(0);
                line1.append(c.cluster_number);
                line1.append(c.right_side ? "|" : " ");
                line2.append(c.below_side ? "----" : "    ");
            }
            Log.d("TEST", line1.toString());
            Log.d("TEST", line2.toString());
        }*/
    }
    
    static private boolean leftIsWall(int i) {
        return (i % MAZE_WIDTH) == 0;
    }

    static private boolean aboveIsWall(int i) {
        return (i / MAZE_WIDTH) == 0;
    }
    static public boolean rightIsWall(int number) {
        return (number % MAZE_WIDTH) == (MAZE_WIDTH - 1);
    }
    
    static public boolean belowIsWall(int number) {
        return (number / MAZE_WIDTH) == (MAZE_HEIGHT - 1);
    }

    private void concat(int i, int j) {
        // swap if i > j so that the last cluster always be 0
        if (i > j) {
            int tmp = i;
            i = j;
            j = tmp;
        }
        //Log.d("TEST", "young = " + i);
        //Log.d("TEST", "old   = " + j);
        int[] young = clusterMap.get(i);
        int[] old   = clusterMap.remove(j);
        clusterList.remove(new Integer(j));

        int[] nuevo = new int[young.length + old.length];
        System.arraycopy(young, 0, nuevo, 0, young.length);
        System.arraycopy(old, 0, nuevo, young.length, old.length);
        for (int k = 0; k < old.length; k++) {
            cells[old[k]].cluster_number = i;
        }
        clusterMap.put(i, nuevo);
    }
}

*1:先生は東大に異動されたそうでこのページは近いうちに消えてしまうそうです。早めに保存してください。