Cuando trabajamos con representaciones del mundo como las
que se utilizan en los juegos de estrategia, nos interesa
tener una abstracción máxima del entorno que represente toda
la información necesaria para el correcto desarrollo, con el
mínimo espacio.

Esto se consigue con el grafo de claridad, que en cada posición
definirá a que distancia se encuentran los obstáculos de la casilla
en cuestión.

Se propone para crear este grafo el algoritmo de Brushfire o tambien
llamado Wavefront. Sin embargo, este algoritmo presenta algunos problemas
desde el punto de vista de un entorno en el que se moverán elementos
de diferente tamaño. Podemos encontrar cuellos de botella que interfieren
en el correcto desarrollo.

Debido a esto, se propone una variante del cálculo para la obtención del
grafo de claridad para diferentes tamaños de unidades. El método en cuestión
se trata de, para cada celda ir ampliando un bloque de NxN creciente hasta
colisionar con un obstáculo, es decir, hasta que en las celdas que pertenecen
al bloque incluyan algún elemento no travesable.

Vemos un ejemplo extremadamente sencillo en las siguientes imágenes donde el
tamaño del bloque crece de izquierda a derecha y de arriba a abajo.

Quedando de esta forma:

Este procedimiento solventa parcialmente el problema pero no lo resuelve completamente.
Existen, del mismo modo, puntos que no son alcanzables cuando si debieran serlo. Esto es debido
a la orientación del crecimiento de los bloques que crecen en una dirección concreta.

Para esto se propone añadir complejidad O(1) al algoritmo, que no supone un impacto excesivo
al desempeño y que consigue resultados mucho mejores. Se trata de, por un lado repetir el proceso desde
las 4 esquinas del entorno, creciendo en direcciones diferentes para cada propuesta y adquiriendo
el máximo de las distancias obtenidas, esto indica que si bien no se puede llegar desde una dirección
concreta, se puede llegar perfectamente por otra.

Con esto ya tenemos una abstracción adecuada al cálculo de nuestro problema. Conseguir un camino será cuestión
de establecer un procedimiento que respete las restricciones. Esto es lo que veremos más adelante.

Os animo a implementarlo por vuestra cuenta, se trata de un ejercicio sencillo y un buen entrenamiento!

Entramos en materia en una de las ramas de la IA aplicada a los juegos que
casi siempre está presente en los juegos de actualidad. En este caso nos centramos
en los juegos de estrategia en los que independientemente de la visión que tengamos
del mundo en el que nos movemos, generalmente se puede representar por una malla
cuadrada.

Generar una estrategia de búsqueda de caminos o pathfinding en un juego de estrategia
y en general para cualquier juego, calculando teniendo en cuenta todos los píxeles o
incluso a una resolución menor, a nivel interno por ejemplo mediante cálculos matemáticos
es una tarea tanto ineficiente como ineficaz ya que generalmente no es necesario un nivel
de precisión tan ajustado, ni siquiera a la mínima unidad que podemos medir (no calcular),
el píxel.

Lo adecuado en este caso es generar una malla que se situa sobre el entorno y que define
las posiciones que una unidad puede ocupar. Para aumentar el realismo se puede definir
un sistema de posicionamiento aleatorio que genera una posición exacta a nivel de píxel
que hace que la unidad se coloque de forma aleatoria en cualquier lugar de la malla.

Centrandonos en los juegos de estrategia nuestros algoritmos tendrán que tratar principalmente
con dos particularidades: los diferentes tamaños de unidades y los diferentes terrenos.

En cuanto a los tamaños de las unidades, para simplificar y hacer más rápidos y sencillos
nuestros algoritmos utilizaremos unidades enteras. De este modo una unidad militar puede tener
un tamaño de 1, 2 o N.

