Laberints (I)
En aquest capítol crearem un petit nino a qui donarem un conjunt de comportaments que simulin una certa forma d'"intel·ligència". Això ens servirà per treballar el conjunt de les regles de la lògica.
Annex dibuixa una quadrícula.
Un cop tinguem una quadrícula que, entre el centre de cada quadrat tingui una distància de 20 passos, dibuixarem el ninot de la forma següent
En exercicis anteriors hem aprés a moure el ninot amb les fletxes del teclat. Anem a escriure unes línies de codi perquè, en pressionar la barra espaiadora, el ninot avanci 20 passos.
Si pressionem la tecla espai, el ninot es mourà 20 passos cada vegada fins arribar al límit de la pantalla. Anem a donar-li instruccions perquè pugui detectar obstacles i hi pugui respondre d´alguna manera. Per això, dibuixem un punt vermell davant del ninot, aproximadament en el centre del quadrat següent amb la direcció d´avanç. Aquest punt vermell ens servirà perquè el ninot detecti informació del seu entorn i la faci servir per decidir el que ha de fer; escrivim ara el codi necessari
El primer que veiem és que fem una pregunta; 'el color vermell és a sobre del color blanc?', a això li diem condició. Com veurem més endavant, aquesta condició podria ser més complexa, desprès aprendrem a formular aquestes condicions complexes. Veiem que a la pregunta només podem contestar ¨verdader¨o ¨fals¨. Si o No.
Aquest és el tipus de preguntes a què responen els ordinadors, si la condició es compleix contestarem amb una acció 'moure 20 passos', sinó, 'girarem 90' en el sentit de les agulles del rellotge. Posem el nostre ninot en el circuit de proves, i modifiquem una mica el codi de la següent forma.
El codi és bàsicament el mateix, ara iniciem el programa pressionant la bandera i a continuació situem el ninot en una casella concreta del nostre circuït de proves. Afegim un bucle sense fi perquè les instruccions principals es repeteixin de forma indefinida, també col·loquem una instrucció d' 'esperar' perquè el ninot no corri massa i es pugui observar la seva evolució. Aquesta última instrucció no és necessària i, si volem, podem eliminar-la o fer diferents proves canviant l´interval de temps.
Veiem que quan pressionem la bandera, el ninot es posa en moviment, descriu diferents trajectòries i acaba movent-se en cercle (en aquest cas en quadrat) de forma indefinida. Podem dir que el ninot ja té comportament propi. Seríem capaços de crear un codi que li donés un comportament més complexe, capaç de resoldre laberints senzills i alguns de no tan senzills?. Veiem el que ens fa falta per afrontar el problema. Primer necessitem disposar de més informació de la que tenim. Coneixent només que la següent casella estigui lliure no en tindrem prou per crear comportaments més elaborats, afegim dos sensors més al nostre ninot, un a la dreta i un altre a l´esquerra de la seva posició
Seguint el mateix patró que el dibuix anterior afegim un punt blau a l´esquerra i un de verd a la dreta del nostre ninot, recordem-nos de mantenir el centre de gir a la seva posició. La informació que ens proporcionaran aquests sensors serà del mateix tipus que l´anterior, és a dir, si les caselles sobre les que estan, són lliures. Fixem-nos que la informació que recollim és local i que no l´emmagatzemarem, és a dir, que la llegim, la utilitzem i ens n'oblidem. De fet, l´únic que "recorda" el ninot és on té els sensors (vermell enfront, blau a l´esquerra, verd a la dreta).
Les condicions que utilitzarem són les que es mostren en la figura següent
A les tres preguntes només es pot respondre "verdader" o "fals", Si o No, Com que tenim tres preguntes i cadascuna té dues respostes, tindrem vuit possibles resultats de les lectures dels sensors. Dit d'una altra forma, tindrem una informació de tres bits (bit = unitat bàsica d'informació). Veiem gràficament els vuit possibles resultats:
Per començar només utilitzem dos sensors, el vermell i el blau. Veiem la taula de decisió reduïda a aquest cas. ( Només utilitzem dos bits d'informació)
Què podem fer amb aquesta informació? Serà suficient per resoldre alguns dels problemes plantejats?
Si estem en un laberint que té una entrada i una sortida i les dues són a les vores d'aquest laberint, és fàcil veure que una vegada situats a l´entrada, si seguim sempre la paret situada a la nostra esquerra (o en el cas simètric, la situada a la nostra dreta) tard o d´hora trobarem la sortida, si aquesta existeix, o bé, tornarem a l´entrada. Per tant, per travessar el laberint serà suficient mantenir-nos sempre en contacte amb la paret triada.
Veiem com apliquem aquest coneixement a l´escriptura del codi corresponent. Observem les figures següents que mostren la situació en la que es pot trobar el ninot.
En la primera imatge observem el ninot amb la paret a la seva esquerra i un espai lliure al davant, per tant, el que ha de fer és avançar. Això en el llenguatge dels sensors és vermell SI, blau NO i correspon a l'estat 2 de la taula de decisió reduïda. La segona imatge correspon a vermell SI, blau SI, que correspon a l'estat 1 de la taula. Veiem com utilitzem la lògica per a expressar amb codis aquests fets. Volem que el ninot distingeixi entre els quatre estats possibles i, en cada cas realitzi l´acció corresponent.
En la figura veiem escrites tres condicions; si observem la imatge del ninot que té la paret enganxada al seu costat esquerre hem de respondre SI a la primera condició 'vermell sobre blanc'. Fixem-nos en la segona condició, és una mica diferent; a la pregunta ' blau sobre blanc' referida a la mateixa imatge d´abans hem de respondre NO, però aquesta condició té un no al davant, per tant si neguem el No tindrem un Si, recordem: dos No fan un Si. Anem ara a la tercera condició que hem escrit, es composa de les dues anteriors unides per una I, això significa que la condició conjunta serà certa si, i només, si ho són les dues. En el nostre cas la resposta a la condició és Si, ja que a la primera 'vermell sobre blanc' responem Si i a la segona,'No blau sobre blanc' també responem Si.
Si es compleix la condició el ninot haurà d'avançar 20 passos. Canviem ara el codi perquè reflecteixi el que hem descobert.
Ja hem dit al ninot el que ha de fer en el cas 2 de la taula de decisió, veiem ara el que ha de fer en els altres tres casos. Comencem pel primer que és el representat per la imatge segona del ninot; quan els dos sensors estan sobre el blanc, el que ha de fer per seguir la paret es girar 90 graus en el sentit de les agulles del rellotge i moure´s 20 passos. Quan hagi realitzat aquesta acció ens trobarem en l´estat 2. Tornem al codi i escrivim el que calgui perquè el ninot faci el que li hem dit. Si ens hi fixem, veurem que en l´estructura de control ' Si - Si no', a l´apartat del 'Si' hem donat instruccions pel cas 2 i a l´apartat ' Si no' ens queden els casos 1, 3 i 4. El primer que farem es distingir entre ells i en consultar la taula de decisió veurem que dels 3 casos que ens queden, els casos 1 i 3 compleixen la condició 'blau sobre blanc' i si mirem la imatge veiem que en els dos casos el ninot ha de girar 90 graus en sentit contrari a les agulles del rellotge i desprès moure´s 20 passos. El codi quedarà així.
Ara en l´apartat 'Si no' de la segona estructura només ens quedarà el cas 4. Si observem, ens adonarem que el que ha de fer el ninot en aquest cas és girar 90 graus en el sentit de les agulles del rellotge. Veiem el codi complert.
Provem el codi; volem que el ninot recorri el laberint i trobi la sortida, amb l´única condició de tenir una paret a la seva esquerra en iniciar el recorregut. Si el ninot va molt de pressa podem afegir una instrucció 'esperar 0,1 segons' en l´interior del bucle 'repetir sempre' com a última instrucció. Fent servir només 2 bits d´informació i poques línies de codi hem aconseguit donar-li al ninot un comportament capaç de resoldre un problema en aparença no massa simple.
Nota: És important controlar la posició inicial del ninot, hem d'assegurar-nos que el ninot toqui una paret, modificar la instrucció 'anar a x: y:' perquè això passi. Ens hem d´assegurar que té la paret a l´esquerra del sentit en que es mourà. Si no és així, arrosseguem a la zona de programa una instrucció 'girar' i col·loquem-li valor 90 graus. Aquesta instrucció ha de quedar solta, sense estar lligada a cap altra. Si li fem doble clic a sobre, el ninot anirà girant, fins que el col·loquem en la posició desitjada.
Compliquem una mica el problema, suprimim la condició inicial i fem que el ninot comenci des de qualsevol casella. Quina estratègia seguirem?. Podríem fer que el ninot primer trobés una paret a la seva esquerra i un cop trobada segueixi el comportament anterior?. Anem a escriure el codi perquè ho faci i després l´enllaçarem en l´escrit anteriorment. El primer que hem d'observar és, si a l´inici compleix una de les següents condicions 'No vermell sobre blanc? o 'No blau sobre blanc'. Si es compleix la primera condició estem en els casos 3 i 4 de la taula de decisió i, per tant podem aplicar el codi escrit anteriorment. Si es compleix la segona condició estem en els casos 2 i 4 de la taula i per tant també apliquem el codi anterior. Veiem les condicions i escrivim el codi corresponent.
El primer que farem serà iniciar el programa pel bloc que busca la paret, i quan la trobi enllaçarem amb el següent bloc que és el que segueix la paret esquerra. Vegem com queda el codi.
Amb aquest codi aconseguim que el ninot solventi laberints senzills, és a dir, que tinguin una paret contínua, o laberints amb una entrada i una sortida, que no continguin illes. En la següent pràctica afegirem comportaments al ninot que li permeti solucionar laberints més complexos i reorganitzarem el codi perquè sigui més llegible.