Лабиринт жасау алгоритмдері: компьютерде лабиринттерді автоматты түрде құрудың қарапайым әдісі – рекурсивті іздеу. Жаңа лабиринттер жасауға көмектеседі!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Лабиринттерді құрудың автоматтандырылған әдістері – лабиринттерді жасауға арналған автоматты әдістер.
Automated methods for the creation of mazes
Maze generation algorithms are automated methods for the creation of mazes.
Рандомизацияланған тереңдіктегі бірінші іздеу
Бұл алгоритм, сондай-ақ "рекурсивті кері іздеуші" алгоритмі деп аталады, тереңдікке бірінші іздеу алгоритмінің кездейсоқ түрі болып табылады. Көбінесе стекпен іске асырылатын бұл тәсіл компьютер арқылы лабиринт жасаудың ең оңай жолдарының бірі. Лабиринт кеңістігін ұяшықтардың үлкен торы (мысалы, үлкен шахмат тақтасы) ретінде қарастырайық, әрбір ұяшық бастапқыда төрт қабырғамен жабдықталған. Кездейсоқ ұяшықтан бастап, компьютер әлі бармаған кездейсоқ көрші ұяшықты таңдайды. Компьютер екі ұяшық арасындағы қабырғаны жойып, жаңа ұяшықты барылған деп белгілейді және кері іздеуді жеңілдету үшін оны стекке қосады. Компьютер осы процесті жалғастырады, ал бармаған көршісі жоқ ұяшық – тұйыққа тірелу болып саналады. Тұйыққа жеткенде, компьютер бармаған көршісі бар ұяшыққа дейін жол арқылы кері қайтады, содан кейін осы жаңа, бармаған ұяшықты барып (жаңа түйіскен жер құрады) жолды жалғастырады. Бұл процесс барлық ұяшықтар барылғанша жалғасады, соның салдарынан компьютер бастапқы ұяшыққа кері қайтады. Біз барлық ұяшықтар барылғандығына көз жеткізе аламыз. Жоғарыда айтылғандай, бұл алгоритм кейбір компьютерлік архитектураларда стек асығып кетуіне себеп болатын терең рекурсияны қамтиды. Алгоритмді лабиринттің өзінде кері іздеу туралы ақпаратты сақтап, циклға айналдыруға болады. Бұл кез келген нүктеден бастап, бастапқы ұяшыққа кері қайту арқылы шешімді жылдам көрсетуге мүмкіндік береді. Тереңдікке бірінші іздеу арқылы жасалған лабиринттерде тармақтану факторы төмен және көптеген ұзын дәліздер болады, себебі алгоритм кері қайтудан бұрын әр тармақ бойынша мүмкіндігінше алысқа дейін іздейді.
This algorithm, also known as the "recursive backtracker" algorithm, is a randomized version of the depth first search algorithm. Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the wall between the two cells and marks the new cell as visited, and adds it to the stack to facilitate backtracking. The computer continues this process, with a cell that has no unvisited neighbours being considered a dead end. When at a dead end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. We can be sure every cell is visited. As given above this algorithm involves deep recursion which may cause stack overflow issues on some computer architectures. The algorithm can be rearranged into a loop by storing backtracking information in the maze itself. This also provides a quick way to display a solution, by starting at any given point and backtracking to the beginning. Mazes generated with a depth first search have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before backtracking.
Өзгертілген нұсқасы
Классикалық Прим алгоритмі шеттер тізімін сақтайтын болса, лабиринт жасау үшін көршілес жасушалар тізімін ұстауға болады. Кездейсоқ таңдалған жасушада егер қазіргі лабиринтке қосылатын бірнеше шет болса, сол шеттердің біреуін кездейсоқ таңдаңыз. Бұл, жоғарыдағы шеттерге негізделген нұсқаға қарағанда, сәл көбірек тармақтануға бейім.
Although the classical Prim's algorithm keeps a list of edges, for maze generation we could instead maintain a list of adjacent cells. If the randomly chosen cell has multiple edges that connect it to the existing maze, select one of these edges at random. This will tend to branch slightly more than the edge based version above.
Жайдастырылған нұсқа
Алгоритмді барлық ұяшықтардың немесе қабырғалардың салмағын есепке алмастан, бұрын барылған ұяшықтардың жанындағы ұяшықтарды кездейсоқ таңдау арқылы одан да оңайлатуға болады. Бастапқы ұяшыққа жол табу әдетте оңай, бірақ басқа жерге жол табу қиын болады.
The algorithm can be simplified even further by randomly selecting cells that neighbour already visited cells, rather than keeping track of the weights of all cells or edges. It will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.
Вильсон алгоритмі
Жоғарыда аталған алгоритмдердің барлығының түрлі қиылыстары бар: тереңдікке бірінші іздеу ұзын дәліздерге қарай қиысады, ал Крускаль/Прим алгоритмдері көптеген қысқа тұйыққа қарай қиысады. Вильсон алгоритмі, керісінше, барлық лабиринттер бойынша біркелкі таралудан циклдерді жоятын кездейсоқ жүріс арқылы бейтарап үлгі жасайды. Алгоритмді лабиринтті кездейсоқ таңдалған бір жасушадан бастау арқылы іске қосамыз. Содан кейін, тағы да кездейсоқ таңдалған жаңа жасушадан бастап, лабиринттегі жасушаға жеткенше кездейсоқ жүріс жасаймыз. Бірақ, егер кездейсоқ жүріс өзінің жолына жетіп, цикл құрса, одан әрі жүргенге дейін осы циклді жоямыз. Жол лабиринтке жеткенде, оны лабиринтке қосамыз. Содан кейін, барлық жасушалар толтырылғанша, басқа кездейсоқ басталатын жасушадан циклдерді жоятын кездейсоқ жүрісті қайталап орындаймыз. Бұл процедура бастапқы жасушаны кездейсоқ таңдау үшін қандай әдіс қолданылса да бейтарап болып қалады. Сондықтан, қарапайымдық үшін біз әрқашан бірінші бос жасушаны (мысалы) солдан оңға, жоғарыдан төменге таңдауымыз мүмкін.
All the above algorithms have biases of various sorts: depth first search is biased toward long corridors, while Kruskal's/Prim's algorithms are biased toward many short dead ends. Wilson's algorithm, on the other hand, generates an unbiased sample from the uniform distribution over all mazes, using loop erased random walks. We begin the algorithm by initializing the maze with one cell chosen arbitrarily. Then we start at a new cell chosen arbitrarily, and perform a random walk until we reach a cell already in the maze—however, if at any point the random walk reaches its own path, forming a loop, we erase the loop from the path before proceeding. When the path reaches the maze, we add it to the maze. Then we perform another loop erased random walk from another arbitrary starting cell, repeating until all cells have been filled. This procedure remains unbiased no matter which method we use to arbitrarily choose starting cells. So we could always choose the first unfilled cell in (say) left to right, top to bottom order for simplicity.
Рекурсивті бөлу әдісі
+ Рекурсивті бөлінудің мысалы бастапқы камера екі қабырғамен бөлінеді қабырғалардағы тесіктер бөлінуді жалғастырады аяқталды
+ Illustration of Recursive Division original chamber division by two walls holes in walls continue subdividing completed
Лабиринттерді рекурсивті бөліну арқылы жасауға болады, бұл алгоритм келесідей жұмыс істейді: лабиринт кеңістігін қабырғаларсыз бастаңыз. Бұны камера деп атаңыз. Камераны кездейсоқ орналасқан қабырғамен (немесе бірнеше қабырғамен) бөліңіз, сонда әр қабырғада кездейсоқ орналасқан өту тесігі болады. Содан кейін, барлық камералар ең кішкентай өлшемге жеткенше, осы процесті рекурсивті түрде қайталаңыз. Бұл әдіс кеңістігін кесіп өтетін ұзын, түзу қабырғалары бар лабиринттерді құрайды, бұл қай аймақтардан қашу керектігін анықтауды жеңілдетеді. Мысалы, тіктөртбұрышты лабиринтте екі қабырғаны кездейсоқ нүктелерде бір-біріне перпендикуляр етіп салыңыз. Бұл екі қабырға үлкен камераны төрт кіші камераға, төрт қабырғамен бөліп, бөледі. Төрт қабырғаның үшеуін кездейсоқ таңдап, әрқайсысында кездейсоқ нүктеде бір ұяшық енді тесік жасаңыз. Әр камераның ені екі бағытта бір ұяшыққа дейін жеткенше осылай жалғастырыңыз.
Mazes can be created with recursive division, an algorithm which works as follows: Begin with the maze's space with no walls. Call this a chamber. Divide the chamber with a randomly positioned wall (or multiple walls) where each wall contains a randomly positioned passage opening within it. Then recursively repeat the process on the subchambers until all chambers are minimum sized. This method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid. For example, in a rectangular maze, build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell wide hole at a random point in each of the three. Continue in this manner recursively, until every chamber has a width of one cell in either of the two directions.
Фракталды теселяция алгоритмі
Бұл лабиринт жасаудың қарапайым және жылдам тәсілі. Әр итерацияда алгоритм өзін 3 рет көшіріп, екі есе үлкен лабиринт құрайды. Әр итерацияның соңында 4 кіші лабиринттің арасында 3 жол ашылады. Бұл әдістің артықшылығы – өте жылдамдығы. Ал кемшілігі – қалаған өлшемдегі лабиринт жасау мүмкін емес, бірақ осы мәселенің шешімі үшін түрлі амалдар қолданылуы мүмкін.
This is a simple and fast way to generate a maze. On each iteration, this algorithm creates a maze twice the size by copying itself 3 times. At the end of each iteration, 3 paths are opened between the 4 smaller mazes. The advantage of this method is that it is very fast. The downside is that it is not possible to get a maze of a chosen size but various tricks can be used to get around this problem.
Қарапайым алгоритмдер
Басқа алгоритмдер де бар, олар 2D лабиринттің бір қатарын немесе 3D лабиринттің бір жазықтығын сақтауға жететін жадты ғана қажет етеді. Эллер алгоритмі ағымдағы қатардағы қай жасушалардың бұрынғы қатарлардағы жасушалар арқылы байланысқандығын сақтап, циклдардың пайда болуын болдырмайды және екі бұрыннан байланысқан жасуша арасындағы қабырғаларды ешқашан жоймайды. Sidewinder алгоритмі жоғарғы қатардың бойымен ашық өткелмен басталады, ал келесі қатарлар жоғарыдағы өткелмен бір байланысы бар қысқа көлденең өткелдерден тұрады. Sidewinder алгоритмін төменнен жоғарыға қарай шешу оңай, себебі оның жоғары бағытта тұйықталған жолдары жоқ. Бастапқы ені берілген екі алгоритм де шексіз биіктіктегі лабиринттерді жасай алады. Көптеген лабиринт құру алгоритмдері оның ішіндегі жасушалар арасындағы байланысты сақтауды талап етеді, нәтижесінде оны шешуге болады. Дегенмен, әр жасушаға жеке-жеке назар аудару арқылы қарапайым байланысқан лабиринттерді жасауға болады. Бинарлық ағаш лабиринті – бұл әр жасушада әрқашан жоғары немесе солға қарай өтетін жол бар, бірақ ешқашан екеуі де бірдей болмайды. Бинарлық ағаш лабиринтін құру үшін әр жасуша үшін жоғары немесе солға қарай өтетін жолды қосуды шешу үшін монетаны лақтырыңыз. Шекарадағы жасушалар үшін әрқашан бірдей бағытты таңдаңыз, нәтижесінде бинарлық ағаш сияқты көрінетін, қарапайым байланысқан лабиринт пайда болады, оның түбірі жоғарғы сол жақ бұрышында орналасқан. Sidewinder сияқты, бинарлық ағаш лабиринтінде де бағытталған тұйық жолдар жоқ. Әр жасуша үшін монетаны лақтырудың ұқсас түрі – кездейсоқ араласқан көлденең және кері көлденең белгілерді пайдаланып сурет жасау. Бұл қарапайым байланысқан лабиринтті емес, жабық циклдар мен біржолғы өткелдерді құрады. Commodore 64 нұсқаулығында осы алгоритмді қолданатын BASIC бағдарламасы ұсынылған, графикалық бейнесін жақсарту үшін PETSCII диагональдық сызық графикалық белгілері қолданылған.
Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze. Eller's algorithm prevents loops by storing which cells in the current line are connected through cells in the previous lines, and never removes walls between any two cells already connected. The Sidewinder algorithm starts with an open passage along the entire top row, and subsequent rows consist of shorter horizontal passages with one connection to the passage above. The Sidewinder algorithm is trivial to solve from the bottom up because it has no upward dead ends. Given a starting width, both algorithms create perfect mazes of unlimited height. Most maze generation algorithms require maintaining relationships between cells within it, to ensure the result will be solvable. Valid simply connected mazes can however be generated by focusing on each cell independently. A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the result will be a valid simply connected maze that looks like a binary tree, with the upper left corner its root. As with Sidewinder, the binary tree maze has no dead ends in the directions of bias. A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters. This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages. The manual for the Commodore 64 presents a BASIC program using this algorithm, using PETSCII diagonal line graphic characters instead for a smoother graphic appearance.
Ұялы автомат алгоритмдері
Кейбір түрдегі ұялы автоматтар лабиринттерді жасау үшін қолданылуы мүмкін. Екі танымал мысал – Maze және Mazectric ұялы автоматтары, олардың ережелері B3/S12345 және B3/S1234 болып табылады. Бірінші жағдайда, бұл жасушалардың бір ұрпақтан екіншісіне тірі қалуын білдіреді, егер олардың кемінде бір және көп дегенде бес көршісі болса. Екінші жағдайда, бұл жасушалардың бірден төртке дейін көршісі болса ғана тірі қалатынын білдіреді. Егер жасушада дәл үш көрші болса, ол пайда болады. Бұл Конвейдің «Өмір» ойынына ұқсас, себебі кез келген ұрпақта 1, 4 немесе 5 басқа тірі жасушалармен тікелей жанаспайтын үлгілер осы ойын сияқты әрекет етеді. Дегенмен, үлкен үлгілер үшін ол «Өмірден» мүлдем өзгеше болып көрінеді. Кездейсоқ бастапқы үлгі үшін, бұл лабиринт жасайтын ұялы автоматтар дәліздерді анық көрсететін қабырғалары бар күрделі лабиринттерге айналады. B3/S1234 ережесіне ие Mazectric, B3/S12345 ережесіне ие Maze-ге қарағанда, ұзын және түзу дәліздер жасауға бейім. Бұл ұялы автоматтар ережелері детерминистік болғандықтан, жасалған әр лабиринт оның кездейсоқ бастапқы үлгісімен толық анықталады. Бұл маңызды кемшілік, себебі лабиринттерді болжау оңай. Жоғарыда сипатталған граф теориясына негізделген әдістер сияқты, бұл ұялы автоматтар әдетте бір бастапқы үлгіден лабиринттерді жасайды; сондықтан бастапқы жасушаға жол табу әдетте оңай, бірақ басқа жерге жол табу қиын.
Certain types of cellular automata can be used to generate mazes. Two well known such cellular automata, Maze and Mazectric, have rulestrings B3/S12345 and B3/S1234. In the former, this means that cells survive from one generation to the next if they have at least one and at most five neighbours. In the latter, this means that cells survive if they have one to four neighbours. If a cell has exactly three neighbours, it is born. It is similar to Conway's Game of Life in that patterns that do not have a living cell adjacent to 1, 4, or 5 other living cells in any generation will behave identically to it. However, for large patterns, it behaves very differently from Life. For a random starting pattern, these maze generating cellular automata will evolve into complex mazes with well defined walls outlining corridors. Mazecetric, which has the rule B3/S1234 has a tendency to generate longer and straighter corridors compared with Maze, with the rule B3/S12345. Since these cellular automaton rules are deterministic, each maze generated is uniquely determined by its random starting pattern. This is a significant drawback since the mazes tend to be relatively predictable. Like some of the graph theory based methods described above, these cellular automata typically generate mazes from a single starting pattern; hence it will usually be relatively easy to find the way to the starting cell, but harder to find the way anywhere else.