Tapaus 4

Tapaus 4

Pelimaailmassa yksi olennainen toiminto on maailmassa liikkuminen. Lähestytään asiaa seuraavasti: Kuvitellaan, että meillä on erilaisia suorakulmaisia labyrintteja (ks. kuvat jäljempänä) ja lisäksi robotti, jonka tulee liikkua annetun labyrintin läpi etsien kohdetta X. Tämä X voi olla labyrintin uloskäynti tai jokin paikka labyrintin sisällä, esimerkiksi jonkin esineen sijaintipaikka.

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

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

Robotin esittäminen

Ensimmäiseen osaongelmaan voidaan ajatella seuraava ratkaisu: Robotti esitetään yksinkertaisena oliona, joka tuntee oman sijaintiruutunsa sekä suunnan, johon se kulloinkin katsoo. Sijainti voidaan ajatella oliona, jolta robotti ei kuitenkaan voi suoraan saada mitään muita tietoja. Suunnan arvo on joko pohjoinen, ita, etela tai lansi.

Robotti osaa seuraavat asiat:

• kaannyVasemmalle() kääntää robottia 90 astetta vasemmalle.
• kaannyOikealle() kääntää robottia 90 astetta oikealle.
• etene() siirtää robottia yhden askeleen eteenpäin, esim. seuraavaan huoneeseen tai seuraavaan ruutuun. Jos eteneminen ei onnistu, metodi palauttaa arvon false, muutoin arvon true.
• voiEdeta() tutkii, voiko robotti edetä suoraan eteenpäin. Jos eteneminen ei onnistu, metodi palauttaa arvon false, muutoin arvon true.
• Lisäksi robottiin voidaan ajatella toteuttavaksi yksi tai useampi metodi, joiden avulla robotti voi muistaa, onko se ollut tietyssä ruudussa (ja mahdollisesti vielä muutakin, esimerkiksi sen, kuinka monta kertaa). Tässä käytetään hyväksi metodia annaSijainti(), joka palauttaa Ruutu-tyyppisen olion. Ruutu-oliolla ei kuitenkaan ole metodeita; ainoastaan tiedetään, että jokainen sijainti on erillinen olionsa.
• Robotti tunnistaa etsimänsä kohteen vasta astuessaan itse kyseiseen huoneeseen. Robotti ei siis tiedä, mistä päin labyrinttia kohdetta kannattaa aluksi etsiä, eikä näe kohdetta suoraan edes viereisestä huoneesta. Metodilla olenMaalissa() robotti voi tutkia, onko se perillä määränpäässään. Tällöin metodi palauttaa arvon true.

Maailman esittäminen

Esittäkää ratkaisu, miten maailma voidaan esittää olioiden avulla. Voitte olettaa, että kaikki maailman huoneet / ruudut ovat samanlaisia. Jokaisesta 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.

1. Yksinkertaisessa tapauksessa labyrintissa on vain mutkitteleva käytävä, mutta käytävät eivät haaraudu.		2. Toisessa tapauksessa labyrintin käytävät voivat haarautua kahteen tai useampaan haaraan, mutta labyrintissa ei ole silmukoita.
3. Kolmannessa tapauksessa labyrintissa käytävät voivat haarautua ja ne voivat muodostaa silmukoita. Etsittävä kohde voi olla silmukan sisällä ja lähtöpiste ulkopuolella.		4. Viimeisessä tapauksessa huone voi sisältää seinämiä ja se voi olla mielivaltaisen muotoinen.

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