Los diferentes terrenos pueden ser por ejemplo tierra, espacio solo para unidades voladoras,
agua para vehículos acuáticos o cualquier otro tipo. Los diferentes vehículos pueden no solo
ceñirse a terreno, por ejemplo anfibios o aéreos.

El mundo se convierte en una malla como la que vemos a continuación donde cada posición de la
estructura es una posición abarcable por las unidades, en caso de que puedan moverse por el tipo
de terreno. De este modo, la representación del mundo queda definida por un conjunto de posiciones
con un tipo de terreno en cada posición. Las unidades se definen además de por sus características
usuales, por su capacidad para moverse por diferentes terrenos.

Por ejemplo. Vehículo terrestre: Movilidad { tierra }. Marine
Vehículo marino: Movilidad { agua }. Barco
Vehículo aereo: Movilidad {agua, tierra, etc}

Una vez definidos los elementos que permiten hacer el problema abarcable y manejable, nos preocuparemos
en ver que algoritmos y procedimientos nos permiten generar una trayectoria o camino válido
para las posiciones de las unidades: Grafos de ckaridad, A estrella simple, A estrella anotado,
algoritmo de Brushfire, Algoritmo A estrella Anotado Jerárquico. Hierarquical Anotated A Star (HAA*),
Pathfinding basado en grafos de claridad y búsqueda con el Algoritmo A estrella anotado jerárquico
, Planificación de caminos jerárquico para agentes de múltiples tamaños en entornos heterogéneos,
Búsqueda de caminos Jerárquica Casi óptima
o Pathfinding y funciones potenciales.

A partir de Ahora cuando vayais a comprar el pan o a hacer algun recado acordaros de dividir vuestra escena en mallas para optimizar el proceso. El procedimiento automático también es valido por eso.

Por lo pronto hasta aqui llegamos hoy. Lo demás lo veremos en detalle.

Hasta la próxima

Bueno amigos hoy una pequeña guia sobre como poner a punto el ORTS y empezar a trabajar con el.

>En primer lugar instalaremos, si no lo tenemos ya, el Visual C++.

- Descargar Visual c++ 2008 Express edition
- Instalar la distribución

Es gratuito como el resto de la versión Express, sin embargo os pedirá que registreis el producto antes de 30 dias. De cualquier forma no os costará ni un duro.

> Ahora que tenemos la IDE (Integrated Development Enviroment)
pasamos a la estructura descargar los diferentes elementos
de ORTS.

- Descarga los archivos del proyecto
- Descargar Paquete Win32

> Ponemos a punto el entorno

- 1. Copiamos los elementos a c:\orts
De este modo quedará C:\orts\trunk…

- 2. Descomprimimos el archivo anterior ‘win32.zip’ y copiamos
el contenido en C:\orts\trunk\
Tendremos entonces C:\orts\trunk\win32

- 3. Copiamos el contenido de win32\include en la carpeta
de sistema de windows System32
Descargamos glew y copiamos tambien la dll en System32
http://sourceforge.net/projects/glew/

- 4. Nos vamos a c:\orts\trunk\misk\windows
y copiamos el contenido en c:\orts\trunk\ para asegurarnos

- 5. Ejecutamos VSTool.exe (Nos pedirá la ruta a los datos)
Escribimos> c:\orts\trunk\        <– No olvidar la barra
Escribimos> tecla enter
Escribimos> orts             <– Nombre del ejecutable

- 6. Ejecutamos: c:\orts\trunk\make_vcproj.bat    (Para definir las rutas)
y creae los proyectos orts.vc7 y ortsg.vc7

- 7. Creamos la carpeta c:\orts\trunk\bin

- 8. Abrimos independientemente    orts.vc7 y ortsg.vc7 y los generamos

- 9. Vamos a buscar los ejecutables orts.exe y ortsg.exe y los pegamos
en la carpeta c:\orts\trunk
- 10. Ejecutamos, asi de facil

