Intel·ligència Artificial en videojocs
======================================

`I.A. en
informàtica <http://ca.wikipedia.org/wiki/Intel%C2%B7lig%C3%A8ncia_artificial>`__:
desenvolupament de programes que prenguin decisions intel·ligents o, si
més no, o que es comportin com si tinguessin una intel·ligència semblant
a la humana.

"La I.A. en videojocs no té a veure amb la intel·ligència, sinó amb
crear experiències realistes i divertides."
`1 <http://www.giantbomb.com/artificial-intelligence/3015-218>`__. El
més habitual és que es refereixi al control del moviment i del
comportament dels `non-player character
(NPC) <http://en.wikipedia.org/wiki/Non-player_character>`__. Vegeu
l'entrada a la wikipedia `Artificial\_intelligence (video
games) <http://en.wikipedia.org/wiki/Artificial_intelligence_%28video_games%29>`__.

Usos més freqüents:

-  Moviments dels elements del joc (*roaming*)
-  Cerca de camins (*pathfinding*), en videojocs de rol (RPGs)
-  Comportament dels NPCs (*behaviour*)

Altres:

-  Estratègia (ex: Escacs)
-  *Emergent AI*: fer que els personatges aprenguin (ex: Nintendogs)
-  Adaptació al nivell de l'usuari (Ex: Mario Karts) o a les
   preferències del jugador (cal deduir-les), per augmentar la
   jugabilitat.

*Roaming*: Moviment dels elements
---------------------------------

Part del programa dedicada a clacular la trajectòria dels
personatges/elements.

Tipus:

-  Fixe
-  Aleatori
-  Seguint un patró (cercles, ziga-zaga,...). Ex:
   `1942 <https://www.youtube.com/watch?v=WRnn-bhv-AE>`__
-  Perseguir
-  Escapar. Ex: `Pacman <https://www.youtube.com/watch?v=OfOCgociObg>`__

"Perseguir" o "escapar" se solen calcular a partir d'un algorisme.

Important: Evitar trajectòries directes (perfectes), perquè són massa
previsibles o massa difícils d'evitar (quan et persegueixen).

*Pathfinding*: Càlcul de camins
-------------------------------

Quan hi ha obstacles, una trajectòria rectilínia o seguint un patró no
serveix. Una solució és associar un graf a l'escena del joc. Un exemple:
   
.. image:: mapa_i_graf.svg
   :align: center


Llavors, s'utilitzen coneguts algorismes existents sobre grafs:

-  `Best-first
   search <http://en.wikipedia.org/wiki/Best-first_search>`__ simple:
   tria la millor direcció segons algun criteri (apropar-se/allunyar-se,
   regla de la mà dreta, ...). No és bo quan hi ha concavitats.
-  `Algorisme de
   Dijkstra <http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm>`__:
   cerca de camins mínim en grafs amb arestes amb pesos.
-  `A\* <http://en.wikipedia.org/wiki/A*_search_algorithm>`__: millora
   Dijkstra, amb heurístics.

Són càlculs lents => millor precalcular-los i emmagatzemar-los.

Cal adaptar-los:

-  què són els nodes del graf? *Tiles*, ...
-  en els jocs, sol haver-hi grans espais "oberts"


*Behaviour*: Control del comportament dels NPC
----------------------------------------------

-  Comportament: trajectòria variable, canviar d'acció o estat, etc.

-  Primer mètode: Diferents tipus de moviment + aleatorietat =
   comportament. Ex:

   +-------------+-----------+---------+------------+
   | Perseguir   | Escapar   | Patró   | Aleatori   |
   +-------------+-----------+---------+------------+
   | 30%         | 20%       | 40%     | 10%        |
   +-------------+-----------+---------+------------+

Pot fer-se variar depenent l'estat del NPC, la dificultat del joc o el
temps.

- Lligar-ho amb la màquina d'estats del NPC.  `Exemple
  <http://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-squad-pattern-using-steering-behaviors--gamedev-13638>`_

-  Usant de llenguatges de regles (*scripting*): "Quan et disparin,
   amaga't; si veus un enemic inferior, ataca'l; si sents un tret,
   ves-hi", etc.

-  Alguns jocs permeten que el jugador defineixi nous comportaments,
   aprofitant el mecanisme de scripting.

-  Moviment i comportament **grupal** (*navigation*):

   -  És més complicat. Comporta evitar xocs i embussos en punts
      estrets.
   -  Ús de patrons (formacions)