PDF de programación - Funciones que ganan partidas

FUNCIONES QUE GANAN

PARTIDAS

Trabajo Final



Coordinador:



Álvaro Espinosa Marlasca.
Grado en Ingeniería de Computadores
[email protected]



David Javier Morán Márquez.
Grado en Ingeniería de Computadores
[email protected]

Francisco Javier Romero Paris.

Grado en Ingeniería de Computadores
[email protected]



Funciones que ganan partidas

Utiliza Matemáticas - 2013

INTRODUCCIÓN

En todos los videojuegos, ya se han desde los primeros en crearse
hasta los más actuales, comprobamos la existencia de “bugs” o fallos
en los personajes controlados por el jugador o por la máquina en
cuestión, personajes controlados por la IA (Inteligencia Artificial),
respecto a su movimiento, aunque bien es cierto que hay más tipo de
“bugs”.

Estos fallos se deben a errores de los personajes en sus funciones y
algoritmos de movimiento. En este trabajo veremos cómo se desplazan
los personajes y explicaremos las funciones y los algoritmos que
utilizan para hacerlo. Para tener una visión más clara de este tipo
de movimientos, los explicaremos usando videojuegos conocidos como
ejemplos.



INDICE:

1. Empezando con el movimiento: cambios en coordenadas

1.1

Primeros juegos: Pong y Space Invaders

2. Movimientos controlados por la IA. Algoritmo de Dijkstra
2.1 Algoritmo de Dijkstra en videojuegos: Pac-Man
2.2 Evolución del algoritmo de Dijkstra: Algoritmo A*
2.3 Algoritmo A* en juegos en 3D: Age of Empires

3. Un enfoque más actual hacia el algoritmo A*.Aumentando la

dificultad.

4. Capturar el movimiento: el futuro del movimiento en videojuegos
5. Bibliografía



Page 2



Funciones que ganan partidas

Utiliza Matemáticas - 2013

1. EMPEZANDO CON EL MOVIMIENTO: CAMBIOS EN LAS COORDENADAS

Para empezar a hablar sobre el movimiento en un videojuego, debemos

tener claro que hay distintos tipos de movimientos; como por ejemplo
el desplazamiento de nuestro personaje o el movimiento corporal del
mismo. En este trabajo se va a tratar sobre el primero.

El desplazamiento de objetos (personajes, animales, u otras cosas)

en un juego a un nivel lógico-bajo consiste en asignar unas
coordenadas iniciales “X” e “Y” (si el juego es 2D) y “X”,”Y” y “Z”
(si son juegos en 3D) e ir variando las mismas mientras asignamos a
estas unas imágenes que iremos haciendo aparecer y desparecer según
toque, para crear una visión de desplazamiento. En los primeros
juegos programaremos para que los jugadores enemigos u otros objetos,
cambien de una forma más o menos prediseñada estas variables
iniciales.

Cuando llegue la Inteligencia Artificial (IA) a los videojuegos, se

usaran algoritmos más complejos para que estos personajes se muevan
“individualmente”, pero en resumidas cuentas, siguen cambiando las
coordenadas.

Todos hemos jugado al juego de hundir la flota, en el que tenemos

un tablero dividido en cuadrados con coordenadas asignadas (números y
letras). Colocamos los “barquitos” en cualquiera de ellas, es decir
les asignamos a cada barco unas letras y unos números, que podríamos
identificar como coordenadas “X” e “Y”. En los videojuegos pasa
exactamente lo mismo. Para empezar a explicar cómo se mueven objetos
en los videojuegos, vamos a empezar por los primeros videojuegos, los
más simples, creados en dos dimensiones (2D). En ellos la pantalla
queda dividida por las coordinadas “X” (de izquierda a derecha) e “Y”
(de arriba abajo).

Cuando programamos el objeto (nos referimos con objeto a cualquier

evento que queramos desplazar ya sean personas, cosas, imágenes,
etc.), solo tenemos que asegurarnos de que esas coordinadas cambien
cada “t” tiempo. El desplazamiento se verá visualmente porque la
imagen con la que representamos ese objeto aparecerá en las
coordenadas correspondientes (desapareciendo de las anteriores, dando
la sensación de desplazamiento).



1.1

PRIMEROS JUEGOS: PONG Y SPACE INVADERS

El primer juego programado que se hizo fue el conocido “PONG”,

el juego consiste en simular un partido de tenis, donde el jugador y
su adversario son representados por una barra y se van lanzando una
pelota de tenis. Representando el movimiento anteriormente descrito
arriba, vamos a centrarnos en el movimiento que hace la pelota.



Page 3



Funciones que ganan partidas

Utiliza Matemáticas - 2013

La pelota va cambiando de

coordenadas X e Y con una velocidad
constante y al chocar con una de las
barras, se multiplican las coordenadas por
(-1), por lo que la pelota se refleja, y
sale en la dirección y sentido contrario
de donde provenía. Las dos funciones que
se tienen que programar son tan simples

como:

f(x)=i
f(y)=j

Donde “x” e “y” van cambiando de valor constantemente, haciendo que la
pelota se desplace de un lado hasta el otro.



