AccueilAccueil  FAQFAQ  RechercherRechercher  Dernières imagesDernières images  S'enregistrerS'enregistrer  Connexion  
Le deal à ne pas rater :
Nike : Jusqu’à 50% sur les articles de fin de saison
Voir le deal

 

 Algorithme de pathfinding sans boucle.

Aller en bas 
3 participants
AuteurMessage
keïtchi
Utilisateur confirmé: Rang **
keïtchi


Messages : 366
Localisation : Don't Follow me, I'm lost too!

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 18:03

Bonjours, je souhaiterais utiliser un algorithme de pathfinding dans mon jeu,
j'utilise actuellement le A Star, et rien à redire sur son fonctionnement,
si ce n'est que la boucle while qu'il contient fait ramé Game Maker.
à chaque calcule du chemin, ça freeze.
Aussi, je me demandais, s'il était possible de trouver une solution pour évité cette boucle,
ou un algorithme de pathfinding qui n'en contiendrais pas.

_________________
Mon Projet:
Algorithme de pathfinding sans boucle. Backgroundchargement1jc9
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 18:14

Vu que A* fait parti des algos de pathfinding les plus rapide, et que (pour une fois) il est bien implémenté sous GM, j'ai du mal a voir comment faire mieux...
Ta grille fait quelle taille?

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
keïtchi
Utilisateur confirmé: Rang **
keïtchi


Messages : 366
Localisation : Don't Follow me, I'm lost too!

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 18:50

Donc A* est le plus rapide? Outch.
Si je calcul le chemin de façon très ponctuel et sur des distance sans embuche ça vas.
Voici un exemple qui te montre l'algo que j'utilise.
Une fois lancé, flood clique gauche, le perso s'arrête 1 demi seconde entre chaque clique,
le temps qu'il recalcule le chemin.
Ca à l'aire de rien comme ça, mais là, y a rien de plus que le pathfinding qui est calculer, aucun event step rien.
A ton avis, c'est possible de trouver un moyen de rendre ce pathfinding moins gourmand?
Ou bien une alternative à celui ci?
Je continue la recherche de mon coté, car, même si je compense les points faible de ce pathfinder,
en le lançant le moins possible, il fera quand même freeze quand il sera calculé en même temps qu'un autre event quelconques.

_________________
Mon Projet:
Algorithme de pathfinding sans boucle. Backgroundchargement1jc9


Dernière édition par keïtchi le Lun 11 Nov 2013 - 21:17, édité 1 fois
Revenir en haut Aller en bas
Térence
Utilisateur confirmé: Rang *****
Térence


Messages : 2213
Localisation : Oui

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 19:21

C'est que t'as fait une connerie, c'est pas censé ramer, sauf si t'as 100 fois le même objet en même temps....
Puis faire un algo de pathfinding (compétent bien sûr)sans boucle, c'est impossible Wink

_________________
Je suis partie sur les ailes du vent et la tempête m'a ramenée.
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 20:53

J'aimerais bien jeter ton œil, mais l’hébergeur que t'utilises est une poubelle vivante.
Impossible de download le fichier sans se faire spammer de popups.
Passe plutôt sous simpleupload ou mediafire.

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
keïtchi
Utilisateur confirmé: Rang **
keïtchi


Messages : 366
Localisation : Don't Follow me, I'm lost too!

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 21:22

Voila je l'ai hébergé sur simpleupload,
et j'ai modifier le liens de mon ancien post aussi.
Merci d'y jeter un coup d'oeil, c'est sympa. happy1 
Une question, dans une boucle for, il est plus rapide de traiter des tableau ou bien des ds_list?

_________________
Mon Projet:
Algorithme de pathfinding sans boucle. Backgroundchargement1jc9


Dernière édition par keïtchi le Lun 11 Nov 2013 - 21:26, édité 1 fois
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 21:24

Tout dépend de ce que tu fais, mais les accès sont plus rapide avec un tableau.
En revanche certains algos existent pour les ds_list comme l'insertion, la suppression d'élément ou le tris.
Dans beaucoup de cas les ds_list peuvent être plus pratiques (mais en perfs c'est moins bon qu'un tableau).

