Алгоритам генерисања лавиринта

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Овај лавиринт је генерисан модификованом верзијом Примовог алгоритма.

Алгоритми генерисања лавиринта су аутоматизовани методи за креирање лавиринта.

Методи засновани на теорији графова[уреди]

Лавиринт може бити генерисан помоћу раније одређеног распореда ћелија (најчешће је то правоугаона мрежа, али су могући и други распореди) са пољима која представљају зид, а налазе се између њих. Овакав, раније генерисан распоред се може сматрати као повезани граф са страницама које представљају могућа поља за зидове и чворовима који представљају ћелије. Циљем алгоритма за генерисање лавиринта се онда може сматрати прављење подграфа у ком је изазов наћи пут између два одређена чвора.

Ако подграф није повезан, онда постоје делови графа који су изгубљени, јер они не спадају у простор претраге. Ако граф садржи петље тада може постојати више различитих путева између изабраних чворова. Због овога, генерисању лавиринта се најчешће приступа генерисањем насумичног разапињућег стабла. Петље које могу да збуне наивне решаваче лавиринта се могу добити додавањем насумичних ивица у резултујући лавиринт за време извршавања.

Претрага у дубину[уреди]

Анимација генерисања лавиринта димензије 30 са 20 коришћењем претраге у дубину.

Овај алгоритам је случајна варијанта алгоритма претраге у дубину. Често имплементиран преко стека, овај приступ је један од најједноставнијих начина да се лавиринт генерише путем рачунара. Сматрајмо да је простор за лавиринт велика мрежа ћелија (као велика шаховска табла), где свака ћелија стартује са четири зида. Почињући од насумичне ћелије, рачунар селектује случајну суседну ћелију која још није посећена. Рачунар уклања зид између ове две ћелије и додаје нову ћелију на стек (ово је аналогно цртанју линије по поду лавиринта). Рачунар наставља са овим процесом, а ћелија која нема непосећених суседа се сматра ћорсокаком. Када се нађе у ћорсокаку, он се враћа по путањи док не наиђе на ћелију која има непосећених суседа, а онда наставља генрисање тако што посећује ту непосећену ћелију. Овај процес се понавља док се не посете све ћелије, што узрокује да рачунар уради повратак кроз цео лавиринт до почетне ћелије. Овај приступ гарантује да је простор лавиринта у потпуности посећен.

Као што је већ речено, алгоритам је веома једноставан и не производи претешке лавиринте. Нека специфична унапређења алгоритма могу помоћи да се генеришу лавиринти које је теже решити.

  1. Почети у некој ћелији и назвати је „излаз“.
  2. Означити тренутну ћелију као посећену и узети листу њених суседа. За сваког суседа, почевши од случајно изабраног урадити:
    1. Ако тај сусед није био посећен, уклонити зид између те ћелије и тог суседа и поновити поступак рекурзивно за суседну ћелију.

Као што је раније наведено, овај алгоритам користи дубоку рекурзију која може проузроковати проблеме везане за прекорачење стека на неким рачунарским архитектурама. Алгоритам се може преправити у петљу, чувањем повратних информација у самом лавиринту. Ово такође омогућава брз начин да се прикаже решење, полазећи од било које тачке повратком до излаза.

Лавиринти генерисани претрагом у дубину имају мали фактор гранања и садрже много дугачких путања, што чини претрагу у дубину добрим алгоритмом за генерисање лавирината у видео играма. Случајним уклањањем одређеног броја зидова након креирања лавиринта методом претраге у дубину може се постићи ефекат проширења ходника лавиринта, што може бити одговарајући метод ако тежина решавања лавиринта није од пресудне важности. Овај метод се такође користи у видео играма.

У лавиринтима генерисаним овим алгоритмом, биће релативно лако наћи пут до квадрата који је пробран на почетку алгоритма, јер већина путања води директно до њега, али је зато тешко пронаћи пут назад.

