Gioco del labirinto (1)

Lisp »Tips 'n Tricks »Gioco del labirinto »1 »2 »3 »4

LABI implementa in AutoLISP l'algoritmo per cercare un'uscita da un labirinto.
Il campo da gioco è un recinto rettangolare diviso in n celle, ogni cella contiene o 0 (sentiero) o 1 (siepe). E si può muovere all'interno del labirinto a nord sud est ed ovest ma non in diagonale.
Il labirinto può essere rappresentato in un linguaggio come il Pascal con un array bidimensionale. E l'algoritmo è il seguente:

if E è sul confine then
   exit
else
   begin
      prova verso est
      if not exit then prova verso sud
      if not exit then prova verso ovest
      if not exit then prova verso nord
   end

Si vede che la soluzione è analoga alla procedura per camminare a Manhattan (vedi Tutorial n.36 in 'AutoLISP Tips & Tricks Volume I', e in particolare la pagina 6) cioè una funzione ricorsiva.
AutoLISP non usa gli array ma si può fingere di usare una lista come se fosse un array.
Il Lisp legge dal file LABI.TXT la struttura del labirinto e la salva in una lista, traducendo 1 (siepe) nel simbolo # e 0 (sentiero) nel simbolo .
Il file LABI.TXT deve avere il seguente formato-dati:
'(
(n₀ n₁ n₂ n₃ n_n)
...
(n₀ n₁ n₂ n₃ n_n)
)
n=0,1
cioè un elenco di liste con lo stesso numero di elementi racchiuso in una lista preceduta dal segno ' (vedi tutorial n.58).
Il lisp segna con il segno x i sentieri percorsi e con * il percorso per uscire dal labirinto; se esiste un'uscita (dal punto digitato alla linea di comando CAD) salva il labirinto, le strade tentate e il sentiero verso l'uscita nel file EXLABI.TXT. Esempio:

############
#**###xxxx##
##***#x###.#
#..#*#x#...#
###**xx#####
#..*###****#
#.#*****##*#
##########*#

Legenda del file EXLABI.TXT:
# = siepe
. = sentiero
* = percorso per uscire dal labirinto
x = vicolo cieco

Il lisp chiede latitudine e longitudine del punto d'inizio, 2 numeri interi maggiori di 0 e diversi dal numero delle righe e dal numero delle colonne del file LABI.TXT (confini del labirinto, in rosso nel codice sorgente).
Ad esempio le coordinate (1 1) corrispondono al rigo 2 e alla colonna 2 nel file LABI.TXT.

LABI

;|
   LABI.LSP (3 Luglio 2005)
   Copyright (C) 2005 Claudio Piccini.
   All rights reserved
   www.cg-cad.com

   Implementa in AutoLISP l'algoritmo 'maze'.

   Legge dal file LABI.TXT il disegno di un labirinto
   Struttura del file LABI.TXT (esempio):
   '(
   (1 1 1 1 1 1 1 1 1 1 1 1)
   (1 0 0 1 1 1 0 0 0 0 1 1)
   (1 1 0 0 0 1 0 1 1 1 0 1)
   (1 0 0 1 0 1 0 1 0 0 0 1)
   (1 1 1 0 0 0 0 1 1 1 1 1)
   (1 0 0 0 1 1 1 0 0 0 0 1)
   (1 0 1 0 0 0 0 0 1 1 0 1)
   (1 1 1 1 1 1 1 1 1 1 0 1)
   )
   Ogni lista deve avere lo stesso numero di elementi (1 0)
   I caratteri riconosciuti dal lisp sono solo 2:
   1 = siepe
   0 = sentiero

   Salva su EXLABI.TXT il percorso per uscire dal labirinto.
   Esempio:
   ############
   #**###xxxx##
   ##***#x###.#
   #..#*#x#...#
   ###**xx#####
   #..*###****#
   #.#*****##*#
   ##########*#

   Legenda:
   # = siepe
   . = sentiero
   * = percorso per uscire dal labirinto
   x = vicolo cieco
|;


;|
  LEGGEFILE()
  legge il file LABI.TXT
  salva il contenuto nella lista X -> L
  traduce 1 in "#" e 0 in "."
