[XP][PSDK] Pathfinder v0.0.2

  • 15 Réponses
  • 372 Vues
[XP][PSDK] Pathfinder v0.0.2
« le: 20 avril 2017, 20:34:01 »
Salutations !

J'ai (enfin) terminé le pathfinder ! Ce script vous permet de générer des move_route pour aller d'un point A à un point B en évitant les obstacles. Il s'agit d'un algorithme A*.

Exemple d'utilisation
- Créez un event et ajoutez une commande script avec ce code :
#/!\ Le script utilise les coordonnées réelles, sans le décalage de MapLinker. /!\
#/!\ Utilisez TrueX/TrueY() pour supprimer le décalage !                      /!\
#/!\ Vous pouvez utiliser FalseX/FalseY() pour retrouver le décalage.          /!\

e=get_character(0)
dx=TrueX(e.x)              #Coordonnée réelle x du point de départ
dy=TrueY(e.y)              #Coordonnée réelle y du point de départ
ax=17                      #Coordonnée réelle x du point d'arrivée
ay=19                      #Coordonnée réelle y du point d'arrivée
mr=FindPath(dx, dy, ax, ay) #Trouve et génère le chemin
e.force_move_route(mr)      #Fait faire le chemin à l'event

Il devrait fonctionner quelque soit la taille de la map. Il ignore cependant la zone commune de MapLinker (3 cases du bord) ne sachant pas vraiment ce que cela pourrait donner comme résultat.

N'hésitez pas à reporter les soucis et à proposer des améliorations !
« Modifié: 06 mai 2017, 03:40:48 par Alizia »
 
Utilisateurs ayant remercié ce post : Nuri Yuri, Vulvoch

[XP][PSDK] Pathfinder
« Réponse #1 le: 20 avril 2017, 21:41:47 »
Intéressant comme script :)
Je me permet de donner certains conseils sur certaines méthodes (qui peuvent être bien plus courtes).

En Ruby l'opérateur Xor c'est le signe : ^. Il marche pour les booléens (xor naturel) et nombres entiers (xor bit à bit), de ce fait la méthode Xor que tu as écrit peut se simplifier ainsi :
def Xor(a, b)
  (a ^ b) == 1
end
Le == 1 va permettre au résultat d'être un booléen.