Puede pareces un poco laborioso a simple vista sin embargo dada la cantidad
de elementos que intervienen y la complejidad del sistema, esta es solo una
ínfima parte. De hecho el código es tan valioso desde el punto de vista ya no
del desarrollo de juegos en general sino de la inteligencia artificial, que
merece la pena dedicar los esfuerzos necesarios a poner a punto el entorno.

Al final es lo más pesado pero una vez listo ya podreis empezar a programar  todos los aspectos del juego, especialmente los que se encargan de la IA. Una vez dominado el entorno se pueden pasar a aspectos más interesantes como el pathfinding o las estrategias de batalla.

Animo con eso

…en 10 minutos y de la forma más sencilla (en windoz).

Aficcionados y profesionales del renderizado gráfico somo muy
afortunados de contar con esta gran herramienta, el Open Graphics
Rendering Enviroment (Ogre).

El Ogre nos permite un abanico infinito de posibilidades en materia
de trabajo con aplicacines que requieren renderizado 3D. Si bien no
es un motor de juego completo, se encarga principalmente del apartado
gráfico, proporciona una gran funcionalidad que hace que muchos juegos
ya lo utilicen.

Como comenta el desarrollador principal Steve Streeting, no se trata de una
solución integral sino de una especialización en el ámbito gráfico
que hace que independientemente del resto de subsistemas (motor
de física, sistemas de interfaces, topologías de red o tipos de
juego). Esto nos permite utilizar por ejemplo ODE o Bullet
(o cualquier otro vaya) para la física y Ogre para los gráficos.

Como lo ponemos a punto. Instalar facilmente todo lo necesario para
empezar a trabajar, que es lo importante de cara a aprender un sistema.
En este caso centrandonos en windows pero estando ámpliamente documentado
el resto de sistemas operativos y entornos.

> Instalacion en todos los entornos

Para ello vamos a instalar 2 elementos en el orden que se establecen.

- Visual C Express
- Ogre SDK

Una vez hecho esto, vamos a la carpeta donde hemos instalado Ogre y
ponemos a punto el entorno de trabajo.

1. Creamos una carpeta contenedora de nuestros proyectos.
Por ejemplo: ‘workspace’

2. Copiamos el contenido de la carpeta ’samples’ para empezar por los
ejemplos.

3. Ya en la carpeta ‘workspace’ creamos una carpeta con el nombre de
‘resultados’ donde pondremos los archivos generados de la compilación.

4. Dentro creamos una carpeta con nombre ‘intermedio’ para los archivos
que se generan derivados de la compilación.

5. Finalmente nos vamos a la carpeta ‘bin’ del directorio raiz donde
hemos instalado la Ogre SDK, entramos en la carpeta ‘debug’ y copiamos
todo el contenido. Lo pegamos en nuestra carpeta ‘workspace/resultados’.
Podemos copiar solamente determinados archivos pero simplificando, que
es gerundio.

Ahora que tenemos la estructura, configuramos el Visual C++.

1. Abrimos el proyecto ‘Samples_vc9.sln’

2. Actualizamos las carpetas de resultados y de intermedios

../resultados

../resultados/intermedio

3. Compilamos todo el proyecto

Generar> Generar Solución o F7

4. A partir de ahora nos centramos en uno en concreto. Por ejemplo Demo_BspCollision

5. Ejecutamos el ejemplo y a disfrutarlo

Siempre podemos encontrar algun error que nos retrase en lo que realmente
nos interesa, ponernos a trabajar lo antes posible en el entorno. Sin
embargo, una vez puesto en marcha el aprendizaje es rápido y el contenido
tremendamente interesante.

Hasta la próxima

Hola amigos,

Que se espera de alguien que vaya a encargarse de la inteligencia
artificial de un juego de estrategia en tiempo real (Real Time
Strategy). Pues bien, eso es lo que vamos a ver de forma muy resumida
en este apartado. Progresivamente nos iremos poniendo en materia y
profundizando en los diferentes aspectos.

