Introduccion

Este artículo le presentará una amplia gama de conceptos de inteligencia artificial en juegos ("IA de juegos"), para que comprenda qué herramientas se pueden usar para resolver problemas de IA, cómo funcionan juntas y cómo comenzar a implementarlas en el motor seleccionado.

Asumiré que estás familiarizado con los videojuegos, un poco versado en conceptos matemáticos como geometría, trigonometría, etc. La mayoría de los ejemplos de código se escribirán en pseudocódigo, por lo que no necesita saber un idioma específico.

¿Qué es una "IA de juegos"?

Game AI se ocupa principalmente de la selección de acciones de una entidad en función de las condiciones actuales. En la literatura tradicional sobre IA, se denomina gestión de " agentes inteligentes ". El agente suele ser un personaje en el juego, pero puede ser una máquina, un robot o incluso algo más abstracto: un grupo completo de entidades, un país o una civilización. En cualquier caso, es un objeto que monitorea su entorno, toma decisiones basadas en él y actúa de acuerdo con estas decisiones. Esto a veces se llama ciclo de percepción-pensamiento-acción (Sentido / Pensar / Actuar):

• Percepción: el agente reconoce, o se le informa al respecto, información sobre el medio ambiente que puede afectar su comportamiento (por ejemplo, peligros cercanos, elementos recolectados, puntos importantes, etc.)
• Pensamiento: el agente decide cómo responder (por ejemplo, decide si es seguro recolectar objetos, si debería pelear o mejor esconderse primero)
• Acción: el agente realiza acciones para implementar sus decisiones (por ejemplo, comienza a moverse a lo largo de la ruta hacia el enemigo o hacia el sujeto, etc.)
• ... luego, debido a las acciones de los personajes, la situación cambia, por lo que el ciclo debe repetirse con nuevos datos.

Las tareas de IA del mundo real, especialmente las que son relevantes hoy en día, generalmente se centran en la "percepción". Por ejemplo, los vehículos no tripulados deben recibir imágenes de la carretera frente a ellos, combinándolos con otros datos (radar y lidar) e intentando interpretar lo que ven. Por lo general, esta tarea se resuelve mediante el aprendizaje automático, que funciona especialmente bien con grandes conjuntos de datos ruidosos del mundo real (por ejemplo, con fotos de la carretera frente al automóvil o unos pocos cuadros de video) y les da algo de significado, extrayendo información semántica, por ejemplo, “hay 20 yardas frente a mí otro coche ". Tales tareas se llaman problemas de clasificación .

Los juegos son inusuales ya que no necesitan un sistema complejo para extraer esta información, ya que es una parte integral de la simulación. No hay necesidad de realizar algoritmos de reconocimiento de imágenes para detectar al enemigo frente a ti; el juego sabe que hay un enemigo y puede transmitir esta información directamente al proceso de toma de decisiones. Por lo tanto, la "percepción" en este ciclo generalmente se simplifica enormemente, y toda la complejidad surge en la implementación del "pensamiento" y la "acción".

Limitaciones de desarrollo de IA de juego

Gaming AI generalmente tiene en cuenta las siguientes restricciones:

• A diferencia del algoritmo de aprendizaje automático, generalmente no se entrena por adelantado; al desarrollar un juego, no es práctico escribir una red neuronal para monitorear a decenas de miles de jugadores para encontrar la mejor manera de jugar contra ellos, porque el juego aún no se ha lanzado y no tiene jugadores.
• Por lo general, se supone que el juego debe entretener y desafiar al jugador, y no ser "óptimo"; por lo tanto, incluso si puede entrenar agentes para resistir a los jugadores de la mejor manera, la mayoría de las veces los diseñadores necesitan algo diferente de ellos.
• A menudo se requiere que los agentes tengan un comportamiento "realista" para que los jugadores sientan que están compitiendo con oponentes similares a los humanos. El programa AlphaGo resultó ser mucho mejor que las personas, pero los movimientos que elige están tan lejos de la comprensión tradicional del juego que los oponentes experimentados hablaron de él como un juego contra un extraterrestre. Si el juego pretende ser un oponente humano, entonces esto generalmente no es deseable, por lo que el algoritmo debe configurarse para que tome decisiones plausibles , no ideales .
• La IA debe ejecutarse en tiempo real. En este contexto, esto significa que el algoritmo no puede, por decisión, monopolizar los recursos del procesador durante mucho tiempo. Incluso 10 milisegundos para tomar una decisión es demasiado, porque la mayoría de los juegos tienen solo 16-33 milisegundos para completar todas las operaciones para el siguiente cuadro del gráfico.
• Idealmente, al menos parte del sistema debería depender de los datos, y no estar codificado para que los no programadores puedan hacer cambios más rápido.

Después de haber aprendido todo esto, podemos comenzar a considerar enfoques extremadamente simples para la creación de IA, que implementan todo el ciclo de "percepción-pensamiento-acción" de manera que garantice la eficiencia y permita a los diseñadores de juegos elegir comportamientos complejos similares a las acciones humanas.

Fácil toma de decisiones

Comencemos con un juego muy simple, como Pong. La tarea del jugador es mover la "raqueta" para que la pelota rebote, en lugar de pasar volando. Las reglas son similares al tenis: pierdes si pierdes la pelota. La IA tiene una tarea relativamente simple de tomar decisiones sobre la elección de la dirección del movimiento de la raqueta.

Construcciones condicionales codificadas

Si quisiéramos escribir AI para controlar la raqueta, entonces hay una solución intuitiva y simple: simplemente mueva constantemente la raqueta para que quede debajo de la pelota. Cuando la pelota llega a la raqueta, ya está en posición perfecta y puede golpearla.

Un algoritmo simple para esto, expresado en pseudocódigo, podría ser:

  en cada cuadro / actualización mientras se ejecuta el juego:

 si la pelota está a la izquierda de la raqueta:

	 mueve la raqueta hacia la izquierda

 de lo contrario si la pelota está a la derecha de la raqueta:

	 mueve la raqueta hacia la derecha 

Si suponemos que la raqueta puede moverse a no menos velocidad que la pelota, entonces este será el algoritmo perfecto para el jugador de IA en Pong. En los casos en que no haya tantos datos de "percepción" para el procesamiento y pocas acciones que el agente pueda realizar, no necesitamos nada más complicado.

Este enfoque es tan simple que apenas muestra el ciclo completo de "percepción-pensamiento-acción". Pero el es .

• Las percepciones son dos si las declaraciones. El juego sabe dónde están la pelota y la raqueta. Por lo tanto, la IA pregunta al juego por su posición, por lo tanto, "siente" si la pelota está a la izquierda o a la derecha.
• El pensamiento también está integrado en dos declaraciones if. Contienen dos soluciones, que en este caso son mutuamente excluyentes, lo que lleva a la elección de una de tres acciones: mover la raqueta hacia la izquierda, moverla hacia la derecha o no hacer nada si la raqueta ya está ubicada correctamente.
• Una "acción" es "mover la raqueta hacia la izquierda" o "mover la raqueta hacia la derecha". Dependiendo de cómo se implemente el juego, esto puede tomar la forma de mover instantáneamente la posición de la raqueta o establecer la velocidad y la dirección de la raqueta para que pueda cambiarse correctamente en otro código del juego.

Tales enfoques a menudo se denominan "reactivos" porque hay un conjunto simple de reglas (en nuestro caso, estas son declaraciones "si" en el código) que responden al estado del mundo y deciden instantáneamente cómo proceder.

Árboles de decisión

Este ejemplo de Pong es en realidad similar al concepto formal de IA llamado el árbol de decisión . Este es un sistema en el que las decisiones se organizan en forma de árbol y el algoritmo debe rodearse para llegar a una "hoja" que contenga la decisión final sobre la acción elegida. Dibujemos una representación gráfica del árbol de decisión para el algoritmo de raqueta Pong usando un diagrama de flujo:


Se puede ver que se parece a un árbol, ¡solo al revés!

Cada parte del árbol de decisión generalmente se denomina "nodo" porque en AI, la teoría de grafos se usa para describir tales estructuras. Cada nodo puede ser uno de dos tipos:

1. Nodos de soluciones: la elección de dos alternativas basadas en la verificación de una condición. Cada alternativa se presenta como su propio nodo;
2. Nodos finales: una acción realizada que representa la decisión final tomada por el árbol.

El algoritmo comienza desde el primer nodo asignado por la "raíz" del árbol, después de lo cual decide a qué nodo secundario ir en función de la condición o realiza la acción almacenada en el nodo, y luego deja de funcionar.

A primera vista, la ventaja del árbol de decisión no es obvia, ya que hace exactamente el mismo trabajo que las declaraciones if de la sección anterior. Pero hay un sistema muy general en el que cada solución tiene exactamente 1 condición y 2 resultados posibles, lo que le permite al desarrollador construir AI a partir de los datos que representan las soluciones en el árbol, y evita escribirlo en el código. Es fácil imaginar un formato de datos simple para describir dicho árbol:

Número de nodo	Decisión (o "fin")	Acción	Acción
1	¿La pelota a la izquierda de la raqueta?	¿Eh? Comprobar nodo 2	No? Comprobar nodo 3
2	El final	Mueve la raqueta hacia la izquierda
3	¿La pelota a la derecha de la raqueta?	¿Eh? Ir al nodo 4	No? Ir al nodo 5
4 4	El final	Mueve la raqueta hacia la derecha
5 5	El final	No hacer nada

Desde el punto de vista del código, necesitamos forzar al sistema a leer cada una de estas filas, crear para cada nodo, adjuntar la lógica de decisión basada en la segunda columna y adjuntar nodos secundarios basados ​​en la tercera y cuarta columna. Todavía necesitamos definir manualmente las condiciones y acciones, pero ahora podemos imaginar un juego más complejo en el que puede agregar nuevas soluciones y acciones, así como configurar toda la IA cambiando el único archivo de texto que contiene la definición del árbol. Podemos transferir el archivo al diseñador del juego, que podrá personalizar el comportamiento sin la necesidad de volver a compilar el juego y cambiar el código, siempre que el código ya tenga condiciones y acciones útiles.

Los árboles de decisión pueden ser muy potentes cuando se construyen automáticamente en función de una gran cantidad de ejemplos (por ejemplo, utilizando el algoritmo ID3 ). Los convierte en una herramienta efectiva y de alto rendimiento para clasificar la situación en función de los datos entrantes, pero este tema está más allá del alcance de los diseñadores para crear sistemas simples para seleccionar acciones para los agentes.

Scripting

Arriba, examinamos un sistema de árbol de decisión que usa condiciones y acciones pre-creadas. El desarrollador de IA puede reconstruir el árbol de cualquier forma que necesite, pero debe confiar en el hecho de que el programador ya ha creado todas las condiciones y acciones necesarias para él. Pero, ¿qué pasa si le damos al diseñador herramientas más poderosas que le permiten crear sus propias condiciones y quizás sus acciones?

Por ejemplo, en lugar de obligar al codificador a escribir las condiciones "¿Bola a la izquierda de la raqueta?" y "¿La pelota a la derecha de la raqueta?", simplemente puede crear un sistema en el que el diseñador escriba independientemente las condiciones para verificar estos valores. Como resultado, los datos del árbol de decisión pueden verse así:

Número de nodo	Decisión (o "fin")	Solución	Acción
1	ball.position.x <paddle.position.x	¿Eh? Comprobar nodo 2	No? Comprobar nodo 3
2	El final	Mueve la raqueta hacia la izquierda
3	ball.position.x> paddle.position.x	¿Eh? Comprobar nodo 4	No? Comprobar nodo 5
4 4	El final	Mueve la raqueta hacia la derecha
5 5	El final	No hacer nada

Lo mismo que antes, pero ahora las soluciones tienen su propio código, similar a la parte condicional de la declaración if. El código leerá los nodos de decisión de la segunda columna y, en lugar de buscar una condición específica (por ejemplo, “¿la pelota a la izquierda de la raqueta?”), Calcule la expresión condicional y devuelva verdadero o falso. Esto se puede implementar incorporando un lenguaje de scripting , como Lua o Angelscript, que permite al desarrollador tomar objetos del juego (por ejemplo, una pelota y una raqueta) y crear variables accesibles desde el script (por ejemplo, ball.position). Por lo general, es más fácil escribir en un lenguaje de secuencias de comandos que en C ++, y no requiere una etapa de compilación completa, por lo tanto, es muy adecuado para realizar cambios rápidos en la lógica del juego y permite que los miembros del equipo con menos conocimientos técnicos creen funciones del juego sin la intervención de un codificador.

