Apprendre


Vous êtes
nouveau sur
Oniromancie?

Visite guidée
du site


Découvrir
RPG Maker

RM 95
RM 2000/2003
RM XP
RM VX/VX Ace
RM MV/MZ

Apprendre
RPG Maker

Tutoriels
Guides
Making-of

Dans le
Forum

Section Entraide

Interviews: Ephy / Tutos: Godot : Premier Contact -Partie (...) / Tutos: Godot : Premier Contact -Partie (...) / Making-of: Ma première game jam classée / Jeux: Oracle of Tao / Chat

Bienvenue
visiteur !




publicité RPG Maker!

Statistiques

Liste des
membres


Contact

Mentions légales

81 connectés actuellement

11006382 visiteurs
depuis l'ouverture

999 visiteurs
aujourd'hui



Barre de séparation

Partenaires

Indiexpo

Akademiya RPG Maker

Hellsoft

Planète Glutko

RPG Maker VX

Guelnika & E-magination

Alex d'Or

Lumen

Tous nos partenaires

Devenir
partenaire



forums

Index du forum > Entraide > [RESOLU] [RM 2003] Peaufinage de traduction pour un tutoriel de Pathfinding


Gari - posté le 28/09/2020 à 17:00:50 (4082 messages postés) - staff -

❤ 1

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=https://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.

image



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.

image





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)



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 de l'algorithme de 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 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.

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 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.

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.

image



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 [02:startRandomWalking] 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 :

image





Conclusion

Une démo est fournie avec différents exemples d'application. Vous pouvez la trouver ici.

image image







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/


timtrack - posté le 29/09/2020 à 01:31:31 (651 messages postés) -

❤ 0

Plop

Salut, c'est super cool de traduire ce tuto pour qui a besoin !

Citation:

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.



C'est ça, comme dit en commentaire dans els événements, l'offset en X et Y définit la position du coin supérieur gauche de la map. Donc ici offset se traduirait en décalage.

J'ai remarqué que tu parlais "d'arbre Dijkstra" à plusieurs reprises, tu entends par là "arbre de recherche" ? C'est assez confus d'autant que c'est pas vraiment un arbre ici (au sens théorie des graphes), c'est plus le parcours d'un graphe (ou une carte). Sinon tu peux parler d'algorithme de Dijkstra ?
C'est ptet juste moi qui bug dessus après.

Citation:

Et enfin, ce tutoriel parle d'une méthode en particulier, mais il existe peut-être d'autres méthodes pour faire du pathfinding ?



Le plus souvent, quand on parle de pathfinding, les algos de recherche qui reviennent sont soit l'algorithme de Dijkstra, soit A* ("A étoile" ou "A star").
Le premier marche très bien pour calculer toutes les routes du "graphe" en partant d'un point A mais doit parcourir tout le graphe et se recalculer complétement si l'objet change (ajout d'obstacle etc.). C'est pas idéal quand l'espace de recherche est très grand.
A* quant à lui demande un point de départ A et un point d'arrivée B et va renvoyer le chemin optimal pour aller du point A au point B mais devra se recalculer complétement si l'un des deux points change. A* est un Dijkstra "guidé" mais dans les situations extrêmes, l'algo devra lui aussi parcourir tout le graphe.

Quant à leur faisabilité en event avec les variables de RPG Maker... 'faut voir si ils occupent pas trop d'espace pour ce qu'ils font.

Projet actuel


Gari - posté le 29/09/2020 à 11:11:44 (4082 messages postés) - staff -

❤ 0

Merci !

J'avais traduit par arbre car ça me permettait justement d'éviter l'utilisation de carte qui sert déjà pour désigner les maps de RM (et que je visualisais le graph comme un arbre). J'ai trouvé l'article en français et j'ai opté pour l'algorithme, effectivement (https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra)
Ca fait partie des "maladresses" de traduction que je mentionnais.

J'ai un peu arrangé pour offset du coup, merci d'avoir confirmé !

Citation:

Quant à leur faisabilité en event avec les variables de RPG Maker... 'faut voir si ils occupent pas trop d'espace pour ce qu'ils font.

Un peu, si.
C'est pour ça que je demandais si les variables temporaires étaient indispensables vu que le tuto de Kazesui n'a pas l'air d'en utiliser autant. En tout cas dans les deux tutos, on ne les recommande que pour des systèmes de type tactical, où une seule entité bouge à la fois, et où la destination finale n'est pas amenée à bouger. Je pense qu'utiliser ce genre d'algorithme sur RM2000/2003 pour des systèmes de combats en temps réels dynamiques ne fonctionnerait pas.

L'algorithme A* a l'air d'être une simplification (moins précis, apparemment).


timtrack - posté le 29/09/2020 à 12:56:04 (651 messages postés) -

❤ 0

Plop

Citation:

L'algorithme A* a l'air d'être une simplification (moins précis, apparemment).



Non A* n'est pas vraiment une simplification mais une recherche guidée, Dijkstra (l'algo de base) permet de calculer toutes les routes optimales qui partent d'un même point de départ et A* donne la route optimale entre deux point.