Otro de los grandes primeros juegos es el famoso “Space

Invaders”. “Space Invaders” es uno de los primeros juegos shoot 'em
up. Es uno de los videojuegos más importantes de la historia. Su
objetivo es eliminar oleadas de alienígenas con un cañón láser y
obtener la mayor cantidad de puntos posible. “Space Invaders” es un
“matamarciano” clásico en dos dimensiones. El jugador controla
un cañón que puede moverse a la derecha o izquierda y un botón de
disparo. Tiene que ir destruyendo los extraterrestres invasores. Vamos
a centrarnos en el movimiento de estos “marcianitos”.

Al igual que el “PONG”, Básicamente

su movimiento consiste en cambiar las
variables X e Y de un objeto, que en este
caso es una imagen, que se moverá bajando la
pantalla. Es decir empezará desde el punto
más alto de las “Y” (arriba de la pantalla)
y se moverá hacia abajo de la pantalla. A su
vez este objeto, se va desplazando hacia la
derecha (empieza a la izquierda) y cuando
llegue a la izquierda, se desplazará a la
derecha. Cabe decir, que cuando el primero
de los objetos de la fila de los marcianitos
choque con la pared de la pantalla, llegue a la coordenada “X” máxima,
es cuando baja una posición en la coordenada de las “Y”.

El juego va incrementando su velocidad a medida que baje,

haciendo que cada vez se muevan más rápido los marcianitos por las
coordenadas. En cuanto la posición de los marcianitos llega a “Y”=0 (o
a la coordenada mínima de Y que programemos), se acabará el juego.



Page 4



Funciones que ganan partidas

Utiliza Matemáticas - 2013



Las funciones que tienen que implementar el juego son:

f(y)= f(y) -1 ( Cada vez que toque cambiar las coordenadas de las
“Y” se reducirá en uno )

f(x)= f(x)+1 (cuando llega al tope, al máximo de las “x”, al igual que
en el “PONG”, vuelve a modificar sus variable multiplicando la
coordenada por -1, por lo que se convertiría en la función f(x)=f(x)-
1)

Al principio del juego, se le asigna a cada f(x) y f(y) un valor
inicial, tal que:

f(x)=i (donde “i” es la coordenada mínima de las “x”)

f(y)=j (donde “j” es la coordenada mínima de las “y”)



2. MOVIMIENTOS CONTROLADOS POR LA IA. ALGORITMO DE DIJKSTRA

Hemos conseguido que en los videojuegos se cree un movimiento

programado, pero, todos sabemos que en la vida real, por muchas
razones los movimientos de los objetos no siempre son los mismos, hay
eventos que lo modifican. Es por eso, que existe una necesidad de que
el movimiento pueda cambiar en tiempo de ejecución del juego y esto lo
conseguimos implementando una Inteligencia Artificial en los objetos
que creamos, para que decida, en tiempo de ejecución, que movimiento
hacer.

Como ya hemos comentando anteriormente, lo que hará la IA será a

nivel lógico más básico cambiar el objeto de coordenadas, no obstante
estos cambios vienen definidos por el camino que tiene que seguir ese
personaje que se calcula en base de algún algoritmo.

Uno de los primeros tipos de videojuegos en implementar una IA, es

el tan famosos “PAC-MAN”. En este juego tienes unos “fantasmitas” que
te van persiguiendo por toda la pantalla. El algoritmo usado en este
juego es una implementación del algoritmo de Dijkstra, que sirve para
calcular el camino más corto (con el mínimo coste) entre los
“fantasmitas” y pacman. “PAC-MAN” consta de cuatro fantasmitas y cada
uno de esos tiene una variación de la implementación de este
algoritmo. Además uno de los puntos más notables e interesantes que
tiene el juego, es que estos algoritmos cambian dependiendo del estado
de los fantasmitas, por ejemplo, normalmente los fantasmitas van hacia
donde se encuentra pacman, pero cuando pacman come cierta fruta, los
fantasmas cambian de estado (es cuando se vuelven azules) y cambian su



Page 5



Funciones que ganan partidas

Utiliza Matemáticas - 2013

algoritmo, para alejarse de él. A continuación vamos a ver que es el
algoritmo de Dijkstra y cómo funcionaria en este juego.

El algoritmo de Dijkstra se encarga de calcular el camino mínimo
entre dos puntos, que forman parte de un grafo, que representa el
mapa de un videojuego.

Ese camino está formando por un número de vértices unidos entre sí
por aristas de diferentes costes. Por coste nos referimos a la
distancia entre los vértices (aunque en un videojuego puede estar
definido por cualquier otro parámetro), referenciado por w(u,v); donde
“u” y “v” son los vértices.

La idea principal consiste en ir explorando todos los caminos que
parten del vértice origen (u) hasta llegar al vértice final (v) y
coger el que tenga el menor coste.

Se construye un conjunto de vértices al que se añade uno más en
cada iteración. Este conjunto (S) es el conjunto de vértices para los
que se ha obtenido un camino de longitud mínima desde el vértice de
partida (u).

Cuando añadimos a este conjunto,