Astar (chemin impossible) trop long

[php_addict]

bonjour

je suis tout nouveau sur le forum je lis le forum depuis un moment déjà mais il y a une question qui ne trouve pas sa réponse, je me permets de vous la soumettre.

J'utilise un algorythme Astar pour la recherche de chemin, c'est un script php que j'ai trouvé et bidouillé pour mes besoins...

J'ai fais pas mal de tests et ca marche très bien, sauf si le chemin est "impossible", c'est à dire si il n'y a pas de solution

ma map est de 200x200 (40.000 cases) et je compte en faire une définitive de 600x600 (360.000 cases)

quand le chemin est impossible et qu'il n'y a pas de solution, le script peut mettre jusqu'à 3 minutes pour analyser mes 40.000 cases de ma map pour me dire qu'il ne trouve pas de chemin. (ceci dit cela fait tout de même 222 cases testées à la seconde...)

j'en viens à ma question

y a t il un moyen pour ne pas tester toutes les cases d'une map quand il n'y a pas de solution? inutile de se taper toutes les 40.000 cases alors qu'il n'y a pas de solution...sur une map de 100 cases on peut se permettre de tout tester mais sur une map de 40.000 ou de 360.000 cases c'est l'enfer pour le CPU :omg: je ne vous cache pas que j'ai fais planté WampServer un certain nombre de fois...

(j'utilise la distance de Manhattan pour H, et certaines cases ont un poids supplémentaire précis en fonction du terrain)

merci de m'avoir lu

bonne fin de journée

[niahoo]

hello,

le truc à faire c'est de superposer des grilles.

par dessus ta grille de 200*200 tu met une grille de 20*20, histoire que ton programme trouve un chemin tout simple de grande case en grande case. Une fois arrivé sur la case d'arrivée, tu lui fais chercher sur la grille plus fine afin de finaliser le chemin, et s'il ne trouve pas alors tu stoppe.

quand je dis 20*20 c'est un exemple, mais c'est pas forcément des carrés, ni des quadrilatères. l'idée c'est de donner à cette grille des formes : celle d'une montagne, une au dessus d'un lac, etc.. de grouper des cases de même type.


Trouvé sur le net:

Quand vous demandez à un bonhomme de se rendre à l'autre bout de la carte, il n'est pas nécessaire de calculer dès le début tout le chemin. Définissez des points clés et faites déjà la recherche de chemin vers le point clé qui correspond à sa position et à sa destination. Vous aurez ensuite le temps de préparer la suite du chemin.
Le jeu connais la carte, vous pouvez donc précalculer des parcours type ou des morceaux de parcours entre des points clés
Si vous calculez tout le chemin dès le début, votre bonhomme évitera dès le début toutes les impasses et tous les culs de sac qu'il aurait pu rencontrer. Pas très réaliste. Découpez la recherche en fonction de l'avancement du personnage.
Si le chemin proposé par l'algorithme passe dans une zone dangereuse, il n'est pas très réaliste d'y aller. Prévoyez un indicateur de danger selon l'endroit et tenez-en compte dans la recherche de chemin en alourdissant le cout pour se rendre à un noeud dangereux. Il cherchera d'abord les chemins les moins dangereux.

[php_addict]

salut

merci pour ta réponse, effectivement c'est très ingénieux

le soucis c'est que je vais avoir beaucoup de mal à implémenter ceci...

J'ai trouver une solution plus pragmatique: faire une map en sorte qu'il n'y ai pas de cases inaccessibles ;-)


merci de ton aide, je garde l'info pour plus tard

[Sloop]

Que veux-tu dire par "chemin impossible" ? Tu voudrais relier deux points qui ne sont pas reliables ? Si c'est le cas, pourquoi est-ce que cela figure sur la même carte ?

Sinon tu peux toujours mettre une condition d'arrêt au-delà d'un certain nombre d'itérations. Il y a surement d'autres solutions mais dans le vide, c'est difficile à dire.

[php_addict]

salut

Que veux-tu dire par "chemin impossible" ? Tu voudrais relier deux points qui ne sont pas reliables ? Si c'est le cas, pourquoi est-ce que cela figure sur la même carte ?

oui, c'est bien ca...dans l'idée seule certaines unités peuvent accéder à un tyoe de terrain, donc il y avait des chemins non-reliables...

Sinon tu peux toujours mettre une condition d'arrêt au-delà d'un certain nombre d'itérations.

c'est que je pensait faire...

mais j'ai opté pour ton point de vue pragmatique: ne pas faire de points non-reliables

Bonne soirée

[Melimelo]

J'ai trouver une solution plus pragmatique: faire une map en sorte qu'il n'y ai pas de cases inaccessibles ;-)

Alors c'est pas une solution ça ton algo va mettre au pire des cas (ca veut dire sur un chemin bien spécifique) le même temps ou presque que s'il y avait pas de solution ... Moi je penses que c'est l'ergonomie du jeu qu'il faudrait revoir car 200*200 ca me parait très très grand sur un écran (et si c'est géré en plusieurs écran alors pourquoi vouloir calculer un chemin à travers toute la map ?)

[QuentinC]

Un autre truc peut-être : ne pas faire des îles trop grandes

J'ai remarqué que, pour une carte à deux types de cellules (terre et mer), le fait d'avoir des îles pas trop grandes aide aussi. L'algorythme ne va pas chercher plus loin que lîle en cours s'il est bien fait.