Atopei algún material interesante sobre a intelixencia artificial nos xogos. Cunha explicación de cousas básicas sobre a IA mediante exemplos sinxelos, e no seu interior hai moitas ferramentas e métodos útiles para o seu cómodo desenvolvemento e deseño. Como, onde e cando usalos tamén está aí.
A maioría dos exemplos están escritos en pseudocódigo, polo que non se requiren coñecementos avanzados de programación. Baixo o corte hai 35 follas de texto con imaxes e gifs, así que prepárate.
UPD. Pido desculpas, pero xa fixen a miña propia tradución deste artigo sobre Habré . Podes ler a súa versión , pero por algún motivo pasoume o artigo (utilicei a busca, pero algo saíu mal). E como estou escribindo nun blog dedicado ao desenvolvemento de xogos, decidín deixar a miña versión da tradución para os subscritores (algúns puntos teñen un formato diferente, algúns foron omitidos deliberadamente por consello dos desenvolvedores).
Que é a IA?
Game AI céntrase en que accións debe realizar un obxecto en función das condicións nas que se atopa. A isto denomínase normalmente xestión de "axente intelixente", onde un axente é un personaxe dun xogador, un vehículo, un bot ou, ás veces, algo máis abstracto: un grupo enteiro de entidades ou mesmo unha civilización. En cada caso, é unha cousa que debe ver o seu entorno, tomar decisións en función del e actuar de acordo con elas. Isto chámase ciclo Sentir/Pensar/Actuar:
- Sentido: o axente atopa ou recibe información sobre cousas do seu contorno que poden influír no seu comportamento (ameazas nas proximidades, elementos para recoller, lugares interesantes para explorar).
- Pense: o axente decide como reaccionar (considera se é o suficientemente seguro para recoller elementos ou se debe loitar/esconderse primeiro).
- Actuar: o axente realiza accións para aplicar a decisión anterior (comeza a moverse cara ao inimigo ou obxecto).
- ...agora a situación cambiou polas accións dos personaxes, polo que o ciclo se repite con novos datos.
A IA tende a centrarse na parte do sentido do bucle. Por exemplo, os coches autónomos toman fotografías da estrada, combínaas con datos de radar e lidar e interprétanas. Normalmente, isto faise mediante a aprendizaxe automática, que procesa os datos entrantes e dálle significado, extraendo información semántica como "hai outro coche 20 metros por diante de ti". Estes son os chamados problemas de clasificación.
Os xogos non necesitan un sistema complexo para extraer información xa que a maioría dos datos xa forman parte integrante del. Non é necesario executar algoritmos de recoñecemento de imaxes para determinar se hai un inimigo por diante: o xogo xa coñece e alimenta a información directamente ao proceso de toma de decisións. Polo tanto, a parte Sentido do ciclo adoita ser moito máis sinxela que a parte Pensar e actuar.
Limitacións da IA do xogo
A IA ten unha serie de limitacións que deben ser observadas:
- A IA non precisa ser adestrada con antelación, coma se fose un algoritmo de aprendizaxe automática. Non ten sentido escribir unha rede neuronal durante o desenvolvemento para supervisar decenas de miles de xogadores e aprender a mellor forma de xogar contra eles. Por que? Porque o xogo non foi lanzado e non hai xogadores.
- O xogo debe ser divertido e desafiante, polo que os axentes non deberían atopar o mellor enfoque contra as persoas.
- Os axentes deben parecer realistas para que os xogadores sintan que xogan contra persoas reais. O programa AlphaGo superou aos humanos, pero os pasos escollidos estaban moi lonxe da comprensión tradicional do xogo. Se o xogo simula un opoñente humano, este sentimento non debería existir. Hai que cambiar o algoritmo para que tome decisións plausibles e non ideais.
- A IA debe funcionar en tempo real. Isto significa que o algoritmo non pode monopolizar o uso da CPU durante longos períodos de tempo para tomar decisións. Incluso 10 milisegundos son demasiado longos, porque a maioría dos xogos só precisan de 16 a 33 milisegundos para procesar todo e pasar ao seguinte cadro gráfico.
- O ideal é que polo menos parte do sistema se basee en datos, para que os non codificadores poidan facer cambios e os axustes poidan ocorrer máis rápido.
Vexamos os enfoques da IA que cobren todo o ciclo Sentido/Pensa/Actuar.
Toma de decisións básicas
Comecemos co xogo máis sinxelo: Pong. Obxectivo: move a paleta para que a pelota rebote nela en lugar de pasar voando. É como o tenis, onde perdes se non golpeas a pelota. Aquí a IA ten unha tarefa relativamente sinxela: decidir en que dirección mover a plataforma.
Declaracións condicionais
Para a IA en Pong, a solución máis obvia é tentar sempre colocar a plataforma debaixo da pelota.
Un algoritmo sinxelo para isto, escrito en pseudocódigo:
cada cadro/actualización mentres o xogo está en execución:
se a pelota está á esquerda da pala:
mover a paleta cara á esquerda
senón se a pelota está á dereita da paleta:
move a paleta cara á dereita
Se a plataforma se move á velocidade da pelota, este é o algoritmo ideal para a IA en Pong. Non hai que complicar nada se non hai tantos datos e posibles accións para o axente.
Este enfoque é tan sinxelo que todo o ciclo Sentir/Pensar/Actuar apenas se nota. Pero aí está:
- A parte do sentido está en dúas declaracións if. O xogo sabe onde está a pelota e onde está a plataforma, polo que a IA busca esa información.
- A parte Think tamén se inclúe nas dúas declaracións if. Encarnan dúas solucións, que neste caso son mutuamente excluíntes. Como resultado, selecciónase unha das tres accións: move a plataforma cara á esquerda, móvaa cara á dereita ou non fai nada se xa está colocada correctamente.
- A parte Act atópase nas instrucións Mover a paleta á esquerda e a Mover a paleta á dereita. Dependendo do deseño do xogo, poden mover a plataforma ao instante ou a unha velocidade específica.
Tales enfoques chámanse reactivos: hai un conxunto simple de regras (neste caso, se as declaracións do código) que reaccionan ao estado actual do mundo e toman medidas.
Árbore de decisión
O exemplo de Pong é en realidade equivalente a un concepto formal de IA chamado árbore de decisións. O algoritmo pasa por el para chegar a unha "folla", unha decisión sobre que acción tomar.
Imos facer un diagrama de bloques da árbore de decisións para o algoritmo da nosa plataforma:
Cada parte da árbore chámase nodo; a IA usa a teoría de gráficos para describir tales estruturas. Hai dous tipos de nodos:
- Nodos de decisión: elixir entre dúas alternativas baseada en probar algunha condición, onde cada alternativa se representa como un nodo separado.
- Nodos finais: A acción a realizar que representa a decisión final.
O algoritmo comeza desde o primeiro nodo (a "raíz" da árbore). Toma unha decisión sobre a que nodo fillo ir ou executa a acción almacenada no nodo e sae.
Cal é o beneficio de que unha árbore de decisión faga o mesmo traballo que as declaracións if da sección anterior? Aquí existe un sistema xeral onde cada decisión ten só unha condición e dous posibles resultados. Isto permite ao desenvolvedor crear IA a partir de datos que representan decisións nunha árbore sen ter que codificala. Presentámolo en forma de táboa:
No lado do código obterás un sistema para ler cadeas. Crea un nodo para cada un deles, conecta a lóxica de decisión baseada na segunda columna e os nodos fillos baseados na terceira e cuarta columnas. Aínda tes que programar as condicións e as accións, pero agora a estrutura do xogo será máis complexa. Aquí engades decisións e accións adicionais e despois personaliza toda a IA simplemente editando o ficheiro de texto de definición da árbore. A continuación, transfire o ficheiro ao deseñador do xogo, quen pode cambiar o comportamento sen recompilar o xogo nin cambiar o código.
As árbores de decisión son moi útiles cando se constrúen automaticamente a partir dun gran conxunto de exemplos (por exemplo, usando o algoritmo ID3). Isto convérteas nunha ferramenta eficaz e de alto rendemento para clasificar situacións a partir dos datos obtidos. Non obstante, imos máis aló dun simple sistema para que os axentes seleccionen accións.
Escenarios
Analizamos un sistema de árbore de decisións que utilizaba condicións e accións creadas previamente. A persoa que deseña a IA pode organizar a árbore como queira, pero aínda ten que confiar no programador que o programa todo. E se puidésemos darlle ao deseñador as ferramentas para crear as súas propias condicións ou accións?
Para que o programador non teña que escribir código para as condicións Is Ball Left Of Paddle e Is Ball Right Of Paddle, pode crear un sistema no que o deseñador escribirá condicións para comprobar estes valores. A continuación, os datos da árbore de decisións terán este aspecto:
Isto é esencialmente o mesmo que na primeira táboa, pero as solucións teñen o seu propio código, un pouco como a parte condicional dunha instrución if. No lado do código, isto leríase na segunda columna para os nodos de decisión, pero en lugar de buscar unha condición específica para executar (Is Ball Left Of Paddle), avalía a expresión condicional e devolve verdadeiro ou falso en consecuencia. Isto faise usando a linguaxe de guión Lua ou Angelscript. Utilizándoas, un desenvolvedor pode coller obxectos no seu xogo (bola e pa) e crear variables que estarán dispoñibles no guión (bola.posición). Ademais, a linguaxe de script é máis sinxela que C++. Non require unha fase de compilación completa, polo que é ideal para axustar rapidamente a lóxica do xogo e permite que os "non codificadores" creen eles mesmos as funcións necesarias.
No exemplo anterior, a linguaxe de script úsase só para avaliar a expresión condicional, pero tamén se pode usar para accións. Por exemplo, os datos Mover Paddle Right poderían converterse nunha instrución de guión (ball.position.x += 10). Para que a acción tamén estea definida no guión, sen necesidade de programar Move Paddle Right.
Podes ir aínda máis lonxe e escribir toda a árbore de decisións nunha linguaxe de script. Este será código en forma de instrucións condicionais codificadas, pero localizaranse en ficheiros de script externos, é dicir, pódense cambiar sen recompilar todo o programa. Moitas veces podes editar o ficheiro de guión durante o xogo para probar rapidamente diferentes reaccións da IA.
Resposta ao evento
Os exemplos anteriores son perfectos para Pong. Realizan continuamente o ciclo Sentir/Pensar/Actuar e actúan baseándose no último estado do mundo. Pero en xogos máis complexos cómpre reaccionar ante eventos individuais e non avaliar todo á vez. Pong neste caso xa é un mal exemplo. Imos escoller outro.
Imaxina un tirador onde os inimigos están inmóbiles ata que detectan o xogador, despois de que actúan dependendo da súa "especialización": alguén correrá para "precipitarse", alguén atacará desde lonxe. Non deixa de ser un sistema reactivo básico - "se un xogador é detectado, fai algo" - pero loxicamente pódese dividir nun evento de xogador visto e unha reacción (selecciona unha resposta e execútaa).
Isto lévanos de volta ao ciclo Sentir/Pensar/Actuar. Podemos codificar unha parte Sense que comprobará cada fotograma se a IA ve o reprodutor. Se non, non pasa nada, pero se ve, créase o evento Player Seen. O código terá unha sección separada que di "cando se produza o evento Player Seen, fai" onde está a resposta que necesitas para abordar as partes Think and Act. Así, establecerás reaccións ao evento Player Seen: para o personaxe "apurado" - ChargeAndAttack e para o francotirador - HideAndSnipe. Estas relacións pódense crear no ficheiro de datos para a súa edición rápida sen ter que recompilar. Aquí tamén se pode usar a linguaxe de script.
Tomar decisións difíciles
Aínda que os sistemas de reacción sinxelos son moi potentes, hai moitas situacións nas que non son suficientes. Ás veces cómpre tomar decisións diferentes en función do que o axente está facendo actualmente, pero é difícil imaxinar isto como unha condición. Ás veces, hai demasiadas condicións para representalas efectivamente nunha árbore de decisións ou guión. Ás veces cómpre avaliar con antelación como vai cambiar a situación antes de decidir o seguinte paso. Son necesarios enfoques máis sofisticados para resolver estes problemas.
Máquina de estados finitos
Máquina de estados finitos ou FSM (máquina de estados finitos) é unha forma de dicir que o noso axente está actualmente nun dos varios estados posibles, e que pode pasar dun estado a outro. Hai un certo número de tales estados, de aí o nome. O mellor exemplo da vida é un semáforo. Hai diferentes secuencias de luces en diferentes lugares, pero o principio é o mesmo: cada estado representa algo (para, camiña, etc.). Un semáforo só está nun estado en cada momento e móvese dun a outro en base a regras sinxelas.
É unha historia semellante cos NPC nos xogos. Por exemplo, imos tomar unha garda cos seguintes estados:
- Patrullando.
- Atacando.
- Fuxindo.
E estas condicións para cambiar o seu estado:
- Se o garda ve ao inimigo, ataca.
- Se o garda ataca pero xa non ve ao inimigo, volve patrullar.
- Se un garda ataca pero está gravemente ferido, foxe.
Tamén podes escribir declaracións if cunha variable de estado do gardián e varias comprobacións: hai un inimigo preto, cal é o nivel de saúde do NPC, etc. Engadimos algúns estados máis:
- Ociosidade - entre patrullas.
- Buscando - cando o inimigo observado desapareceu.
- Buscar axuda: cando se detecta un inimigo, pero é demasiado forte para loitar só.
A elección para cada un deles é limitada; por exemplo, o garda non buscará un inimigo oculto se ten pouca saúde.
Despois de todo, hai unha enorme lista de "se" , Iso " pode chegar a ser demasiado engorroso, polo que necesitamos formalizar un método que nos permita ter presentes os estados e as transicións entre estados. Para iso, temos en conta todos os estados, e baixo cada estado anotamos nunha lista todas as transicións a outros estados, xunto coas condicións necesarias para elas.
Esta é unha táboa de transición de estado: unha forma completa de representar a FSM. Debuxemos un diagrama e obteñamos unha visión completa de como cambia o comportamento dos NPC.
O diagrama reflicte a esencia da toma de decisións para este axente en función da situación actual. Ademais, cada frecha mostra unha transición entre estados se a condición ao lado é certa.
Cada actualización comprobamos o estado actual do axente, miramos a lista de transicións e, se se cumpren as condicións para a transición, acepta o novo estado. Por exemplo, cada fotograma comproba se o temporizador de 10 segundos caducou e, se é así, a garda pasa do estado de inactividade a Patrulla. Do mesmo xeito, o estado Atacante comproba a saúde do axente; se é baixo, pasará ao estado Fuxido.
Trátase de xestionar as transicións entre estados, pero que pasa co comportamento asociado cos propios estados? En termos de implementar o comportamento real para un estado particular, normalmente hai dous tipos de "gancho" onde asignamos accións ao FSM:
- Accións que realizamos periodicamente para o estado actual.
- As accións que realizamos ao pasar dun estado a outro.
Exemplos para o primeiro tipo. O estado de patrulla moverá o axente ao longo da ruta de patrulla cada cadro. O estado Atacante tentará iniciar un ataque en cada fotograma ou transición a un estado onde isto sexa posible.
Para o segundo tipo, considere a transición "se o inimigo é visible e o inimigo é demasiado forte, vai ao estado Buscar axuda. O axente debe escoller onde buscar axuda e almacenar esta información para que o estado Finding Help saiba onde ir. Unha vez que se atopa axuda, o axente volve ao estado de ataque. Neste punto, quererá dicirlle ao aliado sobre a ameaza, polo que pode ocorrer a acción NotifyFriendOfThreat.
Unha vez máis, podemos mirar este sistema a través da lente do ciclo Sentir/Pensar/Actuar. O sentido está plasmado nos datos utilizados pola lóxica de transición. Think - transicións dispoñibles en cada estado. E Act lévase a cabo mediante accións realizadas periodicamente dentro dun estado ou en transicións entre estados.
Ás veces, a consulta continua das condicións de transición pode ser custosa. Por exemplo, se cada axente realiza cálculos complexos en cada fotograma para determinar se pode ver os inimigos e comprender se pode pasar do estado de patrulla ao ataque, isto levará moito tempo á CPU.
Os cambios importantes no estado do mundo pódense considerar como eventos que se procesarán a medida que se produzan. En lugar de que o FSM comprobe a condición de transición "¿pode o meu axente ver o reprodutor?" cada fotograma, pódese configurar un sistema separado para comprobar con menos frecuencia (por exemplo, 5 veces por segundo). E o resultado é emitir Player Seen cando pase o control.
Isto pásase ao FSM, que agora debería ir á condición de recepción do evento Player Seen e responder en consecuencia. O comportamento resultante é o mesmo agás un atraso case imperceptible antes de responder. Pero o rendemento mellorou como resultado de separar a parte Sense nunha parte separada do programa.
Máquina xerárquica de estados finitos
Non obstante, traballar con grandes FSM non sempre é conveniente. Se queremos ampliar o estado de ataque para separar MeleeAttacking e RangedAttacking, teremos que cambiar as transicións de todos os demais estados que levan ao estado de Ataque (actual e futuro).
Probablemente notaches que no noso exemplo hai moitas transicións duplicadas. A maioría das transicións no estado de inactividade son idénticas ás transicións no estado de patrulla. Estaría ben non repetirnos, sobre todo se engadimos máis estados semellantes. Ten sentido agrupar Idling and Patrolling baixo a etiqueta xeral de "non combate", onde só hai un conxunto común de transicións para combater os estados. Se pensamos nesta etiqueta como un estado, entón Idling e Patrolling convértense en subestados. Un exemplo de uso dunha táboa de transición separada para un novo subestado non de combate:
Principais estados:
Estado fóra de combate:
E en forma de diagrama:
É o mesmo sistema, pero cun novo estado de non combate que inclúe Idling and Patrolling. Con cada estado que contén un FSM con subestados (e estes subestados, á súa vez, conteñen os seus propios FSM - e así por diante durante todo o tempo que necesites), obtemos unha máquina de estados finitos xerárquicos ou HFSM (máquina de estados finitos xerárquicos). Ao agrupar o estado non de combate, recortamos unha morea de transicións redundantes. Podemos facer o mesmo para calquera estado novo con transicións comúns. Por exemplo, se no futuro expandimos o estado Ataque aos estados Ataque corpo a corpo e Ataque con mísiles, serán subestados que transirán entre si en función da distancia ao inimigo e da dispoñibilidade de munición. Como resultado, os comportamentos e subcomportamentos complexos pódense representar cun mínimo de transicións duplicadas.
Árbore de comportamento
Con HFSM créanse combinacións complexas de comportamentos dun xeito sinxelo. Non obstante, existe unha lixeira dificultade de que a toma de decisións en forma de regras de transición estea estreitamente relacionada co estado actual. E en moitos xogos isto é exactamente o que se necesita. E un uso coidadoso da xerarquía estatal pode reducir o número de repeticións de transición. Pero ás veces necesitas regras que funcionen independentemente do estado no que te atopes ou que se apliquen en case calquera estado. Por exemplo, se a saúde dun axente cae ao 25%, quererás que fuxa independentemente de se estaba en combate, inactivo ou falando; terás que engadir esta condición a cada estado. E se despois o teu deseñador quere cambiar o limiar de saúde baixo do 25% ao 10%, entón terás que facelo de novo.
Idealmente, esta situación require un sistema no que as decisións sobre "en que estado estar" estean fóra dos propios estados, para facer cambios só nun lugar e non tocar as condicións de transición. As árbores de comportamento aparecen aquí.
Hai varias formas de implementalas, pero a esencia é aproximadamente a mesma para todos e é semellante a unha árbore de decisións: o algoritmo comeza cun nodo "raíz" e a árbore contén nodos que representan decisións ou accións. Non obstante, hai algunhas diferenzas clave:
- Os nodos agora devolven un dos tres valores: Con éxito (se o traballo se completa), Fallo (se non se pode iniciar) ou En execución (se aínda está en execución e non hai resultado final).
- Non hai máis nodos de decisión para escoller entre dúas alternativas. Pola contra, son nodos Decorator, que teñen un nodo fillo. Se teñen éxito, executan o seu único nodo fillo.
- Os nós que realizan accións devolven un valor en execución para representar as accións que se están a realizar.
Este pequeno conxunto de nodos pódese combinar para crear un gran número de comportamentos complexos. Imaxinemos o garda HFSM do exemplo anterior como unha árbore de comportamento:
Con esta estrutura non debería haber unha transición obvia dos estados de inactividade/patrulla a un estado de ataque ou calquera outro estado. Se un inimigo é visible e a saúde do personaxe é baixa, a execución deterase no nodo Fuxido, independentemente do nodo que executase anteriormente: patrulla, inactividade, ataque ou calquera outro.
As árbores de comportamento son complexas: hai moitas formas de compoñelas e atopar a combinación correcta de decoradores e nodos compostos pode ser un reto. Tamén hai preguntas sobre a frecuencia con que comprobar a árbore: queremos revisar todas as partes dela ou só cando unha das condicións cambiou? Como almacenamos o estado dos nodos: como sabemos cando estivemos inactivos durante 10 segundos ou como sabemos que nodos se executaron a última vez para poder procesar a secuencia correctamente?
É por iso que hai moitas implementacións. Por exemplo, algúns sistemas substituíron os nós decoradores por decoradores en liña. Volven a avaliar a árbore cando as condicións do decorador cambian, axudan a unirse aos nós e proporcionan actualizacións periódicas.
Sistema baseado en utilidades
Algúns xogos teñen moitas mecánicas diferentes. É desexable que reciban todos os beneficios de regras de transición simples e xerais, pero non necesariamente na forma dunha árbore de comportamento completa. En lugar de ter un conxunto claro de opcións ou unha árbore de accións posibles, é máis fácil examinar todas as accións e escoller a máis adecuada no momento.
O sistema baseado en utilidades axudará só con isto. Este é un sistema no que o axente ten unha variedade de accións e escolle cales realizar en función da utilidade relativa de cada unha. Onde a utilidade é unha medida arbitraria do importante ou desexable que é que o axente realice esta acción.
A utilidade calculada dunha acción en función do estado e do ambiente actual, o axente pode comprobar e seleccionar o outro estado máis axeitado en calquera momento. Isto é similar ao FSM, excepto cando as transicións están determinadas por unha estimación para cada estado potencial, incluído o actual. Teña en conta que escollemos a acción máis útil para seguir adiante (ou quedarnos se xa a completamos). Para obter máis variedade, esta podería ser unha selección equilibrada pero aleatoria dunha pequena lista.
O sistema asigna un rango arbitrario de valores de utilidade, por exemplo, de 0 (totalmente indesexable) a 100 (completamente desexable). Cada acción ten unha serie de parámetros que afectan ao cálculo deste valor. Volvendo ao noso exemplo de gardián:
As transicións entre accións son ambiguas: calquera estado pode seguir a calquera outro. As prioridades de acción atópanse nos valores de utilidade devoltos. Se un inimigo é visible, e ese inimigo é forte e a saúde do personaxe é baixa, Fleeing e FindingHelp devolverán valores altos distintos de cero. Neste caso, FindingHelp sempre será maior. Así mesmo, as actividades non de combate nunca retornan máis de 50, polo que sempre serán inferiores ás de combate. Debe telo en conta ao crear accións e calcular a súa utilidade.
No noso exemplo, as accións devolven un valor constante fixo ou un dos dous valores fixos. Un sistema máis realista devolvería unha estimación a partir dun intervalo continuo de valores. Por exemplo, a acción Fuxir devolve valores de utilidade máis altos se a saúde do axente é baixa, e a acción de Atacar devolve valores de utilidade máis baixos se o inimigo é demasiado forte. Por iso, a acción Fuxir prima sobre Atacar en calquera situación na que o axente sinta que non ten saúde suficiente para derrotar ao inimigo. Isto permite que as accións se prioricen en función de calquera número de criterios, facendo que este enfoque sexa máis flexible e variable que unha árbore de comportamento ou FSM.
Cada acción ten moitas condicións para o cálculo do programa. Poden escribirse en linguaxe de guións ou como unha serie de fórmulas matemáticas. Os Sims, que simula a rutina diaria dun personaxe, engade unha capa adicional de cálculo: o axente recibe unha serie de "motivacións" que inflúen nas valoracións das utilidades. Se un personaxe ten fame, pasará aínda máis fame co paso do tempo, e o valor de utilidade da acción EatFood aumentará ata que o personaxe a realice, reducindo o nivel de fame e devolvendo o valor de EatFood a cero.
A idea de seleccionar accións baseadas nun sistema de clasificación é bastante sinxela, polo que un sistema baseado en utilidades pode usarse como parte dos procesos de toma de decisións de IA, en lugar de substituírlles completamente. A árbore de decisión pode solicitar unha clasificación de utilidade de dous nodos fillos e seleccionar o superior. Do mesmo xeito, unha árbore de comportamento pode ter un nodo de utilidade composto para avaliar a utilidade das accións para decidir que fillo executar.
Movemento e navegación
Nos exemplos anteriores, tiñamos unha plataforma que movíamos á esquerda ou á dereita e un garda que patrullaba ou atacaba. Pero como manexamos exactamente o movemento dos axentes durante un período de tempo? Como fixamos a velocidade, como evitamos obstáculos e como planificamos unha ruta cando chegar a un destino é máis difícil que movernos en liña recta? Vexamos isto.
Управление
Na fase inicial, asumiremos que cada axente ten un valor de velocidade, que inclúe a rapidez con que se move e en que dirección. Pódese medir en metros por segundo, quilómetros por hora, píxeles por segundo, etc. Recordando o bucle Sense/Think/Act, podemos imaxinar que a parte Think selecciona unha velocidade e a parte Act aplica esa velocidade ao axente. Normalmente os xogos teñen un sistema de física que fai esta tarefa por ti, aprendendo o valor da velocidade de cada obxecto e axustándoo. Polo tanto, podes deixar a IA cunha tarefa: decidir que velocidade debe ter o axente. Se sabes onde debe estar o axente, entón tes que movelo na dirección correcta a unha velocidade establecida. Unha ecuación moi trivial:
viaxe_desexada = posición_destino – posición_axente
Imaxina un mundo en 2D. O axente está no punto (-2,-2), o destino está nalgún lugar do nordeste no punto (30, 20) e o camiño necesario para que o axente chegue é (32, 22). Digamos que estas posicións se miden en metros: se tomamos que a velocidade do axente é de 5 metros por segundo, escalaremos o noso vector de desprazamento e obteremos unha velocidade de aproximadamente (4.12, 2.83). Con estes parámetros, o axente chegaría ao seu destino en case 8 segundos.
Podes volver calcular os valores en calquera momento. Se o axente estivese a metade do obxectivo, o movemento sería a metade da lonxitude, pero como a velocidade máxima do axente é de 5 m/s (decidimos isto anteriormente), a velocidade será a mesma. Isto tamén funciona para os obxectivos en movemento, permitindo que o axente faga pequenos cambios mentres se moven.
Pero queremos máis variación, por exemplo, aumentando lentamente a velocidade para simular un personaxe que pasa de estar de pé a correr. O mesmo pódese facer ao final antes de parar. Estas características coñécense como comportamentos de dirección, cada un deles con nomes específicos: Seek, Flee, Arrival, etc. A idea é que se poidan aplicar forzas de aceleración á velocidade do axente, baseándose en comparar a posición do axente e a velocidade actual co destino en para utilizar diferentes métodos de desprazamento ao obxectivo.
Cada comportamento ten un propósito lixeiramente diferente. A busca e a chegada son formas de mover un axente a un destino. A prevención e a separación de obstáculos axustan o movemento do axente para evitar obstáculos no camiño cara á meta. O aliñamento e a cohesión fan que os axentes se movan xuntos. Pódese sumar calquera número de comportamentos de dirección diferentes para producir un único vector de camiño tendo en conta todos os factores. Un axente que utiliza os comportamentos de chegada, separación e evitación de obstáculos para manterse lonxe das paredes e doutros axentes. Este enfoque funciona ben en lugares abertos sen detalles innecesarios.
En condicións máis difíciles, a adición de diferentes comportamentos funciona peor; por exemplo, un axente pode quedar atrapado nunha parede debido a un conflito entre a chegada e a evitación de obstáculos. Polo tanto, cómpre considerar opcións máis complexas que simplemente engadir todos os valores. O camiño é o seguinte: en lugar de sumar os resultados de cada comportamento, podes considerar o movemento en diferentes direccións e escoller a mellor opción.
Non obstante, nun ambiente complexo con rúas sen saída e eleccións sobre o camiño a seguir, necesitaremos algo aínda máis avanzado.
Buscar un camiño
Os comportamentos de dirección son excelentes para o movemento sinxelo nunha zona aberta (campo de fútbol ou area) onde ir de A a B é un camiño recto con só pequenos desvíos arredor dos obstáculos. Para rutas complexas, necesitamos buscar camiños, que é unha forma de explorar o mundo e decidir unha ruta por el.
O máis sinxelo é aplicar unha cuadrícula a cada cadrado ao lado do axente e avaliar cales deles están autorizados a moverse. Se un deles é destino, segue o percorrido dende cada praza ata o anterior ata chegar ao principio. Esta é a ruta. Se non, repite o proceso con outras prazas próximas ata atopar o teu destino ou quedar sen prazas (o que significa que non hai ruta posible). Isto é o que se coñece formalmente como Breadth-First Search ou BFS (algoritmo de busca de ancho-primeiro). A cada paso mira en todas as direccións (de aí ancho, "ancho"). O espazo de busca é como unha fronte de onda que se move ata chegar á localización desexada: o espazo de busca se expande en cada paso ata que se inclúe o punto final, despois de que se pode rastrexar ata o principio.
Como resultado, recibirá unha lista de prazas polas que se compila a ruta desexada. Este é o camiño (polo tanto, busca do camiño): unha lista de lugares que o axente visitará mentres segue o destino.
Dado que coñecemos a posición de cada cadrado do mundo, podemos usar comportamentos de dirección para movernos ao longo da ruta: do nodo 1 ao nodo 2, despois do nodo 2 ao nodo 3, etc. A opción máis sinxela é dirixirse cara ao centro do seguinte cadrado, pero unha opción aínda mellor é pararse no medio do bordo entre o cadrado actual e o seguinte. Debido a isto, o axente poderá cortar esquinas en curvas pronunciadas.
O algoritmo BFS tamén ten desvantaxes: explora tantos cadrados na dirección "incorrecta" como na dirección "correcta". Aquí é onde entra en xogo un algoritmo máis complexo chamado A* (estrela A). Funciona do mesmo xeito, pero en lugar de examinar cegamente as prazas veciñas (despois veciños de veciños, despois veciños de veciños de veciños, etc.), recolle os nodos nunha lista e ordénaos para que o seguinte nodo examinado sexa sempre o aquela que leva á ruta máis curta. Os nodos ordénanse en función dunha heurística que ten en conta dúas cousas: o "custo" dunha ruta hipotética ata o cadrado desexado (incluíndo os custos de viaxe) e unha estimación de a que distancia está ese cadrado do destino (sesgando a busca no cadrado). dirección correcta).
Este exemplo mostra que o axente explora un cadrado á vez, escollendo cada vez o adxacente que é o máis prometedor. O camiño resultante é o mesmo que BFS, pero no proceso consideráronse menos cadrados, o que ten un gran impacto no rendemento do xogo.
Movemento sen grella
Pero a maioría dos xogos non están organizados nunha cuadrícula e moitas veces é imposible facelo sen sacrificar o realismo. Son necesarios compromisos. Que tamaño deben ter os cadrados? Demasiado grandes e non poderán representar correctamente pequenos corredores ou xiros, demasiado pequenos e haberá demasiadas prazas que buscar, o que en definitiva levará moito tempo.
O primeiro que hai que entender é que unha malla dános unha gráfica de nodos conectados. Os algoritmos A* e BFS realmente funcionan en gráficos e non lles importa nada a nosa malla. Poderíamos poñer nodos en calquera lugar do mundo do xogo: sempre que haxa unha conexión entre dous nodos conectados calquera, así como entre os puntos de inicio e finalización e polo menos un dos nodos, o algoritmo funcionará igual de ben que antes. A miúdo chámase sistema de waypoints, xa que cada nodo representa unha posición significativa no mundo que pode formar parte de calquera número de camiños hipotéticos.
Exemplo 1: un nó en cada cadrado. A busca comeza no nodo onde se atopa o axente e remata no nodo do cadrado desexado.
Exemplo 2: un conxunto máis pequeno de nós (puntos de paso). A busca comeza no cadrado do axente, pasa polo número necesario de nós e despois continúa ata o destino.
Este é un sistema completamente flexible e potente. Pero é necesario un pouco de coidado para decidir onde e como colocar un waypoint, se non, os axentes simplemente non poden ver o punto máis próximo e non poderán iniciar o camiño. Sería máis doado se puidésemos colocar automaticamente waypoints en función da xeometría do mundo.
Aquí é onde aparece a malla de navegación ou navmesh (malla de navegación). Esta é normalmente unha malla 2D de triángulos que se superpón á xeometría do mundo, onde queira que se lle permita camiñar ao axente. Cada un dos triángulos da malla convértese nun nodo do gráfico e ten ata tres triángulos adxacentes que se converten en nós adxacentes no gráfico.
Esta imaxe é un exemplo do motor Unity: analizou a xeometría do mundo e creou unha navmesh (na captura de pantalla en azul claro). Cada polígono dunha malla de navegación é unha área onde un axente pode estar ou moverse dun polígono a outro. Neste exemplo, os polígonos son máis pequenos que os pisos nos que están situados; isto faise para ter en conta o tamaño do axente, que se estenderá máis aló da súa posición nominal.
Podemos buscar unha ruta a través desta malla, de novo usando o algoritmo A*. Isto daranos unha ruta case perfecta no mundo, que ten en conta toda a xeometría e non require nodos innecesarios e creación de waypoints.
Pathfinding é un tema demasiado amplo para o que unha sección dun artigo non é suficiente. Se queres estudalo con máis detalle, isto axudarache .
Planificación
Aprendemos coa busca de camiños que ás veces non é suficiente con escoller unha dirección e movernos; temos que escoller unha ruta e dar unhas cantas voltas para chegar ao destino desexado. Podemos xeneralizar esta idea: acadar un obxectivo non é só o seguinte paso, senón toda unha secuencia na que ás veces hai que mirar adiante varios pasos para saber cal debe ser o primeiro. Isto chámase planificación. Pathfinding pódese considerar como unha das varias extensións da planificación. En termos do noso ciclo Sentir/Pensar/Actuar, aquí é onde a parte Think planea varias partes Act para o futuro.
Vexamos o exemplo do xogo de mesa Magic: The Gathering. Imos primeiro co seguinte conxunto de cartas nas nosas mans:
- Pantano: dá 1 maná negro (tarxeta de terra).
- Bosque: dá 1 maná verde (tarxeta de terra).
- Fugitive Wizard - Require 1 maná azul para convocar.
- Elvish Mystic - Require 1 maná verde para convocar.
Ignoramos as tres cartas restantes para facilitalo. Segundo as regras, un xogador pode xogar 1 carta de terra por turno, pode "tocar" esta carta para extraer maná dela, e despois lanzar feitizos (incluíndo convocar unha criatura) segundo a cantidade de maná. Nesta situación, o xogador humano sabe xogar Forest, tocar 1 maná verde e, a continuación, convocar Elvish Mystic. Pero como pode a IA do xogo entender isto?
Fácil planificación
O enfoque trivial é probar cada acción por turnos ata que non queden as adecuadas. Ao mirar as cartas, a IA ve o que pode xogar Swamp. E el xoga. Quedan outras accións nesta quenda? Non pode convocar nin a Místico Élfico nin ao Mago Fuxitivo, xa que requiren maná verde e azul respectivamente para convocalos, mentres que Swamp só proporciona maná negro. E xa non poderá xogar ao Bosque, porque xa xogou ao Pantano. Así, a IA do xogo seguiu as regras, pero fíxoo mal. Pódese mellorar.
A planificación pode atopar unha lista de accións que levan o xogo ao estado desexado. Do mesmo xeito que cada praza dun camiño tiña veciños (na busca de camiños), cada acción dun plan tamén ten veciños ou sucesores. Podemos buscar estas accións e as seguintes ata chegar ao estado desexado.
No noso exemplo, o resultado desexado é "invocar unha criatura se é posible". Ao comezo da quenda, só vemos dúas accións posibles permitidas polas regras do xogo:
1. Xoga a Swamp (resultado: Swamp no xogo)
2. Xogar Forest (resultado: Forest no xogo)
Cada acción realizada pode levar a outras accións e pechar outras, de novo dependendo das regras do xogo. Imaxina que xogamos a Swamp: isto eliminará Swamp como o seguinte paso (xa o xogamos), e isto tamén eliminará Forest (porque segundo as regras podes xogar unha carta de terra por turno). Despois disto, a IA engade obter 1 maná negro como seguinte paso porque non hai outras opcións. Se segue adiante e escolle Tap the Swamp, recibirá 1 unidade de maná negro e non poderá facer nada con ela.
1. Xoga a Swamp (resultado: Swamp no xogo)
1.1 Pantano "Tap" (resultado: Pantano "tocado", +1 unidade de maná negro)
Non hai accións dispoñibles - FIN
2. Xogar Forest (resultado: Forest no xogo)
A lista de accións era curta, chegamos a unha vía sen saída. Repetimos o proceso para o seguinte paso. Xogamos a Forest, abrimos a acción "obter 1 maná verde", que á súa vez abrirá a terceira acción: convocar Elvish Mystic.
1. Xoga a Swamp (resultado: Swamp no xogo)
1.1 Pantano "Tap" (resultado: Pantano "tocado", +1 unidade de maná negro)
Non hai accións dispoñibles - FIN
2. Xogar Forest (resultado: Forest no xogo)
2.1 Bosque "Toca" (resultado: O bosque está "tocado", +1 unidade de maná verde)
2.1.1 Invocar Elvish Mystic (resultado: Elvish Mystic en xogo, -1 maná verde)
Non hai accións dispoñibles - FIN
Finalmente, exploramos todas as accións posibles e atopamos un plan que convoca unha criatura.
Este é un exemplo moi simplificado. É aconsellable escoller o mellor plan posible, en lugar de calquera plan que cumpra algúns criterios. En xeral, é posible avaliar plans potenciais en función do resultado ou do beneficio xeral da súa implementación. Podes conseguir 1 punto por xogar unha carta terrestre e 3 puntos por convocar unha criatura. Xogar a Swamp sería un plan de 1 punto. E xogar Forest → Tap the Forest → convocar Elvish Mystic dará inmediatamente 4 puntos.
Así funciona a planificación en Magic: The Gathering, pero a mesma lóxica aplícase noutras situacións. Por exemplo, movendo un peón para facer espazo para que o alfil se mova no xadrez. Ou cúbrese detrás dunha parede para disparar con seguridade en XCOM así. En xeral, entendes a idea.
Planificación mellorada
Ás veces hai demasiadas accións potenciais para considerar todas as opcións posibles. Volvendo ao exemplo con Magic: The Gathering: digamos que no xogo e na túa man hai varias cartas de terra e de criatura: o número de combinacións posibles de movementos pode ser de decenas. Hai varias solucións ao problema.
O primeiro método é o encadeamento cara atrás. En lugar de probar todas as combinacións, é mellor comezar co resultado final e tentar atopar unha ruta directa. En lugar de ir da raíz da árbore a unha folla específica, movémonos na dirección oposta: da folla á raíz. Este método é máis sinxelo e rápido.
Se o inimigo ten 1 saúde, podes atopar o plan "fair 1 ou máis dano". Para conseguilo, débense cumprir unha serie de condicións:
1. O dano pode ser causado por un feitizo - debe estar na man.
2. Para lanzar un feitizo, necesitas maná.
3. Para obter maná, cómpre xogar unha carta de terra.
4. Para xogar unha carta de terra, cómpre telo na man.
Outra forma é a mellor primeira busca. En lugar de probar todos os camiños, escollemos o máis axeitado. Na maioría das veces, este método ofrece o plan óptimo sen custos de busca innecesarios. A* é unha forma de mellor primeira busca: ao examinar as rutas máis prometedoras desde o principio, xa pode atopar o mellor camiño sen ter que comprobar outras opcións.
Unha opción de busca de primeira vez interesante e cada vez máis popular é a Busca de árbores de Monte Carlo. En lugar de adiviñar que plans son mellores que outros ao elixir cada acción posterior, o algoritmo escolle sucesores aleatorios en cada paso ata que chega ao final (cando o plan resultou nunha vitoria ou derrota). O resultado final úsase entón para aumentar ou diminuír o peso das opcións anteriores. Ao repetir este proceso varias veces seguidas, o algoritmo dá unha boa estimación do mellor movemento seguinte, aínda que a situación cambie (se o inimigo toma medidas para interferir co xogador).
Ningunha historia sobre planificación nos xogos estaría completa sen Planificación de accións orientadas a obxectivos ou GOAP (planificación de accións orientadas a obxectivos). Este é un método moi usado e discutido, pero ademais dalgúns detalles distintivos, é esencialmente o método de encadeamento cara atrás do que falamos anteriormente. Se o obxectivo era "destruír ao xogador" e o xogador está a cuberto, o plan podería ser: destruír cunha granada → conseguila → lanzala.
Normalmente hai varios obxectivos, cada un coa súa propia prioridade. Se non se pode completar o obxectivo de maior prioridade (ningunha combinación de accións crea un plan de "matar ao xogador" porque o xogador non é visible), a IA volverá caer aos obxectivos de menor prioridade.
Formación e adaptación
Xa dixemos que a IA do xogo non adoita utilizar a aprendizaxe automática porque non é adecuada para xestionar axentes en tempo real. Pero isto non significa que non poidas tomar algo prestado desta zona. Queremos un opoñente nun tirador do que poidamos aprender algo. Por exemplo, descobre as mellores posicións no mapa. Ou un opoñente nun xogo de loita que bloquearía os movementos combinados de uso frecuente do xogador, motivándoo a usar outros. Polo tanto, a aprendizaxe automática pode ser moi útil en tales situacións.
Estatística e probabilidades
Antes de entrar en exemplos complexos, vexamos ata onde podemos chegar tomando algunhas medidas sinxelas e usándoas para tomar decisións. Por exemplo, a estratexia en tempo real: como determinamos se un xogador pode lanzar un ataque nos primeiros minutos do xogo e que defensa se prepara para facelo? Podemos estudar as experiencias pasadas dun xogador para comprender cales poden ser as reaccións futuras. Para comezar, non temos datos tan brutos, pero podemos recollelos; cada vez que a IA xoga contra un humano, pode rexistrar a hora do primeiro ataque. Despois dunhas sesións, obteremos unha media do tempo que tardará o xogador en atacar no futuro.
Tamén hai un problema cos valores medios: se un xogador precipitou 20 veces e xogou lentamente 20 veces, entón os valores necesarios estarán nalgún lugar no medio, e isto non nos dará nada útil. Unha solución é limitar os datos de entrada: pódense ter en conta as últimas 20 pezas.
Un enfoque similar úsase cando se estima a probabilidade de certas accións asumindo que as preferencias pasadas do xogador serán as mesmas no futuro. Se un xogador nos ataca cinco veces con bola de lume, dúas veces con raio e unha vez con corpo a corpo, é obvio que prefire bola de lume. Imos extrapolar e ver a probabilidade de usar diferentes armas: bola de lume=62,5%, raio=25% e corpo a corpo=12,5%. A nosa IA do xogo debe prepararse para protexerse do lume.
Outro método interesante é usar o Naive Bayes Classifier para estudar grandes cantidades de datos de entrada e clasificar a situación para que a IA reaccione do xeito desexado. Os clasificadores bayesianos son máis coñecidos polo seu uso nos filtros de correo lixo. Alí examinan as palabras, compáraas con onde apareceron esas palabras antes (no spam ou non) e sacan conclusións sobre os correos electrónicos entrantes. Podemos facer o mesmo mesmo con menos entradas. En base a toda a información útil que ve a IA (como que unidades inimigas se crean, ou que feitizos usan ou que tecnoloxías investigaron) e o resultado final (guerra ou paz, apresurarse ou defenderse, etc.) - escolleremos o comportamento da IA desexado.
Todos estes métodos de adestramento son suficientes, pero é recomendable utilizalos en función dos datos das probas. A IA aprenderá a adaptarse ás diferentes estratexias que utilizaron os teus probadores. A IA que se adapta ao xogador despois do lanzamento pode volverse demasiado previsible ou difícil de derrotar.
Adaptación baseada en valores
Dado o contido do noso mundo de xogo e as regras, podemos cambiar o conxunto de valores que inflúen na toma de decisións, en lugar de simplemente usar os datos de entrada. Facemos isto:
- Permite que a IA recompile datos sobre o estado do mundo e os eventos clave durante o xogo (como se indica arriba).
- Imos cambiar algúns valores importantes en función destes datos.
- Implementamos as nosas decisións en función do procesamento ou avaliación destes valores.
Por exemplo, un axente ten varias salas para escoller nun mapa de tiradores en primeira persoa. Cada habitación ten o seu propio valor, que determina o desexable que é visitar. A IA elixe aleatoriamente a que sala ir en función do valor. O axente lembra entón en que cuarto morreu e reduce o seu valor (a probabilidade de que volva alí). Do mesmo xeito para a situación inversa - se o axente destrúe moitos opoñentes, entón o valor da sala aumenta.
Modelo de Markov
E se utilizamos os datos recollidos para facer predicións? Se lembramos todas as salas nas que vemos un xogador durante un período de tempo determinado, predeciremos a que sala pode ir. Seguindo e rexistrando os movementos do xogador entre as salas (valores), podemos predicilos.
Imos tomar tres cuartos: vermello, verde e azul. E tamén as observacións que gravamos ao ver a sesión do xogo:
O número de observacións en cada sala é case igual; aínda non sabemos onde facer un bo lugar para unha emboscada. A recompilación de estatísticas tamén é complicada pola reaparición dos xogadores, que aparecen uniformemente en todo o mapa. Pero os datos da seguinte sala na que entran despois de aparecer no mapa xa son útiles.
Pódese ver que a sala verde convén aos xogadores: a maioría da xente pasa da sala vermella a ela, o 50% dos cales permanece alí máis adiante. A sala azul, pola contra, non é popular; case ninguén acode e, se o fan, non se quedan moito tempo.
Pero os datos dinnos algo máis importante: cando un xogador está nunha sala azul, a seguinte sala na que o vexamos será vermella, non verde. Aínda que a sala verde é máis popular que a vermella, a situación cambia se o xogador está na sala azul. O seguinte estado (é dicir, a sala á que irá o xogador) depende do estado anterior (é dicir, a sala na que se atopa actualmente). Debido a que exploramos as dependencias, faremos predicións máis precisas que se simplemente contamos as observacións de forma independente.
Predicir un estado futuro en base a datos dun estado pasado chámase modelo de Markov, e estes exemplos (con cuartos) chámanse cadeas de Markov. Dado que os patróns representan a probabilidade de cambios entre estados sucesivos, móstranse visualmente como FSM cunha probabilidade ao redor de cada transición. Anteriormente, usabamos FSM para representar o estado de comportamento no que se atopaba un axente, pero este concepto esténdese a calquera estado, estea asociado co axente ou non. Neste caso, os estados representan a sala que ocupa o axente:
Esta é unha forma sinxela de representar a probabilidade relativa de cambios de estado, dándolle á IA algunha capacidade para predecir o seguinte estado. Podes prever varios pasos por diante.
Se un xogador está na sala verde, hai un 50% de posibilidades de que permaneza alí a próxima vez que sexa observado. Pero cales son as posibilidades de que siga alí mesmo despois? Non só existe a posibilidade de que o xogador permaneza na sala verde despois de dúas observacións, senón que tamén existe a posibilidade de que marche e regrese. Velaquí a nova táboa tendo en conta os novos datos:
Mostra que a probabilidade de ver ao xogador na sala verde despois de dúas observacións será igual ao 51% - 21% de que será da sala vermella, 5% delas que o xogador visitará a sala azul entre elas, e 25% que o xogador non sairá da sala verde.
A táboa é simplemente unha ferramenta visual: o procedemento só require multiplicar as probabilidades en cada paso. Isto significa que podes mirar cara ao futuro cunha advertencia: asumimos que a posibilidade de entrar nunha sala depende enteiramente da sala actual. Isto chámase Propiedade de Markov: o estado futuro depende só do presente. Pero isto non é cen por cen preciso. Os xogadores poden cambiar as decisións dependendo doutros factores: nivel de saúde ou cantidade de munición. Como non rexistramos estes valores, as nosas previsións serán menos precisas.
N-gramos
E o exemplo dun xogo de loita e a predicción dos movementos combinados do xogador? O mesmo! Pero en lugar dun estado ou evento, examinaremos as secuencias completas que compoñen un ataque combinado.
Unha forma de facelo é almacenar cada entrada (como Kick, Punch ou Block) nun búfer e escribir todo o búfer como un evento. Entón, o xogador preme repetidamente Kick, Kick, Punch para usar o ataque SuperDeathFist, o sistema de IA almacena todas as entradas nun búfer e lembra as tres últimas utilizadas en cada paso.
(As liñas en negra aparecen cando o xogador lanza o ataque SuperDeathFist).
A IA verá todas as opcións cando o xogador seleccione Kick, seguido doutro Kick, e despois notará que a seguinte entrada sempre é Punch. Isto permitirá ao axente prever o movemento combinado de SuperDeathFist e bloquealo se é posible.
Estas secuencias de eventos chámanse N-gramas, onde N é o número de elementos almacenados. No exemplo anterior era un trigrama de 3 gramos, o que significa: as dúas primeiras entradas utilízanse para predicir a terceira. En consecuencia, nun gramo de 5, as catro primeiras entradas predín a quinta e así por diante.
O deseñador debe escoller coidadosamente o tamaño dos N-gramos. Un N máis pequeno require menos memoria pero tamén almacena menos historial. Por exemplo, un bigrama de 2 gramos gravará Kick, Kick ou Kick, Punch, pero non poderá almacenar Kick, Kick, Punch, polo que a IA non responderá ao combo SuperDeathFist.
Por outra banda, os números máis grandes requiren máis memoria e a IA será máis difícil de adestrar xa que haberá moitas máis opcións posibles. Se tiveses tres entradas posibles de Kick, Punch ou Block, e utilizasemos un de 10 gramos, serían unhas 60 mil opcións diferentes.
O modelo de bigrama é unha cadea de Markov sinxela: cada par de estado pasado/estado actual é un bigrama, e podes predecir o segundo estado baseándose no primeiro. Os N-gramas de 3 gramos e maiores tamén se poden considerar como cadeas de Markov, onde todos os elementos (excepto o último do N-grama) forman xuntos o primeiro estado e o último elemento o segundo. O exemplo do xogo de loita mostra a posibilidade de pasar do estado Kick and Kick ao estado Kick and Punch. Ao tratar varias entradas do historial de entrada como unha única unidade, estamos transformando esencialmente a secuencia de entrada en parte de todo o estado. Isto ofrécenos a propiedade de Markov, que nos permite usar cadeas de Markov para predicir a seguinte entrada e adiviñar cal será o seguinte movemento combinado.
Conclusión
Falamos das ferramentas e enfoques máis habituais no desenvolvemento da intelixencia artificial. Tamén analizamos as situacións nas que hai que utilizar e onde son especialmente útiles.
Isto debería ser suficiente para comprender os conceptos básicos da IA do xogo. Pero, por suposto, estes non son todos métodos. Menos populares, pero non menos eficaces inclúen:
- algoritmos de optimización que inclúen escalada, descenso de gradientes e algoritmos xenéticos
- algoritmos de busca/programación adversarias (poda mínima e alfa-beta)
- métodos de clasificación (perceptróns, redes neuronais e máquinas vectoriais de apoio)
- sistemas de percepción e memoria dos axentes de procesamento
- enfoques arquitectónicos da IA (sistemas híbridos, arquitecturas de subconxuntos e outras formas de superpoñer sistemas de IA)
- Ferramentas de animación (planificación e coordinación de movemento)
- factores de rendemento (nivel de detalle, en calquera momento e algoritmos de segmentación temporal)
Recursos en liña sobre o tema:
1. GameDev.net ten E .
2. contén moitas presentacións e artigos sobre unha ampla gama de temas relacionados co desenvolvemento da IA de xogos.
3. inclúe temas do GDC AI Summit, moitos dos cales están dispoñibles gratuitamente.
4. Tamén se poden atopar materiais útiles na páxina web .
5. Tommy Thompson, investigador de IA e desenvolvedor de xogos, fai vídeos en YouTube cunha explicación e estudo da IA en xogos comerciais.
Libros sobre o tema:
1. A serie de libros Game AI Pro é unha colección de artigos breves que explican como implementar funcións específicas ou como resolver problemas específicos.
2. A serie AI Game Programming Wisdom é a predecesora da serie Game AI Pro. Contén métodos máis antigos, pero case todos son relevantes aínda hoxe.
3. é un dos textos básicos para todos os que queiran comprender o campo xeral da intelixencia artificial. Este non é un libro sobre o desenvolvemento de xogos, ensina os conceptos básicos da IA.
Fonte: www.habr.com