Cuando hablo de programar la IA de juegos RTS me ciño al más puro
aspecto académico, es decir, a la búsqueda de conocimiento basado
en cálculos y algoritmos que simulan una situación ‘real’ o si más
no factible. ¿A qué me refiero con esto? La IA de los juegos comerciales
debe en muchas ocasiones (por no decir en la práctica totalidad) hacer
determinadas trampas o acceder a información que el usuario desconoce
con la finalidad de ser realmente competitiva.

Por ejemplo, la IA puede conocer la posición de todas las unidades aunque
estas esten en una zona de niebla de guerra (o warfog). Puede conocer
las órdenes que el jugador da a sus unidades o incluso el tipo de las
mismas, para centrarse en construir ella misma las que mejor pueden
desenvolverse en caso de que ataque o de recibir un ataque. Puede
también incrementar la velocidad de minado o incluso los recursos reales de
los que dispone. Con esto, se generan IA’s altamente competitivas pero
que a la hora de la verdad, NO están resolviendo problemas a situacioens
reales y por lo tanto interesan solo desde el punto de vista comercial
pero no desde el científico. Es por eso que estas prácticas se rechazan
y se dejan como elementos a implementar en determinadas aplicaciones.

Nosotros nos centraremos en estudiar diferentes áreas como:
- Razonamiento de los sistemas
- Planificación de estrategias
- Aprendizaje o machine learning
- Pathfinding o búsqueda de caminos
- Cooperación o sistemas multiagente

Entre otras. Pasando a la plataforma Open Real Time Strategy (ORTS),
estamos en un entorno de juego real donde creamos y gestionamos ejercitos,
disponemos de movimiento en tiempo real(Real time object motion en 2.5D),
tratamos con información imperfecta (niebla, desconocimiento de los recursos
del oponente, detalles de unidades enemigas …etc), recursos y árbol
de tecnología. Con esto tenemos juego más que de sobra para aplicar muchos
de los conceptos de inteligencia artificial que nos interesan.

Los objetivos ahora serán:
- Poner a punto el entorno.
- Compilar el proyecto.
- Ver la estructura general del mismo.
- Empezar a profundizar en los detalles.

En próximos artículos pondremos veremos como poner a punto el entorno
y empezaremos a trabajar con este juego de estrategia real con el mismo
entorno que tendriais que utilizar si trabajaseis como programadores
de inteligencia artificial para videojuegos.

Diversión y aprendizaje garantizados. ¿Quien ha dicho que los juegos
no valen para nada? Por lo pronto ya facturan más que la industria del cine.
Un buen aliciente para aquellos que disfrutamos creando puesto que habrán muchas inversiones
y muchos proyectos en los que trabajar. La próxima vez que alguien os
diga que estais demasiado enganchados a los juegos la respuesta es clara…
…lo siento, soy adicto al trabajo!

Hasta nueva vista.

Hola amigos,

Hoy tengo el placer de presentaros un proyecto que hará las  delicias de muchos aficcionados y profesionales de la inteligencia artificial aplicada a los videojuegos. Se trata del Open Source Real Tyme Strategy (ORTS) que actualmente desarrolla un equipo de investigadores del grupo de Games Research del Departamento de Tecnologías de la Información de la Universidad de Alberta.

Todo un lujo ya que trabajan tanto en la IA aplicada a los juegos clásicos como la aplicada a los grandes juegos comerciales. Una interesante mezcla del rigor académico y las grandes posibilidades de los sistemas actuales del entorno comercial.

Aunque hoy vamos a ver un juego de estrategia en tiempo real, no dejeis de echarle un vistazo a la web del grupo. Poker, ajedrez e incluso ‘go’ que es un juego difícil de trabajar con él en materia de inteligencia artificial. Uno de los integrantes Michael Buro, creador de ORTS, es el constructor de un programa de Othello que venció al campeón mundial del juego por 6 a 0.

