[IA] jeux type Rocks and diamond

**yoshï** · 06/12/2007, 01h15

Bonjour
je me suis lancé récemment dans un petit projet

...
J'essaye de définir une IA pour le minier dans un jeu de type "Rocks and diamond"

Principe du jeu: Le joueur incarne un minier qui évolue en creusant dans des sous-terrains composés de diamants et de pierres et peuplés de monstres, entre autres. Le but du jeu est de récolter un certain nombre de diamants, pour pouvoir s'engouffrer vers l'accès qui mène au prochain sous-terrain, cet accès restant bloqué tant que ce nombre n'est pas atteint. Lorsque le minier se déplace, il laisse derrière lui une case vide, si bien que diamant et pierre peuvent tomber en chaîne. Le minier meurt s'il reçoit un diamant ou une pierre sur la tête.

je me suis fixé pour objectif par ordre croissant de difficulté:

NIVEAU 1
-> Ramasser le nb diamants
-> trouver la sortie
-> gérer les blocages avec un mur

NIVEAU 2
-> Gérer les pierres (avec la gravité)

NIVEAU 3
-> Gérer les monstres

J'aimerai savoir si vous avez quelques conseils pour bien démarrer...
Je serai également intéressé par des liens sur la théorie des jeux ou tout autres sujets pouvant m'être utile.

Je suis tombé sur un algo de recherche de chemin plutot interessant sur le site: Recherche de chemin par l'algorithme A*.Mais j'ai une contrainte supplémentaire dans mon projet, la vision du minier est modifiable => je ne connais pas forcément toutes les cases du sous-terrain, par exemple si on contraint le périmétre de vision à 2, le minier ne distingue que les 24 cases qui l'entourent..Donc je ne connais pas forcément tous les chemins dès le départ.

Merci d'avance pour votre aide et vos conseils

Ps: je développe l'IA en prolog

**pseudocode** · 06/12/2007, 11h26

Envoyé par yoshï

Mais j'ai une contrainte supplémentaire dans mon projet, la vision du minier est modifiable => je ne connais pas forcément toutes les cases du sous-terrain, par exemple si on contraint le périmétre de vision à 2, le minier ne distingue que les 24 cases qui l'entourent..

??

Si tu ne sais pas ou se trouvent:
- les diamants,
- les rochers,
- les voies sans issues
- la sortie
je ne donne pas cher de la vie du minier.

**ToTo13** · 06/12/2007, 11h39

Bonjour,

Dans ce genre de jeux plutôt "simple" au niveau environnement, ton univers est souvent représenté par une grille (un espace discret). Chaque case de ta grille contient une valeur qui va représenter le contenu de ton monde : diamants, pierres, monstres, ...

Envoyé par yoshï

NIVEAU 1
-> Ramasser le nb diamants
-> trouver la sortie
-> gérer les blocages avec un mur

- Si ton joueur passe sur les diamants, il les ramasse. La case où il y avait le diamants devients vide et tu incrémentes le nombre de diamants qu'il a trouvé. Ce sera toujours comme ça pour tout.
Tu n'auras qu'à tester si le nombre de diamants en possession du joueur est égale au nombre de diamants du niveau.
- Idem pour la sortie : si position == sortie alors fini !!!
- Dans ta grille, le joueur se déplace suivant quatre directions. Alors il faut tester : si grille[position + direction] == mur alors on ne fait rien...

Envoyé par yoshï

NIVEAU 2
-> Gérer les pierres (avec la gravité)

Les pierres ne pourront tomber que lorsque je joueur passera dessous, le reste du temps il ne faut pas s'en soucier. Donc lorsque le joueur partira d'une case, il faudra faire un test pour savoir s'il y avait une pierre au dessus de la case précédemment occupée par le joueur. Si c'est le cas, elle tombe. Dans un premier temps elle tombe directement à sa position finale, puis après tu gèreras l'animation (avis purement personnel, à toi de voir comment tu veux faire).

Envoyé par yoshï

NIVEAU 3
-> Gérer les monstres

Là c'est de l' "IA", mais j'aurai plutôt tendance à dire une heuristique. Les monstres chercheront à rejoindre le plus rapidement le joueur, donc il te faut une heuristique du plus cours chemin.

Envoyé par yoshï

J'aimerai savoir si vous avez quelques conseils pour bien démarrer...
Je serai également intéressé par des liens sur la théorie des jeux ou tout autres sujets pouvant m'être utile.

Chez "developpez" il y a un forum consacré entièrement au développement des jeux vidéos, jètes y un coup d'oeil, pose des questions là bas.

Envoyé par yoshï

Ps: je développe l'IA en prolog

Euh... es tu certain que ce soit la meilleure chose à faire ?
J'ai fait du Prolog car j'ai réalisé mes études avec les concepteurs de Prolog.
C'est beau, a des avantages, mais l'utiliser pour une IA alors que je reste du jeu est dans un autres langage ...
Je pense très sérieusement que dans ce genre de jeu, tu aurais tout intérêt à utiliser le langage de développement de l'interface. Il fera aussi bien.