|;
(defun LeggeFile ( / nDir nf 
                     lista 
                     str i j e 
                     rigo X 
 )
 (setq nDir (getvar "dwgprefix"))
 (setq nf (strcat nDir "labi.txt"))
 (setq lista (load nf))
 (setq NR (length lista))
 (setq str (strcat "\nnumero righe file LABI.TXT=" (itoa NR)))
 (princ str)
 (setq NC (length (car lista)))
 (setq str (strcat "\nnumero colonne file LABI.TXT=" (itoa NC)))
 (princ str)
 (setq i 0)
 (while (< i NR)
  (setq j 0)
  (while (< j NC)
   (setq e (nth j (nth i lista)))
   (if (= e 0)
    (setq rigo (append rigo (list "."))) ; sentiero
    (setq rigo (append rigo (list "#"))) ; siepe
   )
   (setq j (1+ j))
  )
  (setq X (append X (list rigo))) 
  (setq rigo nil)
  (setq i (1+ i))
 )
 (setq X X)
)

;|
    SCRIVEFILE()
    salva la lista L nel file EXLABI.TXT
    il disegno del labirinto ed il percorso

    Legenda:
    # = siepe
    . = sentiero
    * = percorso per uscire dal labirinto
    x = vicolo cieco
|;
(defun ScriveFile ( NR NC lista / nDir nf f1 i j e )
 (setq nDir (getvar "dwgprefix"))
 (setq nf (strcat nDir "exlabi.txt"))
 (setq f1 (open nf "w"))
 (setq i 0)
 (while (< i NR)
  (setq j 0)
  (while (< j NC)
   (setq e (nth j (nth i lista)))
   (princ e f1)
   (setq j (1+ j))
  )
  (princ "\n" f1)
  (setq i (1+ i))
 )
 (close f1)
)

;|
   MAZE()
   Implementa l'istruzione 
   L[i,j] := valore
   con le liste
|;
(defun maze ( lista lat long segno / i j e rigo X )
 (setq i 0)
 (while (< i NR)
  (setq j 0)
  (while (< j NC)
   (setq e (nth j (nth i lista)))
   (if (and (= j long)(= i lat))
    (setq rigo (append rigo (list segno))) ; x *
    (setq rigo (append rigo (list e))) 
   )
   (setq j (1+ j))
  )
  (setq X (append X (list rigo))) 
  (setq rigo nil)
  (setq i (1+ i))
 )
 (setq X X)
)

;|
   CERCAEXIT()
   Cerca un sentiero 
   dal quadrato (lat long) 
   all'uscita
|;
(defun CercaExit ( lat long )
 (if (or (= lat 0)(= lat (1- NR))(= long 0)(= long (1- NC)))
  (setq exitOK T)
  (progn
   (setq L (maze L lat long "x"))
   (if (= (nth (1+ long)(nth lat L)) ".")
    (CercaExit lat (1+ long)) ; EST
   )  
   (if (not exitOK)
    (if (= (nth long (nth (1+ lat) L)) ".")
     (CercaExit (1+ lat) long) ; SUD
    )
   )
   (if (not exitOK)
    (if (= (nth (1- long)(nth lat L)) ".")
     (CercaExit lat (1- long)) ; OVEST
    )
   )
   (if (not exitOK)
    (if (= (nth long (nth (1- lat) L)) ".")
     (CercaExit (1- lat) long) ; NORD
    )
   )
  )
 )
 (if exitOK (setq L (maze L lat long "*")))
)

;|
  LABI
  funzione principale
  comando per eseguire il lisp
|;
(defun c:labi ( / str NR NC L
                  lat0 long0
                  exitOK ; valore booleano (T nil)
 )
 (setvar "cmdecho" 0)
 (setq L (LeggeFile))
 (setq str "\nInserire latitudine del quadrato di partenza: ")
 (while 
  (progn
   (initget (+ 1 2 4)) 
   (setq lat0 (getint str))
   (if (< lat0 NR) nil T)
  )
 )
 (setq str "\nInserire longitudine del quadrato di partenza: ")
 (while 
  (progn
   (initget (+ 1 2 4)) 
   (setq long0 (getint str))
   (if (< long0 NC) nil T)
  )
 )
 (setq exitOK nil)
 (CercaExit lat0 long0)
 (if (not exitOK)
  (princ "\nNon c'e' sentiero per uscire dal labirinto")
  (progn
   (princ "\nPercorso salvato in EXLABI.TXT")
   (ScriveFile NR NC L)
  )
 )
 (setvar "cmdecho" 1)
 (princ)
)
;;;eof

