Sokkelo
Sokkelo on reitti, polku tai kuvio jossa läpikulkijan on etsittävä ja valittava reitti alkupisteestä loppupisteeseen. Tämä eroaa labyrintistä, joka on yksipolkuinen reitti eikä siinä ole valinnan mahdollisuutta. Labyrintti tai sokkelo voi olla pellolle istutettu useita kilometrejä halkaisijaltaan oleva, ihmisenkorkuinen kasvustosokkelo tai sormukseen kaiverrettu pikkuruinen polku tai mitä tahansa tältä väliltä. Se voi olla tehty kaivertamalla, kasvattamalla, kiveämällä tai maalaamalla. Suomen rannikolla esiintyy Jatulintarhoja jotka ovat klassisen 7-kehäisen labyrintin kopioita tai muunnelmia. Ne ovat merenkulkijoiden ja/tai kalastajien pääsääntöisesti kivistä rakentamia.
Sokkelon kulkureitit ja seinät ovat kiinteitä. Sokkelotyyppinen älypeli, jossa annetut seinät ja käytävät voivat muuttua pelin aikana, sisältyy älypelien pääkategoriaan.
Yksi sokkelotyyppi koostuu joukoista ovilla yhdistettyjä huoneita (siten uloskäynti on juuri toinen huone tässä määritelmässä). Pelaajat saapuvat yhdestä pisteestä ja poistuvat toisesta tai idea on saavuttaa tietty piste sokkelossa.
Sokkeloita voidaan tulostaa tai piirtää paperille kynällä tai sormella seurattavaksi. On olemassa useita erilaisia menetelmiä sokkelon luomiseen joko käsin tai tietokoneella.
Matemaatikko Leonhard Euler oli ensimmäisiä, jotka ratkaisivat sokkeloita matemaattisesti. Näin hän löysi topologian tieteenä.
Seuraavat algoritmit on suunniteltu käytettäväksi sokkelon sisällä ilman sokkelon matkustajan aiempaa tietämystä sokkelon rakenteesta. On olemassa toisia algoritmeja sokkeloille paperilla, jossa ratkaisijalla on käytössä sokkelon yleiskuva.
Seinän seuraaminen ("wall follower") on tunnetuin sääntö sokkeloiden läpikäymisessä. Se tunnetaan joko "vasemman käden sääntönä" tai "oikean käden sääntönä". Jos sokkelo on yksinkertaisesti yhdistetty (kaikki seinät ovat kiinni toisissaan tai sokkelon ulkorajaan), pitämällä yhden kätensä kiinni yhdessä seinässä seuraaja ei eksy ulos sokkelosta paitsi uloskäyntipaikassa, jos sellainen on. Muussa tapauksessa hän palaa sisääntulokohtaan. Jos sokkelo ei ole yksinkertaisesti yhdistetty, tällä menetelmällä ei voi läpikäydä sokkeloa.
Seinien seuraaja -menetelmää voidaan soveltaa kolmi- tai useampiulotteisiin sokkeloihin, jos niiden käytävät voidaan projisoida kaksiulotteisiksi deterministisessä mielessä. Esimerkiksi kolmiulotteisessa ylöspäin etenevien käytävien voidaan ajatella johtavan luoteeseen ja alaspäin menevien käytävien kaakkoon. Tällöin voidaan käyttää standardia seinien seuraaja -menetelmää.
Erilliset (eivät yksinkertaisesti yhdistettyjä) sokkelot voidaan ratkaista yhä seinien avulla seuraavalla menetelmällä, jos sekä sisääntulokohta että ulostulokohta ovat sokkelon ulkoseinillä. Jos sokkelon ratkaisu alkaa sokkelon keskeltä (sisältä), alkupisteen tulee olla erillään loppupisteestä, sillä muuten ratkaisun eteneminen kiertää jatkuvaa kehää. Pledge-menetelmä (nimetty Exeterin Jon Pledgen mukaan) voi ratkaista tämän ongelman.
Esteiden kiertämiseen suunniteltu menetelmä tarvitsee mielivaltaisesti valitun suunnan. Kun etsintä törmää esteeseen, yksi käsi (esimerkiksi oikea) asetetaan esteeseen (näyttämään suuntaa) ja asetetut kädet merkitään muistiin. Kun ratkaisun haku edistyessään etenee alkuperäiseen suuntaan uudelleen ja kun tehtyjen käännösten summa on 0, ratkaisija jättää esteen ja jatkaa etenemistä sen alkuperäiseen suuntaan.
Tällä menetelmällä kompassin kanssa löytää ulos sokkelosta mistä sisäpisteestä tahansa missä tahansa säännöllisessä ("finite") ja kaksiulotteisessa sokkelossa riippumatta etsinnän alkupisteestä. Kuitenkaan tällä menetelmällä ei voida ratkaista tietä alkupisteestä ulostuloon, jos loppupiste on sokkelon sisällä.
Tämä on triviaali menetelmä, joka voidaan toteuttaa erittäin tyhmällä robotilla tai hiirellä, mutta jolla ei ole takeita toimivuudesta. Menetelmässä edetään suoraan eteenpäin, kunnes saavutetaan este. Sen jälkeen tehdään satunnainen päätös, mihin suuntaan edetään. Tämä menetelmä epäonnistuu tietenkin, jos poistuminen (loppupiste) on seinän keskivaiheilla.
Tremauxin tehokkaassa menetelmässä sokkelon lattiaan on piirrettävä etenemisviiva kuljetun polun merkitsemiseksi. Menetelmä on taattu ratkaisemaan kaikki hyvinmääriteltyjen käytävien sokkelot. Saavuttaessa merkitsemättömään risteykseen otetaan jokin suunta. Jos taas etsintä on jo käynyt aiemmin tässä risteyksessä, etsintä voi palata takaisin tuloreittiä. Jos edetään uudelleen käytävää, joka on jo tutkittu, piirretään toinen viiva ja seuraavassa risteyksessä edetään tutkimattomalle käytävälle, mikäli mahdollista. Muussa tapauksessa edetään jo tutkittua käytävää. Etsintä ei koskaan käy yhtä käytävää useammin kuin kaksi kertaa. Jos sokkelossa ei ole poistumiskohtaa, menetelmä tuo etsinnän takaisin alkupisteeseen.
On olemassa monia tapoja automatisoida sokkelon luominen.
Tämä on yksinkertaisin tapa luoda sokkelo tietokonetta käyttäen. Kuvittele sokkeloon käytettävissä oleva tila laajaksi ruudukoksi (kuten laaja shakkilauta), jonka kussakin ruudussa on alkutilanteessa 4 seinää. Satunnaisesta ruudusta alkaen tietokone valitsee satunnaisen naapurisolun, jossa ei ole vielä vierailtu. Tietokone poistaa seinän näiden kahden ruudun väliltä ja lisää uuden ruudun pinoon (tämä on analogista viivan piirtämiselle lattiaan). Tietokone jatkaa tätä prosessia. Ruutu, jolla ei ole läpikäymättömiä naapurisoluja, on umpikuja. Siihen saavuttuaan luonti palaa takaisin niin kauan, kunnes pinosta löytyy ruutu, jolla on läpikäymättömiä naapuriruutuja (luoden uuden risteyksen). Tämä prosessi jatkuu, kunnes kaikki solut on käyty läpi. Tämä menetelmä johtaa läpikäynnin päättymään lopulta alkusoluun. Tämä merkitsee sitä, että koko sokkelon tila on käyty läpi.
Tällaisenaan menetelmä on erittäin yksinkertainen eikä tuota kovin monimutkaisia sokkeloita. Määritellymmät menetelmän säännöt voivat auttaa vaikeammin ratkaistavia sokkeloita.Sokkeloita käytetään usein tieteellisessä tutkimuksessa tilallista navigointia ja oppimista tutkittaessa. Tyypillisiä koe-eläimiä ovat rotat tai hiiret. Esimerkkejä tutkimuskohteista ovat Barnesin sokkelo, Morrisin vesisokkelo ja kulmasokkelo.Sokkelo, jonka läpikäynti muodostaa kuvion.
Sokkelopeli, jossa läpikäynti muodostaa umpikujia.