Existe un formato de archivos de texto preestablecido para
describir escenarios de Sokoban. Cada línea de texto se
corresponde con una fila de la cuadrícula del
almacén. El significado de cada carácter es el
siguiente
El siguiente código permite leer un archivo de texto fileName en ese formato y devuelve un array de *rows strings, todos ellos de ancho *cols, almacenando además el número de cajas encontradas en *goals.espacio - casilla vacía
# - pared
. - posición de destino sin nada encima
@ - operario del almacén sobre una casilla normal
+ - operario del almacén sobre una casilla destino
$ - una caja sobre una casilla normal
* - una caja sobre una casilla destino
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"
void readline(FILE *f,char *line, int *goals) {
int c,i=0;
c=fgetc(f);
while (c!=EOF && c!='\n') {
line[i++]=c;
if (c=='$' || c=='*') (*goals)++;
c=fgetc(f);
}
line[i]=0;
}
char **loadFile(char *fileName, int *rows, int *cols, int *goals) {
FILE *f;
char line[512], *s;
int i,j,l;
QUEUE lines=qEMPTY;
char **array;
*goals=0;
*cols=-1;
if (fileName==NULL || (f=fopen(fileName,"r"))==NULL) {
printf("Could not open input file %s\n",fileName); exit(1);
}
readline(f,line,goals);
while ((l=strlen(line))!=0) {
if (l>*cols) *cols=l;
s=(char *)malloc((l+1)*sizeof(char));
strcpy(s,line);
qInsertLast(&lines,&s,sizeof(char *));
readline(f,line,goals);
}
fclose(f);
array=(char **)Queue2Array(lines,sizeof(char *),rows);
qFree(&lines);
for (i=0;i<*rows;i++) {
l=strlen(array[i]);
s=(char *)malloc(sizeof(char)* (*cols));
memcpy(s,array[i],sizeof(char)* (*cols));
for (j=strlen(array[i]);j<*cols;j++) s[j]=' ';
free(array[i]);
array[i]=s;
}
return array;
}
NOTA: una vez usado, se deberían liberar todos los
strings del array, y el propio array.
Los siguientes ejemplos contienen 4 dominios de sokoban en ese
formato ordenados por complejidad: soko0.txt,
soko1.txt, soko2.txt,
soko3.txt
Existen dos formas de medir el coste de una solución de
Sokoban: (1) contando el número de movimientos (tanto
desplazamientos del operario, como empujes de cajas); y (2)
contando sólo los desplazamientos de cajas. En nuestro
ejercicio, se pide utilizar esta segunda opción, es
decir, las acciones a considerar serán
únicamente las de empujar cajas y despreciaremos
los demás movimientos del operario para desplazarse.
Obviamente, tendremos que averiguar qué cajas son
"empujables" en un estado dado. Para ello, se pueden calcular
las posiciones accesibles por el operario sin cambiar ninguna
caja. Ese cálculo es más simple que obtener una
ruta concreta para llegar hasta la caja. Así, por
ejemplo, la caja X se puede empujar a la derecha, si la
posición de la izquierda de la caja en este momento es accesible
por el operario.
Se deberá utilizar el código con el que hemos
trabajado en los ejercicios anteriores, creando las funciones
correspondientes para el nuevo dominio. Aparte de diseñar
una función heurística, deberemos también
tener en cuenta que Sokoban es un juego con estados muertos, es
decir, desde los cuales no existe solución posible. Como
ejemplo, podemos pensar que si dejamos simplemente una caja en
una esquina que no es destino, ya no hay manera de moverla de
ahí y por tanto el juego no tiene solución. Para
evitar estas situaciones podemos hacer uso de la función
executable, prohibiendo acciones que lleven a estados
que sabemos que son callejones sin salida.
Más adelante añadiremos algunos casos de prueba
"asequibles" clasificados por niveles (existen infinidad de
ellos en internet). Como herramienta de apoyo para visualizar
soluciones o comprobar si la solución obtenida
efectivamente es mínima, podemos usar la herramienta JSoko.
NOTA: para que la búsqueda en grafo (opción -a
graph) funcione correctamente es necesario especificar
qué parte de la estructura tState se usa para identificar
un estado y poder distinguirlo de otro. Por defecto, la
tabla hash usa una función que compara el contenido de
los struct tState para distinguir dos estados. Esto
funciona bien en los ejemplos de 8puzzle y romania, porque toda
la información está directamente en el struct. Sin
embargo, en el ejemplo de bloques, la comparación por
defecto estará usando valores de punteros y en general no
detectará estados repetidos. Para evitar esa
situación deberemos mantener la información
relevante del estado en un área de memoria cuyo
tamaño vendrá especificado por la variable stateHashKeySize
y cuya dirección de comienzo será una
función que toma un estado y devuelve un puntero a void y
que asignaremos al puntero a función stateHashKey.
En el caso de bloques, sólo con el array blockLoc
podemos identificar por completo el estado, ya que los arrays clear
e inTower son auxiliares y no aportan
información relevante.:
/* Función que vamos a usar para decir dónde comienza la zona de memoria usada para hash */
void *stateBlocksHashKey(tState *s) {
return s->blockLoc; /* El array blockLoc determina por completo el estado */
}
.
.
.
tState *loadDomain(char *fileName) {
.
.
.
stateHashKeySize=numBlocks*sizeof(int); /* Tamaño del array blockLoc */
stateHashKey=stateBlocksHashKey; /* Función que nos devuelve el puntero a blockLoc */
.
.
.
}
La puntuación máxima de la práctica es 1
punto (sobre el total de 10 de la asignatura). Por otro
lado, la asistencia activa en clases prácticas se valora
con un máximo de otros 0,5 puntos adicionales. El
programa a entregar debe ser capaz de obtener soluciones
correctas para escenarios pequeños. Adicionalmente, si
una práctica consigue resolver problemas más
complejos eficientemente, se consolidarán los 0,5 puntos
de asistencia, aunque no se hayan asistido a todas las clases.
El método de entrega es el de buzón de
prácticas. Deberemos subir los archivos fuente en el
directorio /PRACTICAS/GEI/SI/P1/login
en cualquiera de las máquinas de referencia. Las
prácticas se pueden realizar por parejas: en ese caso, es
suficiente con subir la práctica en uno de los dos
buzones, indicando en comentarios en las primeras líneas
del código los componentes del grupo (nombre y login)
siguiendo la sintaxis:
/*
APELLIDOS: xxxxx
NOMBRE: xxxxx
LOGIN: xxxx
APELLIDOS: xxxxx
NOMBRE: xxxxx
LOGIN: xxxx
*/
La fecha límite de entrega es el 12
de abril de 2013. Las prácticas pueden
requerir una defensa posterior. Esto se indicará en un
listado de calificación provisional, así como las
fechas disponibles para la defensa.