作品 ID: 2762

深さ優先探索

公開

深さ優先探索。first routeを押すと綺麗に描画されます。表示される数字は100が最短距離に対してどれだけ探索したか。迷路探索法の一つ。探索可能リストの新しい物を優先する。一般的に効率はブラインド探索ならまし？程度。反復深度優先探索が本来望ましい。

ソース

プログラム

#なでしこ #迷路 #深さ優先探索 ver.5.5
Wall=[]
Vertical_row=75
Horizontal_row=75
Width=4
Direction=[[0,1],[-1,0],[1,0],[0,-1]]
0に線太設定

"Wallをコピーしているなら[OK]
そうで無いなら[キャンセル]で答えてね"と二択。

もしそれ==0なら:
    main__壁作成
    main__迷路作成(1,1)
    main__壁描画(Wall,0)
違えば:
    クリップボード取得
    temp=それを","で区切る
    もし(tempの要素数)==(Horizontal_row*Vertical_row)なら:
        iを0からHorizontal_row-1まで繰り返す:
            Wallのiに(tempの0からVertical_rowを配列取出)を配列挿入

list=Wallを配列複製
stack=[]
goalRoute=[]
distance=2

main__search(1,Vertical_row-2,Horizontal_row-2,1)
FLOOR(distance/(goalRouteの要素数)*100)を表示


firstRoute="firstRoute"のボタン作成。
firstRouteをクリックした時には:
    main__壁描画(Wall,0)
    main__探索路描画(goalRoute)

allRoute="allRoute"のボタン作成。
allRouteをクリックした時には:
    main__壁描画(list,distance)

OutPut="OutPut"のボタン作成
OutPutをクリックした時には:
    Wallをクリップボード設定
    "クリップボードにコピーしました"と言う

research="research"のボタン作成。
researchをクリックした時には:
    list=Wallを配列複製
    stack=[]
    stack2=[]
    goalRoute=[]
    distance=2
    main__search(1,Vertical_row-2,Horizontal_row-2,1)

描画中キャンバスをタッチ終了時には:
    X=FLOOR(タッチX/Width)
    Y=FLOOR(タッチY/Width)
    もしmain__迷路範囲内(X,Y)なら:
        もしWall[X][Y]=0なら:
            Wall[X][Y]=1
        違えば:
            Wall[X,Y]=0
        main__壁描画(Wall,0)

●壁作成とは:
    もしVertical_row%2==0ならば:
    　　Vertical_row=Vertical_row+1
    もしHorizontal_row%2=0ならば:
    　　Horizontal_row==Horizontal_row+1
    Wall=[]
    row=[]
    Vertical_row回:
    　　rowに1を配列追加
    iを0からHorizontal_row-1まで繰り返す:
    　　Wall[i]=rowを配列複製


●壁描画(wall,max)とは:
    全描画クリア
    iを0からHorizontal_row-1まで繰り返す:
        jを0からVertical_row-1まで繰り返す:
            もしwall[i][j]=1なら:
            　　黒色に塗色設定
            　　[i*Width,j*Width,Width,Width]に四角描画
            もしwall[i][j]>1なら:
                hue=CEIL(255/max*wall[i][j])
                RGB(hue,0,255-hue)に塗色設定
            　　[i*Width,j*Width,Width,Width]に四角描画



●探索路描画(route)とは:
    0.01に線太設定
    all=routeの要素数
    i=0
　　routeを反復:
　　　　定数[x,y]=対象
　　　　hue=CEIL(255/all*i)
　　　　RGB(hue,ABS(255-ABS(255-2*hue)),255-hue)に塗色設定
　　　　i=i+1
　　　　[x*Width,y*Width,Width,Width]に四角描画



●(x,y)迷路作成とは:
    Wall[x][y]=0
    way=Directionを配列複製
    wayを配列シャッフル
    wayを反復:
        定数[dx,dy]=対象
        wx=x+dx+dx
        wy=y+dy+dy
        もし迷路範囲内(wx,wy)&&Wall[wx][wy]==1ならば:
            Wall[wx-dx][wy-dy]=0
            迷路作成(wx,wy)


●(px,py)迷路範囲内とは:
    もしpx<0||px>=Horizontal_row||py<0||py>=Vertical_rowならば:
    　　falseを戻す
    trueを戻す


●四方探索(x,y):
    もしlist[x][y]==0なら:
        list[x][y]=distance
    Directionを反復:
        定数[dx,dy]=対象
        mx=x+dx
        my=y+dy
        もし迷路範囲内(mx,my)&&list[mx][my]==0なら:
            stackに[mx,my]を配列追加


●search(x,y,gx,gy):
    px=x
    py=y
    main__四方探索(px,py)
    flag=true
    px<>gx||py<>gyの間繰り返す:
        もし(stackの要素数)==0なら:
            flag=false
            抜ける
        last=stackの要素数-1
    　　px=stack[last][0]
    　　py=stack[last][1]
    　　stackのlastを配列削除
    　　distance=distance+1
    　　main__四方探索(px,py)
    　　0秒待
    　　main__壁描画(list,distance)
    #ここで探索は終了
    もしflagなら:
        mx=gx
        my=gy
        goalRoute=[[mx,my]]
        iをdistanceから2まで繰り返す:
            Directionを反復:
                定数[dx,dy]=対象
                もしlist[mx+dx][my+dy]==iなら:
                    mx=mx+dx
                    my=my+dy
                    goalRouteの0に[mx,my]を配列挿入
                    抜ける

作品について

作品情報

作品を編集

クレスト作

ライセンス: MIT（改変可/表示）
形式: wnako
タグ: Maze, Algorithm
利用バージョン: 3.5.1
アクセス数(累計): 123
アクセス数(今月): 51
更新日時: 2024/03/06 22:19 編集: 2024/03/06 22:29

⭐⭐⭐⭐⭐

作品公開情報

交流

コメントを取得中...