En el ejemplo anterior, el lenguaje de secuencias de comandos se usa solo para evaluar la expresión condicional, pero las acciones finales también se pueden describir en la secuencia de comandos. Por ejemplo, estas acciones del tipo "mover la raqueta hacia la derecha" pueden convertirse en una construcción de script como ball.position.x += 10 , es decir, la acción también se establece en el script sin escribir el código de función MovePaddleRight.

Si da otro paso adelante, puede (y esto se hace a menudo) ir a su conclusión lógica y escribir todo el árbol de decisión en un lenguaje de script, y no como una lista de líneas de datos. Este será un código similar a las construcciones condicionales que se muestran arriba, solo que no están "codificadas"; están en archivos de script externos, es decir, se pueden cambiar sin recompilar todo el programa. A menudo, incluso es posible modificar el archivo de script durante la ejecución del juego, lo que permite a los desarrolladores probar rápidamente varios enfoques para la implementación de IA.

Reacción a eventos

Los ejemplos que se muestran arriba están destinados a la ejecución de un solo cuadro en juegos simples como Pong. La idea es que continuamente realicen un ciclo de "percepción-pensamiento-acción" y continúen actuando sobre la base del último estado del mundo. Pero en los juegos más complejos, en lugar de la informática, a menudo es más razonable reaccionar a los "eventos", es decir, a cambios importantes en el entorno del juego.

Esto no es particularmente aplicable a Pong, así que escojamos otro ejemplo. Imagine un juego de disparos en el que los enemigos están inmóviles hasta que encuentran un jugador, después del cual comienzan a realizar acciones dependiendo de su clase: los luchadores cuerpo a cuerpo pueden apresurarse hacia el jugador, y los francotiradores se mantienen a distancia e intentan apuntar. En esencia, este es un sistema reactivo simple: "si vemos a un jugador, entonces hacemos algo", pero se puede dividir lógicamente en un evento ("ver a un jugador") y reacción (seleccionar una respuesta y ejecutarla).

Esto nos lleva de vuelta al ciclo de percepción-pensamiento-acción. Es posible que tengamos un fragmento de código, que es un código de "percepción", que verifica en cada cuadro si el enemigo ve al jugador. Si no, entonces no pasa nada. Pero si él ve, esto crea un evento "ver al jugador". El código tendrá una parte separada, que dice: "cuando ocurre el evento" ver al jugador ", entonces hacemos" xyz ", y" xyz "es cualquier respuesta que queramos para procesar el pensamiento y la acción. Para un luchador de personajes, puedes conectar la respuesta de correr y atacar al evento "ver al jugador". Para el francotirador, conectaremos la función de respuesta "ocultar y apuntar" a este evento. Como en los ejemplos anteriores, podemos crear tales asociaciones en el archivo de datos para que puedan cambiarse rápidamente sin reconstruir el motor. Además, es posible (y esto se usa a menudo) escribir tales funciones de respuesta en un lenguaje de script para que puedan crear soluciones complejas cuando ocurren eventos.

Toma de decisiones mejorada

Aunque los sistemas reactivos simples son muy potentes, hay muchas situaciones en las que no son suficientes. Algunas veces necesitamos tomar decisiones diferentes basadas en lo que el agente está haciendo en este momento, y presentarlo como una condición es inconveniente. A veces, simplemente hay demasiadas condiciones para presentarlas efectivamente en forma de árbol de decisiones o script. A veces necesitamos pensar con anticipación y evaluar cómo cambiará la situación antes de decidir el próximo movimiento. Para tales tareas se necesitan soluciones más complejas.

Máquinas de estado

Una máquina de estados finitos (FSM) es una manera de decir en otras palabras que algún objeto, por ejemplo, uno de nuestros agentes de IA, se encuentra actualmente en uno de varios estados posibles, y que puede pasar de De un estado a otro. Hay un número finito de tales estados, de ahí el nombre. Un ejemplo del mundo real es el conjunto de semáforos, que cambia de rojo a amarillo, luego a verde, y nuevamente. En diferentes lugares hay diferentes secuencias de luces, pero el principio es el mismo: cada estado significa algo ("estar de pie", "comer", "estar de pie, si es posible", etc.), en un momento dado solo hay un estado, y Las transiciones entre ellas se basan en reglas simples.

Esto se aplica bien a los NPC en los juegos. El guardia puede tener los siguientes estados claramente separados:

• Patrulla
• Asalto
• Vuelo

Y podemos llegar a las siguientes reglas para la transición entre estados:

• Si el guardia ve al enemigo, ataca
• Si el guardia ataca, pero ya no ve al enemigo, vuelve a patrullar.
• Si un guardia ataca pero resulta gravemente herido, escapa

Este esquema es bastante simple y podemos escribirlo con operadores "si" estrictamente definidos y una variable en la que se almacenará el estado del guardia de seguridad y varios controles: la presencia de enemigos cercanos, el nivel de salud del guardia de seguridad, etc. Pero imagine que necesitamos agregar algunos estados más:

• Esperando (entre patrullas)
• Buscar (cuando el enemigo visto anteriormente se escondió)
• Escape en busca de ayuda (cuando se ve al enemigo, pero es demasiado fuerte para luchar solo con él)

Y las opciones disponibles en cada estado generalmente son limitadas; por ejemplo, un guardia probablemente no querrá buscar a un enemigo que se haya perdido de vista si su salud es demasiado baja.

Tarde o temprano, la larga lista de "si <x e y pero no z> entonces <p>" se vuelve demasiado incómoda, y un enfoque formal para la implementación de estados y transiciones entre ellos puede ayudar aquí. Para hacer esto, consideramos todos los estados y en cada estado enumeramos todas las transiciones a otros estados junto con las condiciones necesarias para ellos. También debemos indicar el estado inicial para que sepamos por dónde empezar antes de aplicar otras condiciones.

Condición	Condición de transición	Nueva condición
Esperando	esperado por 10 segundos	Patrulla
	el enemigo es visible y el enemigo es demasiado fuerte	Búsqueda de ayuda
	el enemigo es visible y mucha salud	Asalto
	el enemigo es visible y poca salud	Vuelo
Patrulla	ruta de patrulla completada	Esperando
	el enemigo es visible y el enemigo es demasiado fuerte	Búsqueda de ayuda
	el enemigo es visible y mucha salud	Asalto
	el enemigo es visible y poca salud	Vuelo
Asalto	el enemigo no es visible	Esperando
	poca salud	Vuelo
Vuelo	el enemigo no es visible	Esperando
Buscar	buscado por 10 segundos	Esperando
	el enemigo es visible y el enemigo es demasiado fuerte	Búsqueda de ayuda
	el enemigo es visible y mucha salud	Asalto
	el enemigo es visible y poca salud	Vuelo
Búsqueda de ayuda	amigo ve	Asalto
Estado inicial: esperando

Tal esquema se llama tabla de transición de estado. Es una forma compleja (y poco atractiva) de representar una nave espacial. A partir de estos datos, también puede dibujar un diagrama y obtener una representación gráfica compleja de cómo podría ser el comportamiento de los NPC.


Captura la esencia misma de tomar decisiones para el agente en función de la situación en la que se encuentra. Cada flecha indica una transición entre estados si la condición al lado de la flecha es verdadera.

Con cada actualización (o "ciclo"), verificamos el estado actual del agente, miramos la lista de transiciones y, si se cumple la condición de transición, pasamos a un nuevo estado. El estado Pendiente verifica en cada cuadro o ciclo si el temporizador de 10 segundos ha expirado. Si caduca, comienza la transición al estado "Patrulla". De manera similar, el estado "Ataque" verifica si el agente tiene mucha salud y, de ser así, realiza la transición al estado "Vuelo".

Así es como se manejan las transiciones de estado, pero ¿qué pasa con los comportamientos asociados con los propios estados? Desde el punto de vista de realizar las acciones en sí para un estado, generalmente hay dos tipos de acciones adjuntas a una nave espacial:

1. Las acciones para el estado actual se realizan periódicamente, por ejemplo, en cada cuadro o "ciclo".
2. Las acciones se realizan durante la transición de un estado a otro.

Un ejemplo del primer tipo: el estado de "Patrulla" en cada cuadro o ciclo continúa moviendo al agente a lo largo de la ruta de patrulla. El estado de "Ataque" en cada cuadro o ciclo intenta lanzar un ataque o moverlo a una posición desde donde sea posible. Y así sucesivamente.

Un ejemplo del segundo tipo: considere la transición "si el enemigo es visible y el enemigo es demasiado fuerte → Busque ayuda". El agente debe elegir dónde moverse para buscar ayuda y almacenar esta información para que el estado de "Búsqueda de ayuda" sepa a dónde ir. De manera similar, en el estado "Búsqueda de ayuda", cuando se encuentra ayuda, el agente vuelve al estado "Ataque" nuevamente, pero en este momento quiere informar al personaje amigo sobre la amenaza, por lo que puede haber una acción "decirle a un amigo sobre el peligro" realizada durante esta transición.

Y aquí podemos considerar nuevamente este sistema desde el punto de vista de "percepción-pensamiento-acción". La percepción está incrustada en los datos utilizados por la lógica de transición. El pensamiento está integrado en las transiciones disponibles para cada estado. Y la acción se realiza mediante acciones realizadas periódicamente en un estado o durante la transición entre estados.

Este sistema simple funciona bien, aunque a veces las condiciones de transición de sondeo constante pueden ser un proceso costoso. Por ejemplo, si cada agente necesita realizar cálculos complejos en cada cuadro para determinar la visibilidad de los enemigos y decidir la transición de la patrulla al ataque, esto puede llevar mucho tiempo de procesador. Como vimos anteriormente, es posible percibir cambios importantes en el estado del mundo como "eventos" que se procesan después de que ocurrieron. Por lo tanto, en lugar de verificar explícitamente la condición de transición "¿mi agente puede ver al jugador?" En cada cuadro, podemos crear un sistema de visibilidad separado que realice estas comprobaciones con menos frecuencia (por ejemplo, 5 veces por segundo) y cree el "jugador ver "cuando se activa la prueba. Se transmite a la máquina de estado, que ahora tiene la condición para la transición "Recibió el evento" jugador que ve "", y que responde en consecuencia. El comportamiento resultante será similar, con la excepción de un retraso de reacción apenas notable (e incluso realismo creciente), pero la productividad aumentará debido a la transferencia de "percepción" a una parte separada del programa.

Máquinas de estado jerárquico

Todo esto es bueno, pero con máquinas de estado grandes resulta muy inconveniente trabajar. Si queremos expandir el estado de "Ataque" reemplazándolo con estados separados de "Ataque cuerpo a cuerpo" y "Ataque desde lejos", entonces tendremos que cambiar las transiciones entrantes de cada estado, presente y futuro, que necesita la capacidad de cambiar al estado de "Ataque".

Probablemente también haya notado que en nuestro ejemplo hay muchas transiciones duplicadas. La mayoría de las transiciones en el estado "Pendiente" son idénticas a las transiciones en el estado "Patrulla", y sería bueno evitar la duplicación de este trabajo, especialmente si queremos agregar aún más estados similares. Será lógico combinar "Esperando" y "Patrullar" en algún grupo de "Estados que no sean de combate", que solo tiene un conjunto común de transiciones para combatir estados. Si presentamos a este grupo como un estado, podemos considerar la "espera" y el "patrullaje" como "subestados" de este estado, lo que nos permitirá describir de manera más efectiva todo el sistema. Un ejemplo de uso de una tabla de conversión separada para un nuevo subestado que no es de combate:

Las principales condiciones:

Condición	Condición de transición	Nueva condición
No combate	el enemigo es visible y el enemigo es demasiado fuerte	Búsqueda de ayuda
	el enemigo es visible y mucha salud	Asalto
	el enemigo es visible y poca salud	Vuelo
