Androidの方眼紙マップエディタ制作 その4 – 経路探索機能

床色編集、冒険モード、移動床処理、外部ファイルの読み書き、と実装し、段々と完成に近づいてきました。(前回記事)

何かユニークな機能が欲しいなと考えていたら、最短経路を計算して表示する機能を思いつきました。

ワープも探索に含めています。

ワープとループ

マップの端から出ようとすると、反対側にループ

テレポート、フロア外への階層移動の処理を実装しています

迷路探索プログラムでは、通行可能な隣り合うセルを各ノードに追加することで探索しますが、データ上は実際に隣り合っている必要は無いので、ワープ先のノードを追加するだけで探索できます。

探索の重み付けをすることで、過剰な探索や無限ループを防ぐ事ができます。(ダイクストラ法)

冒険モードでも実際にワープするようにしています。

表示→ワープ動線にチェックを入れると図のようにワープ動線を表示したままにできます。

通行禁止フラグ

壁を書き換えなくても一時的に通り道を塞げるように、通行禁止フラグを用意しました。

フラグを設置することで、そこを通行しないように経路を変更します。

絵が下手なおかげで旗が揺らめいているように見える効果が

終了の旗はEndのEが良いのかなと思ったけど、Startの反対はStopらしいですね。

開始の旗をBeginのBにすると何がなんだか分からなくなりそうなので、終了の旗をGoalのGにしました。(Sの赤い旗がストップに見えてきた)

幅探索アルゴリズム

上下左右、隣り合ったマスを辿って隅々まで検索するアルゴリズムには、幅探索と深さ探索の２種類があります。

幅探索はキューを使って、見つかったデータを積み上げながら始点から近い順番に探索していく方法

深さ探索は再帰を使って、一旦一番奥まで探索してからさかのぼりながら枝葉を伸ばしていく探索方法です。

最短距離を求めるには、近くのセルの重みを比較しながら経路選択をしていく必要があるので、幅探索が適しています。

今回は最短距離を求めるダイクストラ法を用いました

こんな感じで迷路も一瞬で解くことができます。
（※迷路の入力には、とても時間が掛かりまs）

一方通行の移動床にも対応してるので、移動床だらけのダンジョン探索に使えます。

滑り床も実装したいけど、通ってきた方向を使用するから難しい。
(予めどちらへ進めるかという情報を作成してから探索を行うため)
いいアイデアが浮かんだら実装しようと思います。

この機能でグッと汎用性が増したんじゃないでしょうか

プログラム

役に立つかわからないけど参考までに

class MyNode{
    var x = 0
    var y = 0
    var visit = false
    var stop = false
    var weight = 0
    var nexts = mutableListOf<MyNode>()
    var prev:MyNode? = null
}

private var listNode = mutableListOf<MyNode>()
var mw = 0          // マップの幅
var mh = 0          // マップの高さ
var targetX = 0     // 経路探索の目的座標X
var targetY = 0     // 経路探索の目的座標Y

// ルート検索(幅探索)
fun routeFindD(x:Int, y:Int):Boolean{
    var bFind = false
    var maxW = 10000000
    val q = ArrayDeque<MyNode>()
    var node = listNode[mw*y+x]
    node.visit = true
    node.weight = 0
    q.add(node)

    while(q.size != 0){
        node = q.removeFirst()
        if(node.x == targetX && node.y == targetY){
            bFind = true
            if(maxW > node.weight)
                maxW = node.weight
        }
        if(node.weight > maxW){
            continue
        }
        for(node2 in node.nexts){
            if(!node2.visit && !node2.stop){
                q.add(node2)
                node2.prev = node
                node2.visit = true
                node2.weight = node.weight + 1
            }else if(node2.weight > node.weight + 1){
                node2.prev = node
                node2.weight = node.weight + 1
            }
        }
    }
    return bFind
}