Bonne chanche pour ton jeu...

**millie** · 06/12/2007, 16h52

Tiens :

http://jeux.developpez.com/sources/s...UX_boulderdash

Là c'est de l' "IA", mais j'aurai plutôt tendance à dire une heuristique. Les monstres chercheront à rejoindre le plus rapidement le joueur, donc il te faut une heuristique du plus cours chemin.

Oh, l'IA dans boulder dash est ultra simple. Les ennemis ne font que suivre les murs, point barre

**ToTo13** · 06/12/2007, 17h00

Bonjour

Envoyé par millie

Oh, l'IA dans boulder dash est ultra simple. Les ennemis ne font que suivre les murs, point barre

Oui, mais l'algorithmique c'est une façon compliquée de résoudre un problème simple

**millie** · 06/12/2007, 17h07

Envoyé par ToTo13

Bonjour

Oui, mais l'algorithmique c'est une façon compliquée de résoudre un problème simple

Voilà le code C de la partie d'évolution d'un ennemi :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
/* évolution des ennemis*/
void environnementEvoluerEnnemi(Niveau* niveau, Ennemi* ennemi)
{
   int x = ennemiLireX(ennemi);
   int y = ennemiLireY(ennemi);
 
 /*cherche le type de l'ennemi*/
  if (ennemiLireType(ennemi) == ENNEMI_TYPE_ABSENT)
    return;
 
   /* on teste si l'ennemi explose à cause du slim ou d'un joueur*/
   environnementEnnemiTestExplosionSlim(niveau, ennemi);
   environnementEnnemiTestExplosionJoueur(niveau, ennemi);
 
   if (ennemiLireType(ennemi) != ENNEMI_TYPE_ABSENT)
   {
    /* gère la direction suivant la direction précedente,
        j'ai repris l'algorithme de base du jeu d'origine*/
     switch(ennemiLireDirection(ennemi))
     {
       case ENNEMI_DIRECTION_GAUCHE:
          if (niveauLireMatrice(niveau, x, y-1) == ELEMENT_VIDE)
          {
            niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
            niveauEcrireMatrice(niveau, x, y-1, ELEMENT_ENNEMI);
            ennemiEcrireY(ennemi, y-1);      
            ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_HAUT);                      
          }                                     
          else {
             if (niveauLireMatrice(niveau, x-1, y) == ELEMENT_VIDE)
             {
               niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
               niveauEcrireMatrice(niveau, x-1, y, ELEMENT_ENNEMI);
               ennemiEcrireX(ennemi, x-1);
             }  
             else
               ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_BAS);   
 
          }                              
 
 
          break;
 
 
 
       case ENNEMI_DIRECTION_HAUT:
 
         if (niveauLireMatrice(niveau, x+1, y) == ELEMENT_VIDE)
          {
            niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
            niveauEcrireMatrice(niveau, x+1, y, ELEMENT_ENNEMI);
            ennemiEcrireX(ennemi, x+1);      
            ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_DROITE);                      
          }                                     
          else {
             if (niveauLireMatrice(niveau, x, y-1) == ELEMENT_VIDE)
             {
               niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
               niveauEcrireMatrice(niveau, x, y-1, ELEMENT_ENNEMI);
               ennemiEcrireY(ennemi, y-1);
             }  
             else
               ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_GAUCHE);   
 
          }                              
 
 
          break;
 
 
       case ENNEMI_DIRECTION_DROITE:
 
 
          if (niveauLireMatrice(niveau, x, y+1) == ELEMENT_VIDE)
          {
            niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
            niveauEcrireMatrice(niveau, x, y+1, ELEMENT_ENNEMI);
            ennemiEcrireY(ennemi, y+1);      
            ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_BAS);                      
          }                                     
          else {
             if (niveauLireMatrice(niveau, x+1, y) == ELEMENT_VIDE)
             {
               niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
               niveauEcrireMatrice(niveau, x+1, y, ELEMENT_ENNEMI);
               ennemiEcrireX(ennemi, x+1);
             }  
             else
               ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_HAUT);   
 
          }                              
 
         break;
 
       case ENNEMI_DIRECTION_BAS:
          if (niveauLireMatrice(niveau, x-1, y) == ELEMENT_VIDE)
          {
            niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
            niveauEcrireMatrice(niveau, x-1, y, ELEMENT_ENNEMI);
            ennemiEcrireX(ennemi, x-1);      
            ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_GAUCHE);                      
          }                                     
          else {
             if (niveauLireMatrice(niveau, x, y+1) == ELEMENT_VIDE)
             {
               niveauEcrireMatrice(niveau, x, y, ELEMENT_VIDE);
               niveauEcrireMatrice(niveau, x, y+1, ELEMENT_ENNEMI);
               ennemiEcrireY(ennemi, y+1);
             }  
             else
               ennemiEcrireDirection(ennemi, ENNEMI_DIRECTION_DROITE);   
 
          }                   
         break;     
 
 
 
      default:
              break;
 
     }          
 
 
}  
 
 
}

