Difficultés avec a*[rerésolu]

Bonjour, j'essaie de mettre en place un script de pathfinding censément a*, mais je ne sais pas comment gérer
les cas où il n'y a pas de chemin. En effet, il faudrait sur cette petite carte de 96*50 cases effectuer environ 5000 boucles pour les gérer toutes, ça commence à ramer à partir de 300/500.
Est-il possible d'utiliser a* tel quel pour gérer les cas impossibles ou faut-il les prévoir avant d'exécuter le chemin?
Edit: Cherchant plus attentivement dans l'article "A* pathfinding for beginners", j'ai trouvé la réponse à cette question. Il faut enregistrer toutes les cases inaccessibles, ou la carte entière est bouclée dans ce cas.
Je vais poster mes scripts du coup, ils ont l'air de marcher, même si nécessitant un travail préalable.
Edit2: C'est normal que ça rame dès 500 "itérations de cases"? ( cad ouvrir 500 fois la case à moindre coût de distance, pour trouver le chemin). Je suis sous gm7.

Bon, je remonte le sujet, personne n'a l'air de voir les 'edit'. Ma question est donc : est-il normal qu'un chemin nécessitant une 500aine d'itérations de case ralentisse affreusement le programme (5 sec à peu près)? Serai-je obligé de diviser la recherche en plus petits chemins?

GM intègre déjà A* de base, avec les fonctions du type mp_potential_step. J'ose espérer qu'ils ont optimisé ca un minimum, donc si t'as pas besoin de trucs particuliers (genre pondérer les cases), tu devrais utiliser leur système. Ca m'étonne pas que ca rame dès 500 itérations, GM et les structures... Normalement le pathfinding on le fait dans un thread à part parce que de base ca bouffe déjà pas mal. Vu qu'avec GM bah tu peux pas, si tu veux faire ton truc perso, fais en sorte qu'il calcule un nombre maximal de chemins par step, le calcul durera plus de temps mais ca fera pas ramer ton jeu au moins...

Merci!
Pondérer les cases, c'est leur assigner un coût de déplacement différent? Par exemple, une forêt valant 2 de mouvement, une route 0.5... Si c'est ça, je ne sais trop comment faire.
Je vois pas comment diviser les calculs dans les steps, c'est un jeu en tour par tour, donc par exemple, lors de l'appui sur la touche entrée, il faut impérativement que toutes les destinations des unités adverses soient déterminées, je crois.
Enfin je n'ai peut-être pas bien compris ce système de fonctionnement.

Ah bah si c'est au tour par tour c'est beaucoup plus pratique ^^ Donc là soit tu fais tous tes calculs d'un coup mais ca risque de buguer, si l'utilisateur clique pendant que ca charge ca va faire "machin ne répond plus", ou alors comme dis tu divise en plusieurs steps : c'est à dire que quand tu calcule le poids d'un noeud t'incrémente un compteur, et quand ce compteur arrive à une certaine valeur (à déterminer avec des tests), t'arrête de calculer, comme ca il va passer au prochain step. Puis donc ensuite tu continue depuis là ou tu t'étais arrêté, jusqu'à ce que t'ai fini. L'avantage de cette méthode c'est qu'en plus tu va pouvoir afficher un truc disant que t'es en train de calculer, voir une barre de progression.

Pondérer les cases, ouais c'est ce que tu m'a décris. C'est pas compliqué à faire, quand tu détermine le poids de tes cases, typiquement en fonction de la distance, tu peux multiplier par une certaine valeur, en fonction de si c'est une route ou une forêt justement.

Mais bon franchement le pathfinding c'est pas forcément ce qu'il y a de plus simple, et je pense que le système intégré de GM devrait te suffire. Si tu veux pondérer un peu, au pire tu peux recalculer deux fois, d'abord en mettant comme obstacle toutes tes forêts par exemple, puis ensuite en autorisant le passage partout, et ensuite tu détermine c'est lequel des deux chemins le meilleur. Bon par contre je t'avoue que c'est assez dégueulasse ca dans le genre...

D'accord, je ne pense pas que je puisse utiliser cette méthode, puisque qu'il n'y a pas d'animation ou quoi que ce soit que le joueur puisse faire avant que tous les calculs soient effectués.
J'avais pas dû expliquer le fonctionnement du jeu, c'est comme dans un civilisation en gros.
Le joueur ne doit rien modifier, un tour fini a un statut fixe, et avant le tour suivant, tous les déplacements ennemis doivent avoir été faits. Par exemple il ne peut bouger une unité tant que les autres mouvements sont en cours...
Je crois que je vais plutôt mettre des cases intermédiaires pour les chemins, ce sera un peu approximatif à cause des obstacles comme les murailles, mais ça devrait pouvoir le faire... Enfin j'espère. Du coup prise de tête avec les directions.
Bon y'aura pas de messages de chargement, mais on peut toujours interdire les clics.

Je pense que t'as pas tout à fait compris, quand ton joueur clique pour terminer son tour, tu fais les calculs sur plusieurs steps pendant lesquels il peut rien faire, d'où l'idée d'afficher un truc de chargement, et t'affiche le tout quand c'est entièrement calculé. Je suppose que dans civilization aussi t'as un petit temps de chargement entre deux tours.

Effectivement j'y étais pas. Donc il faut interrompre le calcul, genre avec un break, enregistrer les listes, et reprendre au step suivant? Euh ça doit pas être ça encore, ce serait difficile de reprendre une recherche de chemin en cours.
Peut-être, comme il y a plusieurs recherches de chemin pendant le temps de chargement des ordinateurs, en faire un nombre variable et reprendre la boucle des unités en faisant un truc dans le genre for(i=lavar;i<...;i+=1)?
Ce serait plus simple, mais il faut quand même utiliser des points intermédiaires parce qu'une seule recherche de chemin, si c'est d'une extrémité à l'autre de la carte, c'est 5s... en admettant 10 unites par civ pour 5 ordis, ça fait 250s, soit à peu près 4 min. Un peu gavant le tour!

Ta méthode du for est la bonne. Mais comme dit ca ca marche que si t'utilise ton système perso.
Et ouais si ca prend 5s c'est que ta carte est vraiment trop grande... Donc là ouais l'idée des points intermédiaires est bonne.

Merci pour ton aide, je vais continuer dans cette voie alors.