IA Simple de déplacement

[...]Les autres fonctions utilisent un mécanisme beaucoup plus complexe et sophistiqué via une approche basée sur les grilles (appelée parfois algorithme A*). Cette approche est plus efficace en terme de recherche de chemins (bien qu'elle puisse aussi échouer !) et détermine des chemins généralement plus courts mais nécessite davantage de travail de votre part. L'idée générale est la suivante. En premier lieu, nous plaçons une grille à l'endroit le plus approprié de la room. Vous pouvez choisir d'utiliser une grille avec un maillage fin (ce qui sera plus lent) ou une grille brute. Ensuite, pour tous les objets concernés, nous déterminons les cellules de la grille qui recouvrent les objets (en utilisant soit des boîtes de rebonds ou soit un contrôle précis) et marquons ces cellules comme étant interdites. Ainsi, une cellule sera marquée comme totalement interdite, même si elle recouvre partiellement un obstacle. Enfin, nous indiquerons une position de départ et une position cible (qui ne pourra être que parmi les cellules libres) puis la fonction déterminera par elle-même le chemin le plus court (le plus proche théoriquement du plus court) entre ces positions. Le chemin s'exécutera entre les centres des cellules libres. Ainsi, si les cellules sont suffisamment grandes de façon à ce que l'instance placée en son centre soit complétement à l'intérieur, le résultat sera concluant. Vous pourrez ensuite donner ce chemin à une instance pour qu'elle le suive.

L'approche basée sur les grilles est très puissante (elle est d'ailleurs utilisée dans de nombreux jeux professionels) mais demande de votre part une plus grande réflexion. Vous devrez déterminer quelle est la zone et la taille de cellule les mieux adaptées pour résoudre le problème. Vous devrez aussi déterminer quels objets doivent être évités et si une vérification précise est nécessaire pour effectuer ce travail. Tous ces paramètres auront une grande influence sur l'efficacité de cette approche.

En particulier, la taille des cellules est cruciale. Souvenez-vous que les cellules doivent être assez grandes de manière à ce que l'objet en déplacement et placé en son origine au centre d'une cellule, demeure complétement à l'intérieur de la cellule (soyez prudent en ce qui concerne la position de l'origine de l'objet. Pensez à décaler le chemin si l'origine de l'objet n'est pas bien au centre !) D'un autre côté, plus les cellules seront petites et plus il existera de chemins possibles. Si vous créez des cellules trop grandes, les ouvertures entre les obstacles pourront être fernées car toutes les cellules rentreront en intersection avec un obstacle.

Les fonctions actuelles concernant l'approche basée sur les grilles, sont les suivantes :


mp_grid_create(left,top,hcells,vcells,cellwidth,cellheight) Cette fonction crée la grille. Elle retourne un index qui devra être utilisé dans tous les autres appels. Vous pouvez créer et gérer plusieurs structures de grilles en même temps. left (gauche) et top (haut) indiquent la position du coin supérieur gauche de la grille. hcells et vcells indiquent le nombre de cellules horizontales et verticales. Enfin, cellwidth et cellheight indiquent la taille des cellules.
mp_grid_destroy(id) Détruit la structure de la grille indiquée et libére la mémoire occupée. N'oubliez-pas d'appeler cette fonction si vous n'avez plus besoin de la structure.
mp_grid_clear_all(id) Marque toutes les cellules de la grille comme libres.
mp_grid_clear_cell(id,h,v) Efface la cellule indiquée. La cellule 0,0 correspond à la cellule en haut à gauche.
mp_grid_clear_rectangle(id,left,top,right,bottom) Efface toutes les cellules qui sont en intersection avec le rectangle indiqué (dans les coordonnées de la room).
mp_grid_add_cell(id,h,v) Marque les cellules indiquées comme étant interdites. La cellule 0,0 correspond à la cellule en haut à gauche.
mp_grid_add_rectangle(id,left,top,right,bottom) Marque toutes les cellules qui sont en intersection avec le rectangle indiqué comme étant interdites.
mp_grid_add_instances(id,obj,prec) Marque toutes les cellules qui sont en intersection avec une instance d'un objet donné comme êtant interdites. Vous pouvez également utiliser une instance individuelle en donnant à obj l'ID de l'instance. Vous pouvez aussi employer le mot-clé all pour indiquer toutes les instances de tous les objets. prec indique si l'on doit utiliser une vérification précise dans les collisions (ne fonctionnera que si le paramètre contrôle précis a été coché pour le sprite utilisé par l'instance).
mp_grid_path(id,path,xstart,ystart,xgoal,ygoal,allowdiag) Détermine un chemin à l'aide de la grille. path doit mentionner un chemin existant qui sera remplacé par le chemin calculé par l'ordinateur. xstart et ystart indiquent le début du chemin et xgoal et ygoal la cible. allowdiag indique si les mouvements en diagonal sont autorisés au lieu de ne considérer que ceux horizontaux ou verticaux. La fonction retourne si elle a réussi à déterminer un chemin (veuillez noter que le chemin est indépendant de l'instance courante; c'est un chemin calculé dans la grille et non pas un chemin pour une instance particulière).
mp_grid_draw(id) Cette fonction dessine la grille avec les cellules libres de couleur verte et les cellules interdites en rouge. Cette fonction est assez lente et n'est généralement utilisée que dans les outils de déboguage.