Par exemple, si tu considère la carte de france (un graphe) et que tu déroule l'algo de Dijkstra une fois depuis Paris, tu pourras prendre n'importe quelle ville sur la carte et avoir la route optimale de Paris vers cette ville.
A* a pour but de faire moins de calcul de Dijkstra en ne parcourant pas tout le graphe (espace/carte) afin de trouver la meilleure route (garantie) de Paris vers une ville définie, si tu décides de changer d'objectif (soyons fou, Paris-Nantes au Paris-lieu de Lille), tu devras tout recalculer avec A*.

Citation:

Je pense qu'utiliser ce genre d'algorithme sur RM2000/2003 pour des systèmes de combats en temps réels dynamiques ne fonctionnerait pas.



Pas trop en effet, A* serait plus approprié si tu cherches de la réactivité, y a aussi des approximations de A* (calculs plus rapide mais chemin sous-optimal).
Les deux algos sont pas trop gourmands en temps mais en mémoire (donc utilisation de variables) ça monte vite, il faut au moins réserver k variables par nœud du graphe (ici les cases de ta carte).
J'ai pas lu en détail mais l'utilisation des variables temporaires me semble presque indispensable bien qu'il y ait peut-être moyen d'en réutiliser quelques-unes.

Citation:

J'avais traduit par arbre car ça me permettait justement d'éviter l'utilisation de carte qui sert déjà pour désigner les maps de RM (et que je visualisais le graph comme un arbre).



Pas faux, par contre l'algorithme désigne le "code" (la série d'instruction/de commandes) tandis que la "Dijkstra Map" ferait plus référence au résultat (ce que tu construit), j'ai un peu du mal à donner une traduction satisfaisante autre que "carte" ou graphe.

Projet actuel


Gari - posté le 29/09/2020 à 13:00:59 (4082 messages postés) - staff -

❤ 0

OK ça marche ! Je verrai au cas par cas ce qui rend le mieux (sans doute algo pour l'intro, et graph pour la construction du code)

Pour les variables temporaires, il faudrait que je regarde plus attentivement le code et le projet de Kazesui, qui utilise le même algorithme, mais différemment.

Merci en tout cas, ça devrait aider à ce que la traduction soit (d'un peu) meilleure qualité.

Index du forum > Entraide > [RESOLU] [RM 2003] Peaufinage de traduction pour un tutoriel de Pathfinding

repondre up

Suite à de nombreux abus, le post en invités a été désactivé. Veuillez vous inscrire si vous souhaitez participer à la conversation.

Haut de page

Merci de ne pas reproduire le contenu de ce site sans autorisation.
Contacter l'équipe - Mentions légales

Plan du site

Communauté: Accueil | Forum | Chat | Commentaires | News | Flash-news | Screen de la semaine | Sorties | Tests | Gaming-Live | Interviews | Galerie | OST | Blogs | Recherche
Apprendre: Visite guidée | RPG Maker 95 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker MV | Tutoriels | Guides | Making-of
Télécharger: Programmes | Scripts | Packs de ressources | Midis | Eléments séparés | Sprites
Jeux: Au hasard | Notre sélection | Sélection des membres | Tous les jeux | Jeux complets | Le cimetière | RPG Maker 95 | RPG Maker 2000 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker VX Ace | RPG Maker MV | Autres | Proposer
Ressources RPG Maker 2000/2003: Chipsets | Charsets | Panoramas | Backdrops | Facesets | Battle anims | Battle charsets | Monstres | Systems | Templates
Ressources RPG Maker XP: Tilesets | Autotiles | Characters | Battlers | Window skins | Icônes | Transitions | Fogs | Templates
Ressources RPG Maker VX: Tilesets | Charsets | Facesets | Systèmes
Ressources RPG Maker MV: Tilesets | Characters | Faces | Systèmes | Title | Battlebacks | Animations | SV/Ennemis
Archives: Palmarès | L'Annuaire | Livre d'or | Le Wiki | Divers