El proyecto ORTS empieza en el año 2003 con la finalidad de crear un sistema cliente-servidor para el desarrollo de técnicas de Inteligencia Artificial en juegos interactivos de estrategia en tiempo real. El resultado es Open Real Time Strategy.

Elementos de ORTS

Base

En este juego varias facciones disponen sus unidades sobre el campo de batalla y se encargan de  hacer crecer sus recursos.  La finalidad es acabar con el oponente. Un ejemplo de juego es el que vemos a continuación:

Hay mucha documentación al respecto que podemos encontrar en la red. Además se ha documentado de forma exhaustiva la estructura del código por lo que no es muy difícil empezar a probar algunas cosas. En posteriores artículos nos adentraremos aún más en el mundo de ORTS que promete ser muy enriquecedor.

Hoy todos los interesados en la IA que no conocierais el proyecto acabais de conseguir un juguete muy pero que muy elaborado y tan divertivo o más que cualquier otro que nos pueda caer en navidad.

Ya tenemos un punto de vista distribuido en cuanto a las aplicaciones que podemos utilizar para adentrarnos en el mundo de la IA para videojuegos. Ahora es tiempo de profundizar en aspectos más interesantes y en conceptos propios de los problemas que nos encontramos a la hora de trabajar en esta área.

Hasta la próxima

Para la mayoría de los jugones veteranos el Quake ha sido una fuente de alegrías continuas. Para los que no lo conozcáis, el Q3 es un juego de acción shooter primera persona creado por Id Software donde la finalidad es competir contra bots o contra otros jugadores en el modo multiplayer en mapas en los que se distribuyen armas a punta pala. La acción está garantizada.

Quake I

Quake II

Quake III

En este juego no faltan las máquinas humanas capaces de realizar proezas con el armamento. En el video a continuación se muestra un fragmento homenaje de uno de esos sujetos.

Lo realmente interesante desde nuestro punto de vista es el hecho de que el código haya sido publicado por completo. Sin embargo, no todo el material fue distribuido por lo que el juego no era completo. Desde este panorama surge la iniciativa de los chicos de Open Arena mediante la que con el motor de juego del Quake III Arena se han ido creando contenidos y modos de juego.

Lo que nos llama la atención es el hecho de poder  trabajar con la IA del juego. Existen numerosas iniciativas y comentarios al respecto como los que vemos en Aigamedev o PlanetQuake.

Para empezar a trabajar con él debemos:

• Primero Descargar el código fuente.
• Y segundo Conseguir la versión completa o demos oficiales.
• Adicionalmente conseguir la versión de Open Arena.

Iremos viendo poco a poco la forma de profundizar en el desarrollo de la inteligencia artificial para Quake 3.

Otra interesante iniciativa es la Quake 3 Brainworks mediante la que se ha organizado el desarrollo de la reescritura completa de la IA para los bots.

Entre las características que se han creado están:

• Sistema de Percepción Visual y Auditiva
• Esquivando aleatorios en las batallas.
• Evasión de misiles.
• Habilidad de juego por saltos. Strafejumping.
• Puntería del enemigo mejorada.
• Selección inteligente de recogida de items.
• Gestión del tiempo de las reapariciones.
• Selección dinámica del arma.
• Selección de metas redefinida.
• Selección de apuntado redefinida.
• Lógica de juego en equipo redefinida.
• Código de chat reescrito.
• Infraestructura lógica interna redefinida.

Y además se han definido bots con 5 niveles de habilidad

• Skill 1: Alguien que ha jugado a Q3A durante menos de 2 semanas.
• Skill 2: Alguien que ha jugado a Q3A durante 3 meses.
• Skill 3: Media de un jugador en un servidor público.
• Skill 4: El mejor jugador de un servidor público.
• Skill 5: Jugador de clan profesional que compite en torneos.

Echadle un vistazo, no os arrepentireis!