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

Насумични алгоритам миша, алгоритам праћења зида, алгоритам Џона Плеџа (ен. Jon Pledge) и Тремауксов (фр. Charles Pierre Trémaux) алгоритам су дизајнирани тако да се користе када се особа налази унутар самог лавиринта без икаквог познавања структуре и изгледа самог лавиринта, док су алгоритам испуњавања ћорсокака и алгоритам најкраћег пута дизајнирани тако да се користи када особа или рачунарски програм унапред познаје структуру и изглед читавог лавиринта.

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

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

Насумични алгоритам миша

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

Алгоритам праћења зида left|frame|Пролазак коришћењем правила десне руке Алгоритам праћења зида представља један од најпознатијих алгоритама за проналажење излаза из лавиринта, а такође је познат и под називима „правило леве руке“ и „правило десне руке“.

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

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

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

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

На пример, уколико у тродимензионалном алгоритму путање „нагоре“ сматрамо путањама ка северо-западу, а путање „надоле“ сматрамо путањама ка југо-истоку, тада можемо употребити стандардна правила алгоритма праћења зида. Међутим, за разлику од дводимензионалног простора, овде је потребно у сваком моменту знати и тренутну оријентацију, да би се знало који смер је први налево или надесно.

Алгоритам Џона Плеџа

Неповезани алгоритми се ипак на одређене начине могу решити коришћењем алгоритма праћења зида, уколико се улаз и излази из лавиринта налазе на спољашњим зидовима лавиринта. Међутим, уколико се улаз налази у унутрашњости лавиринта, може се наћи на зиду који није спојен са зидом на коме се налази излаз, па би се коришћењем алгоритма праћења зидова особа вртела у круг и враћала на почетак не проналазећи излаз. Алгоритам Џона Плеџа може да реши овај проблем.

Плеџов алгоритам, дизајниран да заобиђе препреке, захтева кретање у унапред одређеном смеру.

Када се наиђе на препреку, једна рука (нпр. десна) наставља да прати препреку, а такође прати се и број окрета на леву и десну страну коришћењем бројача окрета. Окретање на десну страну повећава вредност бројача, а окрет на леву страну смањује његову тренутну вредност. Када се особа поново окрене ка оригиналном унапред одређеном смеру, тада је бројач окрета поново враћен на вредност 0 и препрека је успешно савладана, особа наставља са кретањем у почетном оригиналном смеру ка свом циљу па ако се поново наиђе на препреку претходни поступак се понавља. Рука више не прати зид само када је бројач окрета поново постављен на 0. Овакав приступ омогућава алгоритму да избегне замке које су на пример облика великог латиничног слова Г - ("G").

У суштини алгоритам је врло једноставан и састоји се од провере неколико правила која се проверавају током проласка кроз лавиринт:

(алгоритам заснован на правилу десне руке)

1. Особа се креће унапред одређеним смером. 2. Када се наиђе на препреку први пут, особа се окреће на леву страну. Бројач окрета се тада умањује за 1.

3. Врши се провера постојања препрека. Особа проверава да ли постоји препрека испред, десно или лево.

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

Претходни подкораци корака 3 се наведеним редоследом проверавају све док се бројач окрета поново не врати на вредност 0 и тада сматрамо да је препрека успешно савладана.

4. Особа наставља да се креће почетним смером, све док се поново не наиђе на препреку или се стигне до излаза.

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

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

Јава код алгоритма Џона Плеџа заснованог на правилу леве руке за покретање робота