Рекурзивна анализа наниже[уреди]

Алгоритам претраге у дубину је често имплементиран коришћењем анализе наниже.

  1. Поставити почетну ћелију на текућу и означити је као посећену.
  2. Док постоје непосећене ћелије:
    1. Ако текућа ћелија има суседе који нису посећени
      1. Одабери случајно једног од непосећених суседа
      2. Постави тренутну ћелију на врх стека
      3. Уклони зид између текуће и изабране ћелије
      4. Поставити одабрану ћелију на тренутну ћелију и означити је као посећену
    2. У супротном ако стек није празан:
      1. Скини ћелију са стека
      2. Поставити је да буде текућа ћелија
    3. У супротном:
      1. Узми случајну непосећену ћелију, постави је на текућу и означи као посећену

Случајни Крускалов алгоритам[уреди]

Овај алгоритам је случајна верзија стандардног Крускаловог алгоритма.

  1. Креирај листу свих зидова и креирај сет за сваку ћелију, где сваки сет садржи само по ту једну ћелију.
  2. За сваки зид, у неком случајном редоследу:
    1. Ако ћелије подељене овим зидом припадају различитим сетовима:
      1. Уклонити текући зид
      2. Спојити сетове претходно подељених ћелија

Постоји неколико структура података које се могу користити да моделују сет ћелија. Ефикасна имплементација која користи структуру раздвојених сетова може да изврши сваку унију и нађе операцију над два сета у скоро константном времену (прецизније, time; за сваку могућу вредност ), па је време извршавања овог алгоритма пропорционално броју зидова које лавиринт може да користи.

Питање је само да ли се листа зидова иницијално случајно генерише или је зид случајно пробран из листе која није случајно генерисана. Било који од ова два начина је релативно лаган за кодирање.

Зато што је ефекат овог алгоритма да произведе минимално разапињуће стабло из графа ком су све гране исте тежине, он тежи да произведе тачне шаблоне који су генерално лако решиви.

Случајни Примов алгоритам[уреди]

Анимација генерисања лавиринта димензије 30 са 20 коришћењем Примовог алгоритма.

Овај алгоритам је случајна верзија Примовог алгоритма.

  1. Почети са мрежом попуњеном зидовима.
  2. Одабрати ћелију, обележити је као део лавиринта. Додати зидове ћелије у листу зидова.
  3. Док постоје зидови у листи:
    1. Узми случајан зид из листе. Ако ћелија на супротној страни није у лавиринту још увек:
      1. Направити од зида пролаз и обележити ћелију на супротној страни као део лавиринта.
      2. Додај суседне зидове ћелије у листу зидова.
    2. Ако је ћелија на супротној страни већ била у лавиринту, уклонити зид из листе.

Као у алгоритму претраге у дубину, обично ће бити релативно лако пронаћи пут до почетне ћелије, али тешко пронаћи пут било где друго.

Приметите да једноставно покретање класичног Примовог алгоритма на граф са случајним вредностима тежина грана производи лавиринт стилски идентичан оном који креира Крускалов алгоритам, зато што су и један и други алгоритам засновани на минималном разапињућем стаблу. Уместо тога, овај алгоритам уводи стилску варијацију, јер ивице ближе почетној тачки имају нижу ефективну тежину.

Модификована верзија[уреди]

Иако класични Примов алгоритам чува листу ивица, за генерисање лавиринта можемо уместо тога да одржавамо листу суседних ћелија. Ако случајно изабрана ћелија има више ивица које је повезују са постојећим лавиринтом, треба пробрати неку од ових ивица на случајан начин. Овакав приступ ће да тежи да разграна лавиринт мало више него горња верзија заснована на ивицама.

Метода рекурзивне поделе[уреди]

