Geekly Articles each Day

叀兞的な迷路生成アルゎリズム。 パヌト2チャンスに飛び蟌む



たえがき


→ 前半

だから。 Habrオヌディ゚ンスの反応を評䟡し、問題を敎理し、サむクルの2番目の蚘事を曞き始めたした。 倧衆の反応は私の想定よりもはるかに肯定的でした。぀たり、手続き生成の最も興味深いトピックの1぀である迷路の䜜成に぀いお䌚話を続けおいたす。

このパヌトでは、ランダムおよび擬䌌ランダム生成ずは䜕か、アルゎリズムは互いに同等に異なる迷路を䞎えるこずができるもの、およびそれらの䞍利な点に぀いお説明したす。 今日の冒険のヒヌロヌは、りィル゜ンアルゎリズムずランダムスパニングツリヌ均䞀スパニングツリヌを䜜成するためのAldous-Broderアルゎリズムです。 泚意トラフィック 。

問題の理想的な迷路が䜕であるかを思い出したしょう。 グラフの各頂点から他の頂点たで正確に1぀のパスがあり、同じ゚ッゞを2回通過せずにすべおの頂点を通過できない堎合、このようなグラフをスパニングツリヌず呌びたす 。 各セルから他のセルぞの怜蚎䞭のラビリンスで、正確に1぀の通路があり、同じ廊䞋を2回通過するこずなくすべおのセルを蚪れるこずができない堎合、そのようなラビリンスが理想的であるず蚀いたす。 意味は1぀の簡単な理由で倉わりたせん。迷宮はグラフであり、前の蚘事で曞きたした。 ただ読んでいない堎合は、先に進む前にもう少し䞊にスクロヌルし、リンクをたどっおそれをよく理解するこずを匷くお勧めしたす。

たた、このパヌトで玹介するアルゎリズムは非垞に䜎速で「愚かな」ものですが、トピック党䜓および私のすべおの蚘事の基盀であるため、察凊する必芁がありたす。 私がすぐに圌らから始めなかった䞻な理由は、りィル゜ンは初心者にずっお非垞に簡単に実装および理解するこずができず、それが圌の極端な奜奇心を劚げるものではないからです。

Luaに぀いお
りィル゜ンのアルゎリズム、そしおおそらく、私が曞いおいる他のいく぀かのアルゎリズムでは、次のテヌブル[、むンデックス]関数を䜿甚しお、ただアクセスされおいないランダムなセルを遞択したす。 その説明は、Luaの公匏ドキュメントからのものです。
アプリケヌションがテヌブル内のすべおのフィヌルドを取埗できるようにしたす。 最初のパラメヌタヌはテヌブル、2番目はこのテヌブルのむンデックスです。 nextは、テヌブル内の次のむンデックスずそれに察応する倀を返したす。 2番目のパラメヌタヌがnilの堎合、nextは開始むンデックスずそれに関連付けられた倀を返したす。 最埌のむンデックスが呌び出されたずき、たたは空のテヌブルにnilがある堎合、nextはnilを返したす。 2番目のパラメヌタヌが欠萜しおいる堎合、nilずしお解釈されたす。 特に、nexttを䜿甚しお、テヌブルが空かどうかを確認できたす。

したがっお、math.randomを䜿甚しおセルを遞択し、凊理されたかどうかを確認するか、スタックテヌブルのスタックを䜿甚しおハッシュテヌブルでその堎所を远跡する代わりに、座暙でハッシュされるキヌを1぀だけ䜿甚できたす次から芁玠を取り出したす。

key = next(cellsHash, nil) local start_x, start_y = aux.deHashKey(key) cellsHash[key] = nil — ,  nil  /


倉䜍ずランダム性


ランダム生成ずはどういう意味ですか 2番目のラビリンスで、1番目ずは異なり、南に2぀の壁がない堎合、それらは完党にランダムであるず蚀えたすか たたは、最初の迷路にさらに2぀の氎平通路がある堎合はどうでしょうか はい、いいえ。

ラビリンスのランダム性ずいえば、私たちが䜕を意味するのかを明確に認識しなければなりたせん。 二分朚アルゎリズムの結果を芋おみたしょう





ご芧のずおり、ラビリンス自䜓は完党に異なりたすが、倉䜍はわずかに異なりたす。

ランダムな結果が埗られたしたか はい 圌をそのように考えるこずはできたすか たあ、私の意芋では、いいえ。

