Caso Integrador: Algoritmos en el desarrollo de juegos

Politécnico Internacional[pic 1]

Asignatura: Diseño de algoritmos

Caso Integrador: Algoritmos en el desarrollo de juegos

En el presente informe se muestra los conocimientos básicos adquiridos en el lenguaje de programación (Pseudocodigos). Se presenta unas series de juegos donde el nivel de dificultad hace que al realizar las líneas de código sea mas exigentes y aumente el nivel de actividad lógica al momento de programar. Así mismo, se detalla el procedimiento que se utilizó para la implementación de lo juegos.

Fase 1: Juego de Hanoi

Indagando sobre la historia de la torre de hanoi nos encontramos con la leyenda tan peculiar sobre la cual dicen varias fuentes que surgió el juego, cuenta con un origen místico que termina con un presagio apocalíptico, la historia cuenta que el dios Brahma después de crear al mundo puso 3 astas y 64 discos en una de las astas organizados de mayor a menor, estando el mayor en la base, y cuando todos los discos sean pasados a el asta del otro extremo se acabara el mundo.  En realidad este fue un problema que planteo el matemático italiano Girolamo Cardano (1501–1576) en su libro “De Subtililate”  y el cual fue tomado como base para hacer el juego publicado en 1883 por el matemático francés François Edouard Anatole Lucas, en la parte donde dice “llegara el fin del mundo” hace referencia a la grandísima cantidad de movimientos que hay que hacer para solucionar la torre de hanoi con 64 discos como dice la leyenda, buscando mas información, encontramos una formula la cual nos indica el número mínimo de movimientos que se utilizan para resolver el juego dependiendo del número de discos: d(n) es el número de discos // d(n) = numero de movimientos por 2, más 1, nos da el número de movimientos necesarios para d(n+1).

Ejemplo: d(3) = 7x2: 14 + 1 : 15, 15 es el número mínimo de movimientos necesarios para resolver un juego con 4 discos.

A su misma vez podemos observar que con agregar un solo disco el número de movimientos mínimos crece en gran medida.

Con esto en mente, nos propusimos a jugar la torre de hanoi con diferente número de discos intentando solucionarlo haciendo el menor número de movimientos, después de jugar mucho e intentar, hemos encontrado una secuencia la cual nos puede garantizar la resolución del ejercicio utilizando el mínimo número de movimientos.

Primero al momento de empezar para mover el primer disco, el mas pequeño, se debe tener en cuenta el número de discos, si hay un número par de discos el primer movimiento se debe realizar a el asta mas cercana como muestran las imágenes donde el número de discos es 4.

[pic 2]

[pic 3]

[pic 4]

Si el número de discos es un número impar entonces el primer movimiento que debemos hacer es mover el disco hacia el asta mas distante como muestran las imágenes donde el número de discos es 5.

[pic 5][pic 6]

[pic 7]

A continuación movemos el siguiente disco y apilamos, el tercer disco lo ponemos en el espacio vacío y apilamos.

[pic 8][pic 9]

[pic 10]

[pic 11]

Ahora sacamos un nuevo disco de la pila principal  y lo ponemos en el asta que no tiene discos,

[pic 12]

[pic 13]

Y este es el truco a tener en cuenta para resolverlo con los mínimos movimientos, si la pila a mover tiene un numero impar de discos, se debe empezar moviendo el primer disco a el asta donde uno desea mover toda la pila, en la imagen encerrada en un circulo esta la pila que se desea mover y la flecha indica hacia donde se quiere mover.

[pic 14][pic 15][pic 16]

[pic 17][pic 18]

[pic 19]

[pic 20]

[pic 21]

Lo demás es la secuencia normal para pasar la pila al lugar donde se desea, como se muestra en las anteriores imágenes.

Y si por el contrario el número de discos de la pila que se desea mover es par, el primer movimiento debe ser a el lugar contrario del anterior, es decir al asta donde no deseamos mover nuestra pila, en la imagen, encerrada en un círculo esta la pila que se desea mover, la flecha roja indica hacia donde se debe mover el primer disco y la flecha azul indica a donde se debe mover toda la pila.

[pic 22]

[pic 23]

Y se sigue la secuencia normal para desplazar una pila de una asta a otra como muestra las imágenes.

[pic 24][pic 25][pic 26]

[pic 27][pic 28]

En este momento que estamos en la mitad de la secuencia pasando la pila de cuatro discos se debe hacer la secuencia que hicimos para pasar una pila donde su número de discos es impar, en la imagen señalamos con un circulo la pila impar que se generó y hacia donde la debemos pasar.

[pic 29]

[pic 30]

Y así sucesivamente, teniendo en cuenta esta secuencia podremos solucionar el juego con el menor número de movimientos posibles.

FASE 2: Juegos lógicos

En esta fase, se tiene como objetivo poder tener las bases lógicas para resolver el juego de Hanoi. Para ello se aplica se aplica el siguiente diagrama:

[pic 31]

[pic 32]

Así mismo, para logra comprender lo descrito en la figura 1. Lo aplicaremos en los siguientes juegos cuya descripción son:

• 1 y 1000 en 10 intentos

Adivinar un numero entre 1 y 1000 en 10 intentos, sabiendo que cada intento se dirá si el numero es muy alto (Cuando el numero sea mayor al número buscado) y muy bajo (cuando el numero sea menor al número buscado).

• Quien llegue a 30 con los números 1,2,3.

Este es un juego para dos usuarios donde el objetivo es ver cual de los dos llega primero al numero 30. Cada usuario solo puede usar numero 1,2 o 3, estos se sumarán dependiendo el número.

• Juego de Nim

En este juego se colocan una cantidad de palillos en 2 recipientes, la cantidad de palillos la puede elegir un usuario para un recipiente y el otro usuario para el otro recipiente, usualmente manejamos cantidades de hasta 100, las reglas del juego permiten que un jugador saque del recipiente la cantidad de palillos que quiera, lo que no puede hacer es sacar de los 2 recipientes simultáneamente. Gana el jugador que saque el ultimo palillo d ellos 2 recipientes.

...