// ルート検索のための経路情報の初期化
fun initNode(){
    listNode.clear()
    val (w, h) = mapData.getSize()
    mw = w
    mh = h

    for(y in 0 until h) {
        for (x in 0 until w){
            val node = MyNode()
            node.x = x
            node.y = y
            node.weight = 10000000

            listNode.add(node)
        }
    }
    
    for(y in 0 until h) {
        for (x in 0 until w){
            val c = mapData.get(x, y)
            val node = listNode[y*w+x]
            var bUp = true
            var bRight = true
            var bLeft = true
            var bDown = true
            when(c.type){// 移動床の処理
                5->{bRight=false; bLeft=false; bDown=false}
                6->{bUp=false; bLeft=false; bRight=false}
                7->{bRight=false; bUp=false; bDown=false}
                8->{bUp=false; bLeft=false; bDown=false}
            }

            val (name, rc) = getFloorByPoint(Point(x, y))

            // 1:壁、5:ロック扉
            if(c.up != 1 && c.up != 5 && w*(y-1)+x >= 0 && w*(y-1)+x < (w*h) && bUp){
                if(name != "" && rc.top == y){
                    node.nexts.add(listNode[w * (rc.bottom) + x])
                }else {
                    node.nexts.add(listNode[w * (y - 1) + x])
                }
            }

            if(c.right != 1 && c.right != 5 && w*y+x+1 >= 0 && w*y+x+1 < (w*h) && bRight){
                if(name != "" && rc.right == x){
                    node.nexts.add(listNode[w * y + rc.left])
                }else {
                    node.nexts.add(listNode[w * y + x + 1])
                }
            }

            if(c.down != 1 && c.down != 5 && w*(y+1)+x >= 0 && w*(y+1)+x < (w*h) && bDown){
                if(name != "" && rc.bottom == y){
                    node.nexts.add(listNode[w * (rc.top) + x])
                }else {
                    node.nexts.add(listNode[w * (y + 1) + x])
                }
            }

            if(c.left != 1 && c.left != 5 && w*y+x-1 >= 0 && w*y+x-1 < (w*h) && bLeft){
                if(name != "" && rc.left == x){
                    node.nexts.add(listNode[w * y + rc.right])
                }else {
                    node.nexts.add(listNode[w * y + x - 1])
                }
            }
        }
    }

    // ワープ経路の追加
    for((ptStart, ptEnd) in listWarp){
        if(ptStart.x < 0 || ptStart.x >= wField ||
            ptStart.y < 0 || ptStart.y >= hField ||
            ptEnd.x < 0 || ptEnd.x >= wField ||
            ptEnd.y < 0 || ptEnd.y >= hField) {
            continue
        }

        val nodeStart = listNode[ptStart.y * w + ptStart.x]
        val nodeEnd = listNode[ptEnd.y * w + ptEnd.x]
        nodeStart.nexts.add(nodeEnd)
    }

}

// ルート検索の目的座標を設定する
fun setRouteTarget(x:Int, y:Int){
    for(node in listNode){
        node.weight = 10000000
        node.prev = null
        node.visit = false
    }
    targetX = x
    targetY = y
}

フラグを設置するたびに経路情報を作成していたら、検索に時間が掛かってしまうので、経路探索モードに切り替えた時点でinitNodeを呼び出し、経路情報を作成しています。

ノードに必要な情報は座標(x, y)、訪れ済みフラグ、通行不可フラグ、距離情報、次のノードリスト、１つ前のノード(最短経路)です

kotlinは二次元配列の操作が面倒なので、１次元配列でアクセスします。

listNode[マップ幅 * y座標 + x座標]とアクセスすれば擬似的な二次元配列として扱えます。

kotlinでキューを扱うにはArrayDequeクラスを使います。

addで追加、removeFirstで取り出しです。

ゴールを見つけたあとも、重みの最大値を設定し直して、最短距離を見つけるための探索を続けるようにしてましたが、幅探索では必要なかったかもしれません。

終わりに

プログラムはサクッと書けるんだけど、大変なのがアイコン制作

画力が無さすぎて、幾何学図形を書くのがやっとです。

ワープのアイコンなんてイメージすら出来ないです

でも、頑張って編集アイコンは全て書き直しました。

消しゴムが一番の力作(四角形と回転だけ)

とりあえずダークゾーンを貼っておきますね

次回