問題はバむアスであり、これが䞻に「ランダム性」を決定したす。 定矩䞊、ランダムな迷路を䜜成し、最終的に同様の迷路を䜜成するアルゎリズム。 バむナリツリヌのように「類䌌性」が発音される堎合、そのような迷路は簡単に解決されるず蚀いたす。 いく぀かのラビリンスを比范するずきに、アルゎリズムが䜕に匕き付けられるかを明確に蚀うこずが難しい堎合、そのようなラビリンスを解決するのはより難しいず蚀いたす。 バむアスを芋぀けるには、生成のいく぀かの結果を比范し、このタむプの迷路を解決するために、よりスマヌトなパスたたは自分自身の怜玢を䜜成できる統蚈モデルを構築する必芁がありたす。 たずえば、二分朚アルゎリズムには、垂盎方向の通路のn倍の氎平方向の通路があるず蚀えたす。 これは、デヌタを考慮に入れお、出口を芋぀けるプロセスを高速化できるこずを意味したす。

しかし、バむアスをたったく必芁ずしない堎合はどうでしょうか たずえば、グラフの接続されおいない9個のポむントから、他ずはたったく異なるスパニングツリヌを取埗するたびに、 次に、アルゎリズムの各方向が同等になる必芁がありたす。 これは、すでに完了したピヌクを通過できるこずを意味したす。したがっお、サむクルの各反埩で、そこにいたかどうかに関係なく、4぀の方向のいずれかをランダムに遞択したす。 唯䞀の条件は、フィヌルドを超えないこずです。

甚語ナニフォヌムスパニングツリヌずいえば。 スパニングツリヌが䜕であるかは既にわかっおいたす。 グラフのすべおの頂点を゚ッゞで接続し、同じ゚ッゞを2回通過せずに頂点から別の頂点に到達できないようにするず、スパニングツリヌが䜜成されたす。 しかし、グラフに3぀以䞊の頂点がある堎合、さらに倚くのツリヌバリ゚ヌションがあるかもしれたせん。 そのため、均䞀スパニングツリヌは、特定のグラフにおけるスパニングツリヌのバリ゚ヌションの1぀です。

など。 互いに完党に異なる完党にランダムなラビリンスが必芁であり、速床を犠牲にする準備さえできおいたす。 それでは、Aldous-BroderアルゎリズムずWilsonアルゎリズムに぀いお理解したしょう。

Aldous-Broderアルゎリズム









説明

二分朚アルゎリズムが最も理解しやすいず蚀ったこずを芚えおいたすか だから、私はcでした。 垞に考慮しおいるのは1぀の方向ず1぀の偎面のみを扱うため、実装は非垞に簡単ですが、原始性ず「愚かさ」ではAldous-Broderアルゎリズムがはるかに進んでいたす。 その党䜓のポむントは、䜜成されるスパニングツリヌの䞊郚に぀たずいお別のポむントを取り付けるこずを期埅しお、フィヌルドをあちこち歩き回り、再びランダムに迷路のポむントを遞択し、接続されたものの1぀に入るたで歩くこずです。

Aldous-Broderにはバむアスがありたせん。 絶察に。 その助けを借りお埗られた迷路はすべお完党にランダムであり、䌌おいたせん。 アルゎリズムには、方向性、゚ンタングルメント、たたはその他の特性の奜みはありたせん。 結果のラビリンスはランダムであり、同様に発生する可胜性がありたす。

問題は、乱数ゞェネレヌタヌの欠陥である可胜性がありたす。乱数ゞェネレヌタヌ自䜓は、いく぀かの倀に匕き寄せられ、より頻繁に倀を䞎える堎合がありたす。 しかし、たずえば、自然ノむズ颚、りラン厩壊に基づいたランダムゞェネレヌタヌを䜿甚する堎合、おそらく、アルゎリズムの操䜜を最終的に完党に楜しむこずができたす。

確かに、圌の䜜品を芳察するこずは、存圚のすべおの腐敗性ず無意味さの真の認識を䞎えたす。 圌は5×5のフィヌルドで30秒に収たりたくなかったため、アニメヌションでgifを蚘録するのに倚くの時間を費やしたした。 最埌の1぀の未チェックのセルのみをスパニングツリヌに接続し続けるず、Aldous-Broderは別のコヌナヌに行き、そこで円をラップしたした。 最終的に圌は迷路のすべおのセルを回るこずができるように、アニメヌションの速床を倧幅に䞊げ、フィヌルドを枛らす必芁がありたした。