Edit:
Ah mince c'est un gmx, je ne pourrais pas l'ouvrir.

Tu peux poster les code qui concernent l'engine?

Edit2:
Ah non c'est bon, les données ne sont pas cryptées on peut les lire après avoir extract.

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 21:31

Heuuu, en fait le A* c'est toi qui l'a implémenté.
T'es au courant que GM le gère nativement?

De plus ton implémentation d'A* est pas du tout adaptée a un jeu par 'tiles' (c'est bien le genre de jeu que tu fais non?).
Aussi le gml est assez lent pour tout ce qui est calcul et 'gros' algos. Pas étonnant que cela ai du mal a tourner.

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
keïtchi
Utilisateur confirmé: Rang **
keïtchi


Messages : 366
Localisation : Don't Follow me, I'm lost too!

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 21:41

Je peut convertir en gm8 apparemment, mais
sinon, voila en gm7 mais pour qu'il marche il faut faire 2 modif:
- Changer le nom de la room
- Dans l'obj_wall prendre tout ce qu'il y a dans create et le mettre dans l'alarm[0], et mettre dans create alarm[0]=4;
En faite, faut juste que les instructions sois lancé après l'ini du script sinon ça bug.

Mon jeu sur le long terme est un dota like, mais en 2D, et pour rendre les déplacement plus naturel et le follow de la souris plus performant
je voulais utiliser l'A*.

Enfin là ça devient de plus en plus un jeu à la final fantasy tactic advances avec du tour par tour...
Mais bon, je m'amuse, c'est le principal! :p

_________________
Mon Projet:
Algorithme de pathfinding sans boucle. Backgroundchargement1jc9
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 21:52

Bah t'as le move potential de GM pour avoir un A* simple et efficace.
Tu t'es fait ***** a l'implémenter pour rien j'ai envie de dire (c'est un bon exercice d'algorithmie en revanche).
De plus une implémentation sous forme de liste est lente, et dans ton cas inutile. Il aurais fallu une implémentation sous forme de tableau (tellement plus rapide, tu n'imagines même pas).

Tu crées une grille (mp_grid_create), tu ajoutes les instances a prendre en compte pour les collisions, et tu génère un path avec mp_grid_path. Ton instance n'a plus qu'a suivre le path (qu'il faut mettre a jour s'il y a beaucoup de mouvement depuis le calcul).

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
keïtchi
Utilisateur confirmé: Rang **
keïtchi


Messages : 366
Localisation : Don't Follow me, I'm lost too!

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 22:15

Pour mp_grid, une question:
Si je prend un objet parent: par_fighter, que je lui défini un grid disons _MYGRID, tous les child hériterons de ce grid,
avec les objet qui y sont attribuer comme case interdite en théorie non?
J'aurais donc, pour chaque child, un grid avec toutes les propriétés du parent,
mais que je pourrais modifier en local sans incidence sur le grid des instance similaire.
Ca mérite d'être testé. :p

Je vais regarder un peu tout ça!

_________________
Mon Projet:
Algorithme de pathfinding sans boucle. Backgroundchargement1jc9
Revenir en haut Aller en bas
onilink_
Modérateur
onilink_


Messages : 9178
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. EmptyLun 11 Nov 2013 - 23:37

Normalement oui, par contre faut pas oublier de libérer la grid dans l'instance_destroy() sinon je te dit pas la fuite de mémoire x)

_________________
Algorithme de pathfinding sans boucle. Runningpotato1Algorithme de pathfinding sans boucle. TvF6GED Algorithme de pathfinding sans boucle. MdetltS
Revenir en haut Aller en bas
Contenu sponsorisé





Algorithme de pathfinding sans boucle. Empty
MessageSujet: Re: Algorithme de pathfinding sans boucle.   Algorithme de pathfinding sans boucle. Empty

Revenir en haut Aller en bas
 
Algorithme de pathfinding sans boucle.
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Développement :: Entraide confirmés-
Sauter vers: