TP3

Sokoban 3: Ahora es personal

El objetivo de este TP es agregarle dos funcionalidades a nuestro viejo y querido Sokoban:

  • Deshacer y rehacer
  • Pistas

Como recursos, se proveen los TDAs Pila y Cola:

Deshacer y rehacer

En el caso de que el usuario se equivoque o decida probar una combinación diferente de movimientos, el juego debería permitir deshacer y rehacer los diferentes movimientos.

El "deshacer" permite revertir los últimos movimientos. Para esto el juego debe tener la capacidad de recordar una cantidad ilimitada de grillas previas, y si deshacemos repetidas veces deberíamos siempre poder llegar al estado inicial del nivel.

Por otro lado, el "rehacer" permite "deshacer el deshacer" y solo tiene efecto luego de haber hecho "deshacer" una o más veces seguidas. La idea es que el usuario tenga la opción de usar "deshacer" y "rehacer" todas las veces que quiera para visualizar el cambio de la grilla en sentido inverso (al "deshacer") y en sentido directo (al "rehacer"). En cualquier momento en el que el usuario hace cualquier acción que no sea "deshacer" o "rehacer", pierde la posibilidad de "rehacer" hasta la próxima vez que haga "deshacer".

Estas funcionalidades se implementan con un par de pilas.

Se deberá deshacer y rehacer presionando teclas correspondientes para cada acción (configurable mediante teclas.txt).

Pistas

Presionando una tecla determinada (configurable mediante teclas.txt), el efecto dependerá de dos casos posibles:

  • No hay pistas disponibles: en este caso el juego intentará encontrar una solución al nivel, utilizando el algoritmo de backtracking que se describe a continuación. Si se encuentra la solución, la sucesión de acciones correspondiente será considerada como las pistas disponibles.

  • Hay pistas disponibles: Se desencola una pista y se efectúa esa acción, como si la hubiera hecho el jugador.

Si el jugador efectúa cualquier otra acción que no sea la acción de "pista", se debe descartar las pistas disponibles, ya que no podemos asegurar que sean válidas para el estado actual.

Backtracking

Fuente: Wikipedia

Backtracking es un método para encontrar todas las soluciones (o algunas) a problemas computacionales, que consiste en plantear soluciones candidatas e ir descartando (backtrack) las que se determina que no son soluciones.

Para resolver un nivel de Sokoban utilizando backtracking, lo más fácil es plantear el algoritmo en forma recursiva:

algoritmo buscar_solucion(estado_inicial):
    visitados := un conjunto vacío de estados
    devolver backtrack(estado_inicial, visitados)

algoritmo backtrack(estado, visitados):
    agregar(visitados, estado)                            [1]
    si juego_ganado(estado):
        # ¡encontramos la solución!
        devolver Verdadero, []
    Para toda acción posible `a` desde el estado:
        nuevo_estado := mover(estado, a)
        si pertenece(visitados, nuevo_estado):            [2]
            continuar
        solución_encontrada, acciones := backtrack(nuevo_estado, visitados)
        si solución_encontrada:
            devolver Verdadero, concatenar([a], acciones)
    devolver Falso, ∅

Notar que visitados debe permitir almacenar un conjunto de estados [1], y buscar en forma eficiente si un estado particular está o no en el conjunto [2]. Para que el algoritmo de backtracking sea eficiente, es un requerimiento que pertenece sea más rápido que una búsqueda lineal.

Una forma de lograr eso es que visitados sea un diccionario (dict) o un conjunto (set) de Python. Para ello es necesario que el estado sea inmutable, o bien que haya una forma de obtener una representación única e inmutable a partir de un estado. Supongamos que tenemos una función h que recibe un estado y devuelve una representación inmutable del mismo, entonces [1] y [2] pueden ser cambiados a:

agregar(visitados, h(estado))                        [1]
si pertenece(visitados, h(nuevo_estado)):            [2]

Algunas alternativas para la representación inmutable son:

  • Una cadena con la representación del nivel en el formato de niveles.txt.
  • Una tupla con la posición del jugador y todas las posiciones de las cajas.

Nota: aun logrando que pertenece sea eficiente, el algoritmo de backtracking podrá resolver únicamente los niveles más simples en un tiempo razonable. Por ejemplo, los primeros 10 niveles del set de niveles proporcionado en el TP2 pueden ser resueltos en alrededor de 1 minuto por backtracking. En cambio otros niveles como por ejemplo el 23, que a simple vista parece simple, es computacionalmente más complejo ya que permite al jugador más libertad de movimiento. El algoritmo de backtracking puede no terminar en un tiempo razonable; eso es normal y esperable.

Además, si se implementa el algoritmo de backtracking en forma recursiva, para algunos niveles es probable que se llegue a superar el límite de recursión del intérprete Python. No es un requisito plantear una solución para este problema.

Entrega

La entrega del trabajo (a través del formulario de entregas) debe incluir todos los archivos necesarios para ejecutar el juego comprimidos en un archivo zip.