これは、スパニングツリヌの同等の可胜性のある倉皮を研究した2人の独立した研究者によっお䜜成されたした。カリフォルニア倧孊バヌクレヌ校の教授であるDavid Aldousず、珟圚Googleで働いおいる科孊者のAndrei Broderです。 これらの研究がどの分野で圹立぀かを明確に蚀うこずは困難です。 ただし、ラビリンスに加えお、アルゎリズムは数孊的な確率の研究でしばしばポップアップしたすが、その動䜜原理を考えるず驚くこずではありたせん。

正匏なアルゎリズム

  1. ランダムな頂点セルを遞択したす。 完党にランダム。
  2. ランダムに隣接する頂点セルを遞択しお、そこに進みたす。 蚪問されおいない堎合は、ツリヌに远加したす前のツリヌに接続し、それらの間の壁を削陀したす。
  3. すべおのセルが衚瀺されるたで手順2を繰り返したす。

䜜業䟋
フィヌルド䞊の珟圚の䜍眮は赀で匷調衚瀺されたす。

巊䞊隅から始めたす。 ここでは珍しいこずはありたせん。



ランダムに右に移動しお、2぀のセル間の壁を削陀するこずにしたした。 わかった。



運が悪い。 私たちのRNGは、私たちが巊に戻るず蚀いたす。



今ダりン。 途䞭で、未蚪問のセルをすべお接続し、それらの間の壁を削陀したす。



たたラッキヌ。 ダりン



さお、1回の戻りは蚱されたす。


右偎に移動しお壁を削陀するこずを遞択したす。



そしお、ここで私たちは2回䞍運であり、最初に戻りたす。




遞択肢は二床萜ちお、うたくいきたした。 玠晎らしい、少なくずもいく぀かの皮類。




䞋に行っお壁を取り陀きたす。



そしお、次のセルに移動したす。壁は既に同じツリヌにあるため、壁は削陀したせん。



目的もなく歩き回り、歩き回る時です。






セル2-2に戻り、䞋に降りお壁を取り陀きたす。



掃陀を完了し、生成された迷路を取埗したす。



長所


短所


実装
 local mod = {} local aux = {} aux.width = false aux.height = false aux.sx = false aux.sy = false aux.grid = false aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"} function aux.createGrid (rows, columns) local MazeGrid = {} for y = 1, rows do MazeGrid[y] = {} for x = 1, columns do MazeGrid[y][x] = {visited = false, bottom_wall = true, right_wall = true} end end return MazeGrid end function mod.createMaze(x1, y1, x2, y2, grid) aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1 aux.grid = grid or aux.createGrid(y2, x2) aux.aldous_broder() return aux.grid end function aux.aldous_broder() local unvisited_cells = aux.width * aux.height local ix = math.random(aux.sx, aux.width) local iy = math.random(aux.sy, aux.height) aux.grid[iy][ix].visited = true unvisited_cells = unvisited_cells - 1 while unvisited_cells ~= 0 do local dir = aux.dirs[math.random(1, 4)] if dir == "UP" then if iy-1 >= aux.sy then if aux.grid[iy-1][ix].visited == false then aux.grid[iy-1][ix].bottom_wall = false aux.grid[iy-1][ix].visited = true unvisited_cells = unvisited_cells - 1 end iy = iy-1 end elseif dir == "DOWN" then if iy+1 <= aux.height then if aux.grid[iy+1][ix].visited == false then aux.grid[iy][ix].bottom_wall = false aux.grid[iy+1][ix].visited = true unvisited_cells = unvisited_cells - 1 end iy = iy+1 end elseif dir == "RIGHT" then if ix+1 <= aux.width then if aux.grid[iy][ix+1].visited == false then aux.grid[iy][ix].right_wall = false aux.grid[iy][ix+1].visited = true unvisited_cells = unvisited_cells - 1 end ix = ix+1 end elseif dir == "LEFT" then if ix-1 >= aux.sx then if aux.grid[iy][ix-1].visited == false then aux.grid[iy][ix-1].right_wall = false aux.grid[iy][ix-1].visited = true unvisited_cells = unvisited_cells - 1 end ix = ix-1 end end end end return mod


りィル゜ンアルゎリズム








説明

おめでずう、私たちは぀いにもっず深刻な䜕かに到達したした。 りィル゜ンのアルゎリズムは、実装ず理解の䞡方においお、以前のアルゎリズムよりもはるかに耇雑です。 りィル゜ンの目暙は、圌の愚かなパヌトナヌであるAldous-Broderの目暙のように、同様に確率の高いランダムなスパニングツリヌを生成するこずです。 動䜜原理は倚少䌌おいたすが、詳现は倧きく異なりたす。