1 // код који се односи на кретање особе унапред 2 public boolean isActive() { 3 return true; 4 } 5 public Velocities act() { 6 double rotationalVelocity = 0.0; 7 return new Velocities(TRANSLATIONAL_VELOCITY, rotationalVelocity); 8 } 9 10 11 // код који се односи на скретање у десну страну 12 public boolean isActive() { 13 if (turningRightCount > 0) { 14 return true; 15 } 16 RangeSensorBelt bumpers = getSensors().getBumpers(); 17 // провера постојања предње препреке. 18 if (bumpers.hasHit(0)) { 19 backingUpCount = 10; 20 turningRightCount = getRotationCount(); 21 22 return true; 23 } else { 24 return false; 25 } 26 } 27 28 public Velocities act() { 29 if (backingUpCount > 0) { 30 31 backingUpCount--; 32 33 return new Velocities(-TRANSLATIONAL_VELOCITY, 0.0); 34 } else { 35 turningRightCount--; 36 37 return new Velocities(0.0, -Math.PI / 2); 38 } 39 } 40 41 42 public boolean isActive() { 43 if (postGoingForwardCount > 0) { 44 return true; 45 } 46 47 RangeSensorBelt sonars = getSensors().getSonars(); 48 // провера левог сензора. 49 if (sonars.getMeasurement(1) > 1.0) { 50 // могуће је скренути лево. 51 preGoingForwardCount = 20; 52 postGoingForwardCount = 40; 53 turnLeftCount = getRotationCount(); 54 55 return true; 56 } else { 57 return false; 58 } 59 } 60 61 public Velocities act() { 62 if (preGoingForwardCount > 0) { 63 preGoingForwardCount--; 64 65 return new Velocities(TRANSLATIONAL_VELOCITY, 0.0); 66 } else if (turnLeftCount > 0) { 67 turnLeftCount--; 68 69 return new Velocities(0.0, Math.PI / 2); 70 } else { 71 postGoingForwardCount--; 72 73 return new Velocities(TRANSLATIONAL_VELOCITY, 0.0); 74 } 75 } 76 77 78 public boolean isActive() { 79 RangeSensorBelt sonars = getSensors().getSonars(); 80 81 // да ли смо стигли ван лавиринта? 82 double clearDistance = 1.2; 83 return sonars.getMeasurement(0) > clearDistance 84 && sonars.getMeasurement(1) > clearDistance 85 && sonars.getMeasurement(3) > clearDistance 86 && sonars.getMeasurement(2) > clearDistance; 87 } 88 89 public Velocities act() { 90 // заустављање 91 return new Velocities(0.0, 0.0); 92 } Тремауксов алгоритам

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

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

Приметимо да је ово једна од варијанти алгоритма претраге у дубину.

Јава код Тремауксовог алгоритма за покретање робота 1 package maze.ai; 2 3 import java.awt.Dimension; 4 import java.util.ArrayList; 5 import java.util.List; 6 7 import maze.model.Direction; 8 import maze.model.MazeCell; 9 10 /** 11 * Maze solving algorithm that provides a right wall follower with a memory so 12 * it prefers unexplored cells. 13 */ 14 public class Tremaux extends RobotBase 15 { 16 private Direction[][] ballOfString; 17 private List<RobotStep> moveQueue = new ArrayList<RobotStep>(); 18 private boolean turbo = false; 19 20 /** 21 * This returns the name of the mathematician who came up with this process 22 */ 23 @Override 24 public String toString() 25 { 26 return "Tremaux"; 27 } 28 29 /** 30 * This function should be called by the controller any time a new run is to 31 * commence 32 */ 33 @Override 34 public void initialize() 35 { 36 super.initialize(); 37 38 Dimension size = robotLocation.getMazeSize(); 39 ballOfString = new Direction[(int) size.getWidth()][(int) size.getHeight()]; 40 41 for (int i = 0; i < size.getWidth(); i++) 42 { 43 for (int j = 0; j < size.getHeight(); j++) 44 { 45 ballOfString[i][j] = null; 46 } 47 } 48 ballOfString[size.height - 1] = Direction.North; 49 this.moveQueue.clear(); 50 } 51 52 /** 53 * This returns the state of the turbo flag. Turbo should be true when 54 * traversing previously explored territories. 55 */ 56 public boolean isInTurboMode() 57 { 58 return turbo; 59 } 60 61 /** 62 * This returns the next step for the robot to take. It should be called by 63 * the controller. 64 */ 65 public RobotStep nextStep() 66 { 67 RobotStep next; 68 if (getDirection(robotLocation.getCurrentLocation()) == null) 69 { 70 setDirection(); 71 } 72 if (moveQueue.isEmpty() == true) 73 {