IA #4 - le GOAP

[daemondragon]

Bonjour a tous !

Tous d'abord qu'est ce que le GOAP ?

C'est l'abréviation de Goal Oriented Action Planning, ce qui pour les non anglophone, veut dire la

planification des actions en fonction de tes buts, ou de tes souhaits.

C'est un type d'IA qui a pour but de remplacer les FSMs (Finite State Machine), les automates a états

finis en gros. (Le mot anglais est plus classe et plus court a écrire donc c'est celui là que je vais utiliser maintenant).
En effet, les FSMs sont bêtes et méchantes, bien que facile a réaliser. Mais dès qu'il s'agit d'un comportement où il faut que l'IA ai l'air de réfléchir, les FSMs sont inadaptées. Ainsi les GOAPs sont utilisés principalement dans les FPS,
et aussi dans le mondialement connu Starcraft.
Cette IA a pour but d'offrir plus de challenge au joueur.
Mais rien ne vous empêche de faire une IA bien plus intelligente dans les autres types de jeu comme les RPG, ou les rogues like.

Le principe des GOAP maintenant :
Un pnj a différents but, comme manger, dormir, travailler etc...
chaque but a un niveau d'importance plus ou moins grand.

schéma :

but           : importance
dormir      : 4
manger    : 2
travailler   : 1

Ici par exemple le pnj a très envie de dormir.
Les niveaux d'importance sont mis a jour au fil du temps et les actions les plus importantes
sont exécutées en premier.

En code :

typedef struct t_state
{
    unsigned char id;
    unsigned char importance;
}t_state;

t_state but[nombre_de_but_different];

/* on initialise le tout
int i;
for( i = 0 ; i < nombre_de_but_different ; i++ )
{
    but[i].id = i;
    but[i].importance = 0;
}

L'id sert a savoir le but ( par exemple dormir c'est 0, manger c'est 1 et travailler c'est 3) parce qu’à chaque fois que l'importance d'un but change, il faut retrier le tableau.
Regardez du coté des algorithme de tri, et n'oubliez pas que le tableau est presque trier, seul un élément est a sa mauvaise place.

Une fonction de tri en exemple (oui c'est utile de faire cela)

void tri(t_state but[], int nb_but)
{
	/* Il s'agit ici d'un tri à bulle qui marche, mais qui est le plus lent possible
	c'est pour vous forcer à regarder du côté des algo de tri*/
	int changement = 1;
	int i;
	t_state transition;

	while(changement)
	{
	        changement = 0;
		for(i = 0 ; i < nb_but - 1 ; i++)
		{
			if(but[i].importance < but[i+1].importance)
			{
				transition.importance = but[i].importance;
				transition.id = but[i].id;
				
				but[i].importance = but[i+1].importance;
				but[i].id = but[i+1].id;
				
				but[i+1].importance = transition.importance;
				but[i+1].id = transition.id;
				
				changement = 1;
			}
		}
	}
}

On regarde donc le premier élément du tableau, qui est le plus important, et on exécute l'action associé.

Et la vous allez me dire : "mais alors c'est la même chose que les FSMs non ?"
Et bah non : les état ne sont plus reliés entre eux, donc l’insertion d'un nouveau but ne nécessite pas de tout revoir, mais en contre partie, cela nécessite plus de temps de processeur pour faire cela.
Et aussi, une grande nouveauté : pourquoi ce contenter d'UNE action par but ?
Si vous avez faim, vous pouvez vous faire vous même à manger, aller chez quelqu'un, ou encore aller dans un fast-food. il y a donc plusieurs solutions possibles.

Pour chaque action, il suffit de déterminer son poids :
Celui-ci peut varier en fonction de plusieurs facteurs, comme le temps mis à faire l'action,
le prix que cela va nous coûter etc...
Et il faut aussi déterminer l'importance que vont perdre les but. Par exemple :
fastfood : manger - 2
maison   : manger - 4

On peut aussi choisir une des deux actions en fonction du poids en utilisant le principe des algorithmes de Dijkstra (parcours de graphe), qui est le même principe que le pathfinding. L'avantage, c'est de pouvoir avoir une plus grande flexibilité. Il faut alors voir les actions comme un enchaînement d'actions, et plusieurs actions peuvent menées a la même suivante.

Le poid peut être en fonction de plusieurs choses, comme le temps, et l'importance que cela va perdre.
Par exemple, si l'on a très peu de temps et on est juste à coté du fast-food, alors on va y allez, et si on a tous notre temps, et juste à coté de chez soi, autant allez à sa maison. Le poid peut aussi être influencer par l'argent dépensé etc...

exemple :

/*on calcule le poid de chaque action*/
poid[nb_action_differentes];
int i;

for ( i = 0 ; i < nb_action_differente ; i++)
{
    poid[i] = (temps * 0,5) /* plus le temps est court, mieux c'est. 50% d'importance pour le temps*/
                + (diminution_de_l_importance * 0,5);
}

je suis parfaitement conscient que le temps a un poid totalement aléatoire en fonction de l'unité
utilisé. C'est à vous de calibrer correctement le calcul du poid. il ne s'agit ici que du principe général.
Dans ce cas, plus le poid est grand, plus le temps pris est long.
Attention, la variable diminution_de_l'importance est négative (-2, -4 etc...) !

int meilleur_poid;
int meilleur_poid = poid[0];/*C'est très important d'initialiser !*/
int meilleure_action;

for ( i = 0 ; i < nb_action_differente ; i++)
{
    if(poid[i] < meilleur_poid)
    {
        meilleur_poid = poid[i];
        meilleure_action = i;
    }
}

et on fait l'action :

action[meilleure_action]();

Je considère ici, que l'on envoie rien a la fonction, mais vous pouvez facilement le faire.
Le tableau est un tableau de pointeur de fonctions (voir le tutoriel d'AlexMog à ce sujet).

Pensez à updater ce tableau régulièrement tout les X secondes ou millisecondes, car une action peut à un moment

être plus utile que celle que vous voulez faire, alors qu'avant, elle ne servait à rien.

Vous avez donc maintenant réussi a faire un pnj qui pourra avoir des buts et faire des actions
en conséquence.
N'oubliez pas pas que plus vous augmenter le nombres de buts et d'actions, plus le pnj sera réaliste,
et plus cela prendra de temps pour "réfléchir"(pas beaucoup non plus mais sur des milliers de pnjs, cela se ressent).
Par exemple, le FPS  F.E.A.R (j’insiste sur le mot FPS là !) possède 67 buts différents (pas un seul où
il le but est de tuer l’ennemi ) et 197 actions différentes.

[Azad]

Merci pour ce tutoriel assez intéressant, j'admet qu'en voyant le titre je ne sais pas de quoi aller parler le sujet.
Très bien expliqué, de manière pédagogique. Continue comme ça !

Je suis étonné qu'il n'y ait pas eu plus de réponse.

+1 rep