Asalto	el enemigo no es visible	No combate
	poca salud	Vuelo
Vuelo	el enemigo no es visible	No combate
Buscar	buscado por 10 segundos	No combate
	el enemigo es visible y el enemigo es demasiado fuerte	Búsqueda de ayuda
	el enemigo es visible y mucha salud	Asalto
	el enemigo es visible y poca salud	Vuelo
Búsqueda de ayuda	amigo ve	Asalto
Estado inicial: no combate

Estado sin combate:

Condición	Condición de transición	Nueva condición
Esperando	esperado por 10 segundos	Patrulla
Patrulla	completado la ruta de patrulla	Esperando
Estado inicial: esperando

Y en forma de gráfico:


De hecho, este es el mismo sistema, solo que ahora hay un estado sin combate que reemplaza a "Patrulla" y "Espera", que en sí mismo es una máquina de estado con dos subestados de patrullaje y espera. Si cada estado puede contener potencialmente una máquina de estados de subestados (y estos subestados también pueden contener su propia máquina de estados, etc.), entonces tenemos una máquina de estados jerárquica (HFSM). Al agrupar los comportamientos que no son de combate, cortamos un montón de transiciones innecesarias, y podemos hacer lo mismo para cualquier estado nuevo que pueda tener transiciones comunes. Por ejemplo, si en el futuro expandimos el estado de "Ataque" a los estados de "Ataque cuerpo a cuerpo" y "Ataque de proyectil", pueden ser subestados, cuya transición se basa en la distancia al enemigo y la presencia de municiones, que tienen transiciones de salida comunes basadas en niveles de salud y otras cosas Por lo tanto, con un mínimo de transiciones duplicadas, se pueden representar comportamientos y subcomportamientos complejos.

Árboles de comportamiento

Con HFSM, tenemos la capacidad de crear conjuntos de comportamientos bastante complejos de una manera bastante intuitiva. Sin embargo, se nota de inmediato que la toma de decisiones en forma de reglas de transición está estrechamente relacionada con el estado actual. Muchos juegos requieren solo eso. Y el uso cuidadoso de la jerarquía de estado reduce el número de transiciones duplicadas. Pero a veces necesitamos reglas que se apliquen independientemente del estado actual, o que se apliquen en casi todos los estados. Por ejemplo, si la salud del agente se ha reducido al 25%, es posible que quiera huir, independientemente de si está en batalla, o está esperando, hablando, o está en cualquier otro estado. No queremos recordar que necesitamos agregar esta condición a cada estado que podamos agregar al personaje en el futuro. Entonces, cuando el diseñador más tarde dice que quiere cambiar el valor del umbral del 25% al ​​10%, no tendríamos que clasificar y cambiar cada transición correspondiente.

Lo ideal en tal situación era un sistema en el que las decisiones sobre en qué estado estar existieran por separado de los estados mismos, de modo que podamos cambiar solo un elemento, y las transiciones aún se procesen correctamente. Aquí es donde los árboles de comportamiento son útiles.

Hay varias formas de implementar árboles de comportamiento, pero la esencia es la misma para la mayoría y muy similar al árbol de decisión mencionado anteriormente: el algoritmo comienza a funcionar desde el "nodo raíz", y hay nodos en el árbol que indican decisiones o acciones. Sin embargo, hay diferencias clave:

• Los nodos ahora devuelven uno de los tres valores: "exitoso" (si el trabajo se completó), "sin éxito" (si el trabajo no se completó) o "realizado" (si el trabajo todavía se está completando y no tuvo éxito o no fue completamente exitoso).
• Ahora no tenemos nodos de decisión en los que elegimos entre dos alternativas, pero hay nodos decoradores con un solo nodo hijo. Si tienen "éxito", ejecutan su único nodo hijo. Los nodos decoradores a menudo contienen condiciones que determinan si la ejecución finalizó con éxito (lo que significa que debe ejecutar su subárbol) o falla (entonces no es necesario hacer nada). También pueden regresar "en progreso".
• Las acciones que realizan los nodos devuelven un valor de "ejecución" para indicar lo que está sucediendo.

Se puede combinar un pequeño conjunto de nodos, creando una gran cantidad de comportamientos complejos, y a menudo este esquema es muy breve. Por ejemplo, podemos reescribir la CA jerárquica de la guardia del ejemplo anterior en forma de árbol de comportamiento:


Cuando se usa esta estructura, no hay necesidad de una transición explícita de los estados de "Espera" o "Patrulla" a los estados de "Ataque" o cualquier otro: si el árbol se atraviesa de arriba a abajo y de izquierda a derecha, la decisión correcta se toma en función de la situación actual. Si el enemigo es visible y el personaje tiene poca salud, entonces el árbol completará la carrera en el nodo "Vuelo", independientemente del nodo completado anteriormente ("Patrulla", "Esperando", "Ataque", etc.).

Puede notar que todavía no tenemos una transición para regresar al estado "En espera" de "Patrulla", y aquí los decoradores incondicionales serán útiles. El nodo decorador estándar es "Repetir": no tiene condiciones, solo intercepta el nodo secundario que regresa "exitosamente" y ejecuta el nodo secundario nuevamente, regresando "ejecutado". El nuevo árbol se ve así:


Los árboles de comportamiento son bastante complejos porque a menudo hay muchas formas diferentes de crear un árbol, y encontrar la combinación correcta de decorador y nodos componentes puede ser una tarea desalentadora. También hay problemas con la frecuencia con la que necesitamos verificar el árbol (¿queremos atravesarlo cada cuadro o cuando sucede algo que puede afectar las condiciones?) Y cómo almacenar el estado en relación con los nodos (¿cómo sabemos que esperamos 10 segundos? ¿Cómo ¿descubriremos cuántos nodos se ejecutaron por última vez para completar correctamente la secuencia?) Por lo tanto, hay muchas implementaciones diferentes. Por ejemplo, en algunos sistemas, como el sistema de árbol de comportamiento Unreal Engine 4, los nodos decoradores se reemplazan con decoradores de cadenas que verifican el árbol solo cuando cambian las condiciones del decorador y proporcionan "servicios",que se puede conectar a nodos y proporcionar actualizaciones periódicas incluso cuando el árbol no se vuelve a comprobar. Los árboles de comportamiento son herramientas poderosas, pero aprender a usarlos correctamente, especialmente con tantas implementaciones diferentes, puede ser una tarea desalentadora.

Sistemas Basados ​​en Utilidades

Algunos juegos requieren la existencia de muchas acciones diferentes, por lo que requieren reglas de transición más simples y centralizadas, pero no necesitan el poder para implementar completamente el árbol de comportamiento. En lugar de crear un conjunto explícito de opciones o un árbol de acciones potenciales con posiciones de respaldo implícitas definidas por la estructura del árbol, ¿tal vez sea mejor simplemente examinar todas las acciones y elegir la que sea más aplicable en este momento?

Esto es lo que hacen los sistemas basados ​​en la utilidad: estos son sistemas en los que el agente tiene muchas acciones a su disposición y elige realizar una en función de la utilidad relativacada acción La utilidad aquí es una medida arbitraria de importancia o conveniencia para que un agente realice esta acción. Al escribir funciones de utilidad para calcular la utilidad de una acción en función del estado actual del agente y su entorno, el agente puede verificar los valores de la utilidad y seleccionar el estado más apropiado en este momento.

Esto también es muy parecido a una máquina de estados finitos, excepto que las transiciones están determinadas por una evaluación de cada estado potencial, incluido el actual. Vale la pena señalar que en el caso general, elegimos la transición a la acción más valiosa (o estar en ella si ya estamos realizando esta acción), pero para una mayor variabilidad puede ser una elección aleatoria ponderada (dando prioridad a la acción más valiosa, pero permitiendo la elección de otros) , una opción de acción aleatoria entre los cinco primeros (o cualquier otra cantidad), etc.

El sistema estándar basado en la utilidad asigna un cierto rango arbitrario de valores de utilidad, digamos de 0 (completamente indeseable) a 100 (absolutamente deseable), y cada acción puede tener un conjunto de factores que influyen en la forma en que se calcula el valor. Volviendo a nuestro ejemplo con el guardia, uno puede imaginar algo como esto:

Acción	Cálculo de utilidad
Búsqueda de ayuda	Si el enemigo es visible y el enemigo es fuerte y la salud es baja, entonces devuelve 100, de lo contrario devuelve 0
Vuelo	Si el enemigo es visible y hay poca salud, entonces devuelve 90, de lo contrario devuelve 0
Asalto	Si el enemigo es visible, devuelve 80
Esperando	Si estamos en un estado de espera y ya esperamos 10 segundos, regrese 0, de lo contrario 50
Patrulla	Si estamos al final de la ruta de patrulla, regrese 0, de lo contrario 50

Uno de los aspectos más importantes de este esquema es que las transiciones entre acciones se expresan implícitamente: desde cualquier estado puede pasar legítimamente a cualquier otro. Además, las prioridades de acción están implícitas en los valores de utilidad devueltos. Si el enemigo es visible, y si es fuerte, y el personaje tiene poca salud, los valores distintos de cero devuelven Búsqueda de vuelo y ayuda , pero la Búsqueda de ayuda siempre tiene una calificación más alta. Del mismo modo, las acciones que no son de combate nunca devuelven más de 50, por lo que siempre son derrotados por la lucha. Con esto en mente, se crean acciones y sus cálculos de utilidad.

En nuestro ejemplo, las acciones devuelven un valor de utilidad constante o uno de los dos valores de utilidad constante. Un sistema más realista utiliza un valor de retorno de un rango continuo de valores. Por ejemplo, la acción Escapada puede devolver valores de utilidad más altos si la salud del agente es más baja, y la acción de Ataque puede devolver valores de utilidad más bajos si el enemigo es demasiado fuerte. Esto permitirá que Getaway tenga prioridad sobre Asalto.en cualquier situación en la que el agente sienta que no está lo suficientemente sano como para luchar contra el enemigo. Esto le permite cambiar las prioridades relativas de las acciones sobre la base de cualquier número de criterios, lo que puede hacer que este enfoque sea más flexible que un árbol de comportamiento o una nave espacial.

Cada acción generalmente tiene varias condiciones que influyen en el cálculo de la utilidad. Para no poner todo difícil en el código, puede escribirlos en un lenguaje de script o como una serie de fórmulas matemáticas, juntas de una manera comprensible. Mucha más información sobre esto se encuentra en conferencias y presentaciones de Dave Mark ( @IADaveMark ).

En algunos juegos que intentan simular la vida diaria del personaje, por ejemplo, en Los Sims, se agrega otra capa de cálculos en la que el agente tiene "aspiraciones" o "motivaciones" que afectan los valores de utilidad. Por ejemplo, si un personaje tiene la motivación del Hambre, entonces puede aumentar con el tiempo, y calcular la utilidad para la acción Coma devolverá valores cada vez más altos hasta que el personaje pueda realizar esta acción, reducir el hambre y la acción " Eat "se reduce a cero o casi cero valor de utilidad.

La idea de elegir acciones basadas en el sistema de puntos es bastante sencilla, por lo que es obvio que puede usar la toma de decisiones basada en la utilidad en otros procesos de toma de decisiones de IA, y no reemplazarlas completamente con ella. El árbol de decisión puede consultar el valor de utilidad de sus dos nodos secundarios y seleccionar el nodo con el valor más alto. Del mismo modo, un árbol de comportamiento puede tener un nodo de utilidad compuesto que cuenta la utilidad para seleccionar el nodo secundario que se ejecutará.

Movimiento y navegación

En nuestros ejemplos anteriores, había una raqueta simple, que ordenábamos mover de izquierda a derecha, o un personaje de guardia, a quien siempre se le ordenaba patrullar o atacar. Pero, ¿cómo controlamos exactamente el movimiento de un agente durante un período de tiempo? ¿Cómo podemos establecer la velocidad, evitar obstáculos, planificar una ruta cuando es imposible llegar al punto final directamente? Ahora consideraremos esta tarea.

Dirección

