Bienvenue
visiteur !

◂

Réaliser un pathfinder Ce tutoriel est une application de l'algorithme de Dijkstra. Il permet de créer des événements capables de détecter le chemin le plus court entre sa position actuelle et une position donnée. Ecrit par Momeka le 28/10/2020

▸

❤ 1Gari Une méthode pour réaliser un Pathfinder sur RPG Maker 2003 Introduction C'est quoi le Pathfinding ? Il s'agit d'un terme pour désigner la recherche artificielle du chemin le plus court entre deux points donnés, associé à la théorie des graphes. L'algorithme de Dijkstra constitue une méthode parmi d'autres pour faire du pathfinding. Cette méthode est une application des l'algorithme de Dijkstra, utilisé dans le roguelike Brogue. Son principe de conception est d'attribuer un numéro à chaque tile, avec l'objectif final à 0, et les autres sur un nombre plus élevé, l'objectif étant que chaque tile vérifie la valeur de son voisin. Si le tile sélectionné a une valeur de 2 ou plus que le tile adjacent le plus faible, on lui donne la valeur de 1 addtionnée à la valeur de ce tile faible. Et ainsi de suite jusqu'à ce que plus aucun changement ne soit fait. Un autre tutoriel existe utilisant le même algorithme, mais avec une utilisation différente sur RPG Maker 2003. Vous pouvez le trouver ici (en anglais). Ensuite, l'événement n'a plus qu'à se déplacer du tile le plus élevé au plus faible jusqu'à atteindre son but. Contraintes techniques Ce système nécessite deux variables par tile, une pour stocker la valeur actuelle, et l'autre pour la valeur temporaire pour les calculs, ce qui peut rapidement devenir complexe pour de grandes maps. Pour cet exemple, on utilisera une map de 10 carreaux de côté, ce qui fait déjà 200 variables. Si vous souhaitez plus d'un élément avec cette IA de pathfinding fonctionnant en même temps, vous auriez besoin d'utiliser de nouvelles variables, ce qui peut rapidement monter à un montant excessif de variables. Ce système ne fonctionnerait donc pas pour un jeu d'action en temps réel avec 10 zombies sur la même map, mais serait plus adapté pour un jeu tactique de type Fire Emblem, où une seule unité se déplace à la fois. Enfin, les tags de terrain sont utilisés pour déterminer si un tile est passable ou non. Si un tile de la couche inférieure est impassable sur un sol passable, le système le considérera quand même comme passable, résultant en un freeze du jeu au moment d'effectuer le déplacement. Mise en place Tout d'abord, il faut assigner un ID de terrain sur notre tileset dans la base de données > Terrain. Créez un nouvel ID et appelez-le "Impassable". Le reste n'est pas utile. Dans Tileset, sélectionnez le tileset que souhaitez utiliser. Choisissez la couche inférieure et appliquez votre terrain Impassable sur tous les tiles impraticables. Voici les variables et interrupteurs qui seront utilisés ici : Spoiler (cliquez pour afficher) Interrupteurs : 0001: initializedGame 0002: startRandomlyWalking Variables : 0002: temp 0 0003: temp 1 0004: temp 2 0005: temp 3 0006: temp 4 0007: temp 5 0008: temp 6 0009: temp 7 0010: temp 8 0011: temp 9 0012: tempX 0012: tempY 0021: return 0025: map offset X 0026: map offset X 0027: impassable cost 0028: impassable ID 0032: goal X 0033: goal Y 0034: entity X 0035: entity X 0501: tile 0 0 0502: tile 0 1 0503: tile 0 2 0504: tile 0 3 0505: tile 0 4 0506: tile 0 5 0507: tile 0 6 0508: tile 0 7 0509: tile 0 8 0510: tile 0 9 0511: tile 1 0 0512: tile 1 1 0513: tile 1 2 0514: tile 1 3 0515: tile 1 4 0516: tile 1 5 0517: tile 1 6 0518: tile 1 7 0519: tile 1 8 0520: tile 1 9 0521: tile 2 0 0522: tile 2 1 0523: tile 2 2 0524: tile 2 3 0525: tile 2 4 0526: tile 2 5 0527: tile 2 6 0528: tile 2 7 0529: tile 2 8 0530: tile 2 9 0531: tile 3 0 0532: tile 3 1 0533: tile 3 2 0534: tile 3 3 0535: tile 3 4 0536: tile 3 5 0537: tile 3 6 0538: tile 3 7 0539: tile 3 8 0540: tile 3 9 0541: tile 4 0 0542: tile 4 1 0543: tile 4 2 0544: tile 4 3 0545: tile 4 4 0546: tile 4 5 0547: tile 4 6 0548: tile 4 7 0549: tile 4 8 0550: tile 4 9 0551: tile 5 0 0552: tile 5 1 0553: tile 5 2 0554: tile 5 3 0555: tile 5 4 0556: tile 5 5 0557: tile 5 6 0558: tile 5 7 0559: tile 5 8 0560: tile 5 9 0561: tile 6 0 0562: tile 6 1 0563: tile 6 2 0564: tile 6 3 0565: tile 6 4 0566: tile 6 5 0567: tile 6 6 0568: tile 6 7 0569: tile 6 8 0570: tile 6 9 0571: tile 7 0 0572: tile 7 1 0573: tile 7 2 0574: tile 7 3 0575: tile 7 4 0576: tile 7 5 0577: tile 7 6 0578: tile 7 7 0579: tile 7 8 0580: tile 7 9 0581: tile 8 0 0582: tile 8 1 0583: tile 8 2 0584: tile 8 3 0585: tile 8 4 0586: tile 8 5 0587: tile 8 6 0588: tile 8 7 0589: tile 8 8 0590: tile 8 9 0591: tile 9 0 0592: tile 9 1 0593: tile 9 2 0594: tile 9 3 0595: tile 9 4 0596: tile 9 5 0597: tile 9 6 0598: tile 9 7 0599: tile 9 8 0600: tile 9 9 0601: temp 0 0 0602: temp 0 1 0603: temp 0 2 0604: temp 0 3 0605: temp 0 4 0606: temp 0 5 0607: temp 0 6 0608: temp 0 7 0609: temp 0 8 0610: temp 0 9 0611: temp 1 0 0612: temp 1 1 0613: temp 1 2 0614: temp 1 3 0615: temp 1 4 0616: temp 1 5 0617: temp 1 6 0618: temp 1 7 0619: temp 1 8 0620: temp 1 9 0621: temp 2 0 0622: temp 2 1 0623: temp 2 2 0624: temp 2 3 0625: temp 2 4 0626: temp 2 5 0627: temp 2 6 0628: temp 2 7 0629: temp 2 8 0630: temp 2 9 0631: temp 3 0 0632: temp 3 1 0633: temp 3 2 0634: temp 3 3 0635: temp 3 4 0636: temp 3 5 0637: temp 3 6 0638: temp 3 7 0639: temp 3 8 0640: temp 3 9 0641: temp 4 0 0642: temp 4 1 0643: temp 4 2 0644: temp 4 3 0645: temp 4 4 0646: temp 4 5 0647: temp 4 6 0648: temp 4 7 0649: temp 4 8 0650: temp 4 9 0651: temp 5 0 0652: temp 5 1 0653: temp 5 2 0654: temp 5 3 0655: temp 5 4 0656: temp 5 5 0657: temp 5 6 0658: temp 5 7 0659: temp 5 8 0660: temp 5 9 0661: temp 6 0 0662: temp 6 1 0663: temp 6 2 0664: temp 6 3 0665: temp 6 4 0666: temp 6 5 0667: temp 6 6 0668: temp 6 7 0669: temp 6 8 0670: temp 6 9 0671: temp 7 0 0672: temp 7 1 0673: temp 7 2 0674: temp 7 3 0675: temp 7 4 0676: temp 7 5 0677: temp 7 6 0678: temp 7 7 0679: temp 7 8 0680: temp 7 9 0681: temp 8 0 0682: temp 8 1 0683: temp 8 2 0684: temp 8 3 0685: temp 8 4 0686: temp 8 5 0687: temp 8 6 0688: temp 8 7 0689: temp 8 8 0690: temp 8 9 0691: temp 9 0 0692: temp 9 1 0693: temp 9 2 0694: temp 9 3 0695: temp 9 4 0696: temp 9 5 0697: temp 9 6 0698: temp 9 7 0699: temp 9 8 0700: temp 9 9 A propos des variables : - Toutes les variables "temp" ne servent qu'à stocker temporairement le résultat des calculs et ne sont jamais utilisés en dehors de l'événement. - Goal X et Goal Y sont les coordonnées de l'objectif. - entity X et entity Y sont les coordonnées actuelles de notre objet (celui qui fait le trajet) Rappel : Notre map fait 10*10 carreaux, avec deux variables par carreau. Si vous utilisez une map aux dimensions différentes, vous devrez adapter vos variables. Les autres variables sont expliquées au cours de la démonstration. Le code de l'algorithme de Dijkstra Pour ce système, on utilisera trois événements communs : Set Up (initialisation), l'implémantation de l'algorithme (avec la valeur des différents tiles) et la comparaison entre les tiles adjacents (pour vérifier lequel à la plus petite valeur). 1/ Initialisation des variables Il s'agit du code pour initialiser les variables. Dans ce premier événement, insérez : Portion de code : Tout sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 @> Comment: :             : === :             : Initializes the variables used for building the Dijkstra Map :             : === @> Control Variables: [0027:impassable cost] = 9999999 @> Comment: Should be the same as the terrain id for impassable tiles @> Control Variables: [0028:impassable ID] = 2 @> Comment: :             : The Map Offset variables is used to calculate where our map :             : starts. Should be the top left corner of the pathfinding :             : area. @> Control Variables: [0025:map offset X] = 5 @> Control Variables: [0026:map offset Y] = 2 @> Control Switches: [0001:initializedGame] = ON La variable [27:impassable cost] est la valeur de nos tiles impassables et devrait être un nombre élevé. [0028:impassable ID] désigne le numéro ID de notre terrain Impassable (2 pour cet exemple). Les variables [26 et 27:map offset] désignent les coordonnées de départ de zone de pathfinding (qui n'est pas forcément équivalent aux coordonnées 0,0 de l'éditeur). Enfin, activer[0001:initializedGame] permet à l'événement suivant de prendre place. 2/ Construction du graph Dijkstra Pour cet événement, le code sera divisé en plusieurs parties pour faciliter l'explication. Portion de code : Tout sélectionner 1 2 3 4 5 6 7 8 9 10 11 @> Comment: :             : === :             : Builds the Dijkstra map used for pathfinding :             : === @> Comment: @> Comment: Initialize the variables used for the dijkstra map if :             : not already done @> Conditional Branch: Switch [0001:initializedGame] is OFF   @> Call Event: [Initialize Game]   @> : Branch End Appelle l'événement Set Up l'interrupteur [0001:initializedGame] est désactivé. Portion de code : Tout sélectionner 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 @> Comment: Find all the impassable tiles and set them to a ridiculous :             : high number @> Comment: temp 0 is used to track the current variable index of the :             : tiles we are on in the loop @> Control Variables: [0002:temp 0] = 501 @> Comment: Set the temp Y to the map offset Y  and temp X to 0 @> Control Variables: [0012:tempX] = 0 @> Control Variables: [0013:tempY] = Variable [0026] @> Loop   @> Loop     @> Comment: Offset the X position with map offset     @> Control Variables: [0004:temp 2] = Variable [0012]     @> Control Variables: [0004:temp 2] += Variable [0025]     @> Comment: Check if tile is impassable     @> Get Terrain ID: [0003:temp 1], Variable [0004][0013]     @> Conditional Branch: Variable [0003:temp 1] == Variable [0028:impassable ID]       @> Comment: impassable tile found, set the variable of the index stored       :             : in temp 0 to impassable cost       @> Control Variables: Variable [0002] = Variable [0027]       @>     : Branch End     @> Comment: Continue loop through x     @> Control Variables: [0012:tempX] += 1     @> Control Variables: [0002:temp 0] += 1     @> Conditional Branch: Variable [0012:tempX] > 9       @> Control Variables: [0012:tempX] = 0       @> Break Loop       @>     : Branch End     @>   : Repeat Above   @> Control Variables: [0013:tempY] += 1   @> Comment: Check if we reached the end of our tiles. In this case   :             : variable index 600.   @> Conditional Branch: Variable [0002:temp 0] > 600     @> Break Loop     @>   : Branch End   @> : Repeat Above Cherche les tiles infranchissables et assigne la valeur stockée dans [0027:impassable cost]. Il faut garder à l'esprit qu'il faut ajuster la variable temp X avec la variable offset de la carte avant de vérifier l'ID du terrain. Portion de code : Tout sélectionner 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 @> Comment: Find and set the goal tile to a cost of 0 and set the :             : rest to a cost of 1000 @> Control Variables: [0002:temp 0] = 501 @> Comment: calculate the index of the goal tile and store it in temp 1 @> Control Variables: [0003:temp 1] = Variable [0033] @> Control Variables: [0003:temp 1] *= 10 @> Control Variables: [0003:temp 1] += Variable [0032] @> Control Variables: [0003:temp 1] += Variable [0002] @> Loop   @> Conditional Branch: Variable [0002:temp 0] == Variable [0003:temp 1]     @> Control Variables: Variable [0002] = 0     @>   : Else     @> Control Variables: [0004:temp 2] = Variable ID [V[0002]]     @> Conditional Branch: Variable [0004:temp 2] != Variable [0027:impassable cost]       @> Control Variables: Variable [0002] = 1000       @>     : Branch End     @>   : Branch End   @> Control Variables: [0002:temp 0] += 1   @> Conditional Branch: Variable [0002:temp 0] > 600     @> Break Loop     @>   : Branch End   @> : Repeat Above On boucle encore une fois tous nos tiles et on donne la valeur 0 au tile de destination. Les tiles qui ne sont pas impassables reçoivent quant à eux la valeur 1000. Pour calculer l'index du tile de destination, on utilise la formule (goal Y * map height + goal x) + un ajustement au début des variables de tiles. Portion de code : Tout sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @> Comment: Set up temp tiles cost :             : temp 0 is used to store the current index of the tile we are :             : on in the loop. :             : temp 1 is used to store the current index of the temp tile @> Control Variables: [0002:temp 0] = 501 @> Control Variables: [0003:temp 1] = 601 @> Loop   @> Control Variables: Variable [0003] = Variable ID [V[0002]]   @> Control Variables: [0002:temp 0] += 1   @> Control Variables: [0003:temp 1] += 1   @> Conditional Branch: Variable [0002:temp 0] > 600     @> Break Loop     @>   : Branch End   @> : Repeat Above On copie la valeur de passabilité de nos tiles sur les variables temporaires. Portion de code : Tout sélectionner 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 @> Comment: Build the Dijkstra Map @> Label: 1 @> Comment: :             : temp 0 is used to track the current tile index :             : temp 1 is used to track if any changes was made in the map @> Control Variables: [0002:temp 0] = 501 @> Control Variables: [0003:temp 1] = 0 @> Loop   @> Comment: Check if the tile is passable   @> Control Variables: [0004:temp 2] = Variable ID [V[0002]]   @> Conditional Branch: Variable [0004:temp 2] != Variable [0027:impassable cost]     @> Comment:     :             : Get the cost from all the neighbours. If we have no     :             : neighbour, set the cost to impassable     @> Comment: Get top     @> Control Variables: [0011:temp 9] = Variable [0002]     @> Control Variables: [0011:temp 9] -= 10     @> Conditional Branch: Variable [0011:temp 9] >= 501       @> Control Variables: [0004:temp 2] = Variable ID [V[0011]]       @>     : Else       @> Control Variables: [0004:temp 2] = Variable [0027]       @>     : Branch End     @> Comment: Get bottom     @> Control Variables: [0011:temp 9] = Variable [0002]     @> Control Variables: [0011:temp 9] += 10     @> Conditional Branch: Variable [0011:temp 9] <= 600       @> Control Variables: [0005:temp 3] = Variable ID [V[0011]]       @>     : Else       @> Control Variables: [0005:temp 3] = Variable [0027]       @>     : Branch End     @> Comment: Get right     @> Control Variables: [0011:temp 9] = Variable [0002]     @> Control Variables: [0011:temp 9] %= 10     @> Conditional Branch: Variable [0011:temp 9] == 0       @> Control Variables: [0006:temp 4] = Variable [0027]       @>     : Else       @> Control Variables: [0011:temp 9] = Variable [0002]       @> Control Variables: [0011:temp 9] += 1       @> Control Variables: [0006:temp 4] = Variable ID [V[0011]]       @>     : Branch End     @> Comment: Get left     @> Control Variables: [0011:temp 9] = Variable [0002]     @> Control Variables: [0011:temp 9] -= 1     @> Control Variables: [0010:temp 8] = Variable [0011]     @> Control Variables: [0010:temp 8] %= 10     @> Conditional Branch: Variable [0010:temp 8] == 0       @> Control Variables: [0007:temp 5] = Variable [0027]       @>     : Else       @> Control Variables: [0007:temp 5] = Variable ID [V[0011]]       @>     : Branch End Il s'agit de la première partie du graph. En premier lieu, on on place le Label 1 avant d'appeler la boucle, afin de pouvoir réutiliser celle-ci plus tard dans l'événement. On réinitialise la variable temp 0, qui stocke l'index du terrain sur lequel on se trouve. La variable temp 1 sert à stocker les changements apportés à un tile. Une fois fait, on commence la boucle : si le tile checké n'est pas impassable, on commence à vérifier et stocker les valeurs des tiles adjacents. Si on ne trouve pas de tile adjacent passable, on stocke la valeur de notre variable de tile impassable. La valeur des tiles est stockée comme suit : temp 2 pour le haut, temp 3 pour le bas, temp 4 pour la droite et temp 5 pour la gauche. Toutes ces données auraient besoin d'être changées si vous mappiez une map de dimension autre que 10x10 tiles. Portion de code : Tout sélectionner 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 @> Comment:     :             : Check which neighbour is cheapest. If it is cheaper by two     :             : store away the new cost in the temp tiles     @> Comment: Check if up is lowest     @> Conditional Branch: Variable [0004:temp 2] <= Variable [0005:temp 3]       @> Conditional Branch: Variable [0004:temp 2] <= Variable [0006:temp 4]         @> Conditional Branch: Variable [0004:temp 2] <= Variable [0007:temp 5]           @> Control Variables: [0008:temp 6] = Variable ID [V[0002]]           @> Control Variables: [0008:temp 6] -= Variable [0004]           @> Conditional Branch: Variable [0008:temp 6] >= 2             @> Comment: Set temp 1 to 1 to mark that we did a change             @> Control Variables: [0003:temp 1] = 1             @> Control Variables: [0008:temp 6] = Variable [0002]             @> Control Variables: [0008:temp 6] += 100             @> Control Variables: Variable [0008] = Variable [0004]             @> Control Variables: Variable [0008] += 1             @>           : Branch End           @>         : Branch End         @>       : Branch End       @>     : Branch End     @> Comment: Check if down is lowest     @> Conditional Branch: Variable [0005:temp 3] <= Variable [0004:temp 2]       @> Conditional Branch: Variable [0005:temp 3] <= Variable [0006:temp 4]         @> Conditional Branch: Variable [0005:temp 3] <= Variable [0007:temp 5]           @> Control Variables: [0008:temp 6] = Variable ID [V[0002]]           @> Control Variables: [0008:temp 6] -= Variable [0005]           @> Conditional Branch: Variable [0008:temp 6] >= 2             @> Comment: Set temp 1 to 1 to mark that we did a change             @> Control Variables: [0003:temp 1] = 1             @> Control Variables: [0008:temp 6] = Variable [0002]             @> Control Variables: [0008:temp 6] += 100             @> Control Variables: Variable [0008] = Variable [0005]             @> Control Variables: Variable [0008] += 1             @>           : Branch End           @>         : Branch End         @>       : Branch End       @>     : Branch End     @> Comment: Check if right is lowest     @> Conditional Branch: Variable [0006:temp 4] <= Variable [0004:temp 2]       @> Conditional Branch: Variable [0006:temp 4] <= Variable [0005:temp 3]         @> Conditional Branch: Variable [0006:temp 4] <= Variable [0007:temp 5]           @> Control Variables: [0008:temp 6] = Variable ID [V[0002]]           @> Control Variables: [0008:temp 6] -= Variable [0006]           @> Conditional Branch: Variable [0008:temp 6] >= 2             @> Comment: Set temp 1 to 1 to mark that we did a change             @> Control Variables: [0003:temp 1] = 1             @> Control Variables: [0008:temp 6] = Variable [0002]             @> Control Variables: [0008:temp 6] += 100             @> Control Variables: Variable [0008] = Variable [0006]             @> Control Variables: Variable [0008] += 1             @>           : Branch End           @>         : Branch End         @>       : Branch End       @>     : Branch End     @> Comment: Check if left is lowest     @> Conditional Branch: Variable [0007:temp 5] <= Variable [0004:temp 2]       @> Conditional Branch: Variable [0007:temp 5] <= Variable [0005:temp 3]         @> Conditional Branch: Variable [0007:temp 5] <= Variable [0006:temp 4]           @> Control Variables: [0008:temp 6] = Variable ID [V[0002]]           @> Control Variables: [0008:temp 6] -= Variable [0007]           @> Conditional Branch: Variable [0008:temp 6] >= 2             @> Comment: Set temp 1 to 1 to mark that we did a change             @> Control Variables: [0003:temp 1] = 1             @> Control Variables: [0008:temp 6] = Variable [0002]             @> Control Variables: [0008:temp 6] += 100             @> Control Variables: Variable [0008] = Variable [0007]             @> Control Variables: Variable [0008] += 1             @>           : Branch End           @>         : Branch End         @>       : Branch End       @>     : Branch End     @>   : Branch End Ensuite, on doit comparer la valeur de tous les tiles adjacents et trouver celui qui a la plus petite valeur. Quand c'est fait, on vérifie que sa valeur est plus faible d'au moins 2, et si c'est le cas, on donne la valeur 1 à temp 1 afin de marquer le changement aux valeurs sur l'arbre. Après cela, on calcule la nouvelle valeur, qui devrait être de +1 par rapport à la valeur voisine, et on la stocke dans la variable temp du tile concerné. Pour obtenir la bonne variable temp pour l'index du tile, on doit ajuster la variable temp 0 de 100car notre carte a 100 tiles. Si vous aviez une carte plus petite ou plus grande, il faudrait cette balance selon la largeur * hauteur de la carte. Portion de code : Tout sélectionner 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 @> Control Variables: [0002:temp 0] += 1   @> Conditional Branch: Variable [0002:temp 0] > 600     @> Comment:     :             : If we have made changes to the map then repeat the     :             : loop     @> Conditional Branch: Variable [0003:temp 1] != 0       @> Comment: Apply all the changes from temp tiles       @> Control Variables: [0002:temp 0] = 501       @> Control Variables: [0003:temp 1] = 601       @> Loop         @> Control Variables: Variable [0002] = Variable ID [V[0003]]         @> Control Variables: [0002:temp 0] += 1         @> Control Variables: [0003:temp 1] += 1         @> Conditional Branch: Variable [0002:temp 0] > 600           @> Comment: Start over again           @> Jump to Label: 1           @>         : Branch End         @>       : Repeat Above       @>     : Else       @> Comment: No changes was made, stop building map       @> Break Loop       @>     : Branch End     @>   : Branch End   @> : Repeat Above Si on a fini la boucle sur tous les tiles, on vérifie si on a un fait un changement sur l'arbre en vérifiant que temp 1 ne vaut pas 0. Si des changements ont été faits, on boucle sur toutes les variables temp des tiles et on revient sur le label 1 pour tout recommencer. Si aucun changement n'a été fait, on sort de la boucle et notre graph de Dijkstra est terminé. 3/ A la recherche du meilleur chemin Il nous faut ensuite un dernier événement commun pour retrouver le tile adjacent à notre entité de la plus faible valeur en naviguant sur la carte. Portion de code : Tout sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 @> Comment: :             : === :             : Returns the direction of the cheapest neighbour tile :             : Return  - the direction of cheapest neighbour @> Comment: :             : 1 = down :             : 2 = left :             : 3 = right @> Comment: :             : 4 - up :             : 5 - none :             : === @> Comment: Calculate current tile index from entity X and entity Y @> Control Variables: [0002:temp 0] = Variable [0035] @> Control Variables: [0002:temp 0] *= 10 @> Control Variables: [0002:temp 0] += Variable [0034] @> Control Variables: [0002:temp 0] += 501 On commence par calculer notre index de tile actuel en utilisant la même formule que pour calculer l'index de destination, mais cette fois en utilisant les variables entity X et entity Y. Portion de code : Tout sélectionner 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 @> Comment: Get the cost of each neighbour @> Comment: Get top @> Control Variables: [0003:temp 1] = Variable [0002] @> Control Variables: [0003:temp 1] -= 10 @> Conditional Branch: Variable [0003:temp 1] >= 501   @> Control Variables: [0004:temp 2] = Variable ID [V[0003]]   @> : Else   @> Control Variables: [0004:temp 2] = Variable [0027]   @> : Branch End @> Comment: Get bottom @> Control Variables: [0003:temp 1] = Variable [0002] @> Control Variables: [0003:temp 1] += 10 @> Conditional Branch: Variable [0003:temp 1] <= 600   @> Control Variables: [0005:temp 3] = Variable ID [V[0003]]   @> : Else   @> Control Variables: [0005:temp 3] = Variable [0027]   @> : Branch End @> Comment: Get right @> Control Variables: [0003:temp 1] = Variable [0002] @> Control Variables: [0003:temp 1] %= 10 @> Conditional Branch: Variable [0003:temp 1] == 0   @> Control Variables: [0006:temp 4] = Variable [0027]   @> : Else   @> Control Variables: [0003:temp 1] = Variable [0002]   @> Control Variables: [0003:temp 1] += 1   @> Control Variables: [0006:temp 4] = Variable ID [V[0003]]   @> : Branch End @> Comment: Get left @> Control Variables: [0003:temp 1] = Variable [0002] @> Control Variables: [0003:temp 1] -= 1 @> Control Variables: [0011:temp 9] = Variable [0003] @> Control Variables: [0011:temp 9] %= 10 @> Conditional Branch: Variable [0011:temp 9] == 0   @> Control Variables: [0007:temp 5] = Variable [0027]   @> : Else   @> Control Variables: [0007:temp 5] = Variable ID [V[0003]]   @> : Branch End On obtient la valeur des tiles voisins et on les stocke dans leurs variables temp. On les vérifie de la même façon que pour l'événement précédent. S'il n'y a pas de tile voisin, on obtient la valeur du tile impassable. Portion de code : Tout sélectionner 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 @> Comment: :             : Compare cost and return the cheapest direction :             : temp 9 is used to track if we found a direction @> Control Variables: [0011:temp 9] = 0 @> Comment: If we are surrounded by impassable tiles return direction :             : none (5) @> Conditional Branch: Variable [0004:temp 2] == Variable [0027:impassable cost]   @> Conditional Branch: Variable [0005:temp 3] == Variable [0027:impassable cost]     @> Conditional Branch: Variable [0006:temp 4] == Variable [0027:impassable cost]       @> Conditional Branch: Variable [0007:temp 5] == Variable [0027:impassable cost]         @> Control Variables: [0011:temp 9] = 1         @> Control Variables: [0021:return] = 5         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Branch End On compare ensuite tous ces tiles voisins entre eux pour trouver celui à la plus faible valeur, en commençant par vérifier si ces tiles sont tous infranchissables. Si c'est le cas, on donnne la valeur 5 à la variable return. La variable temp 9 est seulement utilisée pour savoir si on a trouvé le tile voisin le plus faible et l'utiliser comme priorité pour sauter tous les autres points de vérification. Portion de code : Tout sélectionner 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 @> Comment: Check if top is cheapest @> Conditional Branch: Variable [0011:temp 9] == 0   @> Conditional Branch: Variable [0004:temp 2] <= Variable [0005:temp 3]     @> Conditional Branch: Variable [0004:temp 2] <= Variable [0006:temp 4]       @> Conditional Branch: Variable [0004:temp 2] <= Variable [0007:temp 5]         @> Control Variables: [0011:temp 9] = 1         @> Control Variables: [0021:return] = 4         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Branch End @> Comment: Check if bottom is cheapest @> Conditional Branch: Variable [0011:temp 9] == 0   @> Conditional Branch: Variable [0005:temp 3] <= Variable [0004:temp 2]     @> Conditional Branch: Variable [0005:temp 3] <= Variable [0006:temp 4]       @> Conditional Branch: Variable [0005:temp 3] <= Variable [0007:temp 5]         @> Control Variables: [0011:temp 9] = 1         @> Control Variables: [0021:return] = 1         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Branch End @> Comment: Check if right is cheapest @> Conditional Branch: Variable [0011:temp 9] == 0   @> Conditional Branch: Variable [0006:temp 4] <= Variable [0004:temp 2]     @> Conditional Branch: Variable [0006:temp 4] <= Variable [0005:temp 3]       @> Conditional Branch: Variable [0006:temp 4] <= Variable [0007:temp 5]         @> Control Variables: [0011:temp 9] = 1         @> Control Variables: [0021:return] = 3         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Branch End @> Comment: Check if left is cheapest @> Conditional Branch: Variable [0011:temp 9] == 0   @> Conditional Branch: Variable [0007:temp 5] <= Variable [0004:temp 2]     @> Conditional Branch: Variable [0007:temp 5] <= Variable [0005:temp 3]       @> Conditional Branch: Variable [0007:temp 5] <= Variable [0006:temp 4]         @> Control Variables: [0011:temp 9] = 1         @> Control Variables: [0021:return] = 2         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Branch End On compare toutes les directions et définissons la variable return à la valeur de tile la plus faible. Maintenant, il nous reste à créer l'événement qui va permettre à l'entité de se déplacer. Utiliser l'algorithme pour déplacer un événement Créez une nouvelle carte et donnez-lui un nom cool. Conservez les autres paramètres par défaut. Commencez à dessiner un carré de 10*10 à partir des coordonnées (005;002). Créez des passages que l'entité puisse parcourir. Ensuite, créez un nouvel événement sur un tile passable et appelez-le "Entité", et attribuez-lui une apparence. Créez un autre événement et appelez-le "Destination", qui montrera la position où doit se déplacer l'entité. Attribuez-lui également une apparence et placez sa priorité sous le héros. Mettez-le n'importe où sur la carte. Maintenant, il faut créer un nouvel événement pour déplacer tout ça, en mode Autorun. Portion de code : Tout sélectionner 1 2 3 4 @> Call Event: [Initialize Game] @> Control Variables: [0034:entity X] = 0 @> Control Variables: [0035:entity Y] = 0 @> Control Switches: [0002:startRandomlyWalking] = ON Cette portion appelle l'événement commun pour initialiser les variables. Ensuite, on initialise les positions de notre entité. Enfin, on active l'interrupteur [02tartRandomWalking] pour passer à l'étape suivante. Sur une nouvelle page de l'événement avec l'interrupteur précédent activé, on utilise le mode processus parallèle. Portion de code : Tout sélectionner 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 @> Comment: Pick a random position @> Loop   @> Control Variables: [0032:goal X] = Random No. (0...9)   @> Control Variables: [0033:goal Y] = Random No. (0...9   @> Comment: Check if it is a valid position   @> Conditional Branch: Variable [0032:goal X] != Variable [0034:entity X]     @> Conditional Branch: Variable [0033:goal Y] != Variable [0035:entity Y]       @> Control Variables: [0012:tempX] = Variable [0032]       @> Control Variables: [0013:tempY] = Variable [0033]       @> Control Variables: [0012:tempX] += Variable [0025]       @> Control Variables: [0013:tempY] += Variable [0026]       @> Get Terrain ID: [0002:temp 0], Variable [0012][0013]       @> Conditional Branch: Variable [0002:temp 0] != Variable [0028:impassable ID]         @> Break Loop         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> : Repeat Above @> Comment: Build map to position @> Set Event Location: [Goal Marker], Variable [0012][0013] @> Call Event: [Build Dijkstra Map] On commence par choisir une position aléatoire en utilisant goal X et goal Y (les deux valeur étant entre 0 et 9). Ensuite, on vérifie qu'il s'agisse d'une position possible en vérifiant que l'entité ne se situe pas dessus et que la position est passable. Avant d'obtenir l'ID du terrain, il faut ajuster cette position aléatoire avec les variables offset. Pour se faire, on stocke nos valeurs aléatoires dans temp X et temp Y. Si la position est valide, on déplace l'événement "Goal Marker" sur les variables temp X et temp Y. Portion de code : Tout sélectionner 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 @> Comment: Follow path @> Loop   @> Call Event: [Cheapest Neighbour]   @> Conditional Branch: Variable [0021:return] == 1     @> Set Move Route: [Entity], Move Down     @> Wait for All Movement     @> Control Variables: [0035:entity Y] += 1     @>   : Else     @> Conditional Branch: Variable [0021:return] == 2       @> Set Move Route: [Entity], Move Left       @> Wait for All Movement       @> Control Variables: [0034:entity X] -= 1       @>     : Else       @> Conditional Branch: Variable [0021:return] == 3         @> Set Move Route: [Entity], Move Right         @> Wait for All Movement         @> Control Variables: [0034:entity X] += 1         @>       : Else         @> Conditional Branch: Variable [0021:return] == 4           @> Set Move Route: [Entity], Move Up           @> Wait for All Movement           @> Control Variables: [0035:entity Y] -= 1           @>         : Else           @> Text: Stuck           @> Break Loop           @>         : Branch End         @>       : Branch End       @>     : Branch End     @>   : Branch End   @> Comment: Check if we reached goal   @> Conditional Branch: Variable [0034:entity X] == Variable [0032:goal X]     @> Conditional Branch: Variable [0035:entity Y] == Variable [0033:goal Y]       @> Break Loop       @>     : Branch End     @>   : Branch End   @> : Repeat Above @> Wait: 0.0 seconds On crée une boucle qui va parcourir tous les tiles, jusqu'à obtenir celui de destination. En premier lieu, on appelle le troisième événement commun, qui vérifie la valeur des tiles voisins et stocke la direction dans la variable return. On vérifie la direction et on déplace l'entité vers cette direction avec un "attrendre la fin", et on met à jour la position de notre entité. Enfin, la dernière condition vérifie si l'entité a atteint la destination, et sort de la boucle le cas échéant. Au final, vous devriez obtenir quelque chose de similaire à ceci : Conclusion Une démo est fournie avec différents exemples d'application. Vous pouvez la trouver ici. Traduit le 5 octobre 2020. Ce tutoriel a été traduit avec l'autorisation de Momeka. Source : _ Momeka, "Pathfinding", RPG Maker.Net, 26 juin 2016 [consulté le 27 septembre 2020], lien : https://rpgmaker.net/tutorials/1322/ Articles intéressants : _ Kazesui, "Find the shortest path from one point to another", RPG Maker.Net, 9 avril 2011 [consulté le 5 octobre 2020], lien : https://rpgmaker.net/tutorials/547/

Editer

Nemau - posté le 28/10/2020 à 14:39:18 (53238 messages postés) - - ❤ 0
Narrer l'autocatégorème	Merci Gari !
Quel RPG Maker choisir ? • Ocarina of Time PC • Polaris 03

Tassle - posté le 28/10/2020 à 20:40:31 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Cimer ! J'ai pas tout lu parce que lire du code en events c'est relou mais Dijkstra c'est overkill quand le graphe est une grille comme dans RM. Un simple BFS (breadth first search) suffit. Bon en fait dans ce cas particulier BFS et Dijkstra ont le même comportement, mais un BFS est plus simple et plus rapide. Dijkstra peut devenir intéressant si des mouvements diagonaux sont autorisés, si le graphe n'est pas une grille ou si la vitesse de déplacement varie selon les tiles (par exemple un tile de boue sur lequel on se déplace lentement). Après peut-être qu'il fait effectivement un BFS en appelant ça Dijkstra (leur comportement étant similaire sur ce type de graphes)
~~

Gari - posté le 28/10/2020 à 21:05:55 (5901 messages postés) - ❤ 0

C'est bien possible. Ce système n'est pas du tout léger, et n'est de toute manière utilisable que sur des systèmes pas en mouvement (comme les déplacements pour un tactical, par exemple, où les déplacements sont différenciés selon le type de sol). Citation: Un simple BFS (breadth first search) suffit. Si tu te sens l'âme d'expliciter . Pour moi, ça m'a l'air d'être très similaire (si on se réfère à ça). Je ne sais pas pour les termes exacts, mais la source utilisée pour écrire le tuto est ici (le lien est aussi en début de tuto). L'auteur utilise le système par défaut de RM (case par case, horizontal/vertical).

Tassle - posté le 28/10/2020 à 21:11:26 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Je crois que c'est pas exactement Dijkstra ni un BFS si j'ai bien compris. (C'est comme un Dijkstra "naif" où on relaxe toutes les arêtes au lieu de relaxer que les arêtes nécessaires, pour ceux à qui ça parle). Dijkstra et BFS sont effectivement très reliés, la différence se situe dans le choix du prochain nœud à explorer. Sur un graphe où toutes les arêtes ont le même poids (la même distance) le choix en question est identique (d'ailleurs un BFS ne donne le plus court chemin que dans ce cas là). Ici la distance entre deux cases adjacentes est toujours 1 (sauf si des mouvement diagonaux sont autorisés) donc BFS et Dijkstra se comportent pareil ^^ D'ailleurs une petite erreur: Citation: Si le tile sélectionné a une valeur de 2 ou plus que le tile adjacent le plus faible, on additionne 1 à ce tile faible. On additionne pas 1 au plus petit, mais on rend le plus grand égal à "1 + la valeur du plus petit". Après j'avoue que j'ai vraiment la flemme de lire le code, l'important c'est que ça fonctionne Je ramène juste ma science au cas où euh.. quelqu'un utiliserait les tutos d'oniro pour apprendre l'algorithmie
~~

Falco - posté le 29/10/2020 à 10:41:58 (19781 messages postés) - ❤ 0
Indie game Developer	Citation: J'ai pas tout lu parce que lire du code en events c'est relou mais Dijkstra c'est overkill quand le graphe est une grille comme dans RM. Un simple BFS (breadth first search) suffit. Bon en fait dans ce cas particulier BFS et Dijkstra ont le même comportement, mais un BFS est plus simple et plus rapide. Dijkstra peut devenir intéressant si des mouvements diagonaux sont autorisés, si le graphe n'est pas une grille ou si la vitesse de déplacement varie selon les tiles (par exemple un tile de boue sur lequel on se déplace lentement). Le système de boue j'ai galéré à le mettre en place pour mon tactical, qui utilise une grille et le système de Dijkstra. Est ce que la logique serait de faire en sorte que le joueur peut se déplacer sur une case qui a la même valeur que celle sur laquelle il est déjà, si il ne trouve pas plus petit, et ainsi faire en sorte que la cases de boues aient des +1 au niveau de leur cout? Il me semble que c'est ce que j'avais fais... je crois que ça marchait, mais j'avais bien galéré. Bref ce système de pathfinding là est vraiment cool parce qu'il est facilement compréhensible, même pour des novices en maths/prog comme moi. Et on peut faire de super Fire Emblem avec
Inexistence Rebirth - Inexistence - Portfolio

Tassle - posté le 29/10/2020 à 14:38:56 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Je peux pas rentrer dans les détails sans savoir exactement comment ton truc est codé mais conceptuellement je ferais comme ça: Disons que je veux un système où quand on veut bouger vers une case d'eau, ça consomme 2 points de mouvement. Déjà, je commence par imaginer ma map comme un graphe, c'est à dire un ensemble de nœuds et d'arêtes qui les relient. Ici j'ai représenté les cases normales en vert, les cases impassables en gris et les cases d'eau en bleu. On peut ensuite donner un poids (un coût) aux arêtes. Le mieux ici selon moi c'est que les arêtes soient orientées, c'est à dire que le coût dans un sens n'est pas forcément le même que dans l'autre. Donc on donne un coût de 2 à toutes les arêtes qui arrivent vers une case d'eau et un coût de 1 à toutes celles qui arrivent vers une case d'herbe. Ensuite dans l'algorithme de Dijkstra il y a un moment où on dit qu'on "relaxe" une arête. Disons qu'on veut relaxer l'arête A qui va de la case u à la case v (notons ça A = u→v) avec un coût de x (notons ça coût(A) = x). Les cases u et v ont aussi des valeurs associées, notons les dist(u) et dist(v). Relaxer l'arête A veut dire faire l'opération suivante : Portion de code : Tout sélectionner 1 2 Si dist(v) > dist(u) + coût(A):     Alors dist(v) prend la valeur  dist(u) + coût(A). Dans ton code ça ressemble peut être à ça pour l'instant, si tes arêtes ont toutes un coût de 1: Portion de code : Tout sélectionner 1 2 Si dist(v) > dist(u) +1:     Alors dist(v) prend la valeur  dist(u) + 1. Il suffit de remplacer ça par la version d'en haut qui prend en compte les coûts des arêtes pour que le calcul des distances prenne en compte le coût plus élevés sur les tiles d'eau. Ensuite en général pour retrouver le plus court chemin à partir des distances pour chaque case ce que tu fais c'est que tu commences à la case d'arrivée t et tu progresses vers la case de départ s en allant à chaque fois vers la case adjacente u telle que dist(u) est le plus petit possible. C'est le genre de truc très facile à coder dans un vrai langage de programmation mais qui peut être galère avec un "langage de programmation graphique". En compétition de programmation par exemple Dijkstra faut pouvoir le coder en 10min max si tu veux pas te faire défoncer ^^ (si t'as pas le droit à des trucs codés à l'avance).
~~

Falco - posté le 29/10/2020 à 15:23:36 (19781 messages postés) - ❤ 0
Indie game Developer	Hum, je pense que je vois. En gros on partirait pas sur un système ou chaque case à une valeur qui correspond à son coût, mais plutôt chaque arrête. Une fois que le joueur arrive sur une case, on calcul quel arrête lui coûterait le moins de point, et il se dirigerait dans cette direction? (Désolé je suis vraiment nul en mathématique et en logique ) Merci en tout cas !
Inexistence Rebirth - Inexistence - Portfolio

Tassle - posté le 29/10/2020 à 15:54:31 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Nan chaque case garde un coût (ce que j'appelle "dist(u)" pour le coût de la case u), c'est juste qu'au moment de mettre à jour le coût de la case on prend en compte le coût de l'arête. A la fin, une fois qu'on ne fait plus de mises à jour, dist(u) représente le coût total pour aller de la case s à la case u. Pour savoir vers quelle case le joueur doit se diriger ensuite, on regarde quelle case voisine est la plus proche du départ, en prenant aussi en compte le coût de l'arête (et je rappelle qu'en général en cherche le chemin "à l'envers", en partant de l'objectif vers le départ). Donc disons que dist représente la distance d'une case à s et que je suis sur la case v. Je vais chercher parmi les voisins de v une case u telle que dist(u)+coût(u→v) est le plus petit possible. (d'ailleurs j'ai oublié le terme coût(u→v) dans mon post précédent, erreur d’inattention) Mais comme je disais c'est dur à expliquer sans savoir exactement comment ton système fonctionne (sauf à reprendre tout depuis le début). Ça reflète pas tes compétences en maths, mais ma flemme de faire une explication complète et propre là tout de suite (si quelqu'un a besoin d'aide pour modifier un code spécifique n'hésitez pas en revanche)
~~

Falco - posté le 29/10/2020 à 16:27:41 (19781 messages postés) - ❤ 0
Indie game Developer	Ok j'ai totalement compris, et c'est plutôt simple à implémenter dans mon système ! C'est top merci beaucoup Tassle! Je sais que tu utilisais MMF à une époque, ça pourrait vraiment m'aider si par moment je bloque sur un truc et si tu pouvais jeter un oeil... mais j'imagine que ça pourrait être complexe de mettre le nez dans quelque chose que tu n'as pas fait. Enfin là pour le coup je pense qu'avec ton explication tout devrait marcher efficacement. T'as vraiment une capacité et une logique qui m'impressionne coté code et maths, je suis jaloux J'ai toujours eu des lacunes à ce niveau là, sans jamais cherché à m'améliorer parce que j'ai toujours estimé que c'était une question de logique et que c'est quelque chose qui n'était pas inné chez moi. Peut-être que je devrais reprendre la base des maths pour m'améliorer dans ce domaine.
Inexistence Rebirth - Inexistence - Portfolio

Tassle - posté le 29/10/2020 à 17:45:12 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Citation: T'as vraiment une capacité et une logique qui m'impressionne coté code et maths, je suis jaloux Haha c'est gentil mais il y a pas de secret, faut juste pratiquer beaucoup ^^ C'est plus facile aussi quand c'est fait dans le cadre de tes études et que t'es obligé de t'améliorer pour continuer (surtout pour la partie maths, il y a plein de bons codeurs autodidactes). Citation: Je sais que tu utilisais MMF à une époque, ça pourrait vraiment m'aider si par moment je bloque sur un truc et si tu pouvais jeter un oeil... mais j'imagine que ça pourrait être complexe de mettre le nez dans quelque chose que tu n'as pas fait. Ouais c'est toujours plus compliqué quand on l'a pas fait soi-même (et j'ai pas touché à MMF depuis des années) mais je peux toujours tenter de jeter un œil si ça coince encore quelque part
~~

Gari - posté le 30/10/2020 à 15:01:41 (5901 messages postés) - ❤ 0

Citation: On additionne pas 1 au plus petit, mais on rend le plus grand égal à "1 + la valeur du plus petit". J'arrivais pas à comprendre pourquoi ça parlait de "cheapest above the neighbouring tile", ça a sans doute eu un impact. ^^' Est-ce qu'il ne s'agit pas de la valeur du tile actuel par contre (et pas le plus grand tile) ? J'arrive à comprendre ce que ça donne visuellement (en graph), mais en terme de programmation, c'est autre chose. Très chouette l'explication sur la façon de gérer les terrains

Tassle - posté le 30/10/2020 à 22:01:14 (5274 messages postés) ❤ 0
Disciple de Pythagolf	Citation: Est-ce qu'il ne s'agit pas de la valeur du tile actuel par contre (et pas le plus grand tile) ? Yep !
~~