La Planification des Mouvements

La planification des mouvements vous aidera à déplacer certaines instances d'une position à une autre tout en évitant les collisions avec d'autres instances (par exemple des murs). La planification des mouvements est assez difficile à mettre en oeuvre. Il est impossible de donner des fonctions générales qui fonctionneront correctement dans toutes les situations. De plus, le calcul des déplacements à des positions exemptes de collisions est une opération qui consomment beaucoup de temps. Aussi, vous devrez être prudent sur la manière et le moment où vous l'appliquerez. Gardez bien ces remarques à l'esprit quand vous utiliserez les fonctions suivantes.

Différentes formes de planification de mouvements sont déjà fournies avec Game Maker. La forme la plus simple force une instance à se diriger vers une position cible particulière, en essayant d'aller en ligne droite si possible mais en prenant une direction différente si c'est nécessaire. Ces fonctions doivent être utilisées en général dans l'événement step d'une instance. Elles sont similaires à la planification de mouvements proposée par les actions :

mp_linear_step(x, y, stepsize, checkall) Cette fonction déplace d'un step l'instance directement vers la position (x,y) indiquée. La taille du step est indiquée grâce au paramètre stepsize. Si l'instance est déjà à cette position, elle ne sera pas déplacée. Si checkall est à true, l'instance s'arrêtera lorsqu'elle entrera en contact avec une instance d'un objet quelconque. Si ce paramétre est à false, l'instance s'arrêtera uniquement quand elle heurtera une instance solide. Veuillez noter que cette fonction ne tentera pas de faire des détours si l'instance rencontre un obstacle. Elle échouera simplement dans ce cas. La fonction retourne si oui ou non la position cible a été atteinte.
mp_linear_step_object(x, y, stepsize, obj) Mêmes effets que la fonction ci-dessus mais cette fois, seules les instances de obj seront considérées comme des obstacles. obj peut être un objet ou encore un ID d'une instance.
mp_potential_step(x, y, stepsize, checkall) De la même façon que les fonctions précédentes, cette fonction déplace d'un step l'instance en direction d'une position particulière. Mais dans ce cas précis, elle essayera d'éviter les obstacles. Quand l'instance se dirigera vers une instance solide (ou n'importe laquelle instance si le paramètre checkall vaut true), elle changera la direction du mouvement afin d'éviter l'instance et la contournera. Le fonctionnement n'est pas guarantie mais dans la plupart des cas, cette fonction déplacera l'instance vers la cible. La fonction retourne si la cible a été atteinte ou pas.
mp_potential_step_object(x, y, stepsize, obj) Identique à la fonction ci-dessus mais cette fois, seules les instances obj seront considérées comme des obstacles. obj peut être soit un objet soit un ID d'une instance.
mp_potential_settings(maxrot, rotstep, ahead, onspot) La fonction précédente effectue son travail en utilisant un certain nombre de paramètres pouvant être modifiés en utilisant la fonction. Globalement, cette méthode fonctionne de la manière suivante. Elle tente en premier lieu de déplacer directement l'instance vers la cible. Elle regarde un certain nombre de steps en avant, ce nombre pouvant être réglé avec le paramètre ahead (3 par défaut). Réduire cette valeur signifie que l'instance commencera à changer de direction plus tardivement. L'augmenter indiquera que l'instance débutera son changement de direction plus tôt. Si ce contrôle mène à une collision, elle commencera à regarder dans les directions les plus à gauche et les plus à droite afin de déterminer la meilleure direction. Elle effectue cela en utilisant des steps de taille rotstep (10 par défaut). En réduisant ce paramètre, cela donnera à l'instance plus de mouvements possibles mais cela ralentira le processus. Le paramètre maxrot est un peu plus difficile à expliquer. L'instance posséde une direction courante. maxrot (30 par défaut) indique combien de changements de direction l'instance est autorisée à changer sa direction actuelle dans un step. Aussi, même si elle peut se déplacer vers la cible par exemple en ligne droite, elle le fera uniquement si elle ne transgresse pas le nombre maximal de changements de direction. Si vous donnez à maxrot une valeur plus grande, l'instance pourra changer davantage de directions à chaque step. Cela rendra plus facile la recherche du chemin le plus court mais le chemin obtenu sera plus tortueux. Si vous diminuer cette valeur, le chemin sera plus coulé mais vous obtiendrez davantage de détours (et parfois, la recherche de la cible échouera). Si aucun step ne peut être effectué, le comportement dépendera de la valeur du paramètre onspot. Si la valeur de onspot est true (la valeur par défaut), l'instance effectuera une rotation sur son spot selon la valeur indiquée par maxrot. Si la valeur est false, l'instance ne bougera pas du tout. Paramètrer cette valeur à false sera utile par exemple pour des voitures mais réduira la probabilité de trouver un chemin.