En el nivel más simple, a menudo es aconsejable trabajar con cada agente como si tuviera un valor de velocidad que determina la velocidad y la dirección de su movimiento. Esta velocidad se puede medir en metros por segundo, en millas por hora, en píxeles por segundo, etc. Si recordamos nuestro ciclo "percepción-pensamiento-acción", podemos imaginar que "pensar" puede elegir la velocidad, después de lo cual "acción" aplica esta velocidad al agente, moviéndola alrededor del mundo. Por lo general, en los juegos hay un sistema de física que realiza esta tarea de forma independiente, estudia el valor de la velocidad de cada entidad y cambia su posición en consecuencia. Por lo tanto, a menudo es posible asignar dicho trabajo a este sistema, dejando a la IA solo la tarea de elegir la velocidad del agente.

Si sabemos dónde quiere estar el agente, entonces necesitamos usar nuestra velocidad para mover al agente en esta dirección. En una forma trivial, obtenemos la siguiente ecuación:

 deseada_travel = destination_position - agent_position 

Imagine un mundo 2D en el que el agente está ubicado en las coordenadas (-2, -2), y el punto objetivo está aproximadamente en el noreste, en las coordenadas (30, 20), es decir, para llegar allí necesita moverse (32, 22). Supongamos que estas posiciones se indican en metros. Si decidimos que el agente puede moverse a una velocidad de 5 m / s, reduzca la escala del vector de desplazamiento a este valor y veamos que necesitamos establecer la velocidad aproximadamente (4.12, 2.83). Moviéndose en función de este valor, el agente llegará al punto final en poco menos de 8 segundos, como se esperaba.

Los cálculos se pueden realizar nuevamente en cualquier momento. Por ejemplo, si el agente está a medio camino del objetivo, el movimiento deseado será la mitad, pero después de escalar a la velocidad máxima del agente de 5 m / s, la velocidad sigue siendo la misma. Esto también funciona para mover objetivos (dentro de lo razonable), lo que le permite al agente hacer pequeños ajustes en el camino.

Sin embargo, a menudo necesitamos más control. Por ejemplo, es posible que necesitemos aumentar lentamente la velocidad, como si el personaje se detuviera primero, luego avanzara un paso y luego corriera. Por otro lado, es posible que necesitemos reducir la velocidad a medida que se acerca al objetivo. A menudo, tales tareas se resuelven utilizando los llamados " comportamientos de dirección""tener sus propios nombres como Seek, Flee, Arrival, etc. (en Habré hay una serie de artículos sobre ellos: https://habr.com/post/358366/ .) Su idea es que puede aplicar la velocidad del agente fuerzas de aceleración basadas en una comparación de la posición del agente y la velocidad actual de movimiento hacia el objetivo, creando varias formas de moverse hacia el objetivo.

Cada comportamiento tiene su propio propósito ligeramente diferente. Buscar y llegar se utilizan para mover el agente a su destino. La evitación de obstáculos y la separación ayudan al agente a hacer pequeños movimientos correctivos para sortear pequeños obstáculos entre el agente y su destino. La alineación y la cohesión obligan a los agentes a moverse juntos, imitando a los animales del rebaño. Cualquier variación de diferentes comportamientos de dirección se puede combinar, a menudo en forma de una suma ponderada, para crear un valor total que tenga en cuenta todos estos factores diferentes y cree un único vector resultante. Por ejemplo, un agente puede usar el comportamiento de Llegada junto con los comportamientos de Separación y Evitación de Obstáculos para mantenerse alejado de las paredes y otros agentes. Este enfoque funciona bien en entornos abiertos que no son demasiado complejos y abarrotados.

Sin embargo, en entornos más complejos, simplemente agregar los valores de salida del comportamiento no funciona muy bien: a veces el movimiento cerca del objeto es demasiado lento, o el agente se atasca cuando el comportamiento de Llegada quiere pasar un obstáculo, y el comportamiento de Evitar obstáculos empuja al agente hacia el lado del que proviene . Por lo tanto, a veces tiene sentido considerar las variaciones de comportamiento de dirección que son más complicadas que simplemente sumar todos los valores. Una de las familias de tales enfoques consiste en una implementación diferente: no consideramos cada uno de los comportamientos que nos dan dirección, seguidos de su combinación para obtener un consenso (que en sí mismo puede ser inadecuado). En cambio, consideramos el movimiento en varias direcciones diferentes, por ejemplo, en ocho direcciones de la brújula, o en 5-6 puntos delante del agente,después de lo cual elegimos el mejor.

Sin embargo, en entornos complejos con callejones sin salida y opciones de curvas, necesitaremos algo más avanzado, y pasaremos a esto pronto.

Encontrar el camino

Los comportamientos de dirección son excelentes para un movimiento simple en un área bastante abierta, como un campo de fútbol o arena, donde puedes ir de A a B en línea recta con pequeños ajustes para evitar obstáculos. Pero, ¿qué pasa si la ruta al punto final es más complicada? Luego necesitamos una "búsqueda de caminos": explorar el mundo y trazar un camino a lo largo de él para que el agente llegue al punto final.

La forma más sencilla es colocar una cuadrícula en el mundo y, para cada celda al lado del agente, mirar las celdas vecinas a las que podemos movernos. Si uno de ellos es nuestro punto final, entonces regrese la ruta, desde cada celda a la anterior, hasta llegar al principio, obteniendo así una ruta. De lo contrario, repita el proceso con los vecinos alcanzables de los vecinos anteriores hasta que encontremos el punto final o nos quedemos sin celdas (esto significará que no hay ruta). Formalmente, este enfoque se llama algoritmo Breadth-First Search (BFS), porque en cada paso se ve en todas las direcciones (es decir, "ancho") antes de mover las búsquedas. El espacio de búsqueda es como un frente de onda que se mueve hasta toparse con el lugar que estábamos buscando.

Este es un ejemplo simple de una búsqueda en acción. El área de búsqueda se expande en cada etapa hasta que se incluye un punto final, después de lo cual puede seguir el camino hacia el principio.


Como resultado, obtenemos una lista de celdas de cuadrícula, que conforman la ruta que debe seguir. Por lo general, se llama "ruta", ruta (de ahí la "búsqueda de rutas", búsqueda de ruta), pero también puede imaginarlo como un plan, porque es una lista de lugares que debe visitar para lograr su objetivo, es decir, el punto final.

Ahora que conocemos la posición de cada celda en el mundo, puede usar los comportamientos de dirección descritos anteriormente para moverse a lo largo de la ruta: primero del nodo inicial al nodo 2, luego del nodo 2 al nodo 3, y así sucesivamente. El enfoque más simple es moverse hacia el centro de la siguiente celda, pero también hay una alternativa popular: moverse hacia el centro de la costilla entre la celda actual y la siguiente. Esto le permite al agente cortar esquinas de curvas cerradas para crear un movimiento más realista.

Como puede ver, este algoritmo puede desperdiciar recursos porque examina tantas celdas en la dirección "incorrecta" como en la "correcta". Además, no permite tener en cuenta los costos de movimiento, en el que algunas celdas pueden ser "más caras" que otras. Aquí venimos en ayuda de un algoritmo más complejo llamado A *. Funciona de la misma manera que la búsqueda de amplitud, pero en lugar de explorar ciegamente vecinos, luego vecinos de vecinos, luego vecinos de vecinos, vecinos, etc., coloca todos estos nodos en una lista y los ordena para que el siguiente nodo examinado sea siempre el único. Lo más probable es que conduzca a la ruta más corta. Los nodos se ordenan según la heurística (es decir, una suposición razonable),que tiene en cuenta dos aspectos: el costo de una ruta hipotética a la celda (teniendo en cuenta todos los costos necesarios de la mudanza) y una evaluación de qué tan lejos está esta celda del punto final (desplazando así la búsqueda en la dirección correcta).


En este ejemplo, mostramos que él examina una celda a la vez, cada vez que elige una celda vecina que tiene las mejores (o una de las mejores) perspectivas. La ruta resultante es similar a la ruta de búsqueda de amplitud, pero se examinan menos celdas en el proceso, y esto es muy importante para el rendimiento del juego en niveles complejos.

Movimiento sin malla

En los ejemplos anteriores, se usó una cuadrícula superpuesta al mundo y trazamos una ruta alrededor del mundo a través de las celdas de esta cuadrícula. Pero la mayoría de los juegos no se superponen a la cuadrícula y, por lo tanto, la superposición de la cuadrícula puede conducir a patrones de movimiento poco realistas. Además, este enfoque puede requerir compromisos con respecto al tamaño de cada celda: si es demasiado grande, entonces no podrá describir adecuadamente corredores y giros pequeños, si es demasiado pequeño, entonces buscar a través de miles de celdas puede ser demasiado largo. Cuales son las alternativas?

Lo primero que debemos entender es que, desde un punto de vista matemático, la cuadrícula nos da un " gráfico"de nodos conectados. Los algoritmos A * (y BFS) funcionan con gráficos, y no les importa la cuadrícula. Por lo tanto, podemos colocar nodos en posiciones arbitrarias del mundo, y si hay una línea recta entre dos nodos conectados, pero hay una línea entre el principio y el final Si solo hay un nodo, nuestro algoritmo funcionará como antes, y de hecho es aún mejor, porque habrá menos nodos. Esto a menudo se llama el sistema de puntos de referencia, ya que cada nodo indica una posición importante en el mundo que puede crear parte de cualquier número de pu hipotético s.


Ejemplo 1: un nodo en cada celda de la cuadrícula. La búsqueda comienza con el nodo en el que se encuentra el agente y termina con la celda final.


Ejemplo 2: un número mucho menor de nodos o puntos de referencia . La búsqueda comienza con el agente, pasa a través del número requerido de puntos de referencia y se mueve al punto final. Tenga en cuenta que moverse al primer punto de la ruta al suroeste del jugador es una ruta ineficiente, por lo que generalmente es necesario un cierto procesamiento posterior de la ruta generada (por ejemplo, para notar que la ruta puede ir directamente al punto de referencia en el noreste).

Este es un sistema bastante flexible y potente, pero requiere una ubicación cuidadosa de los puntos intermedios; de lo contrario, es posible que los agentes no vean el punto intermedio más cercano para comenzar la ruta. Sería genial si de alguna manera pudiéramos generar waypoints automáticamente basados ​​en la geometría del mundo.

Y luego navmesh viene al rescate. Esto es la abreviatura de malla de navegación. En esencia, esta es (generalmente) una malla de triángulos bidimensional, que se superpone aproximadamente con la geometría del mundo en aquellos lugares donde el juego permite que el agente se mueva. Cada uno de los triángulos en la malla se convierte en un nodo del gráfico y tiene hasta tres triángulos adyacentes que se convierten en nodos adyacentes del gráfico.

A continuación se muestra un ejemplo del motor de Unity. El motor analizó la geometría del mundo y creó navmesh (azul), que es una aproximación de la geometría. Cada polígono nammesh es un área en la que un agente puede pararse, y un agente puede moverse de un polígono a otro adyacente. (En este ejemplo, los polígonos se hacen más estrechos que el piso en el que se encuentran para tener en cuenta el radio del agente, que se extiende más allá de la posición nominal del agente).



Podemos buscar una ruta a través de una malla usando A * nuevamente, y esto nos dará una ruta ideal alrededor del mundo que tiene en cuenta toda la geometría y no requiere un número excesivo de nodos adicionales (como sería con la cuadrícula) y la participación humana en la generación de puntos el camino