このアルゎリズムは、迷路グラフの移動偎のランダムな遞択に等しく基づいおいたすが、2぀の重芁な違いがありたす。

フィヌルド内を移動しお、スパニングツリヌの頂点が芋぀かる前に蚪れたすべおの頂点を「蚘憶」したす。 既に远加された頂点に出䌚うずすぐに、生成されたツリヌに結果のサブグラフブランチを添付したす。 サブグラフにルヌプが䜜成されおいる堎合は、削陀したす。 ルヌプずは、䞀時的なサブグラフにすでにある頂点ず、別のポむントにある頂点ずの接続を意味したす。 ぀たり、頂点が2぀を超える頂点があっおはなりたせん。 あなたが今理解しおいないなら、それは怖くありたせん-あなたは仕事の䟋でさらに明確に芋るでしょう。

サブグラフをスパニングツリヌにアタッチした埌、次のランダムポむントの遞択は、ただアタッチされおいない頂点からのみ発生したす。 その結果、Aldous-Broderずは異なり、りィル゜ンには、すでに凊理されたピヌクをあおもなくさたようずいう䞍利な点がありたせん。

Aldous-BroderのようなWilsonのアルゎリズムは、偏りのない完党にランダムなラビリンスを生成したす。 アルゎリズムには、方向性、゚ンタングルメント、たたはその他の特性の奜みはありたせん。 残念ながら、最良の結果を埗るには、数倀の蚭定がないハヌドりェア乱数ゞェネレヌタヌを䜿甚する必芁がありたす。

アルゎリズム自䜓は、1996幎に、David Wilsonによっお、等確率のランダムスパニングツリヌの生成に関する論文で公開されたした。 前ず同様に、迷路に加えお、数孊的確率に専念するさたざたなサむトに資料がポップアップ衚瀺されたす。 さらに、特に均䞀スパニングツリヌずりィル゜ンアルゎリズムに関するいく぀かの興味深い出版物に出䌚いたした。 それらの1぀でアルゎリズム自䜓がより詳现に説明されおいる堎合、もう1぀では党䜓ずしお抂念自䜓ずスパニングツリヌの数孊的基瀎が説明されおいたす。

読者が興味を持ったら、おそらくパヌト2aを曞きたす。そこで、䜜品自䜓ずその郚分的な翻蚳を匕甚したす。 ここで数孊的な正圓化を避ける䞻な理由は、私の蚘事が初心者や也匏数孊よりもプログラミングに興味がある人を察象にしおいるからです。

正匏なアルゎリズム

  1. スパニングツリヌに属さないランダムな頂点を遞択しお、ツリヌに远加したす。
  2. スパニングツリヌに属さないランダムな頂点を遞択し、ツリヌに既に远加されおいる頂点に到達するたでグラフの移動迷路を開始したす。 サむクルが圢成された堎合、それを削陀したす。
  3. 結果のサブグラフのすべおの頂点をスパニングツリヌに远加したす。
  4. すべおの頂点がスパニングツリヌに远加されるたで、手順2〜3を繰り返したす。

䜜業䟋
ツリヌの最初の頂点が緑色で匷調衚瀺されたす。 èµ€-䜜成されたブランチサブグラフ。

䌝統的に、あなたは巊䞊隅に入る必芁がありたす。 座暙3-2からブランチを構築し始めたす。






これが興味深い重芁なポむントです。 アルゎリズムは䞊昇するこずを決定し、それによっお座暙2-2でブランチを閉じたす。



結果のサむクルを削陀し、2-2から再構築を開始したす。


habrastorage.org/files/e9c/8e6/46a/e9c8e646af564a42bbb391fbe263044b.png

さお、アルゎリズムは䞊昇するこずを決定し、それによっおメむンツリヌに参加したした。 途䞭で壁を取り陀き、次のセルを遞択したす。




再び、圌らは最近䜜成された朚に觊れ、壁を取り陀き、再び始めたした。






私たちは閉じ、サむクルを削陀し、2-3で再び続けたした。



朚に接続され、パスの壁をクリアしたした。 私たちは新しいケヌゞで旅を続けたした。





再びメむンツリヌに接続し、壁を取り陀き、迷路を完成させたした。



長所


短所


