Tik-76.501 IV-studio 1, syksy 2000, OLO

T-106.213 Ohjelmoinnin peruskurssi L1 / OLO

Tapaus 3

Robotti labyrintissä

Pelimaailmassa yksi olennainen elementti on maailmassa liikkuminen. Lähestytään asiaa seuraavasti: Kuvitellaan, että meillä on erilaisia suorakulmaisia labyrinttejä (ks. kuvia alla) ja lisäksi robotti, jonka tulee liikkua annetun labyrintin läpi etsien kohdetta X. X voi olla labyrintin uloskäynti, jokin paikka sen sisällä tai vaikkapa jonkin esineen sijaintipaikka.

Tehtävään liittyy kolme erillistä ongelmaa.

Miten robotti esitetään ko. maailmassa ja mitä toimintoja se osaa?
Miten maailma voidaan esittää olioiden avulla?
Minkälaisia algoritmeja tarvitaan ohjaamaan robottia labyrintissä.

Robotin esittäminen

Ensimmäiseen osaongelmaan voidaan ajatella seuraava ratkaisu: Robotti esitetään yksinkertaisena oliona, joka osaa seuraavat asiat:

Turn_right() kääntää robottia 90 astetta oikealle.
Turn_left() kääntää robottia 90 astetta vasemmalle.
Forward() siirtää robottia yhden askeleen eteenpäin, esim. seuraavaan huoneeseen tai seuraavaan ruutuun. Jos eteneminen ei onnistu, metodi palauttaa arvon False, muutoin arvon True.
Test_forward() tutkii, voiko robotti edetä suoraan eteenpäin. Jos eteneminen ei onnistu, metodi palauttaa arvon False, muutoin arvon True.
Lisäksi robottiin voidaan toteuttaa yksi tai useampi metodi, joiden avulla robotti voi merkitä huoneeseen / ruutuun tiedon tai tietoja, että se on ollut siellä. Vastaavasti se pystyy lukemaan näitä tietoja.

Maailman esittäminen

Esittäkää ratkaisu, miten labyrinttimaailma voidaan esittää olioiden avulla. Voitte olettaa, että kaikki maailman huoneet / ruudut ovat samanlaisia. Kustakin paikasta voidaan periaatteessa edetä johonkin neljään pääilmansuuntaan. Jotkut etenemissuunnat voivat kuitenkin olla tukossa.

Etenemisalgoritmit

Ongelmana on kehittää algoritmeja, joiden avulla robotti voidaan ohjelmoida liikkumaan labyrintissä. Algoritmi tutkii maailmaa robotin avulla ja antaa sille toimintaohjeita tavoitteena edetä lähtöpisteestä haluttuun lopetuspisteeseen. Labyrintteja on erilaisia. Esittäkää kullekin tapaukselle ratkaisualgoritmi.

Yksinkertaisessa tapauksessa (kuva 1) labyrintissä on vain mutkitteleva käytävä, mutta käytävät eivät haaraudu.
Toisessa tapauksessa (kuva 2) labyrintin käytävät voivat haarautua kahteen tai useampaan haaraan, mutta labyrintissä ei ole silmukoita.
Kolmannessa tapauksessa (kuva 3) labyrintissä käytävät voivat haarautua ja ne voivat muodostaa silmukoita. Etsittävä kohde voi olla silmukan sisällä ja lähtöpiste ulkopuolella.
Neljännessä tapauksessa (kuva 4) robotti liikkuu pimeässä suorakaiteen muotoisessa salissa, jossa se voi ottaa monta askelta samassa tilassa eteenpäin. Robotti näkee vain vierusruudut.
Viimeisessä tapauksessa (kuva 5) pimeä huone voi sisältää seinämiä ja se voi olla mielivaltaisen muotoinen.

Voidaanko samaa algoritmia käyttää useamman tapauksen ratkaisemiseen?

Ratkaisut esitetään Java-metodeina tai ns. pseudokoodina, jossa käytetään Java-kielen kontrollirakenteita ja muuttujia, mutta jossa ei tarvitse määritellä muuttujia tarkasti ja noudattaa muutenkaan tiukasti Javan kielioppisääntöjä. Ratkaisualgoritmeja ei tarvitse kääntää Java-kääntäjällä ja testata koneellisesti.