Domaine concerné: Traduction
Logiciel utilisé: RM 2003
Bonjour,
J'ai traduit ce tutoriel de Momeka traitant du pathfinding. Cependant, certaines notions coincent, notamment le "offset", que j'ai du mal à traduire (ajuster, contrebalancer...). Je me demande s'il ne s'agit pas ici du décalage à faire entre les dimensions réelles de la map et le carré de 10*10.
Il existe également un autre tutoriel traitant du même sujet, mais à priori sans les variables temporaires. Sont-elles indispensables, ou peut-on s'en passer ?
Et enfin, ce tutoriel parle d'une méthode en particulier, mais il existe peut-être d'autres méthodes pour faire du pathfinding ?
Voici le tutoriel en question, pour ceux qui voudraient y jeter un coup d'oeil :
Description : Ce tutoriel est une application de l'algorithme de Dijkstra. Il permet de créer des événements capables de détecter le chemin plus court entre sa position actuelle et une position donnée.
Une méthode pour réaliser un Pathfinder sur RPG Maker 2003
Introduction
Cette méthode est une application des [url=http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps]l'algorithme de Dijkstra /url], 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 additionne 1 à ce tile faible.
Et ainsi de suite jusqu'à ce que plus aucun changement ne soit fait.
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 <i>Fire Emblem</i>, 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 :
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 de l'algorithme de Dijkstra
Pour cet événement, le code sera divisé en plusieurs parties pour faciliter l'explication.
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é.
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.
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.
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.
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 de l'algorithme. 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.
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.
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 algorithme 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.
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.
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.
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.
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.
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 [02 tartRandomWalking] 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.
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.
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.
 
Ce tutoriel a été traduit avec l'autorisation de Momeka.
Source :
_ Momeka, "Pathfinding", RMN, 26 juin 2016 [consulté le 27 septembre 2020], lien : https://rpgmaker.net/tutorials/1322/
| 
Chat