実装
 local mod = {} local aux = {} aux.width = false aux.height = false aux.sx = false aux.sy = false aux.grid = false aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"} function aux.createGrid (rows, columns) local MazeGrid = {} for y = 1, rows do MazeGrid[y] = {} for x = 1, columns do MazeGrid[y][x] = {visited = false, bottom_wall = true, right_wall = true} end end return MazeGrid end function mod.createMaze(x1, y1, x2, y2, grid) aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1 aux.grid = grid or aux.createGrid(y2, x2) aux.wilson() return aux.grid end function aux.hashKey(x, y) return x * aux.height + (y - 1) end function aux.deHashKey(value) return math.floor(value/aux.height), value%aux.height + 1 end function aux.hashCells(grid) local vtable = {} for yk, yv in pairs(grid) do for xk, xv in pairs(yv) do if xv.visited == false then vtable[aux.hashKey(xk, yk)] = xv end end end return vtable end function aux.wilson() local cellsHash = aux.hashCells(aux.grid) -- ,     local dirsStack = {} --   local dsHash = {} local dsSize = 0 --   local key, v = next(cellsHash, nil) v.visited = true cellsHash[key] = nil while next(cellsHash) do --    ,  key = next(cellsHash, nil) --        local start_x, start_y = aux.deHashKey(key) local ix, iy = start_x, start_y while not aux.grid[iy][ix].visited do -- ,        local dir = aux.dirs[math.random(1, 4)] local isMoved = false key = aux.hashKey(ix, iy) if dir == "UP" and iy-1 >= aux.sy then iy = iy - 1 isMoved = true elseif dir == "DOWN" and iy+1 <= aux.height then iy = iy + 1 isMoved = true elseif dir == "LEFT" and ix-1 >= aux.sx then ix = ix - 1 isMoved = true elseif dir == "RIGHT" and ix+1 <= aux.width then ix = ix + 1 isMoved = true end if isMoved then --    ,     if dsHash[key] then --   dirsStack[dsHash[key]].dir = dir for i = dsHash[key]+1, dsSize do local x, y = aux.deHashKey(dirsStack[i].hashref) dsHash[dirsStack[i].hashref] = nil dirsStack[i] = nil dsSize = dsSize - 1 end else local x, y = aux.deHashKey(key) --     dsSize = dsSize + 1 dsHash[key] = dsSize dirsStack[dsSize] = {dir = dir, hashref = key} end end end for i = 1, dsSize do --   aux.grid[start_y][start_x].visited = true cellsHash[aux.hashKey(start_x, start_y)] = nil aux.grid[start_y][start_x].point = false local dir = dirsStack[i].dir if dir == "UP" then aux.grid[start_y-1][start_x].bottom_wall = false start_y = start_y - 1 elseif dir == "DOWN" then aux.grid[start_y][start_x].bottom_wall = false start_y = start_y + 1 elseif dir == "LEFT" then aux.grid[start_y][start_x-1].right_wall = false start_x = start_x - 1 elseif dir == "RIGHT" then aux.grid[start_y][start_x].right_wall = false start_x = start_x + 1 end end dsHash, dirsStack, dsSize = {}, {}, 0 --    end end return mod


゚ピロヌグ


䞊蚘のすべおを芁玄するず、より耇雑なアルゎリズムに着手し、グラフのいく぀かのいく぀かの抂念を芋぀けたが、䞻な困難はただ来おいないこずに泚意する䟡倀がありたす。 Eller、Kraskal、Primの明らかに玛らわしいアルゎリズムは、グラフずツリヌの操䜜のみに基づいおおり、興味深いずはいえ、難しい出版物を準備しおいたす。 ただし、それらを曞き始める前に、リタヌンサヌチアルゎリズムず、「CatchKill」ず呌ばれるものを芋おください。迷路を生成する䜜業は他のすべおずは非垞に異なりたす。 次の蚘事に぀いおヒントを䞎えたした。

他に䜕。 前の郚分ぞのコメントで、䞀郚の人々は圌らの生成アルゎリズムを尋ねたり捚おたりしたした。 独自の方法でラビリンスの䜜成を䞀床実装し、今すぐ芚えるこずができる堎合は、共有しおください。 おそらく、あなたの蚱可を埗お、私が圌に぀いお曞く蚘事のいく぀かで。 䞀般的に、私はこのトピックに関する興味深い話や思い出に満足しおいたす。 孊校のノヌトブックや倧孊のコンピュヌタヌで迷路を描く方法を芚えおいおも構いたせん。

たあ、そしおい぀ものように。 願い、批刀、コメントはい぀でも歓迎したす。トピックが気に入っお次のパヌトを芋たい堎合は、コメントに曞いおください。

Lua +のアルゎリズムの゜ヌス+ Love2Dでレンダリングコメント内のリク゚ストでコヌドがレむアりトされたす。リファクタリングされたせん
Github

Source: https://habr.com/ru/post/J321210/

More articles:


All Articles