BFS con agentes

; Los estados serán agentes
breed [estados estado]
estados-own 
[
  contenido  ; Almecena el contenido del estado (el valor)
  explorado? ; Indica si ha sido explorado o no
  camino     ; Almacena el camino para llegar a él
]

; Las transiciones se representarán como links
directed-link-breed [transiciones transicion]
transiciones-own
[
  regla   ; Almacena la versión "representable" de la regla aplicada
]

;--------------- Funciones personalizables -------------------

; Las reglas se representan por medio de pares [ "representación" f ]
; de forma que f permite pasar entre estados (es la función de transición)
; y "representación" es una cadena de texto que permite identificar qué
; regla se ha aplicado

to-report transiciones-aplicables
  report (list 
           (list "*3" (task [? * 3])) 
           (list "+7" (task [? + 7])) 
           (list "-2" (task [? - 2])))
end 

; estado-final? ofrece un report de agente que identifica los estados finales

to-report igual? [ob]
  report ( contenido = ob)
end 

;-------------------- Algoritmo BFS y auxiliares ----------------
; Esencialmente, el algoritmo va calculando los estados hijos de cada estado 
; no explorado y los enlaza por medio de la transición que lo ha generado, hasta
; alcanzar el estado objetivo.

to BFS [estado-inicial estado-final]
  ca
  salida
  ; Creamos el agente asociado al estado inicial
  create-estados 1
  [
    set shape "circle"
    set color green
    set contenido estado-inicial
    set label contenido
    set camino (list self)
    set explorado? false
  ]
  ; Mientras halla estados no explorados (la verificación de haber encontrado
  ; el objetivo se hace dentro)
  while [any? estados with [not explorado?]]
  [
    ask estados with [not explorado?]
    [
      ; Calculamos los estados sucesores aplicando cada regla al estado actual
      foreach transiciones-aplicables
      [
        let estado-aplicado (run-result (last ?) contenido)
        ; Solo consideramos los estados nuevos
        if not any? estados with [contenido = estado-aplicado]
        [
          ; Creamos un nuevo agente para cada estado nuevo
          hatch-estados 1
          [
            set contenido estado-aplicado
            set label contenido
            set explorado? false
            ; y lo enlazamos con su padre por medio de un link etiquetado
            create-transicion-from myself [set regla ? set label first ?]
            set color blue
            ; Formamos el camino desde el inicio hasta él
            set camino lput self camino
          ]
        ]
        ; Podríamos calcular también los diversos caminos para llegar a todos los nodos,
        ; pero en BFS eso complica el grafo de búsqueda construido y la reconstrucción
        ; del camino cuando se halla el objetivo
        ;
        ; create-transicion-to one-of estados with [contenido = estado-aplicado]
        ; [
        ;  set regla ?
        ;  set label first ? 
        ; ]
        
        ; Actualizamos la representación 
        if layout? [layout]
      ]
      ; Cuando hemos calculado todos sus sucesores, marcamos el estado como explorado
      set explorado? true
    ]
    ; Comprobamos si hemos alcanzado el estado objetivo
    if any? estados with [igual? estado-final]
     [ 
       ; Y si es así, lo destacamos en rojo y destacamos el camino que ha llevado 
       ; hasta él (por medio de un reduce con una funciónn adecuada)
       ask one-of estados with [igual? estado-final] 
       [
         set color red
         let a reduce resalta camino
       ]
       output-print (word "Estados explorados: " count turtles)
       stop
     ]
  ]
end 

; La función resalta se usa dentro de un reduce, lo que hace es que dados 
; dos nodos, destaca el link que los une y devuelve el segundo

to-report resalta [x y]
  ask transicion [who] of x [who] of y [set color red set thickness .3]
  report y
end 

; El procedimiento limpia aprovecha que hemos construido un árbol (no vale para
; grafos) para eliminar de forma recursiva todos los nodos que no están en el 
; camino que une estado-inicial y estado-final

to limpia [o1 o2]
  while [any? estados with [grado = 1 and contenido != o2 and contenido != o1]]
  [
    ask estados with [grado = 1 and contenido != o2 and contenido != o1][die]
  ]
end 

; Devuelve el grado de un nodo

to-report grado
  report (count my-in-links + count my-out-links)
end 

; Representación del grafo de forma más adecuada

to layout
  layout-radial estados transiciones estado 0
  ;layout-spring estados transiciones .7 4 .8
end 

; Salida Output

to salida
  output-print (word "Ir desde " Estado_Inicial " hasta " Estado_final)
  output-print (word "usando las operaciones:")
  foreach transiciones-aplicables
  [
    output-print (first ?)
  ]
end