Лавиринти могу бити креирани и рекурзивном поделом, алгоритмом који ради на следећи начин: Почети са простором за лавиринт без зидова. Ово ћемо назвати дворана. Поделити дворану случајно постављеним зидом (или више њих) где сваки зид садржи случајно позициониран пролаз у себи. Затим се рекурзивно понавља процес на поддворане док све дворане не постану најмање могуће. Овај метод резултује лавиринтом са дугим равним зидовима, што олакшава увид у делове лавиринта које треба избегавати.

На пример, у правоугаоном лавиринту, направи на случајним тачкама два зида који су нормални један на други. Ова два зида деле велику дворану у четири мање, одвојене са четири зида. Одабери три од ова четири зида на случајан начин и отвори рупу величине једне ћелије на случајној позицији у сваком од та три зида. Наставити на исти начин рекурзивно, док свака дворана има величину једне ћелије у било ком смеру.

Једноставни алгоритми[уреди]

3Д верзија Примовог алгоритма. Вертикални нивои су означени од 1 до 4 од дна према врху. Степенице на горе су означене са "/", степенице на доле са "\", а степенице које иду у оба смера са "x". Изворни код је укључен у опис слике.

Постоје и другачији алгоритми који захтевају само онолико меморије колико је потребно за чување једне линије 2Д лавиринта или једне равни 3Д лавиринта. Они спречавају петље тако што памте које ћелије у тренутној линији су повезане са ћелијама у претходним линијама, и никада не уклањају зидове између било које две ћелије које су већ повезане.

Већина алгоритама за генерисање лавирината захтева одржавање веза између ћелија, да би се осигурало да ће крајњи резултат бити решив. Валидни једноставно решиви лавиринти могу ипак бити генерисани фокусирањем на сваку ћелију независно. Лавиринт бинарног стабла је стандардни ортогонални лавиринт где свака ћелија увек има пролаз који води лево или горе, али никада обоје. Да би се креирао лавиринт бинарног стабла, за сваку ћелију бацимо новчић и одредимио да ли ће та ћелија имати пролаз који води лево или горе. Увек се узима исти правац за ћелије на границама, и крајњи резултат ће бити валидни једноставно решиви лавиринт који изгледа као бинарно стабло, код ког је горњи леви ћошак његов корен.

Пример кода за генерисање лавиринта написан у програмском језику Python[уреди]

import numpy
from numpy.random import random_integers as rand
import matplotlib.pyplot as pyplot

def maze(width=81, height=51, complexity=.75, density=.75):
    # Only odd shapes
    shape = ((height // 2) * 2 + 1, (width // 2) * 2 + 1)
    # Adjust complexity and density relative to maze size
    complexity = int(complexity * (5 * (shape[0] + shape[1])))
    density    = int(density * (shape[0] // 2 * shape[1] // 2))
    # Build actual maze
    Z = numpy.zeros(shape, dtype=bool)
    # Fill borders
    Z[0, :] = Z[-1, :] = 1
    Z[:, 0] = Z[:, -1] = 1
    # Make isles
    for i in range(density):
        x, y = rand(0, shape[1] // 2) * 2, rand(0, shape[0] // 2) * 2
        Z[y, x] = 1
        for j in range(complexity):
            neighbours = []
            if x > 1:             neighbours.append((y, x - 2))
            if x < shape[1] - 2:  neighbours.append((y, x + 2))
            if y > 1:             neighbours.append((y - 2, x))
            if y < shape[0] - 2:  neighbours.append((y + 2, x))
            if len(neighbours):
                y_,x_ = neighbours[rand(0, len(neighbours) - 1)]
                if Z[y_, x_] == 0:
                    Z[y_, x_] = 1
                    Z[y_ + (y - y_) // 2, x_ + (x - x_) // 2] = 1
                    x, y = x_, y_
    return Z

pyplot.figure(figsize=(10, 5))
pyplot.imshow(maze(80, 40), cmap=pyplot.cm.binary, interpolation='nearest')
pyplot.xticks([]), pyplot.yticks([])
pyplot.show()

Види још[уреди]

Референце[уреди]

Спољашње везе[уреди]