Pathfinding isométrique ouch!!

Bonjour,


Je me casse la tête depuis un moment pour un projet (j'aimerais faire un genre de diablo like et peut être rajouter une librairie pour game maker afin de faciliter la création de jeux isométriques.)
Mon soucis (vraiment saoulant), c'est que j'utilise la souris pour les déplacements.Jusque là tout va bien, j'y arrive.Le problème c'est d'arriver à faire un pathfinding potable en utilisant la souris et avec un jeu isométrique.

Le problème:
Faire un système pour que le perso contourne les objets (murs, arbres etc), sachant qu'il n'utilise que des directions isométriques et qu'il suit la souris.


Je mets les scripts que j'utilise pour le déplacement de mon perso:

obj_curseur:

@create:

Code:

X=x
Y=y

@step:

Code:

if (mouse_x<X-32) && (mouse_y<Y-16)
{x=X-32
X=x
y=Y-16
Y=y}

if (mouse_x<X-32) && (mouse_y>Y+16)
{x=X-32
X=x
y=Y+16
Y=y}

if (mouse_x>X+32) && (mouse_y>Y+16)
{x=X+32
X=x
y=Y+16
Y=y}

if (mouse_x>X+32) && (mouse_y<Y-16)
{x=X+32
X=x
y=Y-16
Y=y}

if (mouse_x<X-64)
{x=X-64
X=x}

if (mouse_x>X+64)
{x=X+64
X=x}

if (mouse_y<Y-32)
{y=Y-32
Y=y}

if (mouse_y>Y+32)
{y=Y+32
Y=y}

obj_perso:

@create:

Code:

move=0
DIRECT=0
X=x
Y=y
dir=0
master=0

@step:

Code:

depth=-y
if (x=X) && (y=Y)
{move=0}

if (move=1)
{if (x<X-2) && (y<Y-1)
{x+=2
y+=1}

if (x<X-2) && (y>Y+1)
{x+=2
y-=1}

if (x>X+2) && (y<Y-1)
{x-=2
y+=1}

if (x>X+2) && (y>Y+1)
{x-=2
y-=1}


if (x>X) && (y<=Y+1) && (y>=Y-1)
{x-=2}

if (x<X) && (y<=Y+1) && (y>=Y-1)
{x+=2}

if (x<=X+2) && (y<Y) && (x>=X-2)
{y+=1}

if (x<=X+2) && (y>Y) && (x>=X-2)
{y-=1}}

@global_left_button:

Code:

move=1
X=obj_curseur.x
Y=obj_curseur.y

Voila pour mes scripts.
J'ai essayé plusieurs techniques, certaines fonctionnant un peu mais pas assez bien je trouve.
J'vous donne les pistes que j'ai exploré:

-Lorsque le perso touche un mur, calculer la distance sur sa droite et sur sa gauche (suivant la vue iso) la plus courte pour contourner le mur.Problème de bugs et du fait que ça fait beaucoup réfléchir mon pc.

-Contourner en partant sur le côté ou se trouve le curseur par rapport au perso:



La aussi j'ai quelques soucis, ça ne marche pas comme je voudrais.
Un des bugs qui revient souvent, c'est lorsque l'obstacle, le perso, et la destination sont alignés:



Bref, si vous avez une idée, un moyen pour y arriver, j'serais ravi et éternellement reconnaissant.

Merci.


Edit:
Je mets une video de dailymotion ou l'on a un exemple de ce que je cherche à faire.C'est vraiment dur et l'exemple m'a impressionné lol:
Lien

Edit2:
J'ai retrouvé le moteur que la personne utilise dans la video.Seul soucis, j'comprends pas comment ça fonctionne et j'arrive pas à la faire marcher pour mes maps en iso (64/32). :honte:

Lien vers le moteur

J'ai réussi à le faire par mes propres moyens (sans utiliser l'engine que j'ai trouvé au dessus), mais je ne suis quand même pas satisfait, ça fait approximatif et pas tres propre car j'ai un peu triché avec les angles.
Je mets un exemple de ce que j'ai fait, vous pourrez me dire ce que vous en pensez. ^^

Isometric

Ca marche pas vraiment je vais essayer de faire un pathfinding

Utilise l'algorithme A*, c'est assez simple à intégrer.

Blizter a écrit:

Utilise l'algorithme A*, c'est assez simple à intégrer.

Euh j'en avais jamais entendu parler avant cet aprem et ça ne me parle pas vraiment.J'ai essayé de chercher sur google et wikipedia mais ça reste obscur.Cela dit, j'ai réalisé qu'étant donné le nom du truc que j'ai mis en lien dans mon edit: AStar.La personne a du l'utiliser. ^^

Mystigris a écrit:

Blizter a écrit:

Utilise l'algorithme A*, c'est assez simple à intégrer.

Euh j'en avais jamais entendu parler avant cet aprem et ça ne me parle pas vraiment.J'ai essayé de chercher sur google et wikipedia mais ça reste obscur.Cela dit, j'ai réalisé qu'étant donné le nom du truc que j'ai mis en lien dans mon edit: AStar.La personne a du l'utiliser. ^^

Beaucoup de monde l'utilise! Et il en existe pleins de variantes.

Il est même intègré à Game maker^^ Cherche un peu plus sur les fonction commencant par "mp_" dans l'aide

Ah j'savais pas que c'était intégré à game maker.
Le truc c'est que ce sont des fonctions que je ne maîtrise pas trop.
Tout ce que j'suis capable de faire c'est:

mp_potential_step(X,Y,2,true)

Avec X=x du curseur et Y=y du curseur.
D'ailleurs c'est ce que j'ai utilisé dans mon exemple, en le mettant uniquement lorsqu'il y a collision, sinon j'sais pas le faire suivre des "chemins" isométriques.
En théorie il faudrait que j'fasse une grille iso avec des nodes etc je crois mais ça me dépasse totalement.

A mon avis en codant nous même un Astar prévu pour la situation isométrique, cela devrait marcher, si j'ai le temps je te fais un exemple ce Weekend.

Bah pour le pathfinding A*.
Il y a ce tuto qui explique la théorie: http://blog.lalex.com/post/2003/09/15/Traduction-%253A-article-sur-le-pathfinding-A
Je l'ai juste survolé, mais il a l'air pas mal ^^

Je l'avais trouvé le tuto moi aussi héhé.
Pour l'algorithme, j'ai essayé avec celui intégré mais de ce que j'ai pu voir il ne gère pas les grilles isométriques.
J'ai réussi à faire une grille verte avec les zones non traversables en rouge etc, mais tout apparait en mode classique et pas iso.C'est dommage d'ailleurs, ce serait vraiment pratique qu'on puisse choisir pour une prochaine version de GM. ^^

Citation :

A mon avis en codant nous même un Astar prévu pour la situation isométrique, cela devrait marcher, si j'ai le temps je te fais un exemple ce Weekend.

J'essairai aussi de le faire, si jamais un miracle arrivait mdr.Cela dit j'dois faire gaffe car j'dois réviser mon bts et comme j'le fais par correspondance, j'suis tenté d'aller voir GM pendant mes pauses et du coup elles durent beaucoup trop.Déjà que je rame avec toutes ces réactions chimiques à réapprendre (hydrogénation, oxydation, les glycérides, acides carboxyliques et j'dois rendre un devoir).

Et bien fait ton BTS moi je me charge de ça, le BTS est plus important.

daminetreg a écrit:

Et bien fait ton BTS moi je me charge de ça, le BTS est plus important.

C'est sympa, cela dit tu dois être pas mal occupé alors ça presse pas.
J'suis un peu dévarié ces temps ci, ça fait des années que j'ai arrêté les études alors reprendre en ayant à gérer soi même son temps c'est pas évident au début.
Heureusement j'ai découvert avec ce bts qu'un cours c'est pas forcément barbant, ça peut même être très intéressant mdr.
Bon j'arrête de raconter ma vie.

alpha a écrit:

Bah pour le pathfinding A*.
Il y a ce tuto qui explique la théorie: http://blog.lalex.com/post/2003/09/15/Traduction-%253A-article-sur-le-pathfinding-A
Je l'ai juste survolé, mais il a l'air pas mal ^^

:ange2: Merci pour le lien ! Maintenant je crois complètement avoir
compris le fonctionnement. (D'ailleur dans les commentaires il y a une
personne qui possait une question pas si bête, c'était s'il y avait un "cul de
sac")

De rien

Hop, je fais remonter ce post car j'ai pas trouvé la solution. :honte:
Je sais ce que je devrais faire pour y arriver, j'ai compris le principe de l'algorithme, mais je suis incapable de le traduire en GML malheureusement.
Si quelqu'un sait comment le faire et se sent d'essayer, il aura mon éternelle reconnaissance. :coeur2:

Bonne chance. Le seul moyen pour ne pas tout ecrire le A* c'est d'envisager (peut etre) tout ton niveau dans une fenetre a l'exterieur qui calcule tous les mouvements. (une sorte de mini map en fait) Après tu n'a plus qu'a projeter ton jeu en isométrie. Ca c'est pour la méthode principal, après je ne sais pas si il y a des complications mais tu as:

tous les points (x,y) de référence de trajet dans ton niveau vu en 2d

tu les changes (transformations)

et ca devient tes nouveaux (x,y).

Le seul problème ca doit être d'orienter la grille, peut être qu'en comparant lors d'un déplacement d'une case:
1) le (x,y) de départ (xstart,ystart)
2) le (x,y) d'arrivée (xgoal,ygoal)
tu peux définir un mouvement. voilà j'ai pas le temps en ce moment mais bon courage.

C'est un poil (un gros ) au dessus de mon niveau.
Finalement, j'ai opté pour un autre gameplay, toujours en isométrique mais déplacement par le clavier et tir directionnel avec la souris.
La prise en main est rapide, c'est très intuitif et avec mon système j'ai les 8 directions possible facilement et pas besoin de pathfinding, sauf pour les monstres mais ça ira.
Il me reste plus qu'à inventer le jeu qui va avec .

Bonjour à tous et à toutes.

Je cherche à créer un système de path finding en isométrique. Je ne souhaiterais cependant pas restreindre mes déplacement aux 8 directions de l'isométrie, mais bien pourvoir me déplacer selon 360°.

Il ne me semble pas que l'on puisse utiliser le A star avec plus de 8 directions, et lorsque je met en oeuvre des commandes de type

mp_potential_settings(maxrot,rotstep,ahead,onspot)
mp_potential_step(x,y,stepsize,checkall)

cela me donne un comportement "moche" et aproximatif (sprite qui oscille de droite à gauche quand l'objet longe l'obstacle et ce même en jouant sur le la forme du masque et les paramàtres de setting.

perso je sèche, d'autant que les commandes mp_potential_step etc... ne permettent pas de donner un comportement différents aux objets (vitesse, angle de rotation selon s'il s'agit d'un camion, d'une voiture ou d'un tank.

Quelqu'un a t'il une solution ?

l'IA reste et restera à jamais le plus dur...

En fait j'ai peut être une idée. mettre en place un algorythme A star et au lieu de raisonner en straight path, faire pareil avec un smooth path, en ne prenant qu'un point sur 2 pour lisser le tout. L'objet qui se déplace suivrait alors un chemin exempt de colision, mais en grignotant un peu à chaque angle. Les changement ne seraient plus brusques ce qui serai plus jolie, que ce soit une voiture ou un tank, ou même un personnage ...

Dites moi si c'est réalisable ou pas. je n'ai pas une grande expérience de GM.

OMG!!!!!!!

J'ai quasiment réussi à écrire un algorithme qui fonctionne pour les déplacements isométriques!
Il y a quelques bugs dans certains cas que j'ai identifiés et que je vais corriger mais ça fonctionne.

Je vous explique ce que j'ai fait, quand j'aurais fini je donnerai le script.

Alors ma méthode:
On crée une grille isométrique avec pour chaque case iso une valeur en fonction des tiles de la room.
Imaginons une case "route" elle aura une valeur faible, une case "marécage", elle aura une valeur forte.Plus la valeur est forte, plus la case nécéssite des efforts au personnage, c'est plus facile de traverser une route qu'un marécage donc le perso s'il a le choix doit préférer la route.

Ensuite, on clique sur la destination:
-D'abord le script calcule la distance entre les 8 cases autour du perso et la case d'arrivée.
-Ensuite il fait un classement de ces cases en fonction des distances:
1 pour la plus courte
...
8 pour la plus longue
-Ensuite il additionne à ces valeurs, celle des cases en lien avec les tiles.
-Enfin il choisit la case ayant la plus petite valeur et avance vers elle.

Voila.


Edit:
Héhéhéhéhéhéh j'ai quasiment terminé et j'ai réussi à implanter mon algorithme pour les monstres également, ça marche super.

t'as presque fait du A* ^^

une star d'algorithme

Mystigris a écrit:

OMG!!!!!!!

J'ai quasiment réussi à écrire un algorithme qui fonctionne pour les déplacements isométriques!
Il y a quelques bugs dans certains cas que j'ai identifiés et que je vais corriger mais ça fonctionne.

Je vous explique ce que j'ai fait, quand j'aurais fini je donnerai le script.

Alors ma méthode:
On crée une grille isométrique avec pour chaque case iso une valeur en fonction des tiles de la room.
Imaginons une case "route" elle aura une valeur faible, une case "marécage", elle aura une valeur forte.Plus la valeur est forte, plus la case nécéssite des efforts au personnage, c'est plus facile de traverser une route qu'un marécage donc le perso s'il a le choix doit préférer la route.

Ensuite, on clique sur la destination:
-D'abord le script calcule la distance entre les 8 cases autour du perso et la case d'arrivée.
-Ensuite il fait un classement de ces cases en fonction des distances:
1 pour la plus courte
...
8 pour la plus longue
-Ensuite il additionne à ces valeurs, celle des cases en lien avec les tiles.
-Enfin il choisit la case ayant la plus petite valeur et avance vers elle.

Voila.


Edit:
Héhéhéhéhéhéh j'ai quasiment terminé et j'ai réussi à implanter mon algorithme pour les monstres également, ça marche super.

salut

je suis très intéressé par ce sujet , car j'essaie de créer une grille isométrique mais je ne sais pas trop comment faire.
On peut trouver ton script quelque part ?
Comment crées-tu une grille isométrique ?

Merci