Encontrar caminos es un tema extenso, para el cual hay muchos enfoques, especialmente si necesita programar detalles de bajo nivel usted mismo. Una de las mejores fuentes de información adicional es el sitio de Amit Patel (traducción del artículo sobre Habré: https://habr.com/post/331192/ ).

Planificacion

Utilizando la búsqueda de rutas como ejemplo, vimos que a veces no basta con elegir una dirección y comenzar a moverse en ella; tenemos que elegir una ruta y hacer varios movimientos antes de llegar al punto final deseado. Podemos generalizar esta idea a una amplia gama de conceptos en los que el objetivo no es solo el siguiente paso. Para lograrlo, debe seguir una serie de pasos, y para saber cuál debería ser el primer paso, es posible que tenga que mirar unos pasos hacia adelante. Este enfoque se llama planificación . Encontrar rutas puede considerarse una de las aplicaciones específicas de planificación, pero este concepto tiene muchas más aplicaciones. Volviendo al ciclo de "percepción-pensamiento-acción", esta planificación es una fase de pensamiento que trata de planificar varias fases de acción para el futuro.

Veamos el juego Magic: The Gathering. Tienes tu primer movimiento, hay varias cartas en tus manos, entre las cuales están "Pantano", que da 1 punto de maná negro, y "Bosque", que da 1 punto de maná verde, "Exorcista", que requiere 1 punto de maná azul para llamar, y " Elven Mystic ”, para llamar al cual necesitas 1 punto de maná verde. (Por simplicidad, omitimos las tres cartas restantes.) Las reglas dicen que un jugador puede jugar una carta de tierra por turno, puede "tocar" sus cartas de tierra para obtener maná de ellas y puede lanzar tantos hechizos (incluidas criaturas de invocación) cuánto maná tiene. En esta situación, es probable que el jugador juegue "Bosque", tóquelo para obtener 1 punto de maná verde y luego llame a "Elven Mystic". Pero, ¿cómo sabe una IA de juegos que se debe tomar tal decisión?

"Planificador" simple

Un enfoque ingenuo puede ser simplemente iterar sobre cada acción en orden, hasta que haya las adecuadas. Mirando la mano, AI ve que puede jugar "Swamp", y por lo tanto lo hace. ¿Quedan más acciones después de este turno? No puede invocar ni a Elven Mystic ni a Exile Wizard, porque esto requiere maná verde o azul, y el pantano jugado solo da maná negro. Y no podemos jugar "Forest" porque ya hemos jugado "Swamp". Es decir, el jugador de IA hará el movimiento de acuerdo con las reglas, pero no será muy óptimo. Afortunadamente, hay una mejor solución.

Casi de la misma manera en que la búsqueda de caminos encuentra una lista de posiciones para moverse por el mundo para llegar al punto correcto, nuestro planificador puede encontrar una lista de acciones que ponen el juego en el estado correcto. Del mismo modo que cada posición en el camino tiene un conjunto de vecinos, que son opciones potenciales para elegir el siguiente paso a lo largo del camino, cada acción en el plan tiene vecinos o “herederos” que son candidatos para el siguiente paso del plan. Podemos buscar estas acciones y las siguientes acciones hasta que alcancemos el estado deseado.

Supongamos, para nuestro ejemplo, que el resultado deseado sería "convocar a una criatura, si es posible". Al comienzo del movimiento, solo tenemos dos acciones potenciales permitidas por las reglas del juego:

 1. Juega "Swamp" (resultado: "Swamp" deja la mano y entra en el juego)
2. Juega "Forest" (resultado: "Forest" deja la mano y entra al juego) 

Cada acción tomada puede abrir más acciones o cerrarlas, también de acuerdo con las reglas del juego. Imagina que elegimos jugar "Swamp": esto cierra la oportunidad de jugar esta carta como una posible acción de herencia (porque "Swamp" ya se ha jugado), cierra la oportunidad de jugar "Forest" (porque las reglas del juego te permiten jugar solo una carta de tierra por turno) y agrega la capacidad de tocar el "Pantano" para obtener 1 punto de maná negro, y esta, de hecho, es la única acción heredada. Si damos un paso más y seleccionamos "tocar" Pantano ", obtendremos 1 punto de maná negro con el que no podemos hacer nada, así que esto no tiene sentido.

 1. Juega "Swamp" (resultado: "Swamp" deja la mano y entra en el juego)
            1.1 Toque "Pantano" (resultado: tocamos "Pantano", +1 maná negro está disponible)
                        No queda acción - FIN
2. Juega "Forest" (resultado: "Forest" deja la mano y entra al juego) 

Esta breve lista de acciones no nos dio mucho y condujo a un "callejón sin salida", si utilizamos la analogía con la búsqueda de caminos. Por lo tanto, repetimos el proceso para el siguiente paso. Elegimos jugar Forest. Esto también elimina la capacidad de "jugar al Bosque" y "jugar al Pantano", y se abre como un posible (y único) paso siguiente "tocar el Bosque". Esto nos da 1 punto de maná verde, que a su vez abre el tercer paso: "llamar" Elven Mystic ".

 1. Juega "Swamp" (resultado: "Swamp" deja la mano y entra en el juego)
            1.1 Toque "Pantano" (resultado: tocamos "Pantano", +1 maná negro está disponible)
                        No queda acción - FIN
2. Juega "Forest" (resultado: "Forest" deja la mano y entra al juego)
            2.1 Toque "Bosque" (resultado: tocamos "Pantano", +1 de maná verde está disponible)
                        2.1.1 Llamada "Elven Mystic" (resultado: "Elven Mystic" en el juego, -1 maná verde está disponible)
                                    No queda acción - FIN 

Ahora hemos investigado todas las acciones posibles y las acciones resultantes de estas acciones, encontrando un plan que nos permite convocar a la criatura: "jugar al bosque", "tocar el bosque", "llamar al" Místico élfico "".

Obviamente, este es un ejemplo muy simplificado y, por lo general, debe elegir el mejorun plan, y no solo un plan que satisfaga algunos criterios (por ejemplo, "convocar a una criatura"). Por lo general, puede evaluar planes potenciales en función del resultado final o los beneficios acumulativos de usar el plan. Por ejemplo, puedes darte 1 punto por un mapa de tierra y 3 puntos por llamar a una criatura. "Jugar" Pantano "" será un plan corto que dará 1 punto, y el plan para "jugar" Bosque "→ tocar" Bosque "→ llamar a" Elven Mystic "" da 4 puntos, 1 para el suelo y 3 para la criatura. Este será el plan más rentable disponible, por lo que debe elegirlo si asignamos dichos puntos.

Arriba, mostramos cómo funciona la planificación dentro de un movimiento Magic: The Gathering, pero también se puede aplicar a acciones en una serie de movimientos (por ejemplo, "mover un peón para dejar espacio para el desarrollo del alfil" en ajedrez o "correr para cubrir una unidad"). podría disparar el siguiente turno, estar a salvo "en XCOM) o para la estrategia general de todo el juego (por ejemplo," construir pilones para todos los demás edificios protoss "en Starcraft, o" beber una poción Fortify Health antes de atacar al enemigo "en Skyrim).

Planificación mejorada

A veces hay demasiadas acciones posibles en cada paso, y evaluar cada opción no es razonable. Volvamos al ejemplo de Magic: The Gathering: imagina que tenemos varias criaturas a mano, muchas tierras ya se han jugado, por lo que podemos llamar a cualquier criatura, varias criaturas con sus habilidades jugadas, y hay un par de cartas de tierra más en la mano: el número de permutaciones la tierra, el uso de la tierra, la invocación de criaturas y el uso de las habilidades de las criaturas pueden ser iguales a miles o incluso decenas de miles. Afortunadamente, hay un par de formas de resolver este problema.

El primero se llama encadenamiento hacia atrás."(" Ida y vuelta "). En lugar de verificar todas las acciones y sus resultados, podemos comenzar con cada uno de los resultados finales deseados y ver si podemos encontrar un camino directo hacia ellos. Puede comparar esto con intentar alcanzar una hoja específica en un árbol, es mucho más lógico comience desde esta hoja y regrese, colocando una ruta a lo largo del tronco (y esta ruta podemos seguir en el orden opuesto), que comenzando desde el tronco e intentando adivinar qué rama elegir en cada paso. Si comienza desde el final y va en la dirección opuesta, luego creado Plan E será mucho más rápido y más fácil.

Por ejemplo, si al enemigo le queda 1 punto de vida, puede ser útil tratar de encontrar un plan para "infligir 1 o más puntos de daño directo al enemigo". Nuestro sistema sabe que para lograr este objetivo necesita lanzar un hechizo de daño directo, lo que a su vez significa que debe estar en nuestras manos y necesitamos suficiente maná para pronunciarlo. Esto, a su vez, significa que necesitamos tocar suficiente tierra para recibir este maná, lo que puede requerir que juegues un mapa de tierra adicional.

Otra forma es buscar por la primera mejor coincidencia. En lugar de analizar todas las permutaciones durante mucho tiempo, medimos cuán "bueno" es cada plan parcial (similar a cómo elegimos entre las opciones de plan anteriores) y calculamos el mejor aspecto cada vez. A menudo, esto le permite crear un plan óptimo, o al menos bastante bueno, sin la necesidad de considerar cada posible reorganización de los planes. A * es una variación de la búsqueda del primer mejor partido: primero explora las rutas más prometedoras, por lo que generalmente puede encontrar el camino hacia la meta sin tener que subir demasiado en otras direcciones.

Una opción de búsqueda interesante y cada vez más popular para la primera mejor coincidencia es la búsqueda de árboles de Monte Carlo .. En lugar de adivinar qué planes son mejores que otros al elegir cada acción posterior, este método elige acciones posteriores aleatorias en cada paso hasta que llega al final donde ya no son posibles acciones, probablemente porque el plan hipotético condujo a un estado de victoria o pérdida - y utiliza este resultado para dar más o menos peso a las opciones seleccionadas anteriormente. Si el proceso se repite muchas veces, el método puede crear una buena evaluación del mejor próximo paso, incluso si la situación cambia (por ejemplo, si el enemigo intenta frustrar nuestros planes).

Finalmente, ninguna discusión sobre la planificación en los juegos estaría completa sin mencionar la planificación de la acción basada en objetivos(Planificación de acciones orientadas a objetivos, GOAP). Esta es una técnica ampliamente utilizada y ampliamente discutida, pero si ignora algunos detalles específicos de implementación, es esencialmente un planificador de ida y vuelta que comienza con un objetivo e intenta recoger una acción que conduzca a ese objetivo, o, más probablemente, una lista de acciones que conducen a a la meta. Por ejemplo, si el objetivo era "matar al jugador" y el jugador estaba cubierto, entonces el plan podría ser: "Fumar al jugador con una granada" → "Sacar un arma" → "Atacar".

Por lo general, hay varios objetivos, y cada uno tiene su propia prioridad. Si los objetivos con la prioridad más alta no se pueden lograr, por ejemplo, ningún conjunto de acciones puede formar el plan "Mata al jugador" porque el jugador no es visible, entonces el sistema vuelve a los objetivos con prioridades más bajas, por ejemplo, "Patrulla" o "Guardia en el lugar".

Entrenamiento y adaptación

Al comienzo del artículo, mencionamos que la inteligencia artificial para juegos generalmente no utiliza el "aprendizaje automático" porque generalmente no es adecuada para el control en tiempo real de agentes inteligentes en el mundo de los juegos. Sin embargo, esto no significa que no podamos tomar prestado algo de esta área donde tenga sentido. Es posible que necesitemos un oponente informático en el tirador para descubrir los mejores lugares para movernos y obtener la mayor cantidad de asesinatos. O podríamos querer al oponente en un juego de lucha. por ejemplo, en Tekken o Street Fighter, aprendió a reconocer a un jugador que usa los mismos combos para comenzar a bloquearlos, lo que obliga al jugador a usar diferentes tácticas. Es decir, hay momentos en que un cierto porcentaje de aprendizaje automático es útil.

Estadísticas y probabilidades

Antes de pasar a ejemplos más complejos, vale la pena averiguar hasta dónde podemos llegar simplemente tomando medidas y utilizando estos datos para tomar decisiones. Por ejemplo, supongamos que tenemos un juego en el género de la estrategia en tiempo real, y necesitamos entender si el jugador comenzará a correr en los primeros minutos para decidir si construir más defensa. Podemos extrapolar el comportamiento anterior del jugador para comprender cuál podría ser el comportamiento futuro. Al principio, no tenemos datos que puedan extrapolarse, pero cada vez que la IA juega contra un enemigo vivo, puede registrar la hora del primer ataque. Después de algunos partidos, este tiempo se puede promediar y obtendremos una aproximación suficientemente buena del tiempo de ataque del jugador en el futuro.

El problema con el promedio simple es que generalmente converge con el tiempo en el centro. Por lo tanto, si un jugador usó la estrategia de prisa las primeras 20 veces, y las siguientes 20 veces cambió a una estrategia mucho más lenta, entonces el valor promedio estará en algún punto intermedio, lo que no nos dará ninguna información útil. Una forma de mejorar los datos es utilizar una ventana de promedio simple que tenga en cuenta solo los últimos 20 puntos de datos.

Se puede usar un enfoque similar para evaluar la probabilidad de ciertas acciones, suponiendo que las preferencias previas del jugador continuarán en el futuro. Por ejemplo, si un jugador atacó cinco veces con una bola de fuego, dos veces con un rayo y mano a mano solo una vez, lo más probable es que prefiera una bola de fuego 5 de 8 veces. Extrapolando a partir de estos datos, podemos ver que la probabilidad de usar un arma es: Bola de fuego = 62.5%, Rayo = 25% Cuerpo a cuerpo = 12.5%. ¡Nuestros personajes de IA se darán cuenta de que es mejor encontrar una armadura a prueba de fuego!

Otro método interesante es utilizar el clasificador Naive Bayes para estudiar grandes volúmenes de datos de entrada con el fin de clasificar la situación actual para que el agente de inteligencia artificial pueda responder en consecuencia. Los clasificadores bayesianos son probablemente más conocidos por su uso en los filtros de correo electrónico no deseado, donde evalúan las palabras en el correo electrónico, las comparan con las palabras que se encontraban con mayor frecuencia en mensajes no deseados y mensajes normales en el pasado. En base a estos cálculos, deciden la probabilidad de que el último mensaje recibido sea spam. Podemos hacer algo similar, solo con menos entrada. Al registrar toda la información útil observable (por ejemplo, unidades enemigas creadas,hechizos o tecnologías de investigación) y al rastrear la situación resultante (guerra / paz, estrategia rápida / estrategia de defensa, etc.), podemos seleccionar el comportamiento apropiado en función de esto.

El uso de todas estas técnicas de enseñanza puede ser suficiente, y con frecuencia y de preferencia aplicado a los datos recopilados durante las pruebas de juego antes del lanzamiento del juego. Esto permite que la IA se adapte a las diversas estrategias utilizadas por los probadores de juego y no cambie después del lanzamiento del juego. Una IA que se adapta a un jugador después del lanzamiento de un juego puede volverse demasiado predecible o incluso demasiado compleja para derrotarla.

Adaptación fácil basada en el peso.

Vamos a ir un paso más allá. En lugar de simplemente usar los datos de entrada para elegir entre estrategias discretas predefinidas, puede cambiar el conjunto de valores que influyen en la toma de decisiones. Si entendemos bien el mundo del juego y las reglas del juego, entonces podemos hacer lo siguiente:

• ( );
• «» ;
• .

Imagine un agente informático que puede seleccionar habitaciones en un mapa en un juego de disparos en primera persona. Cada habitación tiene un peso que determina la conveniencia de visitar esta habitación. Inicialmente, todas las habitaciones tienen el mismo significado. Al elegir una habitación, la IA la selecciona al azar, pero con la influencia de estos pesos. Ahora imagine que cuando un agente informático es asesinado, recuerda en qué habitación está sucediendo esto y reduce su peso, por lo que es menos probable que vuelva a él en el futuro. Del mismo modo, imagine que un agente informático ha cometido un asesinato. Luego puede aumentar el peso de la habitación en la que se encuentra para subirlo a la lista de preferencias. Entonces, si una habitación se vuelve especialmente peligrosa para el jugador de IA, entonces comienza a evitarla en el futuro, y si otra habitación permite que la IA reciba muchos asesinatos,entonces él regresará allí.

Modelos de Markov

¿Qué pasaría si quisiéramos usar los datos que recolectamos para hacer pronósticos? Por ejemplo, si registramos cada habitación en la que vemos a un jugador durante un cierto período de tiempo, podemos predecir razonablemente a qué habitación puede pasar. Al rastrear tanto la sala actual en la que se encuentra el jugador como la anterior, y registrar estos pares de valores, podemos calcular con qué frecuencia cada una de las situaciones anteriores conduce a la siguiente situación, y usar este conocimiento para pronósticos.

Imagine que hay tres salas: rojo, verde y azul, y que durante la sesión del juego recibimos tales observaciones:

La primera sala en la que se ve al jugador.	Observaciones totales	Sala siguiente	Cuantas veces visto	Porcentaje
Rojo	10	Rojo	2	20%
		Verde	7 7	70%
		Azul	1	10%
Verde	10	Rojo	3	30%
		Verde	5 5	50%
		Azul	2	20%
Azul	8	Rojo	6 6	75%
		Verde	2	25%
		Azul	0 0	0%

El número de detecciones en cada una de las habitaciones es bastante uniforme, por lo que no nos da una idea de cuáles de las habitaciones pueden ser un buen lugar para una emboscada. Los datos pueden verse distorsionados por el hecho de que los jugadores aparecen de manera uniforme en el mapa, con la misma probabilidad de aparecer en cualquiera de estas tres salas. Pero los datos sobre visitar la siguiente habitación pueden ser útiles y ayudarnos a predecir el movimiento del jugador en el mapa.

Podemos notar de inmediato que la sala verde es muy atractiva para los jugadores: la mayoría de los jugadores de la sala roja fueron a verde, y el 50% de los jugadores vistos en la sala verde permanecen allí durante la próxima comprobación. También podemos notar que la habitación azul es un lugar poco atractivo. Las personas rara vez se mueven de habitaciones rojas o verdes a azules y parece que a nadie le gusta quedarse allí por mucho tiempo.

Pero los datos nos dicen algo más específico: dicen que cuando un jugador está en la habitación azul, luego de seguirlo es más probable que elija rojo, en lugar de verde. A pesar de que la sala verde es un lugar mucho más popular para ir que la roja, la tendencia es ligeramente opuesta si el jugador está en la sala azul. Parece que el siguiente estado (es decir, la sala en la que decide avanzar) depende del estado anterior (es decir, la sala en la que se encuentra ahora), por lo que estos datos nos permiten crear mejores pronósticos sobre el comportamiento de los jugadores. que con conteo de observación independiente.

Esta idea de que podemos usar el conocimiento del estado anterior para predecir el estado futuro se llama modelo de Markov, y ejemplos similares en los que hemos medido eventos con precisión (por ejemplo, "en qué habitación se encuentra el jugador") se llaman cadenas de Markov. Como representan la probabilidad de una transición entre estados sucesivos, a menudo se representan gráficamente en forma de una máquina de estados finitos, cerca de cada transición de la cual se indica su probabilidad. Anteriormente, utilizamos una máquina de estados para representar el estado de comportamiento en el que se encuentra el agente, pero este concepto puede extenderse a todo tipo de estados, estén o no asociados con el agente. En nuestro caso, los estados indican las habitaciones ocupadas por el agente. Se verá así:


Este es un enfoque simple para indicar la probabilidad relativa de transición a diferentes estados, lo que le da a AI la capacidad de predecir el siguiente estado. Pero podemos ir más allá creando un sistema que mire hacia el futuro en dos o más pasos.

Si un jugador ha sido visto en la sala verde, utilizaremos datos que nos indiquen que hay un 50 por ciento de posibilidades de que todavía esté en la sala verde en la próxima observación. Pero, ¿cuál es la probabilidad de que permanezca en él por tercera vez? Esta no es solo la probabilidad de que permanezca en la sala verde durante dos observaciones (50% * 50% = 25%), sino también la probabilidad de que lo deje y regrese. Aquí hay una nueva tabla con valores previos aplicados a tres observaciones: una actual y dos hipotéticas en el futuro.

Observación 1	Observación hipotética 2		3
		30%		20%	6%
				70%	21%
				10%	3%
		50%		30%	15%
				50%	25%
				20%	10%
		20%		75%	15%
				25%	5%
				0%	0%
				:	100%

Aquí vemos que la probabilidad de ver a un jugador en la sala verde después de 2 observaciones es del 51%: 21% de lo que vendrá de la sala roja, 5% de lo que vemos al jugador visitando la sala azul y 25% de lo que es todo el tiempo. se quedará en la sala verde.

Una tabla es solo una pista visual; un procedimiento solo requiere una multiplicación de probabilidades en cada etapa. Esto significa que podemos mirar hacia el futuro, pero con una advertencia importante: suponemos que la probabilidad de entrar en una habitación depende completamente de la habitación en la que nos encontremos en este momento. Esta idea de que el estado futuro depende solo de la corriente se llama propiedad de Markov. Aunque nos permite usar herramientas poderosas como las cadenas de Markov, generalmente es solo una aproximación. Los jugadores pueden decidir visitar salas en función de otros factores, como su nivel de salud y la cantidad de municiones, y dado que no registramos esta información como parte de la condición, nuestras predicciones serán menos precisas.

N gramos

Volvamos a nuestro ejemplo con el reconocimiento combinado en un juego de lucha. Esta es una situación similar en la que queremos predecir el estado futuro en función del pasado (para decidir cómo bloquear un ataque o esquivarlo), pero en lugar de estudiar un solo estado o evento, consideraremos secuencias de eventos que crean un movimiento combinado.

Una forma de hacerlo es guardar la entrada de cada jugador (por ejemplo, patada , mano o bloque ) en el búfer y escribir todo el búfer como un evento. Imagine que un jugador presiona constantemente una patada , una patada , una patada para usar el ataque " Death Cancer " ", y el sistema de IA guarda todas las entradas del jugador en el búfer y recuerda las últimas 3 entradas utilizadas en cada paso.

Entrar	Una secuencia de entrada existente	Nueva memoria de entrada
Patada	Patada	no
Golpe de mano	Patada, patada	no
Patada	Patada, patada, patada	Patada, patada, patada
Patada	Patada, patada, patada, patada	Patada, patada, patada
Golpe de mano	Patada, patada, patada, patada, patada	Patada, patada, patada
Bloque	Patada, patada, patada, patada, patada, bloque	Patada, patada, bloque
Patada	Patada, patada, patada, patada, patada, bloque, patada	Patada, bloqueo, patada
Patada	Patada, patada, patada, patada, patada, bloque, patada, patada	Bloquear, patear, patear
Golpe de mano	, , , , , , , ,	, ,

(En negrita, el jugador realiza el ataque "Superbuck of Death").

Puedes ver todos los momentos en que el jugador eligió una patada en el pasado , seguida de otra patada , y notar que la siguiente entrada siempre es un puñetazo . Esto permite al agente de IA hacer una predicción de que si un jugador acaba de elegir una patada, seguida de una patada, lo más probable es que seleccione una patada a continuación , lanzando así el Death Superkulak . Esto permite que la IA decida elegir una acción que contrarreste este golpe, como bloquear o esquivar.

Tales secuencias de eventos se llaman N-gramos.donde N es el número de elementos almacenados. En el ejemplo anterior, eran 3 gramos, también llamado trigrama, es decir, los primeros 2 elementos se usan para predecir el tercero. En los 5 gramos, el quinto se predice para los primeros 4 elementos, y así sucesivamente.

Los desarrolladores deben elegir cuidadosamente el tamaño de N-gramos (a veces llamado orden). Cuanto menor es el número, se requiere menos memoria, porque menor es el número de permutaciones permitidas, pero se guarda menos historial, lo que significa que se pierde el contexto. Por ejemplo, un 2 gramos (también llamado "bigram") contendrá registros para patear , patear y grabaciones para patear , patear , pero no puede guardar una patada .kick , hand kick , por lo tanto, no puede rastrear este combo.

Por otro lado, cuanto mayor sea el orden, más memoria se requiere, y el sistema probablemente será más difícil de entrenar, porque tendremos muchas más permutaciones posibles, lo que significa que nunca podremos encontrarnos con el mismo dos veces. Por ejemplo, si hay tres entradas posibles ( patada , mano y bloqueo ) y usamos 10 gramos, habrá casi 60 mil permutaciones diferentes.

El modelo de bigram es esencialmente una cadena trivial de Markov: cada par "estado futuro / estado actual" es un bigram y podemos predecir el segundo estado en función del primero. Los trigramas y los grandes N-gramos también pueden considerarse cadenas de Markov, donde todos los elementos del N-gramo, excepto el último, forman el primer estado, y el último elemento es el segundo estado. En nuestro ejemplo de juego de lucha, se presenta la probabilidad de transición del estado de patear y patear al estado de patear, luego patear. Al percibir varios elementos del historial de entrada como un solo elemento, esencialmente transformamos la secuencia de entrada en un fragmento del estado, lo que nos da una propiedad de Markov, lo que nos permite usar cadenas de Markov para predecir la siguiente entrada, es decir, adivinar qué movimiento combinado seguirá.

Representación del conocimiento

Discutimos varias formas de tomar decisiones, crear planes y pronósticos, y todas se basan en las observaciones del agente del estado del mundo. Pero, ¿cómo podemos observar efectivamente todo el mundo del juego? Arriba, vimos que la forma de representar la geometría del mundo afecta en gran medida el movimiento a lo largo de él, por lo que es fácil imaginar que esto es cierto para otros aspectos de la IA del juego. ¿Cómo podemos recopilar y organizar toda la información necesaria de una manera óptima (para que a menudo sea actualizada y accesible para muchos agentes) y práctica (para que la información pueda usarse fácilmente en el proceso de toma de decisiones)? ¿Cómo convertir datos simples en información o conocimiento ? Para diferentes juegos, las soluciones pueden ser diferentes, pero hay varios enfoques más populares.

Etiquetas / Etiquetas

A veces ya tenemos una gran cantidad de datos útiles, y lo único que necesitamos es una buena manera de clasificarlos y buscarlos. Por ejemplo, en el mundo del juego puede haber muchos objetos, y algunos de ellos son un buen refugio contra las balas enemigas. O, por ejemplo, tenemos un montón de diálogos de audio grabados que son aplicables en situaciones específicas, y necesitamos una forma de resolverlos rápidamente. El paso obvio es agregar una pequeña pieza de información adicional que puede usar para buscar. Dichos fragmentos se denominan etiquetas o etiquetas.

Volvamos al ejemplo del refugio; En el mundo del juego puede haber un montón de objetos: cajas, barriles, racimos de hierba, cercas de alambre. Algunos de ellos son adecuados para refugio, por ejemplo, cajas y barriles, otros no. Por lo tanto, cuando nuestro agente realiza la acción "Mover al refugio", debe buscar objetos cercanos e identificar candidatos adecuados. No puede simplemente buscar por nombre, tal vez el juego tiene Crate_01, Crate_02, hasta Crate_27, y no queremos buscar todos estos nombres en el código. No queremos agregar otro nombre al código cada vez que el artista crea una nueva variación de la caja o barril. En cambio, puede buscar cualquier nombre que contenga la palabra "Crate", pero un día un artista puede agregar "Broken_Crate" con un gran agujero, inadecuado como refugio.

Por lo tanto, en su lugar, crearemos una etiqueta de "CUBIERTA" y pediremos a los artistas y diseñadores que adjunten esta etiqueta a todos los objetos que puedan usarse como refugio. Si agregan una etiqueta a todos los barriles y cajas (enteras), entonces el procedimiento de IA solo necesitará encontrar objetos con esta etiqueta, y sabrá que los objetos son adecuados para este propósito. La etiqueta funcionará incluso si luego se cambia el nombre de los objetos, y se puede agregar a los objetos en el futuro sin realizar cambios innecesarios en el código.

En el código, las etiquetas generalmente se representan como cadenas, pero si se conocen todas las etiquetas utilizadas, puede convertir cadenas en números únicos para ahorrar espacio y acelerar la búsqueda. En algunos motores, las etiquetas son funciones integradas, por ejemplo, en Unity y en Unreal Engine 4 , por lo tanto, es suficiente determinar la elección de etiquetas en ellas y usarlas para el propósito previsto.

Objetos inteligentes

Las etiquetas son una forma de agregar información adicional al entorno del agente, para ayudarlo a descubrir las opciones disponibles, de modo que consultas como "Encuéntrame todos los lugares más cercanos para esconderse" o "Encuéntrame a todos los enemigos cercanos que puedan lanzar hechizos" se realizan de manera eficiente y con un mínimo esfuerzo trabajado para nuevos recursos del juego. Pero a veces las etiquetas no contienen suficiente información para su uso completo.

Imagine un simulador de una ciudad medieval en la que los aventureros deambulan donde quieren, si es necesario, entrenar, luchar y relajarse. Podemos organizar sitios de entrenamiento en diferentes partes de la ciudad y asignarles la etiqueta "ENTRENAMIENTO" para que los personajes puedan encontrar fácilmente un lugar para el entrenamiento. Pero imaginemos que uno de ellos es un campo de tiro para arqueros, y el otro es una escuela de magos. En cada uno de estos casos, necesitamos mostrar nuestra animación, porque bajo el nombre general de "entrenamiento" representan diferentes acciones, y no todos los aventureros están interesados ​​en ambos tipos de entrenamiento. Puede profundizar aún más y crear etiquetas de ARCHERY-TRAINING y MAGIC-TRAINING, separar los procedimientos de entrenamiento unos de otros e incrustarlos en cada animación diferente. Esto ayudará a resolver el problema. Pero imaginaque los diseñadores luego declararán "¡Tengamos una escuela Robin Hood donde pueda aprender tiro con arco y lucha con espadas"! Y luego, cuando agregamos la lucha de espadas, piden la creación de la Academia de Hechizos y Lucha de Espadas de Gandalf. Como resultado, tendremos que almacenar varias etiquetas para cada lugar y buscar diferentes animaciones basadas en qué aspecto de entrenamiento necesita el personaje, etc.

Otra forma es almacenar información directamente en el objeto junto con la influencia que tiene sobre el jugador, para que el actor de IA simplemente pueda enumerar las posibles opciones y elegir entre ellas de acuerdo con las necesidades del agente. Después de eso, puede moverse al lugar apropiado, realizar las animaciones apropiadas (o cualquier otra acción obligatoria), como se indica en el objeto, y recibir la recompensa apropiada.

	Animación en ejecución	Resultado del usuario
Campo de tiro	Disparar-flecha	+10 habilidad de tiro con arco
Escuela de magia	Duelo de espadas	+10 habilidad con espadas
Escuela Robin Hood	Disparar-flecha	+15 habilidad de tiro con arco
	Duelo de espadas	+8 habilidad con espadas
Academia Gandalf	Duelo de espadas	+5 habilidad con espadas
	Hechizo de lanzamiento	+10 Habilidad Mágica

El personaje arquero junto a estas 4 ubicaciones tendrá 6 opciones, 4 de las cuales no son aplicables a él si no usa una espada o magia. Comparando el resultado en este caso con una mejora en la habilidad, en lugar de un nombre o etiqueta, podemos expandir fácilmente las posibilidades del mundo con nuevos comportamientos. Puede agregar hoteles para descansar y satisfacer su hambre. Puedes dejar que los personajes vayan a la biblioteca y lean sobre hechizos y técnicas avanzadas de tiro con arco.

El nombre del objeto.	Animación en ejecución	Resultado final
Hotel	Comprar	-10 al hambre
Hotel	Dormir	-50 a la fatiga
La biblioteca	Leer libro	+10 Habilidad de lanzamiento de hechizos
La biblioteca	Leer libro	+5 habilidad de tiro con arco

Si ya tenemos el comportamiento de "practicar tiro con arco", incluso si marcamos la biblioteca como un lugar para ARCHERY-TRAINING, lo más probable es que necesitemos un caso especial para procesar la animación del libro de lectura en lugar de la animación habitual de lucha con espadas. Este sistema nos brinda más flexibilidad al mover estas asociaciones a datos y almacenar datos en el mundo.

La existencia de objetos o ubicaciones (bibliotecas, hoteles o escuelas) nos informa sobre los servicios que ofrecen, sobre el personaje que puede obtenerlos y le permite utilizar una pequeña cantidad de animaciones. La capacidad de tomar decisiones simples sobre los resultados le permite crear una variedad de comportamientos interesantes. En lugar de esperar pasivamente una solicitud, estos objetos pueden proporcionar una gran cantidad de información sobre cómo y por qué usarlos.

Curvas de reacción

A menudo hay una situación en la que parte del estado del mundo se puede medir como un valor continuo. Ejemplos:

• El "porcentaje de salud" generalmente varía de 0 (muerto) a 100 (absolutamente saludable)
• La "distancia al enemigo más cercano" varía de 0 a algún valor positivo arbitrario

Además, el juego puede tener algún aspecto del sistema de IA, que requiere la entrada de valores continuos en algún otro intervalo. Por ejemplo, para tomar una decisión de huir, un sistema de clasificación de servicios públicos puede requerir tanto la distancia al enemigo más cercano como la salud actual del personaje.

Sin embargo, el sistema no puede simplemente sumar dos valores del estado del mundo para obtener un cierto nivel de "seguridad", porque estas dos unidades de medida son incomparables: los sistemas supondrán que un personaje casi muerto a 200 metros del enemigo está en la misma seguridad que es absolutamente saludable personaje a 100 metros del enemigo. Además, si bien el valor porcentual de salud en un sentido amplio es lineal, la distancia no lo es: la diferencia de distancia del enemigo a 200 y 190 metros es menos significativa que la diferencia entre 10 metros y cero.

Idealmente, necesitamos una solución que tome dos indicadores y los convierta en intervalos similares para que puedan compararse directamente. Y necesitamos que los diseñadores puedan controlar cómo se calculan estas transformaciones para controlar la importancia relativa de cada valor. Para este propósito se utilizan curvas de reacción (curvas de respuesta).

La forma más fácil de explicar la curva de reacción es como un gráfico con entrada a lo largo del eje X, valores arbitrarios, por ejemplo, "distancia al enemigo más cercano" y salida a lo largo del eje Y (generalmente un valor normalizado en el rango de 0.0 a 1.0). Una línea o curva en el gráfico determina la unión de la entrada a la salida normalizada, y los diseñadores ajustan estas líneas para obtener el comportamiento que necesitan.

Para calcular el nivel de "seguridad", puede mantener la linealidad de los valores de porcentaje de salud, por ejemplo, 10% más de salud, esto generalmente es bueno cuando el personaje se lastima gravemente y cuando se lesiona fácilmente. Por lo tanto, asignamos estos valores al intervalo de 0 a 1 de manera directa:


La distancia al enemigo más cercano es ligeramente diferente, por lo que no nos molestan en absoluto los enemigos más allá de cierta distancia (digamos 50 metros), y estamos mucho más interesados ​​en las diferencias a corta distancia que a larga distancia.

Aquí vemos que la salida de "seguridad" para los enemigos a 40 y 50 metros es casi la misma: 0.96 y 1.0.


Sin embargo, hay una diferencia mucho mayor entre el enemigo a 15 metros (aproximadamente 0.5) y el enemigo a 5 metros (aproximadamente 0.2). Tal horario refleja mejor la importancia de que el enemigo se acerque.

Al normalizar ambos valores en el rango de 0 a 1, podemos calcular el valor de seguridad total como el promedio de estos dos valores de entrada. Un personaje con un 20% de salud y un enemigo a 50 metros tendrá una puntuación de seguridad de 0.6. Un personaje con un 75% de salud y un enemigo a solo 5 metros de distancia tendrá una puntuación de seguridad de 0.47. Un personaje gravemente herido con un 10% de salud y un enemigo de 5 metros tendrá un índice de seguridad de solo 0.145.

Lo siguiente debe considerarse aquí:

• — , .
• — , , 50 — , , .
• , ( ) . , — , Unity AnimationCurve , .

Blackboards

A menudo nos encontramos en una situación en la que la IA del agente debe comenzar a controlar el conocimiento y la información obtenidos durante el juego para que puedan utilizarse en la toma de decisiones adicionales. Por ejemplo, un agente puede necesitar recordar qué último personaje atacó para enfocarse en los ataques de ese personaje por un corto tiempo. O debe recordar cuánto tiempo ha pasado después de escuchar un ruido, para que después de un cierto período de tiempo deje de buscar sus razones y regrese a sus estudios anteriores. Muy a menudo, el sistema de registro de datos está muy separado del sistema de lectura de datos, por lo que debe ser fácilmente accesible desde el agente y no integrarse directamente en varios sistemas de inteligencia artificial. La lectura puede ocurrir algún tiempo después de la escritura, por lo que los datos deben almacenarse en algún lugar,para que puedan recuperarse más tarde (y no calcularse a pedido, lo que puede no ser factible).

En un sistema de IA codificado, la solución puede ser agregar las variables necesarias en el proceso de la necesidad. Estas variables se relacionan con instancias del personaje o agente, ya sea integrando directamente en él o creando una estructura / clase separada para almacenar dicha información. Los procedimientos de IA se pueden adaptar para leer y escribir estos datos. En un sistema simple, esto funcionará bien, pero a medida que se agrega más información, se vuelve engorroso y generalmente requiere reconstruir el juego cada vez.

Un mejor enfoque es convertir el almacén de datos en una estructura que permita a los sistemas leer y escribir datos arbitrarios. Esta solución le permite agregar nuevas variables sin la necesidad de cambiar la estructura de datos, proporcionando así la capacidad de aumentar la cantidad de cambios que se pueden hacer desde archivos de datos y secuencias de comandos sin la necesidad de volver a montar. Si cada agente simplemente almacena una lista de pares clave-valor, cada uno de los cuales es un conocimiento separado, entonces diferentes sistemas de IA pueden cooperar agregando y leyendo esta información si es necesario.

En el desarrollo de la IA, estos enfoques se denominan "pizarras" ("pizarras"), porque cada participante, en nuestro caso, los procedimientos de IA (por ejemplo, percepción, encontrar un camino y tomar decisiones), puede escribir en la "pizarra", leer desde donde los datos para el desempeño de su tarea pueden ser cualquier otro participante. Puedes imaginar esto como un equipo de expertos reunidos alrededor del pizarrón y escribiendo algo útil sobre él que necesitas compartir con el grupo. Al mismo tiempo, pueden leer las notas anteriores de sus colegas hasta que lleguen a una decisión o plan conjunto. Una lista codificada de variables comunes en el código a veces se denomina "pizarra estática" (porque los elementos en los que se almacena la información son constantes durante la ejecución del programa), y una lista arbitraria de pares clave-valor a menudo se denomina "pizarra dinámica".Pero se usan aproximadamente de la misma manera, como un enlace intermedio entre partes del sistema de IA.

En la IA tradicional, generalmente se hace hincapié en la colaboración de diferentes sistemas para la toma de decisiones conjunta, pero relativamente pocos sistemas están presentes en la IA del juego. Sin embargo, un cierto grado de cooperación aún puede estar presente. Imagine lo siguiente en un juego de rol de acción:

• El sistema de "percepción" escanea regularmente el área y escribe las siguientes entradas en la pizarra:
  
  • Enemigo más cercano: Goblin 412
    
  • "Distancia al enemigo más cercano": 35.0
    
  • "Amigo cercano": "Guerrero 43"
    
  • "Distancia al amigo más cercano": 55.4
    
  • "Hora del último ruido notado": 12:45 pm
• Los sistemas como un sistema de combate pueden registrar eventos clave en una pizarra, por ejemplo:
  
  • Último daño recibido: 12:34 pm

Muchos de estos datos pueden parecer redundantes: al final, siempre puede obtener la distancia al enemigo más cercano, simplemente sabiendo quién es este enemigo y cumpliendo una solicitud para su posición. Pero cuando se repite varias veces por cuadro, para decidir si un agente está amenazando algo o no, esto se convierte en una operación potencialmente lenta, especialmente si necesita realizar una consulta espacial para determinar el enemigo más cercano. Y las marcas de tiempo del "último ruido detectado" o del "último daño recibido" aún no podrán ser instantáneas; debe registrar la hora en que ocurrieron estos eventos, y la pizarra es un lugar conveniente para esto.

Unreal Engine 4 utiliza un sistema de pizarra dinámica para almacenar datos transmitidos por árboles de comportamiento. Gracias a este objeto de datos común, los diseñadores pueden escribir fácilmente nuevos valores en el pizarrón en función de sus planos (guiones visuales), y el árbol de comportamiento luego puede leer estos valores para seleccionar el comportamiento, y todo esto no requiere la recompilación del motor.

Mapas de influencia

La tarea estándar en AI es decidir a dónde debe moverse el agente. En el tirador podemos elegir la acción "Mover al refugio", pero ¿cómo decidir dónde está el refugio en las condiciones de mover enemigos? De manera similar a la acción "Escape", ¿dónde está la forma más segura de escapar? O en RTS, es posible que necesitemos que las tropas ataquen un punto débil en defensa del enemigo. ¿Cómo determinamos dónde está este punto débil?

Todas estas preguntas pueden considerarse tareas geográficas, porque hacemos una pregunta sobre la geometría y la forma del entorno y la posición de las entidades en él. En nuestro juego, todos estos datos probablemente ya estén disponibles, pero darles sentido no es una tarea fácil. Por ejemplo, si queremos encontrar un punto débil en la defensa del enemigo, simplemente elegir la posición del edificio o fortificación más débil no es lo suficientemente bueno si tienen dos poderosos sistemas de armas en los flancos. Necesitamos una forma de tener en cuenta el área local y dar un mejor análisis de la situación.

Para eso es la estructura de datos del "mapa de influencia". Describe la "influencia" que una entidad puede tener en el área a su alrededor. Combinando la influencia de varias entidades, creamos una visión más realista de todo el paisaje. Desde el punto de vista de la implementación, aproximamos el mundo del juego al superponerle una cuadrícula 2D y, después de determinar en qué celda de la cuadrícula se encuentra la entidad, aplicamos una evaluación de impacto a esta y a las celdas circundantes que indican el aspecto del juego que queremos simular. Para obtener una imagen completa, acumulamos estos valores en la misma cuadrícula. Después de eso, podemos realizar varias consultas de cuadrícula para comprender el mundo y decidir sobre el posicionamiento y los puntos de destino.

Tomemos, por ejemplo, "el punto más débil en la defensa del enemigo". Tenemos un muro defensivo, cuyo ataque queremos enviar soldados de a pie, pero hay 3 catapultas detrás de él: 2 cerca uno del otro a la izquierda, 1 a la derecha. ¿Cómo elegimos una buena posición de ataque?

Para empezar, podemos asignar +1 puntos de protección a todas las celdas de la cuadrícula dentro del ataque de catapulta. Dibujar estos puntos en el mapa de influencia para una catapulta se ve así:


El rectángulo azul limita todas las celdas en las que puedes lanzar un ataque contra la pared. Los cuadrados rojos indican +1 influencia de catapulta. En nuestro caso, esto significa el área de su ataque y la amenaza a las unidades atacantes.

Ahora agregamos el efecto de la segunda catapulta:


Tenemos un área oscura en la que se forma la influencia de dos catapultas, lo que les da a estas células protección +2. ¡La celda +2 dentro de la zona azul puede ser un lugar particularmente peligroso para atacar la pared! Agregue la influencia de la última catapulta:


[Iconos: CC-BY: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

Ahora tenemos una designación completa del área cubierta por las catapultas. En la zona de ataque potencial, hay una celda con influencias de catapulta +2, 11 celdas con influencia de +1 y 2 celdas con influencia de catapulta 0: estos son los principales candidatos para la posición de ataque, en ellos podemos atacar la pared sin temor al fuego de catapulta.

La ventaja de los mapas de influencia es que transforman un espacio continuo con un conjunto casi infinito de posibles posiciones en un conjunto discreto de posiciones aproximadas, con respecto al cual podemos tomar decisiones muy rápidamente.

Sin embargo, obtuvimos esta ventaja solo al elegir un pequeño número de posibles posiciones de ataque. ¿Por qué deberíamos usar el mapa de influencia aquí en lugar de verificar manualmente la distancia desde cada catapulta a cada una de estas posiciones?

En primer lugar, calcular un mapa de influencia puede ser muy económico. Después de poner los puntos de influencia en la carta, no es necesario cambiarla hasta que las entidades comiencen a moverse. Esto significa que no necesitamos realizar cálculos de distancia constantemente o interrogar iterativamente a todas las unidades posibles: “horneamos” esta información en el mapa y podemos enviarle solicitudes cualquier número de veces.

En segundo lugar, podemos superponer y combinar diferentes mapas de influencia para cumplir consultas más complejas. Por ejemplo, para seleccionar un lugar seguro para escapar, podemos tomar un mapa de la influencia de nuestros enemigos y restar el mapa de nuestros amigos: las celdas de la cuadrícula con el mayor valor negativo se considerarán seguras.


Cuanto más rojo, más peligroso y más verde, más seguro. Las áreas en las que se superponen las influencias pueden neutralizarse total o parcialmente para reflejar áreas de influencia en conflicto.

Finalmente, los mapas de influencia son fáciles de visualizar al renderizar en el mundo. Pueden ser una sugerencia valiosa para los diseñadores que necesitan personalizar la IA en función de las propiedades visibles, y pueden ser observados en tiempo real para comprender por qué la IA elige sus decisiones.

Conclusión

Espero que el artículo te brinde una descripción general de las herramientas y enfoques más populares utilizados en la IA de los juegos, así como las situaciones en las que se pueden aplicar. El artículo no consideró muchas otras técnicas (se usan con menos frecuencia, pero podrían ser igualmente efectivas), incluidas las siguientes:

• algoritmos de tareas de optimización, incluida la escalada a la cima, el descenso del gradiente y los algoritmos genéticos.
• algoritmos competitivos de búsqueda / planificación como minimax y recorte alfa beta
• técnicas de clasificación, por ejemplo, perceptrones, redes neuronales y el método del vector de soporte
• sistemas de percepción de agentes y procesamiento de memoria
• enfoques arquitectónicos de la IA, como sistemas híbridos, arquitecturas predicativas (arquitecturas de Brooks) y otras formas de descomponer los sistemas de IA en capas
• herramientas de animación como planificación de movimiento y coincidencia de movimiento
• tareas relacionadas con el rendimiento, como el nivel de detalle, los algoritmos en cualquier momento y la temporización

Para leer más sobre estos temas, así como los temas discutidos en este artículo, puede estudiar las siguientes fuentes.

• GameDev.net tiene artículos y tutoriales sobre inteligencia artificial , así como un foro sobre inteligencia artificial .
• En AiGameDev.com tener muchas presentaciones y artículos sobre una amplia gama de temas de la inteligencia artificial en el contexto del desarrollo de juegos
• GDC Vault tiene informes con GDC AI Summit, muchos de los cuales están disponibles de forma gratuita: https://www.gdcvault.com/
  
• Además, el AI Game Programmers Guild tiene un montón de enlaces a artículos antiguos y presentaciones de esta cumbre: http://gameai.com/
  
• El investigador de IA y desarrollador de juegos Tommy Thompson tiene un canal de YouTube dedicado a explicar y explorar la IA en juegos comerciales: https://www.youtube.com/user/tthompso

Muchos de los materiales de la más alta calidad se pueden encontrar en libros, incluidos los siguientes:

• Game AI Pro Series es una colección de artículos breves que explican cómo implementar funciones específicas o resolver problemas específicos. En http://www.gameaipro.com/ publicaron fragmentos gratuitos de libros anteriores.
  
  • Game AI Pro: Sabiduría recopilada de profesionales de Game AI
    
  • Game AI Pro 2: Sabiduría recopilada de los profesionales de Game AI
    
  • Game AI Pro 3: Sabiduría recopilada de los profesionales de Game AI
    
  
  
• AI Game Programming Wisdom Game AI Pro. , . , !
  
  
  • AI Game Programming Wisdom 1
    
  • AI Game Programming Wisdom 2
    
  • AI Game Programming Wisdom 3
    
  • AI Game Programming Wisdom 4
    
• Artificial Intelligence: A Modern Approach — , . , , , .

Además, hay varios buenos libros sobre juegos de IA en general, escritos por profesionales de la industria. Es difícil dar preferencia a cualquiera: lea las reseñas y elija la que más le convenga.