Computador doméstico. Labirinto

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

• Programazioa

Nesta ocasión, realizaremos un programa que axudará á xagua a buscar a saída ao labirinto. Este programa está escrito paira Tee vídeo, pero tamén se pode escribir paira spectrum.

Sinalaremos o labirinto mediante unha matriz. Os obstáculos indicaranse cun "1" e as celas libres cun "Ø".

A entrada ao labirinto (1,1) será o inerte e a saída (m, n) será a dimensión do inerte, m e n. Neste caso utilizaremos m=n=8.

O rato definirase coa súa posición, é dicir, coas coordenadas do punto ou pila que se atopa no momento. Toma nota do que sempre estará nunha pila Ø. Ademais, hai que definir as posibles directrices que pode ter o pano. As direccións posibles son oito en todas as celas, excepto nas de bordo. Así que para que o comportamento do xagua sexa igualitario en todos os lugares, rodearemos o labirinto de obstáculos. Ver como:

O cambio de coordenadas que supón cada dirección preséntase na táboa NORANTZA (8,2):

Modificación da coordenada de columnas paira seguir o rumbo I NORANTZA (I,1)

Modificación da coordenada de liña paira seguir a dirección NORANTZA (I,2) I

Xagua partirá da pila de entrada e pasará dun punto a outro fuxindo de obstáculos. Cando non se poida seguir adiante, deberá retroceder. Por tanto, o camiño percorrido polo carreiro condúcenos pola táboa BIDEA (64,3).

En cada un dos campos desta táboa gardarase:

Coordenadas dunha pila que compón o camiño
• Sentido de paso desta pila a outra

Cando Xagua atópase nunha pila de auga, a sobriedade deberá analizala en busca dun "bo punto". Para que una pila sexa un "bo punto" debe cumprir os seguintes requisitos:

Ausencia de obstáculos (marcado con Øen a táboa LAB).
• Que a xagua non pase por esta pila (que a MARCA estea marcada con Øen a táboa).

Se atopa entre os oito puntos da zona un punto que cumpra estas condicións, gardaranse as coordenadas da pila actual e a dirección que debe seguir paira pasar ao novo punto e pasarase ao novo punto. Aquí seguirá o mesmo proceso.

Pola contra, si tras analizar os oito puntos da zona non se ve a posibilidade de pasar a ningún punto, deberá retroceder, pasando á primeira pila (a última pila introducida na táboa BIDEA) e desde aquí tentalo noutro sentido. O proceso é repetitivo. Manterase até chegar a unha destas dúas situacións:

Localización da saída
• Non retroceder

No primeiro caso, o camiño aparecerá marcado en vermello. No segundo, a mensaxe será:

"Non hai camiño!!"

Como poderías comprobar, mencionamos tamén a táboa chamada MARCA. Na seguinte táboa iremos marcando cun "1" paira saber de que cuarto pasou a mocha a medida que a movamos. Se non se fai isto, pódese meter nun abrandamento interminable.

Un exemplo axudarache a comprender mellor: Supoñamos que o modesto (3,7) está na inerte, que o primeiro "bo punto" que empeza a estudar e atopar as celas da zona é o do norte (3,6). (3,7,2 norte) se garda na táboa BIDEA e pásase ao momento (3,6). Aquí fará o mesmo, pero si tras revisar as celas adxacentes non se pode mover, deberá retroceder, é dicir, volver ao momento (3,7) e tentar a seguinte dirección (norantza 3, nordés). Seguir así cando poida seguir adiante e non poida retroceder até chegar á saída ou comprobar que non hai camiño.