Veuillez noter que l'approche potentielle utilise uniquement des information locales. Aussi, elle ne pourra trouver un chemin que si ces informations locales sont suffisantes pour déterminer la bonne direction de mouvement. Par exemple, la recherche du chemin hors d'un labyrinthe échouera la plupart du temps.

Le deuxième type de fonctions détermine pour l'instance un chemin exempt de collision. Une fois ce chemin déterminé, vous pourrez l'assigner à l'instance afin de la diriger vers la cible. Le calcul du chemin prend un certain temps mais ensuite, l'exécution du chemin sera rapide. Bien entendu, ce chemin sera valide si seulement la situation n'a pas changé entre temps. Par exemple, si des obstacles se sont déplacés, vous devrez certainement recalculer le chemin. Veuillez remarquer que ces fonctions peuvent également échouer. Ces fonctions sont uniquement disponibles dans la version enregistrée de Game Maker.

Les deux premières fonctions utilisent le déplacement linéaire et une approche de champs potentiel utilisés également dans les fonctions step.

mp_linear_path(path, xg, yg, stepsize, checkall) Cette fonction calcule un chemin en ligne droite pour l'instance de sa position courante vers la position (xg,yg) en utilisant la taille step indiquée. Elle utilise les steps comme dans la fonction mp_linear_step(). Le chemin mentionné doit déjà exister et sera écrasé par le nouveau chemin (se reporter au chapître ultérieur pour savoir comment créer et détruire les chemins). La fonction retournera si un chemin a pu être trouvé. La fonction s'arrêtera et signalera une erreur si aucun chemin direct n'existe entre le début et la cible. En cas d'échec, un chemin sera toujours créé qui s'exécutera à partir de la position où l'instance a été bloquée.
mp_linear_path_object(path, xg, yg, stepsize, obj) Identique à la fonction ci-dessus mais cette fois, seules les instances obj seront considérées comme des obstacles. obj peut être soit un objet soit un ID d'une instance.
mp_potential_path(path, xg, yg, stepsize, factor, checkall) Cette fonction calcule un chemin pour l'instance de sa position courante et en orientation vers la position (xg,yg) en utilisant la taille step indiquée, tout en tentant d'éviter les collisions avec les obstacles. Elle utilise des steps de champs potentiel, comme dans la fonction mp_potential_step() mais aussi des paramètres que l'on peut régler avec mp_potential_settings(). Le chemin indiqué doit déjà exister et sera écrasé par le nouveau chemin (se reporter au chapître ultérieur pour savoir comment créer et détruire les chemins). La fonction retournera si un chemin a pu être trouvé. Afin d'éviter que la fonction continue son calcul indéfiniement, vous devrez fournir un facteur de temps supérieur à 1. La fonction s'arrêtera et signalera une erreur si elle n'a pu déterminer un chemin plus court durant ce laps de temps entre le début et la cible. Un facteur de 4 devrait normalement être suffisant mais si vous souhaitez faire de plus longs détours, il sera peut-être souhaitable de choisir une valeur encore plus grande. En cas d'échec, un chemin sera toujours créé en direction de la cible qui cependant ne sera jamais atteinte.
mp_potential_path_object(path, xg, yg, stepsize, factor, obj) Idem que la fonction précédente sauf que seules les instances obj seront considérées comme des obstacles. obj peut être soit un objet soit un ID d'une instance.

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.

<< Traduction française par Philippe Ragni - (2005) >>