Sokkelogeneraattori ja peli

Näin käytät sokkelogeneraattoria

1. Aseta Leveys (sarakkeet) ja Korkeus (rivit), kumpikin 4–60 ruutua, ja valitse Algoritmi. Napsauta Uusi sokkelo.
2. Sijaintisi on vihreässä sisäänkäynnissä vasemmassa yläkulmassa oleva piste. Pääse punaiseen uloskäyntiin oikeassa alakulmassa.
3. Liiku nuolinäppäimillä tai WASD-näppäimillä. Pidä Shift pohjassa nuolen kanssa, niin juokset käytävää pitkin seuraavaan risteykseen. Puhelimella tai tabletilla pyyhkäise sokkelon päällä juostaksesi siihen suuntaan tai napauta sen alla olevia nuolipainikkeita yksittäisiä askelia varten.
4. Ajastin käynnistyy ensimmäisestä siirrostasi ja pysähtyy uloskäynnillä. Jälkesi piirtyy taaksesi, ja takaisin kulkeminen pyyhkii sen pois, joten se näyttää aina reitin, jolla olet.
5. Jumissa? Näytä ratkaisu piirtää lyhimmän reitin nykyisestä paikastasi uloskäyntiin. Takaisin alkuun vie sinut takaisin sisäänkäynnille ja nollaa ajastimen.
6. Jos haluat pelata paperilla, napsauta Tulosta tai Lataa PDF. Ruksaa ensin Lisää ratkaisusivu, jos haluat vastauksen toiselle sivulle.

Jaa sokkelo koodin avulla

Jokaisella sokkelolla on Sokkelokoodi, esimerkiksi b20x15-k3j9x2: algoritmin kirjain (b, p tai k), leveys × korkeus ja satunnainen siemenluku. Sama koodi rakentaa aina täsmälleen saman sokkelon millä tahansa laitteella, joten voit haastaa ystävän ylittämään aikasi samalla asettelulla. Kirjoita tai liitä koodi ja napsauta Lataa koodi, tai jaa verkko-osoite Kopioi linkki -painikkeella, jolloin se avaa kyseisen sokkelon suoraan.

Kolme sokkelon luontialgoritmia

Kaikki kolme rakentavat täydellisen sokkelon: jokaiseen ruutuun pääsee, ja minkä tahansa kahden ruudun välillä on täsmälleen yksi reitti, joten silmukoita tai suljettuja alueita ei ole. Ne eroavat sokkelon ilmeessä:

• Rekursiivinen peruutus (pitkät käytävät) kulkee satunnaisesti ruudusta toiseen kaataen seiniä ja peruuttaa umpikujaan päästyään. Tuloksena on pitkiä mutkittelevia käytäviä ja vähän haaroja: ratkaisu on yleensä pitkä ja vie ruudukon poikki lähes kokonaan.
• Prim (paljon lyhyitä umpikujia) kasvattaa sokkeloa satunnaisesta ruudusta ulospäin lisäten joka kerta satunnaisen rajaruudun. Saat paljon lyhyitä sivuhaaroja, jotka tekevät sokkelosta vilkkaan näköisen, mutta pääreitti on helpompi nähdä.
• Kruskal (tasainen, haarautuva) poistaa satunnaisesti valittuja seiniä ruutujen välillä, jotka eivät vielä ole yhteydessä toisiinsa (yhteyksiä seurataan union-find-rakenteella). Tulos haarautuu tasaisesti kaikkialla eikä siinä ole näkyvää lähtöpistettä.

Sokkelon yläpuolella oleva rivi kertoo koon, lyhimmän reitin pituuden ja umpikujien määrän, joten voit vertailla algoritmeja yhdellä silmäyksellä.

Miten ratkaisu löydetään

Ratkaisu käyttää leveyssuuntaista hakua (BFS): ruudustasi lähtien se käy läpi kaikki yhden askeleen päässä olevat naapurit, sitten kahden askeleen päässä olevat ja niin edelleen, kunnes se saavuttaa uloskäynnin. Koska jokainen askel maksaa saman verran, BFS löytää aina lyhimmän reitin. Täydellisessä sokkelossa se on myös ainoa reitti ilman peruuttamista. Kun ratkaisu on näytetty pelin aikana, loppuaikaasi ei tallenneta parhaaksi ajaksi.

Tulostusvinkkejä

Tulostetut ja PDF-versiot piirtävät puhtaat mustat seinät valkoiselle pohjalle, ja sokkelokoodi on otsikossa, jotta löydät saman sokkelon uudelleen. Noin 15 × 15 -koot sopivat pienille lapsille, ja 30 × 30 ja sitä suuremmat ovat kunnon pulma aikuisille. Hyvin suurissa sokkeloissa (50 × 60) käytävät ovat A4-sivulla ohuita, joten tulosta ne täyteen sivukokoon.

Tämä työkalu toimii selaimessasi. Mitään kirjoittamaasi ei lähetetä palvelimelle, ja parhaat aikasi tallennetaan vain tähän selaimeen.