C'est dans le dossier environnement des sources de boulder dash

**pseudocode** · 06/12/2007, 17h56

Envoyé par ToTo13

Oui, mais l'algorithmique c'est une façon compliquée de résoudre un problème simple

Mais où ai-je déjà lu cela... ?

**ToTo13** · 06/12/2007, 18h55

Bonsoir

Envoyé par pseudocode

Mais où ai-je déjà lu cela... ?

rho... j'aurai osé faire ça ??? mouah...

Et bien oui, cette phrase résume parfaitement bon nombre d'algorithmes

**yoshï** · 07/12/2007, 01h57

Merci pour toute vos réponses

, j'ai un petit peu avancé dans le projet mais je réalise que ce n'est pas simple....

TOTO 13--> quand je parle d'IA, je veux dire que je cherche à automatiser la progression du minier pour résoudre les sous-terrains.Je ne cherche pas a refaire le jeu...je l'ai déjà fait en C++, je veux juste faire un SOLVEUR de niveau

Pour répondre rapidement aux questions sur le choix de Prolog, c'est un langage dans lequel je débute mais qui m'interesse énormément (car très lié tout comme Lisp au domaine de l'IA).De plus il me parait très puissant pour faire de la résolution de parcours.

Mon ébauche:

REPRESENTATION
J'ai modélisé le champ de vision du minier sous la forme d'une liste de sous liste. Les sous listes représentent les lignes du champ de vision.
La 1ère sous-liste correspond à la 1ère ligne etc...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
9  0  1  1  2
9  2  10 2  3
9  3  3  3  3
 
avec 
9 = Mur ;
0 = case vide ; 
1 = case non visité (terre) ; 
2 = diamant ;
10 = minier ;
3 = pierre ;
 
j'ai une liste de la forme [[9,0,1,1,2],[9,2,10,2,3],[9,3,3,3,3]]
 
//le minier est toujours au centre du champ de vision
//Note importante: la liste est rafraichit a chaque déplacement du mineur 
(en tenant compte de son champ de vision)

Dans un 1er temps je me suis attaqué à mon 1er objectif qui était d'aller chercher les diamants (sans pierre et sans monstre!!)

J'ai créer un prédicat qui permet de déterminer dans quelle direction se trouve un diamand par rapport à la position courante du mineur.Ce prédicat tient compte de ma structure de donnée si bien que le mineur va d'abord chercher à se rapprocher de la ligne où se trouve le diamant (en montant ou en descendant) et ce n'est que lorsequ'il y a un diamant sur sa ligne qu'il va chercher à s'en rapprocher par la droite ou par la gauche...

S' il n'y a pas de diamant dans son champ de vision le minier part dans une direction par défaut (le bas).A ce stade il va évidemment se bloquer en rencontrant la limite basse (mur) du sous terrain si il n'y a pas de diamant dans les parages...

J'ai donc créer un prédicat pour gérer les blocages:
Si le minier veut aller en bas et qu'il ya un mur on part à droite
s' il veut aller à droite et qu'il y a mur on part en haut....
(pour les 4 directions)

ca marche très bien sur des sous terrains de taille raisonnable avec un certain nombre de diamants.
Un pb me vient à l'esprit en écrivant ce post:
si j'ai un grand sous terrain avec un unique diamant au milieu et que mon champ de vision et faible, je vais descendre jusqu'au mur bas puis je vais faire le tour du sous terrain indéfiniment...

Avez vous des remarques ou des critiques sur cette première ébauche?

Attention je rappelle que c'est en Prolog donc je ne pense pas pouvoir gérer ce pb comme avec du java (solution de matrice de point ou autre).Ici il faut passer par des listes. Et pour trouver un élément je dois parcourir les listes...
Je suis pas un expert en prolog donc si vous avez des conseils je suis preneur

**behess** · 22/02/2008, 10h56

Tu pars du principe que le minier ne voit que 24 cases, ok, mais le joueur réel lui voit tout le niveau non ? Tu limites ton solveur là...

Le principe de la recherche de chemin est basé sur un réseau de noeuds avec des arcs et/ou des noeuds valorisés.

Si tu recherches la vitesse (le moins de déplacements) et que ton minier récupère tous les diamants => tu cherches à trouver le chemin de longueur minimum qui passe par tous les diamants ; pour la sortie tu peux simplement imposer que ce soit le dernier noeud parcouru.

Le principe des listes est idéal pour ce genre de recherche, mais le principe est de faire de la récursivité sur la liste des noeuds à parcourir jusqu'à l'épuiser totalement.

Je n'ai plus l'algo exact, mais ça se fait très bien en C++.

Quant au prolog, je ne sais pas si ça peut s'appliquer à ce genre d'algo ?

[IA] jeux type Rocks and diamond

Intelligence artificielle

Discussions similaires

Partager

Partager