Ordinador domèstic. Laberint

1986/10/01 Lizaso, Pili - Informatika SailaElhuyar Fundazioa Iturria: Elhuyar aldizkaria

• Programazioa

En aquesta ocasió, realitzarem un programa que ajudarà a la xagua a buscar la sortida al laberint. Aquest programa està escrit per a Tele vídeo, però també es pot escriure per a spectrum.

Assenyalarem el laberint mitjançant una matriu. Els obstacles s'indicaran amb un "1" i les cel·les lliures amb un "Ø".

L'entrada al laberint (1,1) serà l'inert i la sortida (m, n) serà la dimensió de l'inert, m i n. En aquest cas utilitzarem m=n=8.

El ratolí es definirà amb la seva posició, és a dir, amb les coordenades del punt o pila que es troba en el moment. Pren nota del que sempre estarà en una pila Ø. A més, cal definir les possibles directrius que pot tenir el mocador. Les direccions possibles són vuit en totes les cel·les, excepte en les de vora. Així que perquè el comportament del xagua sigui igualitari en tots els llocs, envoltarem el laberint d'obstacles. Veure com:

El canvi de coordenades que suposa cada direcció es presenta en la taula NORANTZA (8,2):

Modificació de la coordenada de columnes per a seguir el rumb I NORANTZA (I,1)

Modificació de la coordenada de línia per a seguir la direcció NORANTZA (I,2) I

Xagua partirà de la pila d'entrada i passarà d'un punt a un altre fugint d'obstacles. Quan no es pugui seguir endavant, haurà de retrocedir. Per tant, el camí recorregut per la sendera ens condueix per la taula BIDEA (64,3).

En cadascun dels camps d'aquesta taula es guardarà:

Coordenades d'una pila que compon el camí
• Sentit de pas d'aquesta pila a una altra

Quan Xagua es troba en una pila d'aigua, la sobrietat haurà d'analitzar-la a la recerca d'un "bon punt". Perquè una pila sigui un "bon punt" ha de complir els següents requisits:

Absència d'obstacles (marcat amb Øen la taula LAB).
• Que la xagua no passi per aquesta pila (que la MARCA estigui marcada amb Øen la taula).

Si troba entre els vuit punts de la zona un punt que compleixi aquestes condicions, es guardaran les coordenades de la pila actual i la direcció que ha de seguir per a passar al nou punt i es passarà al nou punt. Aquí seguirà el mateix procés.

Per contra, si després d'analitzar els vuit punts de la zona no es veu la possibilitat de passar a cap punt, haurà de retrocedir, passant a la primera pila (l'última pila introduïda en la taula BIDEA) i des d'aquí intentar-lo en un altre sentit. El procés és repetitiu. Es mantindrà fins a arribar a una d'aquestes dues situacions:

Localització de la sortida
• No retrocedir

En el primer cas, el camí apareixerà marcat en vermell. En el segon, el missatge serà:

"No hi ha camí!!"

Com hauràs pogut comprovar, hem esmentat també la taula anomenada MARCA. En la següent taula anirem marcant amb un "1" per a saber de quin quart ha passat la mocha a mesura que la moguem. Si no es fa això, es pot ficar en un estovament interminable.

Un exemple t'ajudarà a comprendre millor: Suposem que el modest (3,7) està en la inerta, que el primer "bon punt" que comença a estudiar i trobar les cel·les de la zona és el del nord (3,6). (3,7,2 nord) es guarda en la taula BIDEA i es passa al punt (3,6). Aquí farà el mateix, però si després de revisar les cel·les adjacents no es pot moure, haurà de retrocedir, és a dir, tornar al punt (3,7) i intentar la següent direcció (norantza 3, nord-est). Seguir així quan pugui seguir endavant i no pugui retrocedir fins a arribar a la sortida o comprovar que no hi ha camí.