Sinon, pour le système, j'utiliserais un module pour définir les méthodes parce que tout définir dans Object ça rend la liste des méthodes d'Object encore plus indigeste ^^ (module_function permet de définir des méthodes utilisable dans et en dehors d'un module).
ln(yo) = <3
 

[XP][PSDK] Pathfinder
« Réponse #2 le: 20 avril 2017, 23:46:27 »
En Ruby l'opérateur Xor c'est le signe : ^. Il marche pour les booléens (xor naturel) et nombres entiers (xor bit à bit), de ce fait la méthode Xor que tu as écrit peut se simplifier ainsi :
def Xor(a, b)
  (a ^ b) == 1
end
Le == 1 va permettre au résultat d'être un booléen.

C'est ce que je voulais faire à la base, mais ça ne fonctionnait pas. J'ai lu que c'était parce que toute valeur, y compris 0, était considéré comme true, ce qui est immonde pour moi venant du c++ xD Je l'ai donc refait à la bourrine^^

Sinon, pour le système, j'utiliserais un module pour définir les méthodes parce que tout définir dans Object ça rend la liste des méthodes d'Object encore plus indigeste ^^ (module_function permet de définir des méthodes utilisable dans et en dehors d'un module).

Faut que je regarde tout ça. Pour l'instant, je corrige les derniers soucis, en premier lieu, le fait que la fonction "passable?" ne semble pas tenir compte des events, ni du joueur... Du coup, l'event qui suit le path se bloque dans tous les autres events sans arrêt et pire attend connement que l'autre event se déplace avant de poursuivre sa route ><... J'aimerai éviter de les faire se traverser comme des fantômes^^
« Modifié: 20 avril 2017, 23:51:32 par Alizia »
 

[XP][PSDK] Pathfinder
« Réponse #3 le: 21 avril 2017, 00:01:12 »
En Ruby c'est vrai que les seuls éléments qui invalident une condition sont false et nil, c'est pour ça qu'avec des nombres ils faut utiliser == ou != :p

Pour l'histoire du passable, c'est parce que $game_map.passable? renseigne sur la possibilité de passer sur la MAP. Il te faut un évènement quelconque pour tester la possibilité de passer event.passable?(x, y, d). La fonction fait appel en interne à $game_map.passable? mais prend en compte les autres évènements à l'exception de lui-même.
ln(yo) = <3
 
Utilisateurs ayant remercié ce post : Alizia

[XP][PSDK] Pathfinder
« Réponse #4 le: 21 avril 2017, 00:49:50 »
Il te faut un évènement quelconque pour tester la possibilité de passer event.passable?(x, y, d). La fonction fait appel en interne à $game_map.passable? mais prend en compte les autres évènements à l'exception de lui-même.

J'essaie de patcher les move_down/up/left/right pour qu'en cas de blocage par un event/player, ils lancent FindPath() pour trouver un autre chemin et modifier le move_route pour contourner l'event bloquant et reprendre la route de l'autre coté... Mais ça marche pas, il refuse de lancer .passable?() sur un event. Une idée ?

[XP][PSDK] Pathfinder
« Réponse #5 le: 21 avril 2017, 15:04:53 »
Comment t'as fait ça avec l'évènement ?
ln(yo) = <3
 

[XP][PSDK] Pathfinder v0.0.2
« Réponse #6 le: 06 mai 2017, 03:53:26 »
Quelques nouvelles et une petite update !

Le pathfinder semble fonctionner pour ce qui est de la génération de route.

J'ai réalisé également un patch sur les move_up/down/left/right pour qu'ils génèrent des déviations (fonction : GeneDeviation() ) lorsqu'ils rencontrent un obstacle (qui se serait déplacé entre temps sur sa route) qui fonctionne... Presque.

Spoiler
a.add_mod( #Patch passable? event move_down
  "Game_Character 3",
  'if passable?(@x, @y, 2)
      #Check du talus
      if($game_map.system_tag(@x,@y+1) == 408)
        jump(0,2,false)
        return follower_move
      end
      # 下を向く
      turn_down
      # 座標を更新
      @y += 1
      follower_move
      particle_push
      @sliding = true if system_tag == 385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else',
  :replace,
  "    if (passable?(@x, @y, 2) and EventIsPassable(@x, @y, 2))
      #Check du talus
      if($game_map.system_tag(@x,@y+1) == 408)
        jump(0,2,false)
        return follower_move
      end
      # 下を向く
      turn_down
      # 座標を更新
      @y += 1
      follower_move
      particle_push
      @sliding = true if system_tag == 385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else
if(@move_route != nil and @move_type != 1) #Si l'event a une route et n'est pas en aléatoire
if(MoveCount(@move_route)>1) #Et qu'il n'est pas à une case de sa destination
@move_route = GeneDeviation(@x, @y, @move_route, @move_route_index) #On évite l'obstacle
end
end")

a.add_mod( #Patch passable? event move_left
  "Game_Character 3",
  'if passable?(@x, @y, 4)
      if($game_map.system_tag(@x-1,@y) == 400)
        jump(-2,0,false)
        return follower_move
      end
      # 左を向く
      turn_left
      # 座標を更新
      @x -= 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else',
  :replace,
  "if (passable?(@x, @y, 4) and EventIsPassable(@x, @y, 4))
      if($game_map.system_tag(@x-1,@y) == 400)
        jump(-2,0,false)
        return follower_move
      end
      # 左を向く
      turn_left
      # 座標を更新
      @x -= 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else
if(@move_route != nil and @move_type != 1) #Si l'event a une route et n'est pas en aléatoire
if(MoveCount(@move_route)>1) #Et qu'il n'est pas à une case de sa destination
@move_route = GeneDeviation(@x, @y, @move_route, @move_route_index) #On évite l'obstacle
end
end")
 
a.add_mod( #Patch passable? event move_right
  "Game_Character 3",
  'if passable?(@x, @y, 6)
      #Check du talus
      if($game_map.system_tag(@x+1,@y) == 392)
        return (jump(2,0,false) ? follower_move : nil)
      end
      # 右を向く
      turn_right
      # 座標を更新
      @x += 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else',
  :replace,
  "if (passable?(@x, @y, 6) and EventIsPassable(@x, @y, 6))
      #Check du talus
      if($game_map.system_tag(@x+1,@y) == 392)
        return (jump(2,0,false) ? follower_move : nil)
      end
      # 右を向く
      turn_right
      # 座標を更新
      @x += 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else
if(@move_route != nil and @move_type != 1) #Si l'event a une route et n'est pas en aléatoire
if(MoveCount(@move_route)>1) #Et qu'il n'est pas à une case de sa destination
@move_route = GeneDeviation(@x, @y, @move_route, @move_route_index) #On évite l'obstacle
end
end")
 
a.add_mod( #Patch passable? event move_up
  "Game_Character 3",
  'if passable?(@x, @y, 8)
      #Check du talus
      if($game_map.system_tag(@x,@y-1) == 408)
        return (jump(0,-2,false) ? follower_move : nil)
      end
      # 上を向く
      turn_up
      # 座標を更新
      @y -= 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else',
  :replace,
  "if (passable?(@x, @y, 8) and EventIsPassable(@x, @y, 8))
      #Check du talus
      if($game_map.system_tag(@x,@y-1) == 408)
        return (jump(0,-2,false) ? follower_move : nil)
      end
      # 上を向く
      turn_up
      # 座標を更新
      @y -= 1
      follower_move
      particle_push
      @sliding = true if system_tag==385
      # 歩数増加
      increase_steps
    # 通行不可能な場合
    else
if(@move_route != nil and @move_type != 1) #Si l'event a une route et n'est pas en aléatoire
if(MoveCount(@move_route)>1) #Et qu'il n'est pas à une case de sa destination
@move_route = GeneDeviation(@x, @y, @move_route, @move_route_index) #On évite l'obstacle
end
end")

Cela fonctionne plutôt bien tant qu'il n'y a pas beaucoup d'obstacle. Cependant, en cas de forte concentration d'obstacle (bougeant en random), il arrive que l'event cible reste immobile et s'arrête de suivre sa route... Je n'ai pas encore trouvé pourquoi.
Si quelqu'un a une idée, cela fait 2 semaines que je cherche...

J'ai également cherché un moyen de relancer le pathfinding tous les x secondes en cas d'impossibilité d'avancer pour vérifier s'il est toujours bloqué, mais en vain.

Je me suis également renseignée sur les modules/class, je le mettrai au propre lorsqu'il sera pleinement fonctionnel.
« Modifié: 06 mai 2017, 04:03:26 par Alizia »
 

[XP][PSDK] Pathfinder v0.0.2
« Réponse #7 le: 06 mai 2017, 13:26:38 »
Je pense à une méthode qui risque d'être chaude à mettre en place mais qui une fois mis en place devrait être assez efficace.
Générer une liste des routes possibles sur la carte de sorte à ce que l'évènement choisisse une route pré construite simple et se débrouille pour éviter les évènements qui gêneraient sur cette route.
Dans la construction des routes, il faut prendre en compte les évents qui n'ont pas de moveroute comme des obstacles du même type qu'une impossibilité de passage, et les évènement ayant un mouveroute comme rien du tout (quelque chose qui sera traité au moment de passer sur la route.
Si on prend la map de départ de PSDK ça donnerai ceci en terme de route (rectangles) :

Après le tout du travail sera d'identifier dans quel rectangle se trouve la cible, dans quel rectangle on se trouve puis de choisir l'ensemble des rectangles pour arriver à la cible. Le déplacement à l'intérieur des rectangles se fera en fonction de ce qui bloque dedans. Si c'est un évènement qui s'est placé là, et qui empêche totalement d'arriver au bout du rectangle, on peut choisir de prendre une nouvelle route ou d'attendre un peu que l'évènement se déplace.

Sur ce screen tu peux voir des zones non couverte mais passable. Il faut considérer que la zone non couverte se trouve dans le rectangle le plus proche de celle-ci (proche et permettant d'y aller). J'ai mis une règle qui dit une route fait au moins 4 tiles (2x2, 1x4).
Bon après ma solution sur des grosses map risque d'induire un délai assez énorme mais ça devrait aller :p
ln(yo) = <3
 
Utilisateurs ayant remercié ce post : Alizia

[XP][PSDK] Pathfinder v0.0.2
« Réponse #8 le: 06 mai 2017, 17:24:13 »
C'est marrant, je me suis réveillée avec une idée similaire en me disant "Non mais t'es pas bien, ça serait diablocalyptique à mettre en place..."

Si on génère les rectangles au lancement du jeu, ça peut être intéressant et même rendre l'algo bien plus rapide, en particulier sur des grosses maps labyrinthiques. Ça supprimerait même la faiblesse de celui-ci lors de chemin contre-intuitif.

M'enfin, il faudrait déjà que l'algo actuel marche en toute circonstance, c'est pas gagné xD

En revanche, je peux déjà prendre en compte les events sans move_route lors du pathfinding initial, afin d'éviter une déviation, ça raccourcira un peu le trajet.

[XP][PSDK] Pathfinder v0.0.2
« Réponse #9 le: 06 mai 2017, 17:44:36 »
Bah le système des rectangles induisent des chemins différents et là on commence à devoir faire du routage comme sur Internet mais avec des notions différente en terme d'intérêt des chemins. Le but reste de réduire le nombre de calcul à réaliser, il serait donc intéressant que ce soit le développeur qui définisse les zones dans lesquelles ont peut passer.
ln(yo) = <3
 

[XP][PSDK] Pathfinder v0.0.2
« Réponse #10 le: 06 mai 2017, 20:33:41 »
il serait donc intéressant que ce soit le développeur qui définisse les zones dans lesquelles ont peut passer.

A la main, ça serait vite interminable. Je vois mal une façon simple de faire autrement qu'un traitement automatique^^

[XP][PSDK] Pathfinder v0.0.2
« Réponse #11 le: 06 mai 2017, 20:53:02 »
Si ça se fait à la main, la manière de procéder sera totalement différente, je ferais par point et lien. En terme d'entrée ça sera assez rapide à faire
pt 1, x, y
pt 2, x, y
pt 3, x, y
pt 4, x, y
pt 5, x, y
pt 6, x, y
pt 7, x, y
pt 8, x, y
pt 9, x, y
pt 10, x, y
pt 11, x, y
pt 12, x, y
pt 13, x, y
pt 14, x, y
pt 15, x, y
pt 16, x, y
pt 17, x, y
pt 18, x, y
pt 19, x, y
lk 1, 11
lk 2, 3
lk 2, 6
lk 3, 4
lk 3, 8
lk 6, 5
lk 6, 7
lk 7, 5
lk 7, 8
lk 4, 9
lk 8, 9
lk 9, 12
lk 9, 10
lk 10, 12
lk 10, 11
lk 11, 13
lk 13, 10
lk 10, 16
lk 12, 16
lk 7, 18
lk 18, 19
lk 19, 17
lk 17, 18
lk 17, 16
lk 17, 15
lk 16, 15
lk 15, 13
lk 15, 14
Ceci pour définir les routes par défaut de la map suivante :


Après je suis d'accord qu'un full automatique serait mieux mais quand les maps sont de la complexité de celles de RSE y'a largement moyen de le faire faire par le Maker. Surtout que quand le système de pont sera ajouté à PSDK ça va se gâter un petit peu du coté automatique car ton système verra des zones passables alors qu'elle ne le sont pas car au moment où l'évent se déplacera (après calcul de la route) l'état de celui-ci sera modifié x)

Un sacré bordel mais c'est toujours intéressant ^^
ln(yo) = <3
 

*

Hors ligne Leikt

[XP][PSDK] Pathfinder v0.0.2
« Réponse #12 le: 08 juin 2017, 10:26:25 »
Salut tout le monde, ce projet de script est fort interressant :D Comment ça avance ?
"Je n'échoue jamais, soit je gagne, soit j'apprend"
- Nelson Mandela -
 

[XP][PSDK] Pathfinder v0.0.2
« Réponse #13 le: 09 juin 2017, 16:13:57 »
Aucune idée en tout cas, je compte à terme l'intégrer dans PSDK :)
ln(yo) = <3
 
Utilisateurs ayant remercié ce post : Bentoxx

*

Hors ligne Leikt

[XP][PSDK] Pathfinder v0.0.2
« Réponse #14 le: 09 juin 2017, 18:36:26 »
Ce serait une bonne chose oui ! Pour faire des PNJ plus évoluer !
"Je n'échoue jamais, soit je gagne, soit j'apprend"
- Nelson Mandela -
 
Utilisateurs ayant remercié ce post : Nuri Yuri