Mummy maze

2010
MUMMY MAZE

19/11/2010

MUMMY MAZE 2010

UNIVERSIDAD NACIONAL DEL CENTRO DE LA PROVINCIA DE BUENOS AIRES

Facultad de Ciencias Exactas

Análisis y Diseño de Algoritmos II

PROYECTO ESPECIAL MUMMY MAZE

Alumnos

Ayudante:

Comisión: viernes

Grupo Nº: 2

2

MUMMY MAZE 2010 Índice
Introducción.....................................................................................................................................4 Objetivos del Trabajo ......................................................................................................................6 Descripción teórica de los algoritmos utilizados .............................................................................8 Espacios de estados.................................................................................................................8 Búsqueda en espacio de estados ..............................................................................................9 Depht-First-Search ................................................................................................................10Breadth-First-Search..............................................................................................................10 Algoritmo AStar ....................................................................................................................11 Código de los algoritmos implementados .....................................................................................13 Breadth-First-Search..............................................................................................................13 Algoritmo A* o A Estrella.....................................................................................................15 Análisis teórico y empírico de los algoritmos ......................................................................28 Gráficos.................................................................................................................................30 Conclusión .....................................................................................................................................33 Bibliografía ....................................................................................................................................34

3

MUMMY MAZE 2010 Introducción
El objetivo deltrabajo es implementar diversos algoritmos de búsqueda que permitan resolver los laberintos propuestos por el juego “Mummy Maze”. El juego está compuesto de una serie de escenarios a través de los cuales se debe guiar al explorador hasta la salida de cada uno de ellos. Cada escenario contiene paredes que constituyen obstáculos para el movimiento, así como enemigos (momias y escorpiones) que intentaránevitar que el explorador llegue a la salida del laberinto.

Diagrama mostrando los elementos que forman parte de los distintos laberintos.

La versión del juego que utilizaremos tiene las siguientes características:   El tamaño del laberinto de 6 casilleros de ancho por 6 casilleros de alto. Los posibles movimientos de todos los personajes son hacia casilleros contiguos; en las direccioneshacia arriba, abajo, derecha e izquierda. Adicionalmente los personajes pueden quedarse en el lugar. En el caso del explorador esto es una acción (hacer nada) y para los enemigos cuando se encuentran bloqueados por alguna pared.

4

MUMMY MAZE 2010
 La dinámica del juego se da en turnos que se otorgan a cada personaje: o El orden es primero el explorador, luego los escorpiones y finalmentelas momias, uno a la vez. o Durante su turno cada personaje debe optar por realizar un movimiento válido o bien no moverse y pasar el turno. o Tanto la momia como el escorpión tienen una lógica determinística para realizar sus movimientos. Los enemigos siguen las mismas reglas para moverse:   Cuando pueden moverse horizontalmente para acercarse al explorador, realizarán ese movimiento primero....