Test del Lisp

LABI.TXT:
'(
(1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 1 1 1 0 0 0 0 1 1)
(1 1 0 0 0 1 0 1 1 1 0 1)
(1 0 0 1 0 1 0 1 0 0 0 1)
(1 1 1 0 0 0 0 1 1 1 1 1)
(1 0 0 0 1 1 1 0 0 0 0 1)
(1 0 1 0 0 0 0 0 1 1 0 1)
(1 1 1 1 1 1 1 1 1 1 0 1)
)

Command: labi
numero righe file LABI.TXT=8
numero colonne file LABI.TXT=12
Inserire latitudine del quadrato di partenza: 1
Inserire longitudine del quadrato di partenza: 1
Percorso salvato in EXLABI.TXT

############
#**###xxxx##
##***#x###.#
#..#*#x#...#
###**xx#####
#..*###****#
#.#*****##*#
##########*#

LABI.TXT:
'(
(1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 1 1 1 0 0 0 0 1 1)
(1 1 0 0 0 1 0 1 1 1 0 1)
(1 0 0 1 0 1 0 1 0 0 0 1)
(1 1 1 0 0 0 0 1 1 1 1 1)
(1 0 0 0 1 1 1 0 0 0 0 1)
(1 0 1 0 0 0 0 0 1 1 0 1)
(1 1 1 1 1 1 1 1 1 1 0 1)
)

Command: labi
numero righe file LABI.TXT=8
numero colonne file LABI.TXT=12
Inserire latitudine del quadrato di partenza: 3
Inserire longitudine del quadrato di partenza: 9
Non c'e' sentiero per uscire dal labirinto

LABI.TXT:
'(
(1 1 1 1 1 1 1 1 1 1 1 1)
(1 0 0 1 1 1 0 0 0 0 1 1)
(1 1 0 0 0 1 0 1 1 1 0 1)
(1 0 0 1 0 1 0 1 0 0 0 1)
(1 1 1 0 0 0 0 1 1 1 1 1)
(1 0 0 0 1 1 1 0 0 0 0 1)
(1 0 1 0 0 0 0 0 1 1 0 1)
(1 1 1 1 1 1 1 1 1 1 0 1)
)

Command: labi
numero righe file LABI.TXT=8
numero colonne file LABI.TXT=12
Inserire latitudine del quadrato di partenza: 5
Inserire longitudine del quadrato di partenza: 1
Percorso salvato in EXLABI.TXT

############
#..###....##
##...#.###.#
#..#.#.#...#
###....#####
#***###****#
#.#*****##*#
##########*#

LABI.TXT:
'(
(1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 0 1 1 1 1 1 1 1 1 1)
(1 0 0 1 1 1 0 0 0 0 1 1)
(1 1 0 0 0 1 0 1 1 0 0 1)
(1 0 0 1 0 1 0 1 0 0 0 1)
(1 1 1 0 0 0 0 1 0 1 1 1)
(1 0 0 0 1 1 1 0 0 0 0 1)
(1 0 1 0 0 0 0 0 1 1 0 1)
(1 0 0 1 1 0 1 1 1 1 0 1)
(1 1 1 1 1 0 1 1 1 0 1 1)
)

Command: labi
numero righe file LABI.TXT=10
numero colonne file LABI.TXT=12
Inserire latitudine del quadrato di partenza: 3
Inserire longitudine del quadrato di partenza: 3
Percorso salvato in EXLABI.TXT

############
##.#########
#..###****##
##.**#*##**#
#..#*#*#***#
###.***#*###
#...###**xx#
#.#..***##x#
#..##*####x#
#####*###.##

Trick

Come si esce dalla funzione ricorsiva CercaExit()? (non necessariamente dal labirinto).

Lisp »Tips 'n Tricks

Ultimo Aggiornamento_Last Update: 3 Luglio 2005